【舌尖上的演算法】Day29 -- Sudoku - Algorithm X

2020 IT邦鐵人賽

Posted by Hank Lee on Tuesday, October 6, 2020

4 Minutes Read

Table of Contents

本系列文章同步分享於IT邦幫忙第12屆鐵人賽

前言

昨天我們介紹了如何使用Backtracking的方式來破解數獨,這個Backtracking的解法在網路上可以找到很多資料參考學習,然而今天要講的這個Algorithm X好像比較沒什麼人在提,至少我好像沒有找到關於這個Algorithm X的中文介紹,今天就主要介紹什麼是Algorithm X


Algorithm X是什麼

Algorithm X是在2000年Stanford University的Knuth教授提出來的概念(參考資料3),雖然在這篇paper中主要介紹的是Dancing Links這種資料結構,但是Algorithm X可以說是Dancing Links的前身,而Algorithm X一種包含Backtracking概念且用遞迴設計的演算法,主要是用來解決Exact Cover Problem,而透過Algortihm X來處理exact cover problem的時候,是將資料變成陣列(Matrix),並在每個位置以0和1的方式紀錄每一筆資料的資訊,然後目標是找出一個對於所有欄(Column)都是1的一個組合,大概的流程如下:

  1. 如果Matrix中已經沒有任何的欄(Column)時,表示目前已經取得的結果是有效的,因此結束程序。
  2. 反之,則選擇其中一個欄(Column)作為目標。(需要設定如何選擇目標欄)
  3. 藉由這個欄來選擇一個欄位值為1的列(row) – M(r, c) = 1
  4. 將這一列資料作為解答的一部分。
  5. 根據這一列的資料中,哪些欄位的值為1,就將這些欄位的『欄』刪除;同時將這些欄刪除時,也會對應到一些其他的列,將這些列也刪除。
  6. 反覆1~5步。

好吧~我知道還是很抽象,因此下面我們來解說一個範例。

上面提到的Dancing Links就是將Matrix轉換成一個Doubly Linked List的資料結構,有興趣的人可以Google看看,資料也滿多的,我之後有空再來補一篇介紹Dancing Links的內容,但可能就只會發布在我個人Blog上了。


Algorithm X的範例

首先,Algorithm X的概念下,需要先將資料轉換成一個Matrix的形式,轉換的過程如下(這個範例中我就不把空的欄位補0了,這樣看可能比較清楚地可以看到1的分布狀況):

Algorithm X - example

有了上面的Matrix,我們就可以利用這個Matrix去進行Algorithm X,目標就是找出一個組合可以包含1~7

Algorithm X - steps

在這個範例中,我們如何決定要從哪一個欄(Column)來作為目標呢?答案就是:合計每個欄中的1的數目,從總合最小的欄開始。從GIF中可以看到,一開始選了Column 1作為目標,因為針對Column 1計算1的數量,合計為2,且順序靠前;而有包含1的列(row)有A和B,因為順序的關係,先選了A,結果當下一個要選擇的Column(2)的時候,發現在Column 2中並沒有其值為1的欄位,這就表示目前的解答是無效的(因為解答絕對沒有辦法包含1~7),因此就會進行backtracking,才去選了B,因為選B的話,B本身就包含了1,4,因此其他有含1或4的Row都要跟著刪除,故A和C就被刪除了,剩下DEF;在計算每個欄的1數量後,Column 5的1數目只有1,因此選擇Column 5為下一個目標,又唯一有包含Column 5的列為D,因此先將D加入解答中,再依據D包含的數字(3, 5, 6)來刪除其他的Row(E),結果只剩下了F,因此最後也把F加入了解答,此時Matrix為空,因此程式終止,取得最後的結果是B, D, F


小結

Algorithm X會需要先將資料轉換成Matrix的型態,然後再從中選出每個欄都被包含進去的組合作為解答。


預告

明天就是我們這三十天系列文的最後一篇文章了,最後一天我們來介紹Algorithm X與數獨的關係。


References

  1. Knuth’s Algorithm X
  2. Knuth, Donald E. (2000), “Dancing links”, in Davies, Jim; Roscoe, Bill; Woodcock, Jim (eds.), Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare, Palgrave, pp. 187–214