编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 '.' 表示。
示例:
输入: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] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解
#include<iostream> #include<stack> #include<algorithm> #include<string> #include<vector> using namespace std; /* 对于每个需要填数字的格子带入1到9,每代入一个数字都判定其是否合法, 如果合法就继续下一次递归,结束时把数字设回 '.', 判断新加入的数字是否合法时,只需要判定当前数字是否合法, 不需要判定这个数组是否为数独数组,因为之前加进的数字都是合法的, 这样可以使程序更加高效一些,整体思路是这样的, 但是实现起来可以有不同的形式。 一种实现形式是递归带上横纵坐标,由于是一行一行的填数字, 且是从0行开始的,所以当i到达9的时候, 说明所有的数字都成功的填入了,直接返回 ture。 当j大于等于9时,当前行填完了,需要换到下一行继续填,则继续调用递归函数, 横坐标带入 i+1。否则看若当前数字不为点, 说明当前位置不需要填数字,则对右边的位置调用递归。 若当前位置需要填数字,则应该尝试填入1到9内的所有数字, 让c从1遍历到9,每当试着填入一个数字, 都需要检验是否有冲突,使用另一个子函数 isValid 来检验是否合法, 假如不合法,则跳过当前数字。若合法,则将当前位置赋值为这个数字, 并对右边位置调用递归,若递归函数返回 true, 则说明可以成功填充,直接返回 true。不行的话,需要重置状态, 将当前位置恢复为点。若所有数字都尝试了,还是不行,则最终返回 false。 */ class Solution { public: void solveSudoku(vector<vector<char>>& board) { helper(board); } bool helper(vector<vector<char>>& board) { for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] != '.') { continue; } for (char c = '1'; c <= '9'; ++c) { if (!isValid(board, i, j, c)) { continue; } board[i][j] = c; if (helper(board)) { return true; } board[i][j] = '.'; } return false; } } return true; } bool isValid(vector<vector<char>>& board, int i, int j, char val) { for (int k = 0; k < 9; ++k) { if (board[k][j] != '.' && board[k][j] == val) { return false; } if (board[i][k] != '.' && board[i][k] == val) { return false; } int row = i / 3 * 3 + k / 3, col = j / 3 * 3 + k % 3; if (board[row][col] != '.' && board[row][col] == val) { return false; } } return true; } };