Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character'.'
.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
本题使用回溯法来解题,思路:
1 使用两个循环,逐个检查所有的方格
2 每到一个方格,检查到位空,以‘.'字符代表,就循环使用’1‘<=a<=9字符测试是否合法。
3 如果a合法,那么就继续填写下一个
4 如果不合法那么就回溯到上一个空格。
这里最巧妙和最难的地方就是在第2步中,逐个循环检查'1'<=a<='9'循环中使用了递归,就是如果当前字符合法,然后递归检查下个空格。这样程序就变得非常简洁。
还有难点就是判断什么时候需要返回真或者假。有两个地方:
1 当前测试'1'到'9'个数字都不合法,那么返回假
2 棋盘中所有空格都填满,那么就返回真
判断和Leetcode另外一个题目判断Sudoku是否合法的题目不同的就是,这里只需要判断当前格,一个循环就可以了,不需要判断所有的格。
const static int SQUNUM = 9;
const static int NUM = 3;
bool isValid(vector<vector<char> > &board, int row, int col)
{
int sRow = row / NUM;
int sCol = col / NUM;
for (int i = 0; i < SQUNUM; i++)
{
if (i != col && board[row][col] == board[row][i])
return false;
if (i != row && board[row][col] == board[i][col])
return false;
int r = sRow*NUM + i/NUM, c = sCol*NUM + i%NUM;
if (!(r == row && c == col) && board[row][col] == board[r][c])
return false;
}
return true;
}
bool solveSudoku(vector<vector<char> > &board)
{
for (int i = 0; i < SQUNUM; i++)
{
for (int j = 0; j < SQUNUM; j++)
{
if (board[i][j] == '.')
{
//本程序精华:主要的回溯思想就是这个循环和递归体现出来
//1. 逐个可行答案'1'->'9'去填写试一试是否可行
for (char a = '1'; a <= '9'; a++)
{
//填写
board[i][j] = a;
//测试是否可行
if (isValid(board, i, j) && solveSudoku(board))
//可行返回真
return true;
//不可行,回溯,即回到本次回溯前的状态
board[i][j] = '.';
}
//本格不符合规则,那么就可以马上返回了,所以不用到所有循环外。
//就是不用等到之后的循环完了。
return false;
}
}
}
//别忘记了最后,i==9&&j==9的时候跳出循环,这个时候就是成功了,要返回true
return true;
}
2014-1-26 update
更新一个更加简洁容易理解, 且相对上面的程序不那么容易出错,的标准递归回溯法程序:
主要少了个两重循环,容易驾驭多了。
class Solution {
public:
void solveSudoku(vector<vector<char> > &board)
{
solve2(board);
}
bool solve2(vector<vector<char> > &board, int row = 0, int col = 0)
{
if (row == 9) return true;
int nr = col==8? row+1:row;
int nc = col==8? 0:col+1;
if (board[row][col] != '.')
{
if (solve2(board, nr, nc)) return true;
}
else
{
for (char i = '1'; i <= '9'; i++)
{
board[row][col] = i;
if (isValid(board, row, col) && solve2(board, nr, nc)) return true;
}
board[row][col] = '.';
}
return false;
}
const static int SQUNUM = 9;
const static int NUM = 3;
bool isValid(vector<vector<char> > &board, int row, int col)
{
int sRow = row / NUM;
int sCol = col / NUM;
for (int i = 0; i < SQUNUM; i++)
{
if (i != col && board[row][col] == board[row][i])
return false;
if (i != row && board[row][col] == board[i][col])
return false;
//注意这里的计算公式:先定位小九宫大位置,然后小九宫里面的小位置
int r = sRow*NUM + i/NUM, c = sCol*NUM + i%NUM;
if (!(r == row && c == col) && board[row][col] == board[r][c])
return false;
}
return true;
}
};
分享到:
相关推荐
大佬的leetcode刷题笔记(c++版本)
刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的...
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
算法笔记
【leetcode】斐波那契数 c++(csdn)————程序
leetcode代码200题,语言c++。用了一个月做了下leetode。都是AC代码。
leetcode刷题147页(c++版).rar
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
leetcode,刷题的一些解法,建议先自己写,然后再参考别人的思路, leetcode,刷题的一些解法,建议先自己写,然后再参考别人的思路,
leetcode 答案使用计算机视觉和回溯的数独求解器 安装 存储库可以克隆或下载为 zip。 按照说明安装tesseract 其他需求可以通过运行pip install -r requirements.txt来安装 用法 执行代码如下: python main . py '...
c++ c++_c++编程基础之leetcode题解第37题解数独
本书包含了 LeetCode Online Judge所有题目的答案,所有代码经过精心编写,编码规范良好,适合读者反复揣摩,模仿,甚至在纸上默写
(C++)LeetCode刷题题解答案
该文档是开源项目,并非本人整理。只是觉得文档整理很的很棒,希望和大家分享。感恩,文档整理者。