本文為個(gè)人解題思路整理,水平有限,有問(wèn)題歡迎交流
概覽
本題已數(shù)獨(dú)問(wèn)題為背景牙言,要求計(jì)算出唯一解辆毡,表面是一個(gè)暴力深搜和回溯的問(wèn)題菜秦,然而實(shí)際上如何優(yōu)化才是精華所在
難度:中等
核心知識(shí)點(diǎn):DFS(回溯)、狀態(tài)壓縮舶掖、位運(yùn)算
題目來(lái)源
力扣:https://leetcode-cn.com/problems/sudoku-solver
題目?jī)?nèi)容
編寫(xiě)一個(gè)程序球昨,通過(guò)已填充的空格來(lái)解決數(shù)獨(dú)問(wèn)題。
一個(gè)數(shù)獨(dú)的解法遵循如下規(guī)則:
數(shù)字
1-9
在每一行只能出現(xiàn)一次眨攘。數(shù)字
1-9
在每一列只能出現(xiàn)一次主慰。數(shù)字
1-9
在每一個(gè)以粗實(shí)線分隔的3x3
宮內(nèi)只能出現(xiàn)一次嚣州。
本題滿足以下設(shè)定:
給定的數(shù)獨(dú)序列只包含數(shù)字
1-9
和字符'.'
。你可以假設(shè)給定的數(shù)獨(dú)只有唯一解共螺。
給定數(shù)獨(dú)永遠(yuǎn)是
9x9
形式的该肴。
樣例
源數(shù)據(jù)
結(jié)果
解題思路
-
基本思路:顯然可以使用遞歸
DFS
暴力搜索每個(gè)可能的結(jié)果若最終所有結(jié)果被排除則搜索失敗
若所有空白被填充即搜索成功
剪枝:只需要搜索空白點(diǎn)就可以了,那么可以將這些空白點(diǎn)整理出來(lái)
剪枝:玩過(guò)數(shù)獨(dú)的都知道先從選擇少的點(diǎn)下手璃谨,這里同理沙庐,可以減少搜索的可能路徑數(shù)量
優(yōu)化:搜索的時(shí)候需要確定當(dāng)前點(diǎn)可能的數(shù)字,而這些數(shù)字要求不允許與同行佳吞、同列拱雏、同塊(3*3)相同,那么可以提前將每行底扳、每列铸抑、每塊已出現(xiàn)的數(shù)字存儲(chǔ)起來(lái),只需要檢查某個(gè)點(diǎn)所在的行列塊就能知道可選數(shù)字衷模,第一想法是存在數(shù)組里鹊汛,
-
優(yōu)化:行列快均只允許
1-9
數(shù)字,那么可以用二進(jìn)制數(shù)字表示阱冶,第i
位為1
則代表數(shù)字i
出現(xiàn)過(guò)刁憋,為0
則代表沒(méi)出現(xiàn)過(guò),注意二級(jí)制高位在右邊木蹬,比如第一行的二進(jìn)制是001010100
至耻,這樣處理帶來(lái)下面幾個(gè)好處每行僅需要一個(gè)10位二進(jìn)制數(shù)字表示即可,最大也就2047镊叁,總共只需要三個(gè)
int[9]
即可分別存放行尘颓、列、塊的狀態(tài)-
使用位運(yùn)算進(jìn)行數(shù)據(jù)變更或者檢查都極其方便(性能消耗也谢奁)
如某個(gè)目標(biāo)狀態(tài)為
states
疤苹,進(jìn)行以下操作將第
i
位設(shè)為1
:state |= 1 << i
將第
i
位設(shè)為0
:state ^= 1 << i
檢查第
i
位是否為0:(state >> i) % 2 == 0
-
優(yōu)化:因?yàn)橹恍枰@得唯一解,那么放置一個(gè)全部變量用于標(biāo)記是否找到答案即可敛腌。當(dāng)標(biāo)記為
true
的時(shí)候即結(jié)束所有搜索卧土,不再搜索;若檢查了所有可能性迎瞧,該標(biāo)記仍未false
則證明沒(méi)有答案當(dāng)然夸溶,如果答案不止一個(gè)就不能這么處理了
解題思路確定,開(kāi)始整理解題方案
解題方案
-
遍歷整個(gè)棋盤的每個(gè)點(diǎn)凶硅,以計(jì)算行缝裁、列、塊的狀態(tài),并獲取
若該點(diǎn)為
.
捷绑,證明為空白韩脑,將這個(gè)點(diǎn)存儲(chǔ)在列表中若該點(diǎn)不位
.
,證明為數(shù)字粹污,將相關(guān)的行段多、列、塊中標(biāo)記已出現(xiàn)過(guò)這個(gè)數(shù)字
-
開(kāi)始深度搜索
獲取選擇可能性最小的點(diǎn)
position
壮吩,并計(jì)算其可能的所有數(shù)字檢查
position
是否存在进苍,不存在則證明所有空點(diǎn)已填充,修改標(biāo)記為搜索成功鸭叙,并結(jié)束遞歸-
用數(shù)字
i
枚舉1-9
檢查是否是否允許數(shù)字
i
觉啊,不允許則跳過(guò)-
修改數(shù)據(jù)
將當(dāng)前搜索的點(diǎn)修改為數(shù)字
i
修正與當(dāng)前相關(guān)的行、列沈贝、塊的狀態(tài)
將當(dāng)前點(diǎn)標(biāo)記為已填充
進(jìn)行下一層搜索
檢查搜索成功的標(biāo)記杠人,若搜索成功則結(jié)束遞歸
-
撤回修改數(shù)據(jù)
將當(dāng)前搜索的點(diǎn)修改為空白
.
修正與當(dāng)前相關(guān)的行、列宋下、塊的狀態(tài)
將當(dāng)前點(diǎn)標(biāo)記為未填充
完整代碼
<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n398" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> class DemoBasicApplicationTests {
@Test
void test() {
char[][] board = {
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '.', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
solveSudoku(board);
}
?
public int[] col = new int[9];//行
public int[] row = new int[9];//列
public int[][] block = new int[3][3];//塊
List<Integer> list = new ArrayList<>();//空白位列表
boolean flag = false;//標(biāo)記嗡善,用于識(shí)別搜索是否成功
?
/**
- 解決方案
/
public void solveSudoku(char[][] board) {
//初始化
init(board);
//執(zhí)行dfs搜索
dfs(board);
//打印結(jié)果
// System.out.println(flag);
out(board);
}
?
/* - 打印board
- 調(diào)試用
- @param board 目標(biāo)board
/
public void out(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
?
/* - 初始化,填充行学歧、列罩引、塊以及空白位列表的值
- @param board 目標(biāo)board
/
public void init(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
//不為空的時(shí)候,更新行枝笨、列蜒程、塊的值
update(i, j, board);
} else {
//為空,則將其添加到空白位列表
list.add(i * 9 + j);
}
}
}
}
?
/* - 執(zhí)行搜索
- 在排除所有可能后結(jié)束搜索伺帘,flag標(biāo)記搜索成功或失敗
- @param board 目標(biāo)board
/
private void dfs(char[][] board) {
//查詢到list中下一個(gè)位置
int nextPosition = getNextPosition();
//找不到下一個(gè)嘗試位置,即所有點(diǎn)均填充完成忌锯,則結(jié)束搜索伪嫁,并判斷為搜索成功
if (nextPosition < 0) {
flag = true;
return;
}
//下一個(gè)位置的棋盤中的位置
int next = list.get(nextPosition);
int state = getState(next);
//從1開(kāi)始檢索,檢索到9
int i = 0;
while (++i < 10) {
//開(kāi)始嘗試
if ((state >> i) % 2 == 0) {//第i位為0偶垮,則證明該位置可能為i
//更新行列
board[next / 9][next % 9] = (char) (i + '0');
list.set(nextPosition, -1);
update(next / 9, next % 9, board);
// out();
// System.out.println("" + next / 9 + " " + next % 9 + " " + i);
//開(kāi)始搜索下一個(gè)位置
dfs(board);
//找到答案张咳,結(jié)束搜索
if (flag) {
return;
}
//未找到答案,撤回修改似舵,繼續(xù)嘗試
board[next / 9][next % 9] = '.';
list.set(nextPosition, next);
update(next / 9, next % 9, i, board);
}
}
}
?
/* - 獲取下一個(gè)位置
- @return 下一個(gè)位置在list中的位置脚猾,若結(jié)果為-1則證明沒(méi)有需要查詢的結(jié)果
/
private int getNextPosition() {
int position = -1;
int minNum = -1;
for (int i = 0; i < list.size(); i++) {
//忽略被標(biāo)記為-1的位置
if (list.get(i) >= 0) {
//找到可能性最少的位置
int possibleNum = getPossibleNum(list.get(i));
if (position < 0 || possibleNum < minNum) {
minNum = possibleNum;
position = i;
}
}
}
return position;
}
?
/* - 計(jì)算可能數(shù)字的數(shù)量
/
private int getPossibleNum(int position) {
int state = getState(position);
int num = 0;
//遍歷每個(gè)二進(jìn)制位,若為1則計(jì)數(shù)器加1
while (state > 0) {
num += state & 1;
state >>= 1;
}
return 9 - num;
}
?
/* - 查詢某個(gè)位置的狀態(tài)
/
private int getState(int position) {
int x = position / 9;
int y = position % 9;
int state = col[x] | row[y] | block[x / 3][y / 3];
return state;
}
?
/* - 更新某個(gè)位置的數(shù)據(jù)
- @param x 橫坐標(biāo)
- @param y 縱坐標(biāo)
- @param board 棋盤
/
private void update(int x, int y, char[][] board) {
int num = 1 << (board[x][y] - '0');
col[x] |= num;
row[y] |= num;
block[x / 3][y / 3] |= num;
}
?
/* - 更新某個(gè)位置的數(shù)據(jù)到指定數(shù)字
- @param x 橫坐標(biāo)
- @param y 縱坐標(biāo)
- @param target 目標(biāo)數(shù)字
- @param board 棋盤
*/
private void update(int x, int y, int target, char[][] board) {
int num = 1 << target;
col[x] ^= num;
row[y] ^= num;
block[x / 3][y / 3] ^= num;
}
}</pre>
執(zhí)行結(jié)果:
性能:
記得關(guān)閉掉打印砚哗,否則會(huì)影響執(zhí)行時(shí)間
后記
表面深搜龙助,實(shí)則優(yōu)化,提出解決方案并不難蛛芥,提出優(yōu)質(zhì)的解決方案才是我們?cè)撟非蟮?/p>
作者:Echo_Ye
WX:Echo_YeZ
Email :echo_yezi@qq.com
個(gè)人站點(diǎn):在搭了在搭了提鸟。军援。。(右鍵 - 新建文件夾)