当前位置：首页 > news >正文

LeeCode 37. 解数独

news 2025/9/1 15:48:16

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

答案：

void solveSudoku_(char** board, int boardSize, int* boardColSize, int *lines, int *cols, int* squres, int startRow, int startCol, int *finish);void solveSudoku(char** board, int boardSize, int* boardColSize) {// board是一个9X9的二维数组int lines[9] = {0}; // 标识每一行有哪些数字。用二进制判断每个数字是否使用过了。比如最低位1表示数字1使用过了，否则没使用。 次低位判断2是否使用过了。int cols[9] = {0}; // 同理标识9列的数字int squres[9] = { 0 }; // 同理，标识9个小方格的数字// 遍历board数组，初始化上述数组int squareLine = 0, squareLineCol = 0; // 标识位置位于哪个小方格for (int i = 0; i < boardSize; i++) {for (int j = 0; j < boardColSize[i]; j++) {if (board[i][j] != '.') {// 存的数字int num = board[i][j] - '0'; // 得到数字int offset = 1 << (num - 1);lines[i] |= offset;cols[j] |= offset;// 判断在哪个3X3小方格中squareLine = i / 3; // 把每个3X3小方块看成整体， 该数字的行数squareLineCol = j / 3;int squareIdx = squareLine * 3 + squareLineCol;squres[squareIdx] |= offset;}}}// 再递归填数字。int finish = 0;solveSudoku_(board, boardSize, boardColSize, lines, cols, squres, 0, 0, &finish);
}void solveSudoku_(char** board, int boardSize, int* boardColSize, int *lines, int *cols, int* squres, int startRow, int startCol, int *finish) {if (*finish) return;// 按顺序先找到没填数字的格子for (;board[startRow][startCol] != '.';) {if (startCol == boardColSize[startRow] - 1) {startCol = 0;startRow++;if (startRow >= boardSize) {*finish = 1;return;}			}else {startCol++;}}// 需要往board[startRow][startCol]的位置填一个数。需判断能填入哪些数// 遍历1-9，判断哪些数字可以填入for (int i = 1; i < 10; i++) {if (*finish) return;int squareLine = startRow / 3;int squareLineCol = startCol / 3;int squareIdx = squareLine * 3 + squareLineCol;int offset = 1 << (i - 1);if ((lines[startRow] & offset) == 0&& (cols[startCol] & offset) == 0&& (squres[squareIdx] & offset) == 0) {// 数字i可以填, 尝试填入i这个数字board[startRow][startCol] = i + '0';// 标记用了这个数lines[startRow] |= offset;cols[startCol] |= offset;squres[squareIdx] |= offset;if (startRow == 8 && startCol == 8) {// 最后一个填完了.*finish = 1;return;}// 再递归填写下一个solveSudoku_(board, boardSize, boardColSize, lines, cols, squres, startRow, startCol, finish);if (*finish) return;// 回退，尝试其他填法board[startRow][startCol] = '.';int mask = ~(1 << (i - 1));lines[startRow] &= mask;cols[startCol] &= mask;squres[squareIdx] &= mask;}}
}

测试代码：

#include <stdlib.h>void printCharArr(char** arr, int size, int* returnColumnSizes);void testLeeCode37(void) { // LeeCode37.解数独char boardArr[9][9] = {{'5' ,'3' ,'.' ,'.' ,'7' ,'.' ,'.' ,'.' ,'.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};int boardColSize[9] = {9,9,9,9,9,9,9,9,9};char** board = (char**)malloc(9 * sizeof(char*));if (!board) return;for (int i = 0; i < 9; i++) {char* col = (char*)malloc(9 * sizeof(char));if (!col) return;*(board + i) = col;}for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {board[i][j] = boardArr[i][j];}}solveSudoku(board, 9, boardColSize);printCharArr(board, 9, boardColSize);// 释放内存for (int i = 0; i < 9; i++) {free(board[i]);}free(board);
}void printCharArr(char** arr, int size, int* returnColumnSizes) {printf("[");int isFirst = 1;for (int i = 0; i < size; i++) {if (isFirst) {isFirst = false;}else {printf(",");}int isSubFirst = 1;printf("[");for (int j = 0; j < returnColumnSizes[i]; j++) {if (isSubFirst) {isSubFirst = false;}else {printf(",");}printf("%c", arr[i][j]);}printf("]");}printf("]\n");
}

运行：