【算法刷題】解數(shù)獨(dú)

本文為個(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ù)
img
結(jié)果
img

解題思路

  • 基本思路:顯然可以使用遞歸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è)為1state |= 1 << i

      • 將第i位設(shè)為0state ^= 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)始整理解題方案

解題方案

  1. 遍歷整個(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ù)字

  2. 開(kāi)始深度搜索

    1. 獲取選擇可能性最小的點(diǎn)position壮吩,并計(jì)算其可能的所有數(shù)字

    2. 檢查position是否存在进苍,不存在則證明所有空點(diǎn)已填充,修改標(biāo)記為搜索成功鸭叙,并結(jié)束遞歸

    3. 用數(shù)字i枚舉1-9

      1. 檢查是否是否允許數(shù)字i觉啊,不允許則跳過(guò)

      2. 修改數(shù)據(jù)

        1. 將當(dāng)前搜索的點(diǎn)修改為數(shù)字i

        2. 修正與當(dāng)前相關(guān)的行、列沈贝、塊的狀態(tài)

        3. 將當(dāng)前點(diǎn)標(biāo)記為已填充

      3. 進(jìn)行下一層搜索

      4. 檢查搜索成功的標(biāo)記杠人,若搜索成功則結(jié)束遞歸

      5. 撤回修改數(shù)據(jù)

        1. 將當(dāng)前搜索的點(diǎn)修改為空白.

        2. 修正與當(dāng)前相關(guān)的行、列宋下、塊的狀態(tài)

        3. 將當(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é)果:

image-20200916163654701

性能:

image-20200916164057937

記得關(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):在搭了在搭了提鸟。军援。。(右鍵 - 新建文件夾)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末称勋,一起剝皮案震驚了整個(gè)濱河市胸哥,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌赡鲜,老刑警劉巖空厌,帶你破解...
    沈念sama閱讀 211,496評(píng)論 6 491
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異银酬,居然都是意外死亡嘲更,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,187評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門捡硅,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)哮内,“玉大人,你說(shuō)我怎么就攤上這事壮韭”狈ⅲ” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 157,091評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵喷屋,是天一觀的道長(zhǎng)琳拨。 經(jīng)常有香客問(wèn)我,道長(zhǎng)屯曹,這世上最難降的妖魔是什么狱庇? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,458評(píng)論 1 283
  • 正文 為了忘掉前任,我火速辦了婚禮恶耽,結(jié)果婚禮上密任,老公的妹妹穿的比我還像新娘。我一直安慰自己偷俭,他們只是感情好浪讳,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,542評(píng)論 6 385
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著涌萤,像睡著了一般淹遵。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上负溪,一...
    開(kāi)封第一講書(shū)人閱讀 49,802評(píng)論 1 290
  • 那天透揣,我揣著相機(jī)與錄音,去河邊找鬼川抡。 笑死辐真,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播拆祈,決...
    沈念sama閱讀 38,945評(píng)論 3 407
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼恨闪,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了放坏?” 一聲冷哼從身側(cè)響起咙咽,我...
    開(kāi)封第一講書(shū)人閱讀 37,709評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎淤年,沒(méi)想到半個(gè)月后钧敞,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,158評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡麸粮,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,502評(píng)論 2 327
  • 正文 我和宋清朗相戀三年溉苛,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片弄诲。...
    茶點(diǎn)故事閱讀 38,637評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡愚战,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出齐遵,到底是詐尸還是另有隱情寂玲,我是刑警寧澤,帶...
    沈念sama閱讀 34,300評(píng)論 4 329
  • 正文 年R本政府宣布梗摇,位于F島的核電站拓哟,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏伶授。R本人自食惡果不足惜断序,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,911評(píng)論 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望糜烹。 院中可真熱鬧违诗,春花似錦、人聲如沸疮蹦。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,744評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)挚币。三九已至,卻和暖如春扣典,著一層夾襖步出監(jiān)牢的瞬間妆毕,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,982評(píng)論 1 266
  • 我被黑心中介騙來(lái)泰國(guó)打工贮尖, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留笛粘,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,344評(píng)論 2 360
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像薪前,于是被迫代替她去往敵國(guó)和親润努。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,500評(píng)論 2 348