Pythonで数独を解く

#はじめに
hello😇初めてのアドベントカレンダーですがいつも通り書いていきます。今回はpythonで数独を解いていこうと思います。
※コードはこちらに挙げておくので主要なコードのみ説明します。

#数独のルール

1. あいているマスには1から9までの数字が必ず1つ入る。

• 縦9マスに1から9までの数字が1つずつ入る。(重複はしない)
• 横9マスに1から9までの数字が1つずつ入る。(重複はしない)
• 太線で囲まれた3×3のブロックのどれにも1から9までの数字が1つずつ入る。(重複はしない)

(例)

#実装

今回は最適化問題でよく使われるmypulpモジュールを使います。データはエクセルに格納しopenpyxlを使い扱います。必要なモジュールはrequirements.txtに格納しておいたので下記コードをコマンドラインで実行してください。

pip install -r requirements.txt

データ作成

まず数独のデータを保管するリストを用意します。

N = [i for i in range(1,10)]    #行番号，列番号，数
C = [(3*i+2, 3*j+2) for i in range(3) for j in range(3)]   #ブロックの中心位置の集合
D = [(i-1, j-1) for i in range(3) for j in range(3)]       #周囲8マス＋そのマスの相対的な位置の集合

そしてエクセルからヒントの数を読み込みます。

n = {}
for i in N:
    for j in N:
        n[i, j] = sheet.cell(row=i+1, column=j+3).value

制約条件

制約条件は主に四つ挙げられます。
① 何かしらの数字が入る(ヒントの数字含む)

for i in N:
    for j in N:
        if type(n[i, j]) is int and 1 <= n[i, j] <= 9:
            model.addConstr(x[i,j,n[i, j]]==1)#ヒントの数字
        else:
            model.addConstr(quicksum(x[i,j,k] for k in N)==1)#それ以外

② 行に各数字が1つずつ入る

for i in N:
    for k in N:
        model.addConstr(quicksum(x[i,j,k] for j in N)==1)

③ 列に各数字が1つずつ入る

for j in N:
    for k in N:
        model.addConstr(quicksum(x[i,j,k] for i in N)==1)

④ ブロックに各数字が1つずつ入る

for (ci, cj) in C:
    for k in N:
        model.addConstr(quicksum(x[ci+di, cj+dj, k] for (di, dj) in D)==1)

目的変数

通常最適化問題では何らかの数値を最大、最小にすることが多いですが今回は特にありません。

実行

今回はsudoku_ans.xlsxという別のファイルに書き込むようになっています。

model.optimize()
# 出力
if model.Status == GRB.Status.OPTIMAL:
    print('解が見つかりました。')
    for i in N:
        for j in N:
            for k in N:
                if x[i, j, k].X > 0.01:
                    font = copy(sheet.cell(row=i+1, column=j+13).font)
                    if type(n[i, j]) is int:
                        font.color = styles.colors.Color(rgb='ffff0000')     #ヒントの数
                    else:
                        font.color = styles.colors.Color(rgb='ff000000')   #求めた数
                    sheet.cell(row=i+1, column=j+13).font = font
                    sheet.cell(row=i+1, column=j+13).value = k                    
    book.save('sudoku_ans.xlsx')
else:
    print('解が見つかりませんでした。')

最後にsudoku_ans.xlsxを確認ししっかり数が入っていれば成功です。

まとめ

今回は数独を解きましたが、数学パズルゲーム全般解けるのでいろいろ試してみたいですね。それでは😇