「数独でPythonを 6」で書いた探索のアルゴリズムを実装するには、仮定を置いた時の状態を記憶していく必要があるが、それには連結リスト（linked list）を使うのがいいだろう。
連結リストは、一連のノードが、任意のデータフィールド群を持ち、次（および前）のノードを指す構造をしているもので、ノードを順番で管理するには都合がよい。
ここで、ノードに仮定を置くときの状態を対応させ、ノードから出る枝にそのときに選んだマスにおける候補の数字を対応させた図のような木を考える。
仮定を置く必要が生じたとき、その時の盤面の状態と選択したマスＡを記録したノードを連結リストの最後に追加し、マスＡにおける候補のうちのa1を仮定して処理を進める。更に仮定を置く必要が生じたら、再びその時の盤面の状態と選択したマスB記憶したノードを連結リストの最後に追加し、マスＢにおける候補のうちb1を仮定して処理を進める。もし途中で盤面に矛盾が生じれば、それはb1の仮定が誤っていたためなので、マスBで仮定を置いた時の状態に戻り、別の候補b2を仮定する。途中で再び盤面に矛盾が生じたときは、マスＢで仮定を置いた時の状態に戻る。マスＢにはそれ以上有効な候補数字がないときは、そのノードを削除し、一つ前にマスＡで仮定を置いたときの状態に戻り、別の候補a2を仮定する。・・・・この処理を繰り返すことにより深さ優先の探索ができる。
Pythonの標準的なライブラリの中には連結リストは用意されていないようで、ネット上には独自に作っている例を多く見かける。
そこで、Pythonの練習も兼ねて自前の連結リストとして、最も単純な片方向リストをクラスとして作ることにする。これを必要に応じて、双方向、循環リストに拡張することは容易である。
図のような片方向の連結リストを考え、それを管理するクラスをLinkedListクラス、データを保持するノードをNodeクラスとし、次のように実装した。
class Node: def __init__(self, data, next): self.data = data self.next = next class LinkedList: def __init__(self) -> None: self.len = 0 self.head = None def __len__(self) -> int: return self.len def add_first(self, data) -> None: ptr = self.head self.head = Node(data, ptr) self.len += 1 def add_last(self, data) -> None: if self.head is None: self.add_first(data) else: ptr = self.head while ptr.next is not None: ptr = ptr.next ptr.next = Node(data, None) self.len += 1 def remove_first(self) -> None: if self.head is not None: self.head = self.head.next self.len -= 1 def remove_last(self): if self.head is not None: if self.head.next is None: self.remove_first() else: ptr = self.head pre = self.head while ptr.next is not None: pre = ptr ptr = ptr.next pre.next = None self.len -= 1 def print_link(self): print("head",end="") if self.len > 0: ptr = self.head while ptr.next is not None: print("->",ptr.data,end="") ptr = ptr.next print("->",ptr.data,"->null") if self.len == 0: print("-> null") def get_last(self) : ptr = self.head if ptr is None: return None else: while ptr.next is not None: ptr = ptr.next return ptr.data
