目次
- ソルバー
- 適切チェック
■ソルバー
事前に計算した辞書により、手がかり数字から可能パターンリストを取得できる。 ので、そのパターンすべての and と or を取ると、黒が確定する位置とバツが確定する位置を得ることができる。
例えば、手がかり数字が14の場合、可能パターンリストは [0b011111111111111, 0b111111111111110] となる。 全要素の and を取ると 0b011111111111110 となり、残った１の部分が黒確定なので、両端以外が黒確定となる。 逆に、全要素の or を取ると 0b111111111111111 となり、残った0の部分がバツ確定なので、バツの確定は無しとなる。
横方向の可能なパターンリストを行ごとに h_candidates 配列で、縦方向は列ごとに v_candidates で保持しておき、 横方向で確定した1または0と矛盾する要素を縦横交互に削除していく。 これを繰り返し、解が求まるか、候補リストが変化しなくなったときに探索を終了する。
ソルバーのコードは下記のようになる。
func doSolve(): # [適切な問題か？, 難易度] を返す
set_crosses_null_line_column() # 手がかり数字0の行・列に全部 ☓ を埋める
init_arrays() # 各種配列を初期化
init_candidates() # 候補配列（可能パターンリスト）を初期化
#print_clues(v_clues)
#print_clues(h_clues)
var nc0 = 0 # 前回の解候補数
var solved = false
var itr = 0 # 難易度
while true:
update_h_fixedbits() # h_candidates[] を元に h_fixed_bits_1, 0 を計算
#print("num candidates = ", num_candidates())
var nc = num_candidates() # 全候補数を計算
if nc == N_IMG_CELL_HORZ + N_IMG_CELL_VERT: # solved
solved = true
break
if nc == nc0: # CAN't be solved
break;
nc0 = nc
hFixed_to_vFixed()
update_v_candidates()
update_v_fixedbits()
vFixed_to_hFixed()
update_h_candidates()
itr += 1
return [solved, itr]
最初に手がかり数字から、各行の可能な解候補を h_candidates に設定し。 それらの and/or を計算することで 1/0 が確定するビットを h_fixed_bits_1, h_fixed_bits_0 に格納する。
これを縦方向（v_fixed_bits_1, v_fixed_bits_0）に変換し、これに矛盾する縦方向解候補を削除する。 同様に縦方向確定ビットを計算し、それを横方向解候補に反映する。
これを、解が求まるか解候補数が変化しなくなるまで繰り返す。
init_arrays() は各種配列の初期化、 num_candidates() は解が求まったかどうかを判定するために行・列の候補数の合計を求める。 それぞれの実装は下記の通り。
func init_arrays(): # 各種配列を初期化
h_candidates.resize(N_IMG_CELL_VERT)
v_candidates.resize(N_IMG_CELL_HORZ)
h_fixed_bits_1.resize(N_IMG_CELL_VERT)
h_fixed_bits_0.resize(N_IMG_CELL_VERT)
v_fixed_bits_1.resize(N_IMG_CELL_HORZ)
v_fixed_bits_0.resize(N_IMG_CELL_HORZ)
func num_candidates(): # 全候補数を計算
var sum = 0
for y in range(N_IMG_CELL_VERT): # 水平方向について
sum += h_candidates[y].size()
for x in range(N_IMG_CELL_HORZ): # 垂直方向について
sum += v_candidates[x].size()
return sum # 全候補数を返す
各行・列の手がかり数字から各行・列の可能な解リストを計算する init_candidates() の実装は下記の通り。
# 手がかり数字から可能な候補パターンを取得し、h_candidates[], v_candidates[] に格納
func init_candidates():
for y in range(N_IMG_CELL_VERT): # 水平方向について
if h_clues[y] == null: # 手がかり数字が無い場合
h_candidates[y] = [0]
else:
h_candidates[y] = g_map[h_clues[y]].duplicate()
for x in range(N_IMG_CELL_HORZ): # 垂直方向について
if v_clues[x] == null: # 手がかり数字が無い場合
v_candidates[x] = [0]
else:
v_candidates[x] = g_map[v_clues[x]].duplicate()
手がかり数字が無い場合は 0 とみなすので [0] を設定し、そうでない場合はあらかじめ計算した g_map を参照する。 このとき、v_candidates[x] = g_map[v_clues[x]] と記述すると、参照渡しのため、 後で候補リストを編集すると辞書の内容が壊れてしまうので、duplicate() を呼んでオブジェクトをコピーしている （ちなみに、筆者は最初この duplicate() を忘れていて、辞書が壊していたのだが、 次にその要素を参照しない限り動作が変にならず、原因究明・対処に1時間近くもの時間を要してしまった orz）。
水平方向で、確定したビット情報の h_fixed_bits_1, h_fixed_bits_0 を考慮して、 不可能な候補を削除する update_h_candidates() の実装は下記の通り。
# h_fixed_bits_1, 0 を元に h_candidates[] から不可能なパターンを削除
func update_h_candidates():
for y in range(N_IMG_CELL_VERT):
for i in range(h_candidates[y].size()-1, -1, -1):
if( (h_candidates[y][i] & h_fixed_bits_1[y]) != h_fixed_bits_1[y] ||
(~h_candidates[y][i] & h_fixed_bits_0[y]) != h_fixed_bits_0[y] ):
h_candidates[y].remove(i)
何行目かを示す y と、ビット位置を i を for 文で回し、1が確定している部分が 1 でないか、 0 が確定している部分が 0 でない候補を削除している。
水平方向に確定したビット情報を垂直方向の確定ビットに変換する hFixed_to_vFixed() の実装は下記の通り。
func hFixed_to_vFixed():
for x in range(N_IMG_CELL_HORZ): # とりあえず 0 に初期化
v_fixed_bits_1[x] = 0
v_fixed_bits_0[x] = 0
var hmask = 1 << N_IMG_CELL_HORZ; # 水平方向マスク
for x in range(N_IMG_CELL_HORZ):
hmask >>= 1
var vmask = 1 << N_IMG_CELL_VERT; # 垂直方向マスク
for y in range(N_IMG_CELL_VERT):
vmask >>= 1
if( (h_fixed_bits_1[y] & hmask) != 0 ):
v_fixed_bits_1[x] |= vmask;
if( (h_fixed_bits_0[y] & hmask) != 0 ):
v_fixed_bits_0[x] |= vmask;
水平・垂直方向マスクをシフトしながら、h_fixed_bits_1, h_fixed_bits_0 の各ビットが立っていれば、 v_fixed_bits_1, v_fixed_bits_0 のビットをセットしている。
update_v_candidates()、vFixed_to_hFixed() は縦横が変わるだけなので、説明は省略する。
■適切チェック
前節まででソルバーができたので、それを使ってユーザが作った問題が解答がひとつだけの適切な問題かどうかをチェックする機能を実装する。
画面右下に「検査」コマンドアイコンを設置し、pressed シグナルを _on_CheckButton_pressed() に接続する。 その実装は下記の通り。
func _on_CheckButton_pressed():
var t = doSolve() # ソルバーコール
var solved = t[0] # 適切な問題か？
var itr = t[1] # 難易度
print(solved)
if solved: # 適切な問題の場合
$MessLabel.add_color_override("font_color", Color.black)
$MessLabel.text = "適切な問題です(難易度: %d)。" % itr
#$MessLabel.text = "Propper Quest (difficulty: %d)" % itr
else: # 不適切な問題の場合
$MessLabel.add_color_override("font_color", Color.red)
$MessLabel.text = "不適切な問題です。"
#$MessLabel.text = "Impropper Quest"
var txt = ""
for y in range(N_IMG_CELL_VERT):
#print(to_binText(h_fixed_bits_1[y]), " ", to_binText(h_fixed_bits_0[y]))
var mask = 1<<(N_IMG_CELL_HORZ-1)
var x = -1
while mask != 0:
x += 1
if (h_fixed_bits_1[y] & mask) != 0:
txt += "#"
elif (h_fixed_bits_0[y] & mask) != 0:
txt += "."
else: # 解が確定していない場合
txt += "?"
$BoardBG/TileMapBG.set_cell(x, y, 0) # 黄色背景強調
mask >>= 1
txt += "\n"
print(txt)
clear_all_crosses();
ソルバーは doSolve() という関数になっているので、それをコールする。 返り値は配列で [0] に適切な問題か、[1] に難易度が格納されている。 それらを参照し、画面に「適切な問題」＋難易度、または「不適切な問題」を表示する。
また、h_fixed_bits_1, h_fixed_bits_0 を参照し、確定していないセルの背景を黄色にし強調する。
以上を実行すると下図のように、確定しない部分が黄色背景で強調される。
TechProjin Godot入門 関連連載リンク
Godotで学ぶゲーム制作
さくさく理解するGodot入門 連載目次
標準C++ライブラリの活用でコーディング力UP!
「競技プログラミング風」標準C++ライブラリ 連載目次
