荆州网站建设荆州,品牌推广岗位,网站建设市场介绍,设计制作售卖题目描述
编写一个程序#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] 是一位数字或者 .题目数据 保证 输入数独仅有一个解
解答
class Solution {
public:void solveSudoku(vectorvectorchar board) {// 将每行的每个位置都用1-9去尝试回溯类似于dfs的思路// 满足条件是同行同列及所在3x3格子内都不出现backtrack(board);}bool backtrack(vectorvectorchar board){// 按行搜索每一个位置的可能情况for(int i 0; i board.size(); i){for(int j 0; j board[0].size(); j){if(board[i][j] .){for(char k 1; k 9; k){// 判断在数独棋盘(i, j) 点放k值是否合法if(isValid(i, j, k 0, board)){board[i][j] k 0;if(backtrack(board)) return true;board[i][j] .;}}// 某一个格子放1-9都不行,返回false从而能够回溯到上一层重新选取return false;}}}return true;}bool isValid(int row, int col, char val, vectorvectorchar board){// 判断行同一行是否有重复元素for(int i 0; i 9; i){if(board[row][i] val) return false;}// 判断行同一列是否有重复元素for(int j 0; j 9; j){if(board[j][col] val) return false;}// 判断所在9宫格内是否有重复元素(注意确定行列起点)int startRow (row / 3) * 3;int startCol (col / 3) * 3;for(int i startRow; i startRow 3; i){for(int j startCol; j startCol 3; j){if(board[i][j] val) return false;}}return true;}
};
