【每日LeetCode】37. 解数独

题目

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

图片说明

答案被标成红色。

图片说明
Note:

给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

题解

直接搜索就好,写一个辅助函数检查三条规则：

1. 行上有没有冲突的元素
2. 列上有没有冲突的元素
3. 九宫格上有没有冲突的元素

如果有冲突,那么本次搜索失效,就要对数独进行回溯。

public class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0)
            return;
        searchRes(board);
    }
    private boolean searchRes(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.') {
                    continue;
                }
                for (char num = '1'; num <= '9'; num++) {//尝试
                    if (!isValid(board, i, j, num)) {
                        continue;
                    }
                    board[i][j] = num;
                    if (searchRes(board)) {
                        return true;
                    } else {
                        board[i][j] = '.';//回退之前的状态,本轮搜索失败,回退的时候也是递归的
                    }
                }
                return false;
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, int i, int j, char num) {
        // 行有相同的,说明尝试错误.
        for (int row = 0; row < 9; row++) {
            if (board[row][j] == num) {
                return false;
            }
        }
        // 列有相同的,说明尝试错误.
        for (int col = 0; col < 9; col++) {
            if (board[i][col] == num) {
                return false;
            }
        }
        // 9宫格中有相同的,说明尝试错误.
        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 (board[row][col] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}

每日英文

• live off 依靠
  一般off是离开的意思,比如飞机起飞take off,这里比较特殊.
• survive (v.) 幸存
• survival(n.)
  • -al 名词后缀
• reside(v.) 定居
  • -sid 坐下来.
• residence(n.)住宅住处.
• redident 居民
  • resident evil 生化危机(居民变成魔鬼)

热门阅读

• 35. 搜索插入位置
• 程序员实习（初入职场）怎么最大限度提高自己？

image

找工作的同学扫码关注，每天一道面试算法题，和博主一起学英文