The Fool In The Valleyの雑記帳

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

数独でPythonを 9

数独Pythonを6」で記した数独の解法アルゴリズムを実装するために、いくつかのクラスを定義する。

● 数独の各マスをオブジェクトとして扱うためのクラス

class TableElement:
    def __init__(self):
        self.defVal = 0
        self.candList = [1,2,3,4,5,6,7,8,9]
        self.candNum = 9
        self.newlyDefined = 0
        self.known = 0 # 1 for known, 0 for unknown


● 数独の9×9のマス全体をオブジェクトとして扱うためのクラス

class WorkSheet:
    def __init__(self, orgTable):
        self.curCntOfFixed = 0
        self.Table = [[TableElement() for i in range(9)] for j in range(9)]
        for y in range(9):
            for x in range(9):                
                if(orgTable[y,x] != 0 ): # 数字が確定しているElementは以下の設定をする
                    self.curCntOfFixed = self.curCntOfFixed + 1 # 確定しているElementの数
                    self.Table[y][x].defVal = orgTable[y,x]
                    self.Table[y][x].candList = [0,0,0,0,0,0,0,0,0]
                    self.Table[y][x].candNum = 0
                    self.Table[y][x].newlyDefined = 1
                    self.Table[y][x].known = 1


● 仮定を置くときの状態をオブジェクトとして扱うためのクラス

class KeepStatus:
    def __init__(self, WS):
        self.hypox = 0
        self.hypoy = 0
        self.recordOfTable = [[TableElement() for i in range(9)] for j in range(9)]
        for y in range(9):
            for x in range(9):
                self.recordOfTable[y][x] = WS.Table[y][x]
        self.countOfFixed = WS.curCntOfFixed

これらのクラスを使うと、「数独Pythonを6」で記した解法のアルゴリズムは、下記に示すような形でコーディングすることができる。このプログラムでは、数独の問題をorgTableとして二次元配列で表し、TestWS = WorkSheet(orgTable) でインスタンスを生成することにより、最終的に TestWS.Table[y][x].defVal で解を得ることができる。

linkedStatus = LinkedList() 
TestWS = WorkSheet(orgTable)
trialCnt = 0
while TestWS.curCntOfFixed != 81 :
    trialCnt += 1
    prevCntOfFixed = TestWS.curCntOfFixed  
    updateCandList(TestWS)
    fixElemIfCandAppearOnlyThere(TestWS)  
    fixElemIfItHasOnlyOneCand(TestWS)

    if(prevCntOfFixed == TestWS.curCntOfFixed): 
        memoryOfStatus = copy.deepcopy(KeepStatus(TestWS)) 
        min = 9  
        for y in range(9):
            for x in range(9):
                if(memoryOfStatus.recordOfTable[y][x].candNum >= 2):
                    if(memoryOfStatus.recordOfTable[y][x].candNum < min):
                        min = memoryOfStatus.recordOfTable[y][x].candNum
                        memoryOfStatus.hypoy = y
                        memoryOfStatus.hypox = x
  
        linkedStatus.add_last(memoryOfStatus)       
        ym = memoryOfStatus.hypoy
        xm = memoryOfStatus.hypox
        hypoAtYpXp(TestWS, ym, xm, linkedStatus) 
         
    tableValid = checkValidity(TestWS)
    if(tableValid == False):
        yp = linkedStatus.get_last().hypoy
        xp = linkedStatus.get_last().hypox     
        while(linkedStatus.get_last().recordOfTable[yp][xp].candNum == 0):
            linkedStatus.remove_last()
            yp = linkedStatus.get_last().hypoy
            xp = linkedStatus.get_last().hypox
       
        for y in range(9): 
            for x in range(9):
                TestWS.Table[y][x].defVal = linkedStatus.get_last().recordOfTable[y][x].defVal
                for i in range(9):
                    TestWS.Table[y][x].candList[i] = linkedStatus.get_last().recordOfTable[y][x].candList[i]
                TestWS.Table[y][x].candNum = linkedStatus.get_last().recordOfTable[y][x].candNum
        TestWS.curCntOfFixed = linkedStatus.get_last().countOfFixed
        
        hypoAtYpXp(TestWS, yp, xp, linkedStatus)

