新博文地址:[leetcode]Sudoku Solver
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.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
好了,最后一道题了,一直对数独特别害怕,不知道为啥,但是仔细看了这道题,貌似没啥难度,跟八皇后问题一样,典型的回溯算法,当然也可以用迭代实现,我同学用了迭代实现的,因此我就写了一个递归版本的,算法思想就是典型的DFS,因此这里不再啰嗦。
尴尬的是,DFS在找到一个结果的时候会继续回溯寻找下一个可能的结果,因此我又设置了一个全局变量来添加控制。这无疑让代码可读性变差,如果谁有更好的方法:找到一个解之后立马跳出整个递归过程,请告之
代码如下:
boolean over = false; public void solveSudoku(char[][] board) { if (board == null || board.length == 0 || board.length != board[0].length || board.length % 9 != 0) { return; } int height = board.length; int width = board[0].length; dfs(0, 0, board, height, width); } private void dfs(int row, int column, char[][] board, int height, int width) { if(over) return; if (row == board.length ) { over = true; return; } if (board[row][column] != '.' ) { if (column < width - 1 && !over) { dfs(row, column + 1, board, height, width); } else if (column == width - 1 && !over) { dfs(row + 1, 0, board, height, width); } } else { for (char c = '1'; c <= '9' && !over; c++) { if (!isConflict(c, row, column, board)) { board[row][column] = c; if (column < width - 1) { dfs(row, column + 1, board, height, width); } else if (column == width - 1) { dfs(row + 1, 0, board, height, width); } } } if(!over)board[row][column] = '.'; } } private boolean isConflict(char num, int row, int column, char[][] board) { int height = board.length; int width = board[0].length; for (int i = 0; i < width; i++) { if (i != column && board[row][i] == num) { return true; } } for (int i = 0; i < height; i++) { if (i != row && board[i][column] == num) { return true; } } int beginRow = (row / 3) * 3; int endRow = beginRow + 2; int beginColumn = (column / 3) * 3; int endColumn = beginColumn + 2; for (int i = beginRow; i <= endRow; i++) { for (int j = beginColumn; j <= endColumn; j++) { if (i == row && j == column) continue; if (board[i][j] == num) return true; } } return false; }
相关推荐
leetcode 答案使用计算机视觉和回溯的数独求解器 安装 存储库可以克隆或下载为 zip。 按照说明安装tesseract 其他需求可以通过运行pip install -r requirements.txt来安装 用法 执行代码如下: python main . py '...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
Solver 深度优先遍历 回溯 先检查后修改 Group Anagrams 排序 unordered_map Minimum Window Substring 两个指针遍历 map Maximal Rectangle 栈 局部递增 或者 动态规划 Binary Tree Inorder Traversal 栈 递归 ...
Sudoku Solver题目: | 源码:标签:dfs,数独难度:困难 / Hard82. Remove Duplicates from Sorted List II题目: | 源码:标签:单向链表难度:中等 / Medium146. LRU Cache题目: | 源码:标签:哈希表,双向...
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
vs code LeetCode 插件
leetcode中文版
100个leetCode详细解答
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
LeetCode 刷题汇总1
LeetCode 选讲1
噪声 leetcode
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
sudoku example 做leetcode37的时候看到的解数独的非常棒的方法。在简单回溯的基础上还加上了限制条件,会更快。主要参考 . 自己在main里面加上了一点从txt里读写,这样可以自己敲进去题目然后得到答案,比只是...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
LeetCode 刷题笔记
leetcode高频面试笔试题150+道,亲身总结。