原题链接: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等。
分享到:
相关推荐
js js_leetcode题解之37-sudoku-solver.js
LeetCode-cpp 个人 LeetCode C++ 答案库。 我的 LeetCode 个人资料: 如果你想讨论,请加入QQ群: 其他语言 优先级从高到低排列。 一句话总结问题 命名规则 number-this_is_title-difficulty (e-easy, m-medium, h-...
Solver 深度优先遍历 回溯 先检查后修改 Group Anagrams 排序 unordered_map Minimum Window Substring 两个指针遍历 map Maximal Rectangle 栈 局部递增 或者 动态规划 Binary Tree Inorder Traversal 栈 递归 ...
标题“_leetcode-python.pdf”所指的知识点: 该标题表明此文件是一份关于LeetCode的Python解题集。LeetCode是一个面向程序员的在线编程题库,提供各种编程语言的算法和数据结构题目,用于帮助编程者提升技能,尤其...
leetcode 答案使用计算机视觉和回溯的数独求解器 安装 存储库可以克隆或下载为 zip。 按照说明安装tesseract 其他需求可以通过运行pip install -r requirements.txt来安装 用法 执行代码如下: python main . py '...
第37题,即“解数独”(Sudoku Solver),是这类问题的一个经典实例,它要求我们用这两种方法来解决实际问题。在这个题解中,我们将详细探讨递归和回溯的概念,并结合解数独的具体步骤进行讲解。 首先,让我们了解...
Sudoku Solver题目: | 源码:标签:dfs,数独难度:困难 / Hard82. Remove Duplicates from Sorted List II题目: | 源码:标签:单向链表难度:中等 / Medium146. LRU Cache题目: | 源码:标签:哈希表,双向...
- 最后挑战难题,如“Sudoku Solver”和“Kth Smallest Element in a Sorted Matrix”,锻炼算法设计和复杂问题解决能力。 6. **资源利用** - 通过阅读他人的解决方案,可以学习不同的解题思路和优化技巧。 - ...
9. **Sudoku Solver.cpp** - 第36题“数独求解器”,解冑会利用回溯法来填充值,确保每一行、每一列和每一个宫格内的数字都符合数独规则。 10. **Subsets II .cpp** - 第90题“子集II”,要求找到一个集合的所有不...
在本压缩包文件中,我们聚焦于C语言基础,并通过解决LeetCode编程挑战中的第37题——"Sudoku Solver"(数独求解器)来深入理解和实践C语言编程技巧。LeetCode是一个广泛使用的在线平台,它提供了一系列编程题目,...
* Sudoku Solver:该题目要求解决数独问题,即填充一个9x9的数独矩阵,使得每行、每列、每个小矩阵中的数字唯一。解决该题目需要使用回溯算法,递归地探索所有可能的填充方式,然后逐步回溯,直到找到最优解。 分治...