Knuth的跳舞鏈接算法的數據結構

Question

如果我的問題聽起來很愚蠢，因爲我的數據結構理解不是很好，我很抱歉。

我一直在閱讀關於Knuth's Dancing Links算法，並非常瞭解它如何工作。有人提到跳舞鏈接的數據結構可視化看起來像一個有列和行的表格，每個單元格連接到它們的上，下，左，右單元格。我也讀過循環雙鏈表在這個算法中使用。

我想知道的是如何將雙鏈表設置爲具有列和行的表格？

據我所知，大多數雙鏈表只有2個指針（上下），這是否意味着我必須製作自己的自定義鏈表 - 它有4個指針（上，下，左，右） ）？還是有其他方法？

在此先感謝。

Answer 1

該算法對每個行和列使用雙向鏈表，而不僅僅是一個列表。

這個article on using dancing links to solve sudoku有一個不錯的圖片。

至少在本文的代碼中，行確實被表示爲左和右指針，而列在相同節點中表示爲上下指針，或多或少地如您所述，因此這些列表是相互關聯的。