🤖

キラーナンプレRTAチャレンジ

2024/03/12に公開

Streamlit

はじめに

みなさんは"キラーナンプレ"というゲームをご存知でしょうか？これは、通常のナンプレにひねりを加えたとても難しいゲームです^[1]。

難しいと言われると解きたくなるのが人の性、会社の同期の間でキラーナンプレのRTAがにわかに流行っていました^[2]。例に漏れず私も挑戦していたのですが、RTAどころか解くこともままならない状況でした。悔しい。

そこで、同期のはだくん、いいだくんに協力してもらい、キラーナンプレを自動で解くwebアプリケーションの開発に取り組みました。

本記事ではその取り組みを紹介したいと思います。
なお本記事は私ぐんじに加え、はだくん、いいだくんの3人で執筆しており、各々の担当箇所は次の通りです。

ぐんじ: はじめに〜定式化
はだくん: 入力画像の識別/各マスの連結成分
いいだくん: 入力画像の識別/光学文字認識（OCR）による左上認識

キラーナンプレとは

キラーナンプレを説明する前に、その元ネタである"ナンプレ"（別名：数独）についておさらいしておきます。

ナンプレとは、9×9のマス目（ボードと呼ぶ）を考え、そのマスを次のルールに従って1から9までの整数で埋めるゲームです。

ボード内のいくつかのマスにはゲームの開始時点で既に数字が入っており、その数字と上記のルールを手がかりにボード内全てのマスに数字を埋めていきます。(Fig.1参照)

Figure.1 ナンプレの問題例。画像は https://sudoku.com/jp より抜粋後一部加工。

一方、キラーナンプレでは、従来のナンプレのルールに加えて新たに"ケージ"についてのルールが導入されます。（参考: https://sudoku.com/killer ）

ケージとは、ボード内で点線で囲まれた数マスからなる領域です。
ゲーム開始時点で、各ケージの左上隅にはそれぞれ数字が与えられており、次のルールに従いながら数字を埋めます。

これがキラーナンプレです。特にマスの初期値が一つも与えられない問題は難易度が非常に高いです。そこで、今回は初期値なしの高難易度版に挑みます^[3]。

Figure.2 キラーナンプレの問題例。画像は https://sudoku.com/jp より抜粋後一部加工。

定式化

今回キラーナンプレを解くあたって数理最適化によるアプローチを試みました。
定式化には次の記事を参考にさせていただきました。

どうやら、ルールを制約条件とした整数計画で定式化することで解けそうです。ということで次のように定式化しました。

目的関数
今回は最小化・最大化する問題ではないため、目的関数は定数項 $0$ とします。

制約条件

制約条件を定式化するにあたって、記号を次のように定義します。

マスに入りうる数字の集合: $N=\{1,2,\dots,9\}$
マスのx座標の集合: $X=\{1,2,\dots,9\}$
マスのy座標の集合: $Y=\{1,2,\dots,9\}$
ボックス番号の集合: $B=\{1,2,\dots,9\}$
初期値を持つマスの座標と初期値のタプル $(x,y,n)$ の集合: $S_0$
ボックス $b\in B$ に含まれるマスの座標の集合: $V_b$
ケージ番号の集合: $C=\{1,2,\dots\}$
ケージ $c\in C$ に含まれるマスの座標の集合: $V_c$

加えて、解を表現するためにバイナリ変数 $a_{xyn}=\{0,1\}$ を導入します。ここで、 $x, y$ $(x\in X, y\in Y)$ はマスの座標添字、 $n\in N$ はマスに入りうる数字の添字です。(Fig.3参照)
座標 $(x,y)$ のマスに数字 $n$ がある場合には $a_{xyn}=1$ であり、それ以外は0の値をとります。
このバイナリ変数を用いて、キラーナンプレのルールを次のような制約式で表しました。

マスの初期値 $(x,y,n)\in S$ に対応する変数 $a_{xyn}$ の値
$a_{xyn} = 1 \quad ((x,y,n)\in S_0)$
一つのマスに一つの数字が入る
$\sum_{n\in N} a_{xyn} = 1 \quad ( x\in X,~y\in Y )$
横のマスに入る数字が重複しない
$\sum_{x\in X} a_{xyn} = 1 \quad (y\in Y,~n\in N)$
縦のマスに入る数字が重複しない
$\sum_{y\in Y} a_{xyn} = 1 \quad (x\in X,~n\in N)$
ブロックに入る数字が重複しない
$\sum_{(x,y)\in V_b} a_{xyn} = 1 \quad (b\in B,~n\in N)$
ケージ内の数字合計がケージに与えられた数字に等しい
$\sum_{(x, y)\in V_c}\sum_{n\in N} a_{xyn}\cdot n = n_c \quad (c\in C)$
ただし、 $n_c$ はケージ $c\in C$ に与えられた数字を表す。

