`
bcyy
  • 浏览: 1881073 次
文章分类
社区版块
存档分类
最新评论

Sudoku Solver -- LeetCode

 
阅读更多
原题链接: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-QueensCombination SumCombinationsPermutations等。

分享到:
评论

相关推荐

    js-leetcode题解之37-sudoku-solver.js

    js js_leetcode题解之37-sudoku-solver.js

    數位之和leetcode-leetcode-cpp:我的LeetCodeC++答案

    LeetCode-cpp 个人 LeetCode C++ 答案库。 我的 LeetCode 个人资料: 如果你想讨论,请加入QQ群: 其他语言 优先级从高到低排列。 一句话总结问题 命名规则 number-this_is_title-difficulty (e-easy, m-medium, h-...

    dna匹配leetcode-leetcode:leetcode刷题

    Solver 深度优先遍历 回溯 先检查后修改 Group Anagrams 排序 unordered_map Minimum Window Substring 两个指针遍历 map Maximal Rectangle 栈 局部递增 或者 动态规划 Binary Tree Inorder Traversal 栈 递归 ...

    _leetcode-python.pdf

    标题“_leetcode-python.pdf”所指的知识点: 该标题表明此文件是一份关于LeetCode的Python解题集。LeetCode是一个面向程序员的在线编程题库,提供各种编程语言的算法和数据结构题目,用于帮助编程者提升技能,尤其...

    leetcode答案-SudokuSolver:使用计算机视觉和回溯解决数独

    leetcode 答案使用计算机视觉和回溯的数独求解器 安装 存储库可以克隆或下载为 zip。 按照说明安装tesseract 其他需求可以通过运行pip install -r requirements.txt来安装 用法 执行代码如下: python main . py '...

    javascript-leetcode面试题解递归与回溯问题之第37题解数独-题解.zip

    第37题,即“解数独”(Sudoku Solver),是这类问题的一个经典实例,它要求我们用这两种方法来解决实际问题。在这个题解中,我们将详细探讨递归和回溯的概念,并结合解数独的具体步骤进行讲解。 首先,让我们了解...

    LeetCode:关于LeetCode.com和ACM的一些算法问题

    Sudoku Solver题目: | 源码:标签:dfs,数独难度:困难 / Hard82. Remove Duplicates from Sorted List II题目: | 源码:标签:单向链表难度:中等 / Medium146. LRU Cache题目: | 源码:标签:哈希表,双向...

    leetcode_solutions:Leetcode问题的解决方案

    - 最后挑战难题,如“Sudoku Solver”和“Kth Smallest Element in a Sorted Matrix”,锻炼算法设计和复杂问题解决能力。 6. **资源利用** - 通过阅读他人的解决方案,可以学习不同的解题思路和优化技巧。 - ...

    Leetcode部分解答(126题)

    9. **Sudoku Solver.cpp** - 第36题“数独求解器”,解冑会利用回溯法来填充值,确保每一行、每一列和每一个宫格内的数字都符合数独规则。 10. **Subsets II .cpp** - 第90题“子集II”,要求找到一个集合的所有不...

    C语言基础-C语言编程基础之Leetcode编程题解之第37题解数独.zip

    在本压缩包文件中,我们聚焦于C语言基础,并通过解决LeetCode编程挑战中的第37题——"Sudoku Solver"(数独求解器)来深入理解和实践C语言编程技巧。LeetCode是一个广泛使用的在线平台,它提供了一系列编程题目,...

    2、DFS、回溯、分治法必练题(含答案).pdf

    * Sudoku Solver:该题目要求解决数独问题,即填充一个9x9的数独矩阵,使得每行、每列、每个小矩阵中的数字唯一。解决该题目需要使用回溯算法,递归地探索所有可能的填充方式,然后逐步回溯,直到找到最优解。 分治...

Global site tag (gtag.js) - Google Analytics