剛才刷leetcode，碰到一個問題，驗證一個數(shù)獨的正確性(36. Valid Sudoku)，意思是只要滿足以下規(guī)則就行：
1、每一行只能出現(xiàn)1～9這九個數(shù)字，并且不能重復。
2、每一列只能出現(xiàn)1～9這九個數(shù)字，并且不能重復。
3、每一個子九宮格里面只能出現(xiàn)1～9這九個數(shù)字，不能重復。
數(shù)獨問題
這道題目的解法也不難，直接暴力就可以，n方的復雜度。
精彩的部分來了，大家注意（敲黑板）。
下面一題是，給你一個數(shù)獨，寫通用程序去解這個數(shù)獨(37. Sudoku Solver)。
我覺得這存粹是一個數(shù)學題目了，求幾十個方程組的解嘛，可能用到線性代數(shù)矩陣啥的，早忘了。于是果斷放棄，去看題目后面的討論。
首先看到了新加坡總理李顯龍的解法，總理寫代碼誰也擋不住啊，深深地感受到智商被壓制了?？梢詤⒖枷旅鎯蓚€鏈接。
https://arstechnica.com/information-technology/2015/05/prime-minister-of-singapore-shares-his-c-code-for-sudoku-solver/
https://leetcode.com/problems/sudoku-solver/discuss/15796/Singapore-prime-minister-Lee-Hsien-Loong's-Sudoku-Solver-code-runs-in-1ms
然后我看到下面這種暴力解決方法：
public class Solution {
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0)
return;
solve(board);
}
public boolean solve(char[][] board){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
if(isValid(board, i, j, c)){
board[i][j] = c; //Put c for this cell
if(solve(board))
return true; //If it's the solution return true
else
board[i][j] = '.'; //Otherwise go back
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char c){
for(int i = 0; i < 9; i++) {
if(board[i][col] != '.' && board[i][col] == c) return false; //check row
if(board[row][i] != '.' && board[row][i] == c) return false; //check column
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
}
return true;
}
}
沒有耐心看代碼的同學我簡單說一下原理，這個方法就是把1到9這個數(shù)字逐一放到數(shù)獨中去，然后驗證是否是合法數(shù)獨（調用上面一題的代碼的部分邏輯），如果是合法的將數(shù)字放入數(shù)獨中去，對新的數(shù)獨做遞歸，直到填滿整個數(shù)獨。
我表示，這種方法與李顯龍的方法比起來，不僅僅是暴力了，還有一種江湖氣息?？彻锨胁耍粋€一個試過去，就是遞歸到底！
