原题链接:http://oj.leetcode.com/problems/sudoku-solver/
这道题的方法就是用在N-Queens中介绍的常见套路。简单地说思路就是循环处理子问题,对于每个格子,带入不同的9个数,然后判合法,如果成立就递归继续,结束后把数字设回空。大家可以看出代码结构和N-Queens是完全一样的。判合法可以用Valid
Sudoku做为subroutine,但是其实在这里因为每次进入时已经保证之前的board不会冲突,所以不需要判断整个盘,只需要看当前加入的数字和之前是否冲突就可以,这样可以大大提高运行效率,毕竟判合法在程序中被多次调用。实现的代码如下:
public void solveSudoku(char[][] board) {
helper(board,0,0);
}
private boolean helper(char[][] board, int i, int j)
{
if(j>=9)
return helper(board,i+1,0);
if(i==9)
{
return true;
}
if(board[i][j]=='.')
{
for(int k=1;k<=9;k++)
{
board[i][j] = (char)(k+'0');
if(isValid(board,i,j))
{
if(helper(board,i,j+1))
return true;
}
board[i][j] = '.';
}
}
else
{
return helper(board,i,j+1);
}
return false;
}
private boolean isValid(char[][] board, int i, int j)
{
boolean[] map = new boolean[9];
for(int k=0;k<9;k++)
{
if(k!=j && board[i][k]==board[i][j])
return false;
}
for(int k=0;k<9;k++)
{
if(k!=i && board[k][j]==board[i][j])
return false;
}
for(int row = i/3*3; row<i/3*3+3; row++)
{
for(int col=j/3*3; col<j/3*3+3; col++)
{
if((row!=i || col!=j) && board[row][col]==board[i][j])
return false;
}
}
return true;
}
再强调一下哈,以上方法是一个非常典型的套路,大部分NP问题的都是可以这个方法,比如N-Queens,Combination
Sum,Combinations,Permutations等。
分享到:
相关推荐
ufo2mstar-SuDoku-Solver-archive-refs-heads-master.zip
sudoku-solver-源码.rar
快速、基于逻辑的分步数独求解器。
数独刷新matlab代码sudoku-solver-matlab这是带有gui的matlab代码,可以解决提供给它的数独难题。 解决方案有点接近蛮力。 需要安装matlab才能运行它。
python sudoku求解器是作为第一年的工程项目而完成的,它是用python编程的,它允许用户输入一个未解决的sudoku .txt文件,然后它会对其进行求解,并以用户友好的gui形式将已解决的sudoku呈现给用户。
SudokuSolver-Python Python中的Sudoku解算器。输入图形用户界面运行SudokuUI.py。 这需要Web浏览器和Chris Knot提供的Python软件包 。 后者可以通过pip install eel进行安装。 可以在网格空间中自由输入数字。 非...
解决数独难题。 支持快速解决方案模式和逐步训练模式。
Sudoku Solver 是一个 C 程序,可以快速解决数独问题。
Sudoku Solver是使用开放式choco(http://choco.sourceforge.net)约束编程库以Java编程语言管理的项目,可解决给定的Sudoku难题。
八字java源码(与作业中的报告相同,报告被迫填写不必要的信息和空白文本。) 数独解算器 梅尔特·塞林贝奥卢 计算机工程系 科贾埃利大学 ...摘要 本项目的目的是使用多线程从多点解数独...kagiru”的组合中提取了“SUDOKU
数独解算器 用Go编写的数独解算器结合使用消除和递归回溯过程
A Sudoku solver implemented in C++. It can solve a given Sudoku problem, or count the possibilities for all valid Sudoku grids.
语言:English 解决数独的扩展。 使用此方便的扩展程序解决数独。 您可以输入自己的拼图或从站点http://www.free-sudoku.com导入/导出数独。