[LeetCode] 37. Sudoku Solver

alaege 发布于2019-08-19 11:14 / 2174人阅读

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character ".".

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

The given board contain only digits 1-9 and the character ".".
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.

Solution

class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) return;
        solve(board);
    }
    
    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                
                if (board[i][j] == ".") {
                    for (char ch = "1"; ch <= "9"; ch++) {
                        if (isValid(board, i, j, ch)) {
                            board[i][j] = ch;
                            if (solve(board)) return true;
                            else board[i][j] = ".";
                        }
                    }
                    return false;
                }
                
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char ch) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == ch) return false;
            if (board[row][i] == ch) return false;
            if (board[row/3*3+i/3][col/3*3+i%3] == ch) return false;
        }
        return true;
    }
}

GPU云服务器云服务器 Solver sudoku LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77247.html

leetcode37 Sudoku Solver

摘要：题目要求也就是给出一个解决数独的方法，假设每个数独只有一个解决方案。并将当前的假象结果带入下一轮的遍历之中。如果最终遍历失败，则逐级返回，恢复上一轮遍历的状态，并填入下一个合理的假想值后继续遍历。题目要求 Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indi...

pepperwang 2019-08-15 10:49 评论0 收藏0
[Leetcode]36 Valid Sudoku

摘要：的可以由确定，这一点在里面的位置可以由确定所以每确定一行，每一个值都可以被转换到一个之中。如果允许的空间复杂度，可以设置一个二维数组来用来判断是否在里重现了重复的数字。将一个数字的每一个位上表示每一个数字。 Leetcode[36] Valid Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles - ...

zhichangterry 2019-08-14 14:54 评论0 收藏0
leetcode36 Valid Sudoku 查看数独是否合法

摘要：如果重复则不合法，否则极为合法。在这里我们使用数组代替作为存储行列和小正方形的值得数据结构。我存储这所有的行列小正方形的情况，并判断当前值是否重复。外循环则代表对下一行，下一列和下一个小正方形的遍历。题目要求 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku boa...

wing324 2019-08-16 10:32 评论0 收藏0
leetcode 36 Valid Sudoku

摘要：要求我们判断已经填入的数字是否满足数独的规则。即满足每一行每一列每一个粗线宫内的数字均含，不重复。没有数字的格子用字符表示。通过两层循环可以方便的检查每一行和每一列有没有重复数字。对于每个，作为纵坐标，作为横坐标。题目详情 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.The Sudo...

entner 2019-08-15 14:51 评论0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月汇总（109 题攻略）

摘要：每天会折腾一道及以上题目，并将其解题思路记录成文章，发布到和微信公众号上。三汇总返回目录在月日月日这半个月中，做了汇总了数组知识点。或者拉到本文最下面，添加的微信等会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 评论0 收藏0