Figure.3 座標の取り方。画像は https://sudoku.com/jp より抜粋後一部加工。

ここまでで定式化が終わりました。あとはpython等で実装して実際の問題に対して解を求めれば良い訳です。
そこで、今回はPuLPを用いて実装し、いくつかのナンプレ問題に対して無事解を求められることを確認しました。(最終的なコードは Bitbucketリポジトリを参照。)

しかし、ここで致命的な課題が判明しました。実は、ナンプレの盤面情報（マスの初期値やケージの条件）を手で入力する作業に非常に時間がかかってしまっていたのです。
実際、盤面を手入力する時間する時間が自力で問題を解く時間とコンパラになっていました。これではせっかく解を求めても、キラーナンプレRTAで負けてしまいます。

そこで、同期のはだくんといいだくんに協力してもらい、盤面情報の入力を容易にし、サクッと解を求めてくれるキラーナンプレソルバーアプリケーションの作成に取り組みました。

入力画像の識別

入力画像からソルバーに渡すための盤面情報を取得するには以下の二つの情報が必要です

9x9の各マスがどのように連結しているかを求める (グラフの隣接リストを求める)
各連結成分における左上の数字を求める

各マスの連結成分の判定

まず各マスがどのように接続しているのかの情報を取得する方法について説明します。
最初に前処理として2000x2000の一枚の画像を9x9=81枚の216x216のそれぞれのマスの画像にします。(両端など余計な部分を切りとる)
ここで、あるマスの上下左右の4近傍との接続情報は、そのマスの点線が途切れている方向を判定するば良いということが分かります。
(下の画像の例なら点線が途切れているのは右と下)

ここでどのようにマスが途切れているかの情報を取得するかを考える必要があります。
色々方法は考えられるかと思いますが、今回はOpenCvのパターンマッチを使用して判定を行います。
まず、あらかじめマスの線の途切れ方としてあり得る全てのパターンを用意します。
今回の場合だと上下左右に点線が存在する、しないの2^4=16通りのパターンを用意すれば良いです。
特に今回は、後で使う用にそれぞれのパターンに対して4桁の数字で名前をつけます。

命名規則

穴が空いていれば1、そうでないなら0として

左上右下.png

の形で画像のテンプレートを表す

0000.png

0001.png

1100.png

このような要領で以下のようなテンプレートフォルダを作成しておきます

ここまで用意すればあとは左上のマスから順番に連結成分の探索を行います。
改めてソルバーの入力として

[(8,[(0,0),(0,1),(0,2)]), (16,[...])] #[(ケージの総和, [(y1,x1), (y2,x2),...# 各ケージの座標]), (...), ...]

のような連結成分の情報を取得したい状況です。
深さ優先、幅優先どちらでも良いですが、今回はスタックを用いた深さ優先探索を実装します

連結成分の判定

def make_optimize_input_data(img:np.ndarray):
    imgs = split_img(img)
    cell_templates = load_cell_templates()

    seen = [[False]*9 for _ in range(9)]
    dy = [1, 0, -1, 0]
    dx = [0, -1, 0, 1]
    cages = []
    for i in range(9):
        for j in range(9):
            if seen[i][j] == True: # 訪問済みならば見ない
                continue
            else:
                ret = [(i,j)]
                stack = [(i,j)] # 探索用のスタックを用意
                num = read_digit(imgs[i][j]) # 左上のマスに対しては数字の読み取りを行う(後で説明)
                while(stack):
                    y,x = stack.pop()
                    seen[y][x] = True # 訪問済みにする
                    
                    # 左上右下どちらに穴が空いているかを判定する
                    # 0110_(2) = 6みたいな感じで値が返る(0〜15の値)
                    cell_type = judge_cell_type(imgs[y][x]) 

                    for k in range(4):
                        if cell_type & (1<<k):
                            ny = y + dy[k]
                            nx = x + dx[k]
                            if seen[ny][nx] == True:
                                continue
                            # 重複を許さない
                            if (ny,nx) not in ret:
                                ret.append((ny,nx))
                            stack.append((ny,nx))

                cages.append((num, ret))
    
    return OptimizeInputData(cages = cages)

