題目描述：編寫一個程序熔酷，通過已填充的空格來解決數(shù)獨(dú)問題吵聪。
一個數(shù)獨(dú)的解法需遵循如下規(guī)則：
數(shù)字?1-9?在每一行只能出現(xiàn)一次。
數(shù)字?1-9?在每一列只能出現(xiàn)一次。
數(shù)字?1-9?在每一個以粗實(shí)線分隔的?3x3?宮內(nèi)只能出現(xiàn)一次捻爷。
空白格用?'.'?表示。
示例：
Java代碼：
class Solution {
???int n = 3;
???????int N = n * n;
???????int[][] rows = new int[N][N+1];
???????int[][] columns = new int[N][N+1];
???????int[][] boxes = new int[N][N+1];
???????char[][] board;
???????boolean sudokuSolved = false;
???????public boolean couldPlace(int d,int row,int col) {
???????????//check if one could place a number in (row,col) cell
???????????int idx = (row / n) * n + col / n;
???????????return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
???????}
???????public void placeNumber(int d,int row,int col) {
???????????// place a number d in (row,col) cell
???????????int idx = (row / n) * n + col / n;
???????????rows[row][d]++;
???????????columns[col][d]++;
???????????boxes[idx][d]++;
???????????board[row][col] = (char)(d+'0');??
???????}
???????public void removeNumber(int d,int row,int col) {
???????????//remove a number which didn't lead to a asolution
???????????int idx = (row / n) * n + col /n;
???????????rows[row][d]--;
???????????columns[col][d]--;
???????????boxes[idx][d]--;
???????????board[row][col] = '.';
???????}
???????public void placeNextNumbers(int row,int col) {
???????????//call backtrack function in recursion to continue to place numbers tillthe moment we have a asolution
???????????//if we're in the end of therow,that means we have a solution
???????????if((col == N-1) && (row == N-1)) {
??????????????? sudokuSolved = true;
???????????}else {
??????????????? if(col == N - 1)backtrack(row+1,0);
??????????????? else backtrack(row,col+1);
???????????}
???????}
???????public void backtrack(int row,int col) {
???????????if(board[row][col] == '.') {
??????????????? //iterate over all numbers from1 to 9
??????????????? for(int d=1;d<10;d++) {
?????????????? ?????if(couldPlace(d,row,col)) {
??????????????????????? placeNumber(d,row,col);
???????????????????????placeNextNumbers(row,col);
??????????????????????? if(!sudokuSolved)removeNumber(d,row,col);
??????????????????? }
??????????????? }
???????????}else placeNextNumbers(row,col);
???????}
? public void solveSudoku(char[][] board) {
? ? this.board = board;
? ? // init rows, columns and boxes
? ? for (int i = 0; i < N; i++) {
? ? ? for (int j = 0; j < N; j++) {
? ? ? ? char num = board[i][j];
? ? ? ? if (num != '.') {
? ? ? ? ? int d = Character.getNumericValue(num);
? ? ? ? ? placeNumber(d, i, j);
? ? ? ? }
? ? ? }
? ? }
? ? backtrack(0, 0);
? }
}