このプログラムの実行例を次の二次元配列で表される問題を使って示す。

orgTable = 
np.array([[0,0,0,0,0,0,0,0,0],
               [0,0,0,0,0,0,2,8,0],
               [3,7,6,4,0,0,0,0,0],
               [7,0,0,0,0,1,0,0,0],
               [0,2,0,0,0,0,0,0,0],
               [4,0,0,3,0,0,0,0,6],
               [0,1,0,0,2,8,0,0,0],
               [0,0,0,0,0,5,0,0,0],
               [0,0,0,0,0,0,0,0,3]])

この問題では、途中で、マスの値を確定させることができなくなり、どこかで仮定する必要がでてくる。その探索の様子は次のとおりである。ここで、マスの位置を(y,x)で表すことにする。
・途中で、マスの値を確定させることができなくなり、どこかで仮定する必要がでてくる。
・候補が少ない(0,5)で仮定を置くことにして、その時の状態をLinkedListの最後に追加する。
・(0,5)には候補7,9が存在する。その中から最も小さい値の7を仮定する。その後、(2,7)で確定していないのに候補が無くなるルール違反が発生する。それは仮定が誤っていたためなので、候補がある仮定ポイントまで状態を戻す。
・(0,5)には候補9が存在するのでそれを仮定する。途中で、マスの値を確定させることができなくなり、再度、どこかで仮定する必要がでてくる。
・候補が少ない(0,0)で仮定を置くことにして、その時の状態をLinkedListの最後に追加する。
・(0,0)には候補1,8,が存在する。その中から最も小さい値の1を仮定する。その後、マスの値を確定させることができなくなり、再度、どこかで仮定する必要がでてくる。
・候補が少ない(0,6)で仮定を置くことにして、その時の状態をLinkedListの最後に追加する。
・(0,6)には候補3,6が存在する。その中から最も小さい候補3を仮定する。その後、(6,8)で確定していないのに候補が無くなるルール違反が発生する。それは仮定が誤っていたためなので、候補がある仮定ポイントまで状態を戻す。
・(0,6)には候補6が存在するのでそれを仮定する。途中で、マスの値を確定させることができなくなり、再度、どこかで仮定する必要がでてくる。
・候補が少ない(1,0)で仮定を置くことにして、その時の状態をLinkedListの最後に追加する。
・(1,0)には候補5,9が存在する。その中から最も小さい値の5を仮定する。その後、(6,8)で確定していないのに候補が無くなるルール違反が発生する。それは仮定が誤っていたためなので、候補がある仮定ポイントまで状態を戻す。
・(1,0)には候補9が存在するのでそれを仮定する。その後、(2,7)で確定していないのに候補が無くなるルール違反が発生する。それは仮定が誤っていたためなので、候補がある仮定ポイントまで状態を戻す。
・(1,0)には候補がないのでその前の(0,6)に戻す。
・(0,6)には候補がないのでその前の(0,0)に戻す。
・(0,0)には候補8が存在するのでそれを仮定する。その仮定ですすめると、それ以降、ルールに違反することなしに81個のマスが決定する。

この処理を図で示すと次のようになり、多分木を深さ優先で探索しているのが分かる。

f:id:tfitv:20201101224259p:plain

この例に対しては、最終的に次のような解が得られる。

____0__1__2___3__4__5___6__7__8__
-----------------------------------
0 |_8__4__2_|_5__1__9_|_3__6__7_|
1 |_1__5__9_|_6__7__3_|_2__8__4_|
2 |_3__7__6_|_4__8__2_|_9__5__1_|
-----------------------------------
3 |_7__3__5_|_2__6__1_|_4__9__8_|
4 |_6__2__1_|_8__9__4_|_7__3__5_|
5 |_4__9__8_|_3__5__7_|_1__2__6_|
-----------------------------------
6 |_5__1__3_|_7__2__8_|_6__4__9_|
7 |_9__6__4_|_1__3__5_|_8__7__2_|
8 |_2__8__7_|_9__4__6_|_5__1__3_|
-----------------------------------

Pythonを 6で記したアルゴリズムを使うと、簡単な問題であれば仮定を置かずに解くことができるし、難問と評価される問題に対しても上記の例のように複数回の仮定を置くことにより解を得ることができることが確かめられた。