37. Sudoku Solver

文章目錄

• 1 題目了解
• 2 回溯

1 題目了解

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.

Each of the digits 1-9 must occur exactly once in each column.

Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The ‘.’ character indicates empty cells.

輸入：一個字元數組char[][] board。如果這個單元格沒有數字，用.表示。

輸出：一個數獨

規則：每一行，每一列從1到9，每個數隻出現一次。每個3x3的方格，從1到9，每個數隻出現一次。

2 回溯

對于沒有數字的位置，依次嘗試1-9的數字，看是否有效。有效則移動位置。思路比較簡單，難點在于怎麼查找每一行，每一列，每一個方格内數字是否有效。原數組是字元，可以用int類型的數組來表示，查找會更快。int[][] rows表示每一行出現了哪些數字，例如rows[0][3]=1表示第0行數字3已經出現。int[][] cols表示每一列出現了哪些數字。int[][][] boxes 表示第i行第j個方格，哪些數字已經出現。

class Solution {
    private char[][] board;
    private int[][] rows;
    private int[][] cols;
    private int[][][] boxes;
    private int n = 9;
    public void solveSudoku(char[][] board) {
        this.board = board;
        rows = new int[n][n+1];
        cols = new int[n][n+1];
        boxes = new int[3][3][n+1];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]!='.'){
                    placeNumber(i,j,board[i][j]-48);
                }
            }
        }
        
        dfs(0,0);
    }
    
    private boolean dfs(int i,int j){
        if(j==n){
            return true;
        }
        int nextI = (i+1)%n;
        int nextJ = (nextI==0?j+1:j);
        if(board[i][j] == '.'){
            for(int d =1;d<=n;d++){
                if(isValidate(i,j,d)){
                    board[i][j] = (char)(d+'0');
                    placeNumber(i,j,d);
                    if(dfs(nextI,nextJ)){
                        return true;
                    }else{
                        board[i][j] = '.';
                        unPlaceNumber(i,j,d);
                    }
                }
            }
        }else{
            return dfs(nextI,nextJ);
        }
        return false;
    }
    
    
    private void placeNumber(int i,int j,int d){
        rows[i][d] = 1;
        cols[j][d] = 1;
        boxes[i/3][j/3][d] = 1;
    }
    
    private void unPlaceNumber(int i,int j,int d){
        rows[i][d] = 0;
        cols[j][d] = 0;
        boxes[i/3][j/3][d] = 0;
    }
    
    private boolean isValidate(int i,int j,int d){
        if(rows[i][d]==1) return false;
        if(cols[j][d]==1) return false;
        if(boxes[i/3][j/3][d] == 1) return false;
        return true;
    }
    
}