TIM Labs

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

| コメント(0) | トラックバック(0)
盤面をクラスとして書く部分を今日は紹介する。
 クラス名はわかりやすく、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()

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/546

コメントする

このブログ記事について

このページは、fujiが2017年1月 4日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「謹賀新年:人工知能でナンプレ問題集をつくる」です。

次のブログ記事は「Python正月特集:ナンプレを解く (3)Solver編」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。