[Leetcode单排] 数独 (N37)

backtracking dfs search

字数统计: 488阅读时长: 2 min

 2019/07/29  Share

37. Sudoku Solver

https://leetcode.com/problems/sudoku-solver/

这道题目你知道是回溯，知道是DFS，但是如果需要你完整的做出来，你会发现还是有各种各样的问题。下面这个做法来源于花花酱的讲解。

N皇后是每次递归是确定一行一列，但是这个题目你会发现连每个单元格都可能有N种可能，所以递归的时候不是定住行和列，而是以单元格进行递归。访问变量也从一维变成了两位。比如rows boolean[i][j]就是指第 i 行值为 j 的数是否已存在，而boxes[i][j]就是在第 i 个九宫格值为 j 的数是否已存在。

输入里面已经包含部分数值，所以开局先填充一波访问变量，之后正式开始递归。递归函数 fill的返回值是布尔类型，代表 x 和 y 确定时，board中的位置是否有满足条件的情况。在 for 循环里面只要有一个满足了条件则立刻结束。

boolean[][] rows = new boolean[9][10];
boolean[][] cols = new boolean[9][10];
boolean[][] boxes = new boolean[9][10];

public void solveSudoku(char[][] board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char c = board[i][j];
            if (c != '.') {
                int n = c - '0';
                int bx = j / 3;
                int by = i / 3;
                rows[i][n] = true;
                cols[j][n] = true;
                boxes[by * 3 + bx][n] = true;
            }
        }
    }
    fill(board, 0, 0);
}

private boolean fill(char[][] board, int x, int y) {
    if (y == 9) {
        return true;
    }
    int nextX = (x + 1) % 9;
    int nextY = (nextX == 0) ? y + 1 : y;
    if (board[y][x] != '.') {
        return fill(board, nextX, nextY);
    }
    // 每个单元格以 1-9 去试
    for (int i = 1; i <= 9; i++) {
        int boxIndex = y / 3 * 3 + x /3;
        if (!rows[y][i] && !cols[x][i] && !boxes[boxIndex][i]) {
            rows[y][i] = true;
            cols[x][i] = true;
            boxes[boxIndex][i] = true;
            board[y][x] = (char)(i + '0');
            if (fill(board, nextX, nextY)) {
                return true;
            }
            board[y][x] = '.';
            rows[y][i] = false;
            cols[x][i] = false;
            boxes[boxIndex][i] = false;
        }
    }
    return false;
}

Next Post

[Leetcode单排] 括号生成 (N22)
Previous Post

[Leetcode单排] N皇后 (N51 N52)

CATALOG

1. 37. Sudoku Solver

