Sudoku Solver 37

Description

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

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

Hint

Straight forward DFS try each possible way to slove it we can add global variable to do memory searching

a special solution https://discuss.leetcode.com/topic/13314/singapore-prime-minister-lee-hsien-loong-s-sudoku-solver-code-runs-in-1ms/2

Method

has expontian

Time & Space

The time complexity should be 9 ^ m (m represents the number of blanks to be filled in), since each blank can have 9 choices

Code

public class Solution {

    private boolean sign=false;
    private boolean[][] row,line,block;

    public void solveSudoku(char[][] board) {
        row=new boolean[10][10];
        line=new boolean[10][10];
        block=new boolean[10][10];
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]=='.');
                else {
                    int t=board[i][j]-'0';
                    row[i][t]=true;
                    line[t][j]=true;
                    block[(i/3)*3+j/3][t]=true;
                }
            }
        }
        dps(board,0,0);
    }

    public void dps(char[][] board,int i,int j){
        if(i==9){
            sign=true;
            return;
        }
        if(board[i][j]!='.'){
            dps(board,i+(j+1)/9,(j+1)%9);
            return;
        }
        int temp=(i/3)*3+j/3;
        for(int t=1;t<=9;t++){
            if(!row[i][t] && !line[t][j] && !block[temp][t]){
                board[i][j]=(char) ('0'+t);
                row[i][t]=true;
                line[t][j]=true;
                block[temp][t]=true;
                if(i==8 && j==8){
                    sign=true;
                    return;
                }
                dps(board,i+(j+1)/9,(j+1)%9);
                if(sign) return;
                board[i][j]='.';
                row[i][t]=false;
                line[t][j]=false;
                block[temp][t]=false;
            }
        }
    }
}