Pythonでナンプレを解いてみよう

Pythonでナンプレを解いてみよう

今回はPythonでナンプレを解く方法を紹介する。新聞やパズル雑誌でどうしても解けない問題をプログラミングの力で解いてみよう。

ナンプレとは？

『ナンプレ（ナンバープレース）』は、空いているマスに1から9のいずれかの数字を入れるパズルゲームだ。その際、縦と横の各マス、太線で囲まれた3×3のブロック内に同じ数字が重ならないように入れるというルールだ。このゲームは、1980年代から世界中のパズル愛好家の間で遊ばれていた。2005年にイギリスでブームになり、日本でも改めて話題になったという歴史がある。

例えば、以下のような問題がある。左が問題であり、右側が答えだ。各マスごとに縦列と横列を確認してみよう。1から9までの数字が重複なく入っていることが確認できるだろう。

• ナンプレの簡単な問題

Pythonでナンプレを解くには？

プログラミングでナンプレを解こうと思った場合、様々なアルゴリズムが考えられる。今回は、力任せに考え得る組み合わせをすべて試すバックトラッキングという手法を使ってみよう。

左上のマスから右下のマスへと順番に空白マスを調べていって、空白があれば1から9まで順番に数を配置していく。配置する際、縦列と横列で重複があるものは飛ばすことにする。これを何度も繰り返していくことで、答えを導き出すことができる。

もう一度、詳しく箇条書きにして確認しよう。

(1) 左上から右下へと順に空白マスを調べていく
(2) 空白マスがあれば、その時点で配置可能な数字を調べる
(3) 配置可能な数字を仮に配置して、次のマスを調べていく
(4) もし配置がうまくいかなければ(3)に戻る
(5) 最後のマスに到達するまで、(2)以降の処理を繰り返す
(6) 最後に到達したら結果を出力する

ナンプレの問題データを準備しよう

プログラムを作成する前に、ナンプレの問題データを用意しよう。ナンプレでは、9x9のマスのデータを利用する。そこで、Excelなどの表計算ソフトで作成し、CSV形式で出力したものをデータとしよう。

例えば、Excelで以下のようなデータを作成しよう。

• ExcelなどでCSVファイルを作成

これを「data.csv」という名前で保存しよう。ちなみに、ファイルの内容は以下のようになる。

 , ,5, ,3, ,6, ,
8, , ,4, , ,3, ,
4, , , , ,9, ,2,
 , , , , , ,9, ,6
 , , ,1, , , ,8,
7, , , , ,8, , ,
3, , ,5, , ,8, ,
2, ,1, ,7,3, , ,
 ,9, , ,1,2, , ,

ナンプレを解くプログラム

それでは、ナンプレを解くプログラムを紹介しよう。以下がそのプログラムだ。

import csv, copy, pprint
# 問題データをCSVで指定 --- (*1)
QFILE = "data.csv"

# 問題データを読む --- (*2)
data = []
with open(QFILE, "rt") as f:
    for row in csv.reader(f):
        r = []
        for v in row:
            try:
                r.append(int(v.strip()))
            except:
                r.append(0)
        data += [r]
print("--- 問題データ ---")
pprint.pprint(data)

# 空白の部分を再帰的に解く --- (*3)
def set_num(vdata, idx):
    # 終了判定 --- (*4)
    if idx >= 81:
        pprint.pprint(vdata)
        return True
    # 空白があるか調べる --- (*5)
    col = idx % 9
    row = idx // 9
    if vdata[row][col] != 0:
        return set_num(vdata, idx + 1)
    # どの数字が利用可能か調べる --- (*6)
    u = {}
    for i in range(9):
        u[vdata[i][col]] = True
        u[vdata[row][i]] = True
    # 利用可能な数値を順に入れて再帰 --- (*7)
    for n in range(1, 10):
        if n in u: continue
        if not check3x3(vdata, col, row, n): continue
        ndata = copy.deepcopy(vdata) # リストをコピー
        ndata[row][col] = n
        if set_num(ndata, idx + 1): return True
    return False

# 3x3のマスの中も数字が重複しないか確認
def check3x3(vdata, col, row, val):
    c3 = col // 3 * 3
    r3 = row // 3 * 3
    u = {}
    for x in range(0, 3):
        for y in range(0, 3):
            n = vdata[r3 + y][c3 + x]
            u[n] = True
    return not val in u

# 結果表示
print("--- 完成データ ---")
set_num(data, 0)
print("ok")

(※3x3ブロック内での重複機能が未実装であったため修正したあります2019年9月21日)

上記のプログラムを「numplace.py」という名前で保存する。そして、コマンドラインで「python numplace.py」を実行しよう。すると、ナンプレの答えを調べて結果が表示される。

• プログラムを実行したところ

それでは、プログラムを確認してみよう。プログラムの(＊1)の部分ではデータファイル名を指定している。(＊2)の部分では、問題CSVデータを読み込んでいる。データを読み込む時に、文字列データを数値データに変換している。その際、穴埋めすべき空のマスは数値0になるようにした。

そして、(＊3)以降の部分では、再帰的に数値を配置していく関数set_numを定義している。この関数では、(＊4)の部分で終了判定を行う。ナンプレでは9x9で81マスあるので、検索位置idxが81を超えたら再帰処理を終了し答えを表示する。(＊5)の部分では、検索位置idxのマスに空白部分があるかどうかを調べる。もし、空白がなければ、次位置の配置を行うようset_numを再帰的に呼び出す。(＊6)の部分では、利用可能な数字を調べる。(＊7)では利用可能な数字を順番にデータに入れた上で、再帰的にset_numを呼び出す。

プログラムの動きを簡単な図にしてみた。

• 今回のプログラムの動きを図にしてみた

すべての値を満遍なく調べるために、再帰的にset_num関数を呼び出しているのがポイントだ。set_num関数には仮のリスト(vdata)と捜査位置(idx)を指定する。また、仮の値を覚えておくために、試すたびにリストを複製して利用する。

まとめ

以上、今回はPythonを使ってナンプレの答えを見つけるプログラムを作ってみた。今回は、読みやすく短いプログラムを目指したので、処理の最適化などあまりやっていない。そのため、場合によっては、答えを見つけるまでに、かなり長い時間を要する場合もあるだろう。というのも、とにかく総当たりで答えを探すため時間がかかる場合がある。特に空白のマスが増えれば増えるほど、計算量が膨らむので答えを見つけるまでに時間がかかるのだ。もちろん、アルゴリズムを改良することで、より高速にナンプレの答えを見つけることができる。いろいろと工夫してみると楽しいだろう。

自由型プログラマー。くじらはんどにて、プログラミングの楽しさを伝える活動をしている。代表作に、日本語プログラミング言語「なでしこ」 、テキスト音楽「サクラ」など。2001年オンラインソフト大賞入賞、2004年度未踏ユース スーパークリエータ認定、2010年 OSS貢献者章受賞。技術書も多く執筆している。