#大有學問#
一、數獨規則
解數獨大家都玩過,它的規則是:
1.數字1-9在每一行隻能出現一次。
2.數字1-9在每一列隻能出現一次。
3.數字1-9 在每一個粗實線圍成的3×3方格中 隻能出現一次。
下圖就是一個未解答的數獨
數獨
二、計算機求解數獨思路
那如何解答數獨呢?下圖為解答的思路圖:
思路圖
解答的思路是:
1.選擇一個未填空的方格(可以按照從左到右,從上到下的順序選擇),如果發現沒有未填空的方格,則說明數獨已解答。
2.在選定的方格中嘗試填入數字1-9,分别檢查填入的數字是否違反數獨的規則(見上),如果不違反規則,繼續執行1。如果違反規則,就将填入的數字清除,繼續選擇其他數字填入該方格進行嘗試。如果發現該方格無法填入1-9的任何數字,則說明該數獨無解。
實例講解:
思路看起來有點繞,我們拿實例講解。案例中,首先我們選擇第一行第三列的格子,嘗試填入數字1。由檢查得,它沒有違反數獨規則。因此,繼續選擇第一行第四列的格子,嘗試填入數字1,發現這違反了數獨規則1(數字1-9在每一行隻能出現一次),于是删除該格填入的數字。再次嘗試在第一行第四列的格子中填入數字2,由檢查得,它沒有違反數獨規則。可以繼續選擇新的格子嘗試填入數字。如此循環,直到找出數獨的解或者發現數獨無解。
以下為解數獨的僞代碼:
僞代碼
該案例參考了leetcode網站題庫,感興趣的朋友可以去力扣嘗試求解。
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!