解数独

问题描述

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

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

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

代码语言：javascript复制

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

解决方案

大体思路为从上至下，从左至右依次填表，填表的过程中要时刻保证上述三条性质，若当前位置无数可填则回溯到上一个位置重新选择，当到达右下角的位置时流程结束。

定义三个布尔型的数组:

代码语言：javascript复制

boolean[] [] row;

boolean[] [] col;

boolean[] [] [] square;

row[i] [num] 表示i行num这个数字是否使用过了，col[i] [num] 表示i列num这个数字是否使用过了，square[i] [j] [num] 为第i行j列的那个九宫格中num这个数字是否已经使用过了。

代码语言：javascript复制

class Solution {
    boolean[][] row;
    boolean[][] col;
    boolean[][][] square;
    char[][] board;   
    public void solveSudoku(char[][] board) {
        int N = 9;
        // row[i][j] 为第i行j元素是否已经被使用了
        this.board = board;
        row = new boolean[N][N];
        col = new boolean[N][N];
        square = new boolean[N / 3][N / 3][N];
        // init
        for(int i = 0; i < N; i  ){
            for(int j = 0; j < N; j  ){
                if(board[i][j] != '.'){
                    int num = board[i][j] - '1';
                    row[i][num] = true;
                    col[j][num] = true;
                    square[i / 3][j / 3][num] = true;
                }
            }
        }
        dfs(0, 0);
    }
    // 从i j位置开始是否已经完成任务
    public boolean dfs(int i, int j){
        if(i == 9){
            return true;
        }
        if(j == 9){
            return dfs(i   1, 0);
        }
        if(board[i][j] != '.'){
            return dfs(i, j   1);
        }
        for(int num = 0; num < 9; num  ){
            if(row[i][num] || col[j][num] || square[i / 3][j / 3][num]){
                continue;
            }
            row[i][num] = true;
            col[j][num] = true;
            square[i / 3][j / 3][num] = true;
            board[i][j] = (char)('1'   num);
            if(dfs(i, j   1)){
                return true;
            }
            board[i][j] = '.';
            row[i][num] = false;
            col[j][num] = false;
            square[i / 3][j / 3][num] = false;
        }
        return false;
    }
}

row

0 人点赞