細かい工夫としてどの方向に穴が空いているかを判定するjudge_cell_type()関数の中ではちょっとした点線のブレを補正するために、切り取った画像とテンプレート画像をそれぞれガウシアンフィルターをかけて粗くさせた画像でパターンマッチングを行うというテクニックを行なっています

ぼかし処理を入れたテンプレート

光学文字認識（OCR）による左上認識

続いて各連結成分の左上に書いてある数字の読み取り方法について説明します。

大まかなフロー図は以下です。

各番号での詳細は後述します。

①.数値領域の抽出

左上の数値領域のみを抽出する。
数値領域は毎回ほとんど同じ位置に1桁もしくは2桁の数値で現れるため、2桁の領域分をピクセルで指定し、クロップしました。

②.桁数の判定および各桁での数値領域の抽出

今回は、2桁の数値はOCRでは認識できない状況（後述）だったため、2桁の数値を10の位と1の位で領域を分割する必要がありました。
また画像をよく見ると、1桁の数値は10の位の位置に現れていたので、1の位に該当する領域に数値があるか否かを判定できれば、数値の桁数判定はできそうだと考えました💡
具体的には、画像全体を大津法で2値化し、1の位の領域に数値と同じ画素値のピクセルが10%以上存在する場合は2桁の数値、10%未満の場合は1桁の数値として判定しました。

③.OCRにて各桁の数値認識

各桁の画像に対して、pyOCRを用いてOCR数値認識を行いました。

OCRの設定は以下で行いました。

tools = pyocr.get_available_tools()
tool = tools[0]
# 画像中には単一のテキストブロックが存在する設定
builder = pyocr.builders.DigitBuilder(tesseract_layout=6)
# 文字の候補リストはの数値のみ（0-9）
builder.tesseract_configs.append('tessedit_char_whitelist=0123456789')

④.各桁の画像データから数値を予測するモデルを構築

OCRだけではうまくいかなかったので、最終手段としてゴリゴリに過学習させた機械学習モデルを用いて数値検出する力技を用いました。
具体的な方法は以下です。

20枚の盤面画像から数値領域、さらに各桁ごとの画像を用意し、OCRにて教師ラベルを付与する
画像を1次元配列に変換し、SVMにて学習

Webアプリケーションの作成

上までの説明で画像をダウンロードしてmain.pyを実行すれば勝手に解いてくれるという従来の入力が面倒という課題は解決されたものの、毎回pythonを実行するの面倒です。
そこで画像ファイルをアップロードしたら勝手に解いてくれるwebアプリも作成しました。

Streamlitによるアプリ化

画像のアップロードと求解した結果をテーブルで返すだけのシンプルなアプリなので記述するコードはこれだけです
(インポート文を除けば10行だけで終わります、便利ですね…)

キラーナンプレソルバーアプリ

import streamlit as st
import numpy as np
from utils import *
from PIL import Image
from scripts import run_optimize


st.title('キラーナンプレソルバー')

st.write('https://sudoku.com/jp/killer/ekisupato/')
st.write("画像をアップロードしてくだいさい")
uploaded_file = st.file_uploader('Choose a image file')

if uploaded_file is not None:
    uploaded_img = np.array(Image.open(uploaded_file).convert('RGB'))    
    st.image(uploaded_img)

    with st.spinner(text="In progress..."):
        optimize_input_data, optimzie_output_data = run_optimize.main(uploaded_img)
        st.table(optimzie_output_data.optimal_board)

Streamlitで作成した簡易webアプリ

おわりに

キラーナンプレを題材として整数計画問題の定式化、入力データ作成のための画像処理、さらに簡易的な最適化アプリケーションの作成を行いました。
現状のアプリの欠点としてOCRパートで一つでも誤判定があると最適化が失敗してしまう点が挙げられます。
実際アプリケーションを使ってみても20%くらいで左上の数字の読み取りミスが原因でエラーを吐き出してしまいます。
この問題の解決策としては、画像判別モデルの予測確率や整数計画の既約不整合部分系情報を情報をもとにして入力データに誤りがあった場合は人手で修正できるUIの実装することなどが考えられそうです。

脚注

難易度は個人の主観です。 ↩︎
諸説あります。 ↩︎
なお、今回作成したアプリは初期値がある場合のキラーナンプレにも対応しています。 ↩︎

GitHubで編集を提案