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

盤面をクラスとして書く部分を今日は紹介する。
 クラス名はわかりやすく、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}          # 利用可能数字

boardは辞書で、(x,y)に数字nが入っていることを、(x,y):n で示す。
hconstのconstは定数ではなく制約constraintの省略形である。
ヨコの制約が９組、タテの制約が９組、ブロックの制約が９組あるのを、集合のリストで表現し、使われている数字を集合に入れる。
１から９までの数字の集合があった方が便利そうなので、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()