给定一个数独棋盘，输出它的一个解。
解法一 回溯法
从上到下，从左到右遍历每个空位置。在第一个位置，随便填一个可以填的数字，再在第二个位置填一个可以填的数字，一直执行下去直到最后一个位置。期间如果出现没有数字可以填的话，就回退到上一个位置，换一下数字，再向后进行下去。
publicvoidsolveSudoku(char[][] board) { solver(board); } privatebooleansolver(char[][] board) { for (inti=0; i<9; i++) { for (intj=0; j<9; j++) { if (board[i][j] =='.') { charcount='1'; while (count<='9') { if (isValid(i, j, board, count)) { board[i][j] =count; if (solver(board)) { returntrue; } else { //下一个位置没有数字，就还原，然后当前位置尝试新的数board[i][j] ='.'; } } count++; } returnfalse; } } } returntrue; } privatebooleanisValid(introw, intcol, char[][] board, charc) { for (inti=0; i<9; i++) { if (board[row][i] ==c) { returnfalse; } } for (inti=0; i<9; i++) { if (board[i][col] ==c) { returnfalse; } } intstart_row=row/3*3; intstart_col=col/3*3; for (inti=0; i<3; i++) { for (intj=0; j<3; j++) { if (board[start_row+i][start_col+j] ==c) { returnfalse; } } } returntrue; }
时间复杂度：
空间复杂度：O（1）。
总
回溯法一个很典型的应用了。
