題目描述

請編寫一個程序抹剩，給數(shù)獨中的剩余的空格填寫上數(shù)字
空格用字符'.'表示
假設給定的數(shù)獨只有唯一的解法

這盤數(shù)獨的解法是：

在這里插入圖片描述

紅色表示填上的解

在這里插入圖片描述

分析

• 這個問題抽象，對于一個9*9矩陣横辆，給它的空白處，依次填入適當?shù)臄?shù)字竹习。
• 這樣就可以歸納出一個窮舉問題评姨，每一個空格都有1~9 候選值洋满。需要做的是：
  • 如何依次找到空格曼振。
  • 對空格處的值進行合理性判斷。
  • 遞歸到下一個空格红符。
  • 在某一層青柄，所有的取值都失敗了，要有返回上一層的機制预侯，使上一層繼續(xù)嘗試下一個數(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 ++;
            }
        }
        //沒有可填充的了 全部完成
        if(row >= 9){
            return true;
        }
        
        //找出下一個填充點
        int rowNew = row + col/8;
        int colNew = (col + 1)%9;    
        
        //所以接下來嘗試給 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;
    }
}