题目描述：编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
示例：
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);
}
}
