Knuthのダンスリンクアルゴリズムのデータ構造

Question

データ構造の理解度があまり良くないため、私の質問が愚かに聞こえる場合は申し訳ありません。

私はKnuth's Dancing Linksアルゴリズムを読んでいて、それが基本的にどのように動作するかをほとんど理解しています。リンクのデータ構造の視覚化をダンスすることは、列と行を持つ表のように見え、各セルは上、下、左、右のセルに接続されていると言われています。また、このアルゴリズムでは円環状の二重リンクリストが使用されていることも読んでいます。

私が知りたいことは、二重リンクリストをどのように列と行を使ってそのようなテーブルに作ることができるかです。

私が知っているように、ほとんどのダブルリンクされたリストは2つのポインタ（上下）を持っています、それは私が4つのポインタ（上、下、左、右） ）？それとも別の方法がありますか？

ありがとうございます。

Answer 1

このアルゴリズムでは、1つのリストだけでなく、各行と列に対して2重リンクのリストが使用されます。

このarticle on using dancing links to solve sudokuには素晴らしい画像があります。

少なくとも、この記事のコードでは、行は実際には左右のポインタとして表現され、列は同じノード内の上下のポインタとして表現されます。リストは相互に関連しています。