PlayGround Article Python Pythonでナンプレの話 takumah 2018年6月6日 Created with Sketch. 1 Created with Sketch. 453 mcz9mm iOS Engineer 先日行われた[Pythonでナンプレを解くプログラムを作ろう](https://playground-i.com/contents/11/)に先がけて個人的にナンプレを解くプログラムを作っていたのでそれについてちょっと書きます. ## ナンプレを解く際の基本方針 縦列,横列,箱内部の消去法をメインに用いる. ## 入力サンプル 数字からなる空白で区切られた9文字×9行の文字列.<br> 例: ``` 0 0 0 1 0 0 0 3 0 4 1 0 3 0 0 0 0 8 0 0 3 0 0 0 0 0 0 3 0 0 0 0 0 4 1 5 0 0 0 6 0 9 0 0 0 0 0 0 0 0 1 7 0 0 5 6 0 0 0 0 2 0 0 0 0 0 0 0 7 1 0 9 0 0 8 0 9 5 0 0 0 ``` ## 出力サンプル ``` この盤面を解きます! +-----+-----+-----+ |0 0 0|1 0 0|0 3 0| |4 1 0|3 0 0|0 0 8| |0 0 3|0 0 0|0 0 0| +-----+-----+-----+ |3 0 0|0 0 0|4 1 5| |0 0 0|6 0 9|0 0 0| |0 0 0|0 0 1|7 0 0| +-----+-----+-----+ |5 6 0|0 0 0|2 0 0| |0 0 0|0 0 7|1 0 9| |0 0 8|0 9 5|0 0 0| +-----+-----+-----+ 解けました! +-----+-----+-----+ |9 8 7|1 5 4|6 3 2| |4 1 5|3 2 6|9 7 8| |6 2 3|9 7 8|5 4 1| +-----+-----+-----+ |3 9 6|7 8 2|4 1 5| |7 5 1|6 4 9|8 2 3| |8 4 2|5 3 1|7 9 6| +-----+-----+-----+ |5 6 9|4 1 3|2 8 7| |2 3 4|8 6 7|1 5 9| |1 7 8|2 9 5|3 6 4| +-----+-----+-----+ ``` ## ソースコード ### 実装済み機能 - 盤面のインプット - 盤面の整形表示 - 候補リストの作成 - 縦横箱の消去法の実装 ### 未実装機能 - やや発展的思考の再現 ``` #!/usr/bin/python # -*- Coding: utf-8 -*- """ number-place solver by Takuma-Honjo(@takurnah) 入力は空白で区切られた9x9の数字からなる """ board = [] numb = [i+1 for i in range(9)] suggest = [[[i+1 for i in range(9)]for j in range(9)]for k in range(9)] def showsuggest():#候補リストの表示 for i in suggest: print(i) def loadboard():#盤面の読み込み for i in range (9): board.append(list(map(int, input().strip().split(' ')))) def showboard():#盤面の表示 print("+-----+-----+-----+") for i in range(9): print('|{0[0]} {0[1]} {0[2]}|{0[3]} {0[4]} {0[5]}|{0[6]} {0[7]} {0[8]}|'.format(board[i])) if i%3 == 2: print("+-----+-----+-----+") def fillcol(num,colmun):#縦列の候補削除 for i in suggest: if num in i[colmun]: i[colmun].remove(num) def fillrow(num,row):#横列の候補削除 for i in suggest[row]: if num in i: i.remove(num) def fillbox(a,box):#箱内部の候補削除 x0 = (box%3)*3 y0 = int(box/3)*3 for i in range(3): for j in range(3): if a in suggest[y0+i][x0+j]: suggest[y0+i][x0+j].remove(a) def confcell(x,y):#ボードの更新(Core) suggest[y][x].clear() fillcol(board[y][x],x) fillrow(board[y][x],y) fillbox(board[y][x],int(y/3)*3+int(x/3)) def updateboard():#ボードの更新(sub) for i in range(9): for j in range(9): if (board[j][i]!=0): confcell(i,j) def singlecell():#候補数が1のセルを確定させる flag = False for i in range(9): for j in range(9): if len(suggest[j][i])==1: flag = True board[j][i]=suggest[j][i].pop() confcell(i,j) return flag def chkcol(x):#縦列の候補数を減らす flag = False for i in numb: cnt = 0 for y in range(9): if i in suggest[y][x]: cnt += 1 x1 = x y1 = y if cnt == 1: flag=True board[y1][x1]=i confcell(x1,y1) return flag def chkrow(y):#横列の候補数を減らす flag = False for i in numb: cnt = 0 for x in range(9): if i in suggest[y][x]: cnt += 1 x1 = x y1 = y if cnt == 1: flag=True board[y1][x1]=i confcell(x1,y1) return flag def chkbox(box):#箱内部の候補数を減らす flag = False x0 = (box%3)*3 y0 = int(box/3)*3 for a in numb: cnt = 0 for i in range(3): for j in range(3): if a in suggest[y0+i][x0+j]: cnt += 1 x1 = x0+j y1 = y0+i if cnt == 1: flag=True board[y1][x1]=a confcell(x1,y1) return flag def chkans():#解の正当性をチェック for i in range(9): c1 = 1 c2 = 1 for j in range(9): c1 *= board[i][j] c2 *= board[j][i] if c1 != 362880 or c2 != 362880: return False return True def solveboard(): while True: flag = True for i in range (9): if singlecell(): flag = False if chkcol(i): flag = False if chkrow(i): flag = False if chkbox(i): flag = False if flag: break loadboard() print("この盤面を解きます!") showboard() print("\n") updateboard() solveboard() if chkans(): print("解けました!") else: print("解けませんでした...") showboard() ``` ## 課題 - 現状のロジックだけでは解くことができない問題がある. - 探索のコードまたは追加のロジックを書かなくてはならない. ### 全探索の危険性 例えば ``` +-----+-----+-----+ |7 2 1|6 3 9|5 8 4| |5 4 8|2 7 1|6 9 3| |0 6 0|0 8 0|1 2 7| +-----+-----+-----+ |6 7 0|3 0 2|8 4 1| |2 1 0|7 0 8|0 5 6| |0 8 0|1 0 6|0 7 2| +-----+-----+-----+ |1 0 7|0 6 0|2 3 8| |4 0 2|8 1 3|7 6 0| |8 3 6|0 2 7|4 1 0| +-----+-----+-----+ ``` のような盤面のとき,解は１通りだが全体では7077888通りある.<br> これは愚直に書く（全通り試す）ことをしてもだいたい数秒で終わる.<br> しかし, ``` +-----+-----+-----+ |0 0 6|0 8 1|0 0 4| |1 0 0|2 0 5|8 0 6| |5 0 0|0 0 3|9 2 1| +-----+-----+-----+ |0 1 0|0 0 0|3 9 7| |3 0 0|0 1 0|2 6 5| |7 6 0|0 3 2|1 4 8| +-----+-----+-----+ |0 5 1|3 0 0|6 8 9| |0 0 0|1 0 6|0 0 3| |6 7 3|0 5 0|4 1 2| +-----+-----+-----+ ``` の場合,全体で1141260857376768通り,だいたい1141兆通り,これはやりたくない.<br> もっと見てみよう. ``` +-----+-----+-----+ |0 0 5|4 0 7|8 1 0| |0 0 0|1 0 2|7 0 0| |0 0 1|0 5 6|0 0 2| +-----+-----+-----+ |1 0 7|0 0 0|4 0 8| |4 0 2|0 0 1|0 0 9| |8 0 6|0 0 0|2 0 1| +-----+-----+-----+ |6 0 0|0 1 0|0 0 0| |0 1 3|9 0 8|0 0 0| |0 0 4|7 0 3|1 0 0| +-----+-----+-----+ ``` 全体で71899434014736384000000通り.もう自分で数えてください. <br>つまり,全探索は非常に危険なのでやめるべきで,数を１個仮で決めたらそこからさらに絞る行為をする必要がある. ## こぼれ話 C++でもほぼ一緒のロジックを実装して同一の問題を与えた時の時間を計測. ``` Python3:0.079s C++14 :0.002s ``` C++はやっぱり高速ですわ!