Leetcode: 37.解数独

题目描述

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

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

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



一个数独。



答案被标成红色。

Note:

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

思路

思路1

使用回溯法，利用受行、列、3*3矩阵约束，进行回溯

代码

代码1

class Solution {
    char[][] board;
    int[][] rowCount = new int[9][9];
    int[][] columnCount = new int[9][9];
    int[][] matrixCount = new int[9][9];
    boolean canSolve = false;

    private boolean canSet(int row, int column, int num){
        int matrixIndex = (row / 3) * 3 + column / 3;
        return rowCount[row][num - 1] == 0 && columnCount[column][num - 1] == 0 && matrixCount[matrixIndex][num - 1] == 0;
    }

    private void setNum(int row, int column, int num){
        int matrixIndex = (row / 3) * 3 + column / 3;
        rowCount[row][num - 1] += 1;
        columnCount[column][num - 1] += 1;
        matrixCount[matrixIndex][num - 1] += 1;
        board[row][column] = (char)('0' + num);
    }

    private void removeNum(int row, int column, int num){
        int matrixIndex = (row / 3) * 3 + column / 3;
        rowCount[row][num - 1] -= 1;
        columnCount[column][num - 1] -= 1;
        matrixCount[matrixIndex][num - 1] -= 1;
        board[row][column] = '.';
    }

    private void setNext(int row, int column){
        if (row == 8 && column == 8){
            this.canSolve = true;
        }
        if (column != 8){
            backTrack(row, column + 1);
        }else{
            backTrack(row + 1, 0);
        }
    }

    private void backTrack(int row, int column){
        if (row > 8 || column > 8){
            return;
        }
        if (this.board[row][column] == '.'){
            for(int i = 1; i < 10; i++){
                if (canSet(row, column, i)){
                    setNum(row, column, i);
                    setNext(row, column);
                    if (!this.canSolve){
                        removeNum(row, column, i);
                    }
                }
            }
        }else{
            setNext(row, column);
        }
    }

    public void solveSudoku(char[][] board) {
        this.board = board;
        for(int i = 0; i < 9; i++){
            for(int j=0; j < 9; j++){
                if (this.board[i][j] != '.'){
                    int num = (int)(this.board[i][j] - '0');
                    setNum(i, j, num);
                }
            }
        }
        backTrack(0, 0);
    }
}