​LeetCode刷题实战37: 解数独

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 解数独,我们先来看题面:

https://leetcode-cn.com/problems/valid-sudoku/

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 '.'.

题意

编写一个程序,通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

题解

回溯法解数独

让我们想象一下已经成功放置了几个数字在数独上。
但是该组合不是最优的并且不能继续放置数字了。该怎么办?回溯。
意思是回退,来改变之前放置的数字并且继续尝试。如果还是不行,再次回溯。
数独首先行,列,还有 3*3 的方格内数字是 1~9 不能重复。
声明布尔数组,表明行列中某个数字是否被使用了, 被用过视为 true,没用过为 false。
初始化布尔数组,表明哪些数字已经被使用过了。
尝试去填充数组,只要行,列, 还有 3*3 的方格内 出现已经被使用过的数字,我们就不填充,否则尝试填充。
如果填充失败,那么我们需要回溯。将原来尝试填充的地方改回来。
递归直到数独被填充完成。

class Solution {
    public void solveSudoku(char[][] board) {
        // 三个布尔数组 表明 行, 列, 还有 3*3 的方格的数字是否被使用过
        boolean[][] rowUsed = new boolean[9][10];
        boolean[][] colUsed = new boolean[9][10];
        boolean[][][] boxUsed = new boolean[3][3][10];
        // 初始化
        for(int row = 0; row < board.length; row++){
            for(int col = 0; col < board[0].length; col++) {
                int num = board[row][col] - '0';
                if(1 <= num && num <= 9){
                    rowUsed[row][num] = true;
                    colUsed[col][num] = true;
                    boxUsed[row/3][col/3][num] = true;
                }
            }
        }
        // 递归尝试填充数组
        recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0);
    }
    
    private boolean recusiveSolveSudoku(char[][]board, boolean[][]rowUsed, boolean[][]colUsed, boolean[][][]boxUsed, int row, int col){
        // 边界校验, 如果已经填充完成, 返回true, 表示一切结束
        if(col == board[0].length){
            col = 0;
            row++;
            if(row == board.length){
                return true;
            }
        }
        // 是空则尝试填充, 否则跳过继续尝试填充下一个位置
        if(board[row][col] == '.') {
            // 尝试填充1~9
            for(int num = 1; num <= 9; num++){
                boolean canUsed = !(rowUsed[row][num] || colUsed[col][num] || boxUsed[row/3][col/3][num]);
                if(canUsed){
                    rowUsed[row][num] = true;
                    colUsed[col][num] = true;
                    boxUsed[row/3][col/3][num] = true;
                    
                    board[row][col] = (char)('0' + num);
                    if(recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1)){
                        return true;
                    }
                    board[row][col] = '.';
                    
                    rowUsed[row][num] = false;
                    colUsed[col][num] = false;
                    boxUsed[row/3][col/3][num] = false;
                }
            }
        } else {
            return recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1);
        }
        return false;
    }
}

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:

LeetCode1-20题汇总,速度收藏!
LeetCode刷题实战21:合并两个有序链表
LeetCode刷题实战23:合并K个升序链表
LeetCode刷题实战24:两两交换链表中的节点
LeetCode刷题实战25:K 个一组翻转链表
LeetCode刷题实战26:删除排序数组中的重复项
LeetCode刷题实战27:移除元素
LeetCode刷题实战28:实现 strStr()
LeetCode刷题实战29:两数相除
LeetCode刷题实战30:串联所有单词的子串
LeetCode刷题实战31:下一个排列
LeetCode刷题实战32:最长有效括号
LeetCode刷题实战33:搜索旋转排序数组
LeetCode刷题实战34:在排序数组中查找元素
LeetCode刷题实战35:搜索插入位置
LeetCode刷题实战36:有效的数独
(0)

相关推荐

  • 技术贴 | R语言:手把手教你画pheatmap热图

    导读: pheatmap默认会对输入矩阵数据的行和列同时进行聚类,但是也可以通过布尔型参数cluster_rows和cluster_cols设置是否对行或列进行聚类,具体看分析需求.利用display ...

  • ​LeetCode刷题实战36: 有效的数独

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战260:只出现一次的数字 III

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战258:各位相加

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战257:二叉树的所有路径

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战256:粉刷房子

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战262:行程和用户

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战255:验证前序遍历序列二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战263:丑数

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战254:因子的组合

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...