題目描述

請(qǐng)編寫(xiě)一個(gè)程序，給數(shù)獨(dú)中的剩余的空格填寫(xiě)上數(shù)字
空格用字符'.'表示
假設(shè)給定的數(shù)獨(dú)只有唯一的解法

這盤(pán)數(shù)獨(dú)的解法是：

在這里插入圖片描述

紅色表示填上的解

在這里插入圖片描述

分析

• 這個(gè)問(wèn)題抽象，對(duì)于一個(gè)9*9矩陣，給它的空白處，依次填入適當(dāng)?shù)臄?shù)字。
• 這樣就可以歸納出一個(gè)窮舉問(wèn)題，每一個(gè)空格都有1~9 候選值。需要做的是：
  • 如何依次找到空格。
  • 對(duì)空格處的值進(jìn)行合理性判斷。
  • 遞歸到下一個(gè)空格。
  • 在某一層，所有的取值都失敗了，要有返回上一層的機(jī)制，使上一層繼續(xù)嘗試下一個(gè)數(shù)字。（回溯）。
  • 找到合理解時(shí)，要有正確的返回條件。

java 代碼

public class Solution {
    public void solveSudoku(char[][] board) {
        if(board == null || board.length != 9 || board[0].length != 9){return;}
        boolean res = SudokuHelper(board,0,0);       
    }
    //給 board【row】【col】填數(shù)
    public boolean SudokuHelper(char [][] board, int row,int col){
        
        while(row < 9 && col < 9){
            if(board[row][col] == '.'){break;}
            if(col == 8){
                col = 0;
                row ++;                
            }else{              
                col ++;
            }
        }
        //沒(méi)有可填充的了 全部完成
        if(row >= 9){
            return true;
        }
        
        //找出下一個(gè)填充點(diǎn)
        int rowNew = row + col/8;
        int colNew = (col + 1)%9;    
        
        //所以接下來(lái)嘗試給 row col 填充數(shù)字
        for(int i = 1; i <= 9; i++){
            //檢查i的可行性
            if(isValid(board,row,col,i)){
               board[row][col] = (char)(i + '0');
               boolean res = SudokuHelper(board,rowNew,colNew);
               if(res){
                   //填充成功
                   return true;
               }else{
                   //填充失敗
                   board[row][col] = '.';
               }               
            }
        }        
        return false;
    }    
    public boolean isValid(char [][] board, int row,int col,int num){        
        for(int i = 0; i < board.length; i++){
            if(board[row][i] == num+'0' || board[i][col] == num + '0'){
                return false;
            }
        }        
        int rowOff = row/3*3;
        int colOff = col/3*3;        
        for(int i = 0;i < 3;i++){
            for(int j = 0; j < 3;j++){
                if(board[rowOff + i][colOff + j] == num + '0'){
                    return false;
                }
            }
        }        
        return true;
    }
}