🌕 🌕 🌕 🌗 37. 解数独

难度: 🌕 🌕 🌕 🌗

问题描述

---

解法

class Solution {
    int len = 9;
    public void solveSudoku(char[][] board) {
        // 思路：
        mySol(board);
    }

    private boolean mySol(char[][] board) {
        for(int i = 0; i < len; i ++) {
            for(int j = 0; j < len; j ++) {
                if(board[i][j] == '.') {
                    for(int k = 1; k <= len; k ++) {
                    if(isValid(board, i, j, k)) {
                        board[i][j] = (char)('0' + k);
                        if(mySol(board)) {
                            return true;
                        }
                        board[i][j] = '.';
                    }
                    }
                    return false; // k 从 1 - 9 全部都找了一遍，发现在该点没有任何满足要求的值
                } else {
                    continue;
                }
            }
        }
        return true;
    }

    private void print(char[][] board) {
        for(int i = 0; i < 9; i ++) {
            System.out.println(Arrays.toString(board[i]));
        }
        System.out.println("-------------");
    }

    private boolean isValid(char[][] board, int curRow, int curCol, int num) {
        // 每行只能出现一次
        for(int j = 0; j < len; j ++) {
            if(board[curRow][j] == (char)(num + '0')) {
                return false;
            }
        }
        // 每列只能出现一次
        for(int i = 0; i < len; i ++) {
            if(board[i][curCol] == (char)(num + '0')) {
                return false;
            }
        }
        // 每一个以粗实线分隔的 3x3 宫内只能出现一次
        // 3 * 3 方格左上角下标
        int m = 3 * (curRow / 3);
        int n = 3 * (curCol / 3);
        for(int p = 0; p < 3; p ++) {
            for(int q = 0; q < 3; q ++) {
                if(board[m + p][n + q] == (char)(num + '0')) {
                    return false;
                }
            }
        }
        return true;
    }
}

---

输出