「数独でPythonを６」で記した数独の解法アルゴリズムを実装するために、いくつかのクラスを定義する。
● 数独の各マスをオブジェクトとして扱うためのクラス
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
● 数独の９×９のマス全体をオブジェクトとして扱うためのクラス
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を６」で記した解法のアルゴリズムは、下記に示すような形でコーディングすることができる。このプログラムでは、数独の問題を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個のマスが決定する。
この処理を図で示すと次のようになり、多分木を深さ優先で探索しているのが分かる。
この例に対しては、最終的に次のような解が得られる。
____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を ６で記したアルゴリズムを使うと、簡単な問題であれば仮定を置かずに解くことができるし、難問と評価される問題に対しても上記の例のように複数回の仮定を置くことにより解を得ることができることが確かめられた。
