网站制作商城,长沙大型网站建设公司,建设厅网站上人员怎么导出,淮南市城乡建设局网站题目
编写一个程序#xff0c;通过填充空格来解决数独问题。
数独的解法需 遵循如下规则#xff1a;
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。#xff08;请参考示例图#xff09;
数独…题目
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 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 9board[i].length 9board[i][j] 是一位数字或者 .题目数据 保证 输入数独仅有一个解
代码
可以参考前身有效的数独
#include stdio.h
#include stdlib.h
#include stdbool.h
#include string.hvoid solveSudoku(char **board, int boardSize, int *boardColSize);
bool isValidSudoku(char **board, int boardSize, int *boardColSize);int main()
{// char b[9][10] // {53..7....,// 6..195...,// .98....6.,// 8...6...3,// 4..8.3..1,// 7...2...6,// .6....28.,// ...419..5,// ....8..79};char b[9][10]{..9748...,7........,.2.1.9...,..7...24.,.64.1.59.,.98...3..,...8.3.2.,........6,...2759..};int t, *te;char **board (char **)malloc(sizeof(char *) * 9);for (int i 0; i 9; i){board[i] b[i];printf(%s , b[i]);}printf(\n);solveSudoku(board, t, te);for (int i 0; i 9; i){printf(%s , board[i]);}return 0;
}void solveSudoku(char **board, int boardSize, int *boardColSize)
{int r, c;for (int p 0; p 9; p){for (int q 0; q 9; q){if (board[p][q] .){r p;c q;continue;}}}static int sign 0;for (int i 0; i 9; i){for (int j 0; j 9; j){if (board[i][j] .){int p;for (p 1; p 9 sign 0; p){board[i][j] p 0;if (isValidSudoku(board, boardSize, boardColSize) 1){if (i r j c){sign 1;}solveSudoku(board, boardSize, boardColSize);if (sign 1){return;}}else{sign 0;continue;}}if (p 10){board[i][j] .;}return;}}}for (int i 0; i 9; i){printf(%s , board[i]);}printf(\n);
}bool isValidSudoku(char **board, int boardSize, int *boardColSize)
{int rownums[10], colnums[10];memset(rownums, 0, sizeof(rownums));memset(colnums, 0, sizeof(colnums));for (int i 0; i 9; i){for (int j 0; j 9; j){if (board[i][j] ! .){int number board[i][j] - 0;if (rownums[number] 0){rownums[number] 1;}elsereturn false;}if (board[j][i] ! .){int number board[j][i] - 0;if (colnums[number] 0){colnums[number] 1;}elsereturn false;}}memset(rownums, 0, sizeof(rownums));memset(colnums, 0, sizeof(colnums));}int i 0, j 0;for (int p 3; p 9; p p 3){for (int q 3; q 9; q q 3){i p - 3;for (; i p; i){j q - 3;for (; j q; j){if (board[i][j] ! .){int number board[i][j] - 0;if (rownums[number] 0){rownums[number] 1;}elsereturn false;}}}memset(rownums, 0, sizeof(rownums));}}return true;
}
