※現在、ブログ記事を移行中のため一部表示が崩れる場合がございます。
順次修正対応にあたっておりますので何卒ご了承いただけますよう、お願い致します。

Python正月特集:ナンプレを解く (2)Board編


2017年 01月 04日

盤面をクラスとして書く部分を今日は紹介する。
 クラス名はわかりやすく、Boardとした。
そして、最初に5つのメンバー変数を用意した。
class Board():
board = {}                             # ナンプレ問題盤面 (x,y):n
hconst = [set() for i in range(9)]     # ヨコ制約
vconst = [set() for i in range(9)]     # タテ制約
bconst = [set() for i in range(9)]     # ブロック制約
numbers = {1,2,3,4,5,6,7,8,9}          # 利用可能数字
boardは辞書で、(x,y)に数字nが入っていることを、(x,y):n で示す。
hconstのconstは定数ではなく制約constraintの省略形である。
ヨコの制約が9組、タテの制約が9組、ブロックの制約が9組あるのを、集合のリストで表現し、使われている数字を集合に入れる。
1から9までの数字の集合があった方が便利そうなので、numbers を作った。

あとは、メソッドを色々用意した。

Boardの初期化は、最初から数字のあるところをリストでもらい、setnumで順番にその数字を盤面にセットしていく。これで、初期化を終えることにする。

問題を解くために、数字の入っていないマスをリストで持っておき、そのリストを見ながら数字を埋めたり剥いだりするとよい。そのために数字の入っていないマスのリストを作るのがmakeblanklistメソッド。

xy2bは、(x,y)のマスが属するブロックの番号を返す。
 
isusedは、(x,y)に数字nを入れられるかどうかを調べる。

    def __init__(self,hint):
for x,y,n in hint:
self.setnum(x,y,n)

def makeblanklist(self):
return [(x,y) for y in range(9) for x in range(9) if (x,y) not in self.board]

def xy2b(self,x,y):  return  x//3*3+y//3

def isused(self,x,y,n):
return (n in hconst[x]) or (n in vconst[y]) or (n in bconst[xy2b(x,y)])
setnumは、(x,y)に数字nをセットする。盤面boardの(x,y)にnを入れる。

さらに、タテ、ヨコ、ブロックの制約にもnを追加しておく。

 rmnumは、setnumの逆操作を行う。

    def setnum(self,x,y,n):
self.board[(x,y)] = n
self.vconst[x].add(n)
self.hconst[y].add(n)
self.bconst[self.xy2b(x,y)].add(n)

def rmnum(self,x,y,n):
self.board.pop((x,y))
self.vconst[x].remove(n)
self.hconst[y].remove(n)
self.bconst[self.xy2b(x,y)].remove(n)
possiblesは、(x,y)に入れられる数字の集合を返す。

 getは、盤面のboard[(x,y)]に入っている数字を返すのだが、存在しないとエラーになるので、存在チェックが行われている。
    def possibles(self,x,y):
return  self.numbers - (self.vconst[x]|self.hconst[y]|self.bconst[self.xy2b(x,y)])

def get(self,x,y):
return self.board[(x,y)] if (x,y) in self.board else 0
盤面をプリントするメソッドがprintである。説明の必要はないであろう。
    def print(self):
for y in range(9):
print()
for x in range(9):
n = self.get(x,y)
print((str(n) if n!=0 else '_')+' ',end='')
print()
これだけ道具を用意し、あとは次回、解くためのクラスSolverを説明する。 以下に、Boardクラスをまとめて示す。
class Board():
board = {}                             # ナンプレ問題盤面 (x,y):n
hconst = [set() for i in range(9)]     # ヨコ制約
vconst = [set() for i in range(9)]     # タテ制約
bconst = [set() for i in range(9)]     # ブロック制約
numbers = {1,2,3,4,5,6,7,8,9}          # 利用可能数字

def __init__(self,hint):
for x,y,n in hint:
self.setnum(x,y,n)

def makeblanklist(self):
return [(x,y) for y in range(9) for x in range(9) if (x,y) not in self.board]

def xy2b(self,x,y):  return  x//3*3+y//3

def isused(self,x,y,n):
return (n in hconst[x]) or (n in vconst[y]) or (n in bconst[xy2b(x,y)])

def setnum(self,x,y,n):
self.board[(x,y)] = n
self.vconst[x].add(n)
self.hconst[y].add(n)
self.bconst[self.xy2b(x,y)].add(n)

def rmnum(self,x,y,n):
self.board.pop((x,y))
self.vconst[x].remove(n)
self.hconst[y].remove(n)
self.bconst[self.xy2b(x,y)].remove(n)

def possibles(self,x,y):
return  self.numbers - (self.vconst[x]|self.hconst[y]|self.bconst[self.xy2b(x,y)])

def get(self,x,y):
return self.board[(x,y)] if (x,y) in self.board else 0

def print(self):
for y in range(9):
print()
for x in range(9):
n = self.get(x,y)
print((str(n) if n!=0 else '_')+' ',end='')
print()