今天是元宵佳節(jié)袍睡，又恰逢周末，原本應(yīng)該出門鬧花燈肋僧，但是當(dāng)前的新冠疫情讓大家關(guān)門閉戶異常冷清斑胜。
猜燈謎是元宵節(jié)的傳統(tǒng)項(xiàng)目，記得小時(shí)候在老家每個(gè)元宵節(jié)都打著燈籠出門嫌吠，大街上滿是彩燈和燈謎止潘，城市還專門組織有大型的煙火表演，人山人海熱鬧非凡辫诅。
既然沒(méi)法出門凭戴，在家也能做些個(gè)游戲，例如用看怎么用代碼來(lái)解決數(shù)獨(dú)問(wèn)題吧：）
我們有如下數(shù)獨(dú)問(wèn)題：
這是一個(gè)9X9的數(shù)獨(dú)矩陣炕矮，其中需要保證：
- 整數(shù)1～9在每一行中只能出現(xiàn)一次
- 整數(shù)1～9在每一列中只能出現(xiàn)一次
- 在其中9個(gè)3X3的子矩陣中么夫，整數(shù)1～9也只能出現(xiàn)一次
通過(guò)以上限制，我們期望得到以下的答案：
為了能用程序來(lái)解決數(shù)獨(dú)問(wèn)題肤视，我們用一個(gè)二維字符數(shù)組來(lái)代表字符矩陣：
char[][] board = {
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
其中未知的單元格用字符'.'來(lái)表示档痪，期望實(shí)現(xiàn)個(gè)函數(shù)將所有'.'替換為'1'~'9'的字符并保證數(shù)獨(dú)矩陣的合法性。
我們可以將此問(wèn)題分解為兩個(gè)子問(wèn)題來(lái)考慮：檢驗(yàn)放入一個(gè)值后邢滑，是否滿足數(shù)獨(dú)矩陣合法性腐螟；遞歸遍歷整個(gè)矩陣，并在未知位置依次試探放入'1'~'9'并檢查合法性殊鞭，如果不合法則使用下一個(gè)值進(jìn)行回溯分析遭垛。
校驗(yàn)當(dāng)前單元格放入數(shù)值后的合法性
要校驗(yàn)合法性，滿足數(shù)據(jù)矩陣所要求的三個(gè)規(guī)則即可：
/**
* 校驗(yàn)放入當(dāng)試探值是否能保證數(shù)獨(dú)矩陣的正確性
*
* @param board 數(shù)獨(dú)矩陣
* @param x x軸坐標(biāo)代表列號(hào)
* @param y y軸坐標(biāo)代表行號(hào)
* @param c 試探放入的值操灿，為'1'~'9'的整數(shù)
* @return 返回true當(dāng)校驗(yàn)通過(guò)
*/
private boolean isValid(char[][] board, int x, int y, char c) {
//3*3方塊的開(kāi)始y軸號(hào)
int regionRow = 3 * (y / 3);
//3*3方塊的開(kāi)始x軸坐標(biāo)
int regionCol = 3 * (x / 3);
for (int i = 0; i < 9; i++) {
//檢查每一行的正確性
if (board[i][x] == c) return false;
//檢查每一列的正確性
if (board[y][i] == c) return false;
//檢查3*3方格內(nèi)的正確性
if (board[regionRow + i / 3][regionCol + i % 3] == c) return false;
}
return true;
}
遞歸回溯分析整個(gè)矩陣
我們循環(huán)遍歷整個(gè)二維數(shù)組锯仪，當(dāng)遇到'.'后試探放入'1' ~ '9‘的整數(shù)并使用上面的方法進(jìn)行正確性分析，如果正確后趾盐，遞歸調(diào)用下一個(gè)單元格庶喜，如果當(dāng)前單元格放入'1' ~ '9'都不能得到合法的數(shù)獨(dú)矩陣小腊，則說(shuō)明之前單元格放入了錯(cuò)誤的值，此時(shí)回溯到上一次遞歸久窟，試探放入下一個(gè)合法的整數(shù)秩冈，繼續(xù)進(jìn)行遞歸分析：
/**
* 遞歸函數(shù)，當(dāng)?shù)玫胶戏ǖ臄?shù)據(jù)矩陣后返回true
*
* @param board 數(shù)獨(dú)矩陣
* @param x x軸坐標(biāo)代表列號(hào)
* @param y y軸坐標(biāo)代表行號(hào)
* @return
*/
private boolean check(char[][] board, int x, int y) {
for (; y < 9; y++) {
//如果輸入的列號(hào)溢出斥扛，則直接進(jìn)入下一行從第一列開(kāi)始
for (; x < 9; x++) {
if (board[y][x] != '.') continue;
//當(dāng)前值為'.'時(shí)入问，
//依次試探放入'1'~'9'的值來(lái)看是否滿足合法的數(shù)獨(dú)矩陣
for (char c = '1'; c <= '9'; c++) {
//放入后不合法，直接忽略稀颁，嘗試下一個(gè)值
if (!isValid(board, x, y, c)) continue;
board[y][x] = c;
//當(dāng)前位置試探放入值c后芬失，遞歸調(diào)用下一列
if (check(board, x + 1, y)) {
//當(dāng)前值賦值c后，遞歸調(diào)用全部滿足數(shù)獨(dú)矩陣合法性匾灶，
//則返回成功
return true;
}
//當(dāng)前位置放入c后棱烂，后續(xù)位置不能得到合法的數(shù)獨(dú)矩陣，
//繼續(xù)進(jìn)行回溯分析阶女，因?yàn)樯洗螌舆f歸調(diào)用要重寫(xiě)開(kāi)始分析颊糜，
//所以要恢復(fù)當(dāng)前的原始值
board[y][x] = '.';
}
//'1'~'9'全部試探完成后，
//依然無(wú)法獲得合法數(shù)獨(dú)矩陣秃踩，
//則說(shuō)明之前放入的值有誤衬鱼，
//返回后上次層遞歸方法繼續(xù)取其他值進(jìn)行遞歸
return false;
}
//下一行，從第一列開(kāi)始
x = 0;
}
//此時(shí)數(shù)組已經(jīng)越界吞瞪，
//說(shuō)明全部遞歸完成沒(méi)有發(fā)現(xiàn)非法數(shù)獨(dú)矩陣馁启，返回成功
return true;
}
驗(yàn)證
最后完成測(cè)試用例以及調(diào)用方法，進(jìn)行結(jié)果驗(yàn)證：
public void solveSudoku(char[][] board) {
check(board, 0, 0);
}
public static void main(String[] args) {
Solution solution = new Solution();
char[][] board = {
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
solution.solveSudoku(board);
System.out.println("{");
for (char[] row : board) {
System.out.print(" {");
String split = "";
for (char c : row) {
System.out.print(split + c);
split = ",";
}
System.out.println("},");
}
System.out.println("}");
}
得到正確結(jié)果：
{
{5,3,4,6,7,8,9,1,2},
{6,7,2,1,9,5,3,4,8},
{1,9,8,3,4,2,5,6,7},
{8,5,9,7,6,1,4,2,3},
{4,2,6,8,5,3,7,9,1},
{7,1,3,9,2,4,8,5,6},
{9,6,1,5,3,7,2,8,4},
{2,8,7,4,1,9,6,3,5},
{3,4,5,2,8,6,1,7,9},
}
好了芍秆，以后這種數(shù)獨(dú)問(wèn)題我們都能在幾毫秒內(nèi)解決它了：）
