[LeetCode] 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.

这道求解数独的题是在之前那道 Valid Sudoku 验证数独的基础上的延伸,之前那道题让我们验证给定的数组是否为数独数组,这道让我们求解数独数组,跟此题类似的有 Permutations 全排列Combinations 组合项 N-Queens N皇后问题等等,其中尤其是跟 N-Queens N皇后问题的解题思路及其相似,对于每个需要填数字的格子带入1到9,每代入一个数字都判定其是否合法,如果合法就继续下一次递归,结束时把数字设回'.',判断新加入的数字是否合法时,只需要判定当前数字是否合法,不需要判定这个数组是否为数独数组,因为之前加进的数字都是合法的,这样可以使程序更加高效一些,具体实现如代码所示:

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        if (board.empty() || board.size() != 9 || board[0].size() != 9) return;
        solveSudokuDFS(board, 0, 0);
    }
    bool solveSudokuDFS(vector<vector<char> > &board, int i, int j) {
        if (i == 9) return true;
        if (j >= 9) return solveSudokuDFS(board, i + 1, 0);
        if (board[i][j] == '.') {
            for (int k = 1; k <= 9; ++k) {
                board[i][j] = (char)(k + '0');
                if (isValid(board, i , j)) {
                    if (solveSudokuDFS(board, i, j + 1)) return true;
                }
                board[i][j] = '.';
            }
        } else {
            return solveSudokuDFS(board, i, j + 1);
        }
        return false;
    }
    bool isValid(vector<vector<char> > &board, int i, int j) {
        for (int col = 0; col < 9; ++col) {
            if (col != j && board[i][j] == board[i][col]) return false;
        }
        for (int row = 0; row < 9; ++row) {
            if (row != i && board[i][j] == board[row][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[i][j] == board[row][col]) return false;
            }
        }
        return true;
    }
};

本文转自博客园Grandyang的博客,原文链接:求解数独[LeetCode] Sudoku Solver ,如需转载请自行联系原博主。

相关文章
|
6月前
|
Java
leetcode-37:解数独
leetcode-37:解数独
44 0
|
22天前
|
存储 算法 C++
Leetcode第三十六题(有效的数独)
这篇文章介绍了如何使用C++编写一个算法来验证一个9x9数独是否有效,遵循数独的规则,即数字1-9在每一行、每一列和每个3x3宫内只能出现一次。
34 0
|
3月前
|
存储 算法 索引
LeetCode第36题有效的数独
这篇文章介绍了LeetCode第36题"有效的数独"的解题方法,通过使用三个二维数组分别记录每一行、每一列以及每个3x3宫格内1-9数字出现的次数,来验证给定数独是否有效。
|
5月前
|
算法
力扣经典150题解析之三十四:有效的数独
力扣经典150题解析之三十四:有效的数独
39 0
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
|
6月前
leetcode-36:有效的数独
leetcode-36:有效的数独
48 0
|
12月前
|
JavaScript 前端开发 算法
LeetCode 37.解数独(注释完整+JavaScript解题)
LeetCode 37.解数独(注释完整+JavaScript解题)
70 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2