The Fool In The Valleyの雑記帳

-- 好奇心いっぱいのおじいちゃんが綴るよしなし事 --

数独でPythonを 8

数独Pythonを 6」で書いた探索のアルゴリズムを実装するには、仮定を置いた時の状態を記憶していく必要があるが、それには連結リスト(linked list)を使うのがいいだろう。
連結リストは、一連のノードが、任意のデータフィールド群を持ち、次(および前)のノードを指す構造をしているもので、ノードを順番で管理するには都合がよい。

ここで、ノードに仮定を置くときの状態を対応させ、ノードから出る枝にそのときに選んだマスにおける候補の数字を対応させた図のような木を考える。

f:id:tfitv:20201022214411p:plain

仮定を置く必要が生じたとき、その時の盤面の状態と選択したマスAを記録したノードを連結リストの最後に追加し、マスAにおける候補のうちのa1を仮定して処理を進める。更に仮定を置く必要が生じたら、再びその時の盤面の状態と選択したマスB記憶したノードを連結リストの最後に追加し、マスBにおける候補のうちb1を仮定して処理を進める。もし途中で盤面に矛盾が生じれば、それはb1の仮定が誤っていたためなので、マスBで仮定を置いた時の状態に戻り、別の候補b2を仮定する。途中で再び盤面に矛盾が生じたときは、マスBで仮定を置いた時の状態に戻る。マスBにはそれ以上有効な候補数字がないときは、そのノードを削除し、一つ前にマスAで仮定を置いたときの状態に戻り、別の候補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