【代码随想录】【算法训练营】【第30天 2】 [37]解数独

前言

思路及算法思维，指路 代码随想录。
题目来自 LeetCode。

day 30，周四，好难，会不了一点~

[37] 解数独

题目描述

37 解数独

解题思路

前提：……
思路：回溯
重点：……。

代码实现

C语言

使用3个used数组判断数值是否冲突 + 优化递归的起始行列号

#define INVALID_DATA (100)
#define countIdx(i, j) ((i / 3) * 3 + (j / 3))
bool usedRow[9][9];
bool usedCol[9][9];
bool used33[9][9];
void initUsed(char** board, int boardSize, int boardColSize)
{
// 初始化
for (int c = 0; c < 9; c++) {
memset(usedRow[c], false, sizeof(bool) * 9);
memset(usedCol[c], false, sizeof(bool) * 9);
memset(used33[c], false, sizeof(bool) * 9);
}
// 赋储值
for (int i = 0; i < boardSize; i++) {
for (int j = 0; j < boardColSize; j++) {
if ((board[i][j] >= '1') && (board[i][j] <= '9')) {
int num = (board[i][j] - '0');
// 初始化行
usedRow[i][num - 1] = true;
// 初始化列
usedCol[j][num - 1] = true;
// 初始化3*3
char idx = countIdx(i, j);
used33[idx][num - 1] = true;
}
}
}
return ;
}
bool isVaild(int row, int col, int val)
{
// 行有效
if (usedRow[row][val - 1] == true) {
return false;
} 
// 列有效
if (usedCol[col][val - 1] == true) {
return false;
}
// 3*3有效
int idx = countIdx(row, col);
if (used33[idx][val - 1] == true) {
return false;
}
return true;
}
bool backtracking(char ***board, int boardSize, int boardColSize, int startRow, int startCol)
{
// 递归
for (int row = startRow; row < boardSize; row++) {
for (int col = startCol; col < boardColSize; col++) {
if ((*board)[row][col] == '.') {
for (int num = 1; num <= 9; num++) {
if (isVaild(row, col, num) == false) {
continue;
}
// 保存该数值
(*board)[row][col] = num + '0';
usedRow[row][num - 1] = true;
usedCol[col][num - 1] = true;
int idx = countIdx(row, col);
used33[idx][num - 1] = true;
// 找到合适的数值，返回成功
if (backtracking(board, boardSize, boardColSize, startRow, startCol) == true) {
return true;
}
// 回溯
(*board)[row][col] = '.';
usedRow[row][num - 1] = false;
usedCol[col][num - 1] = false;
used33[idx][num - 1] = false;
}
// 没有找到合适数值, 返回失败
return false;
}
}
}
return true;
}
void solveSudoku(char** board, int boardSize, int* boardColSize){
// 初始化used数组
initUsed(board, boardSize, *boardColSize);
// 递归
(void)backtracking(&board, boardSize, *boardColSize, 0, 0);
return;
}

今日收获

1. 收获不了一点，已晕菜。