Very conscine solution 252ms in Java


  • 0
    W
    public class Solution {
    boolean[][] rows = new boolean[9][9];
    boolean[][] cols = new boolean[9][9];
    boolean[][] grids = new boolean[9][9];
    boolean flag = false;
    public void solveSudoku(char[][] board) {
        if(board.length!=9) return;
    	if(board[0].length!=9) return;
    	
    	for(int i=0;i<9;i++){//先记录一遍目前数独中的初始状态
    		for(int j=0;j<9;j++){
    			char c = board[i][j];
    			if(c=='.') continue;
    			rows[i][c-'1'] = true;
    			cols[j][c-'1'] = true;
    			grids[i/3*3+j/3][c-'1'] = true;
    		}
    	}
    	help(board,0,0);
    }
    public void help(char[][] board,int row,int col){
    	if(row>=9){//已经找到了数独的解
    		flag = true;
    		return;
    	}
    	char c = board[row][col];
    	if(c=='.'){//当前是一个空格
    		for(int i=0;i<=8;i++){//从1到9遍历的去尝试
    			if(rows[row][i]||cols[col][i]||grids[row/3*3+col/3][i]) continue;//新填入的数不能和数独中已有的状态产生冲突
    			rows[row][i] = true;
    			cols[col][i] = true;
    			grids[row/3*3+col/3][i] = true;
    			board[row][col] = (char)(i + '1');//暂时先填上这个数
    			
    			if(col>=8) help(board,row+1,0);//到了该行的末尾,从下一行的头部开始
    			else help(board,row,col+1);//继续去考察下一格
    			
    			if(flag) return;//如果已经找到答案了则直接返回
    			rows[row][i] = false;//尝试的当前数不合适,继续尝试下一个数
    			cols[col][i] = false;
    			grids[row/3*3+col/3][i] = false;
    			board[row][col] = '.';
    		}
    	}else if(col>=8) help(board,row+1,0);
    	else help(board,row,col+1);
    }
    

    }


  • 0
    M

    我觉得 这才是人写的代码。很好多谢


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.