目次
- 使いきった手がかり数字強調
- 間違った手がかり数字強調
- クリア判定
■使いきった手がかり数字強調
本アプリは、下図の様に使い切った手がかり数字の背景をグレイにすることで強調する。 どの手がかり数字を使い切ったかがすぐにわかり、とても便利だ。
どれが使い切った手がかり数字なのかは自明ではないので、その判定を行う必要がある。 usedup_clues() でどの数字を使い切ったかの判定を行っている。
func usedup_clues(lst : Array, # 可能な候補リスト
data : int, # ユーザ入力状態（黒のビットパターン）
nc : int): # nc: 手がかり数字数
var uu = [] # 各要素：手がかり数字を使い切ったか？
uu.resize(nc)
for i in range(nc): uu[i] = false # false で初期化
var ds = to_sliced(data) # ユーザ入力状態を連続する黒ビット塊に分ける
for k in range(ds.size()): # ユーザ入力の各ビット塊について
var pos = -1 # ビット塊が対応する位置、-1 for 対応位置無し
for i in range(lst.size()): # 各候補について
var cs = to_sliced(lst[i]) # 候補を連続する黒ビット塊に分ける
var ix = cs.find(ds[k]) # ユーザ入力のk番目の塊を検索
if ix < 0: # not found
pos = -1 # 対応する候補が無い
break
if pos < 0: # 対応位置無しが無い場合
pos = ix # 対応位置保存
elif ix != pos: # 対応位置が複数ある場合は
pos = -1 # 対応位置無しに
break
if pos >= 0: # 対応位置が一意に存在する場合
uu[pos] = true # pos 番目の手がかり数字を使い切った
return uu
まずは、ユーザが入力した黒のビットパターンを連続する黒の塊に分けた配列にする。例えば、「黒黒・・黒・」であれば、 2進数表記は 0b110010 なので、[0b11000, 0b000010] となる。
次に、可能なすべての解のビットパターンも同様に分解し、それぞれを検索することで対応を探す。 対応するものが一つだけの場合は、その手がかり数字が使い切られていると判断するわけだ。
例えば、手がかり数字が「3, 1」であれば、2番めの手がかり数字1は 0b000010 とだけマッチするので、 それを使い切った、ということになる。
to_sliced(data) の実装を下記に示す。
func to_sliced(data): # dataをビット塊に分ける
if data == 0: # 黒が無い場合
return [0]
var ar = [] # 1が連続するビット列の配列
while data != 0:
var b = data & -data # 値が１の最右ビット
var t = b # 1が連続するビット列
data ^= b
b <<= 1
while (data & b) != 0: # 値1が続いている間ループ
data ^= b # data の b ビットを0に
t |= b # b を t に追加
b <<= 1 # ひとつ上のビットに移動
ar.push_back(t) # 1が連続するビット列を ar に追加
return ar
連続する１のビットを探し、それを順に配列に格納している。
「data & -data」というのは、値が１の最右ビットを最高速で取り出すビット演算のテクニックだ。 ちょっと高度で理解が難しいかもしれないが、よく使うテクニックなのでぜひマスターしておいてほしい。
使い切った手がかり数字のグレイアウトは、check_h_clues(y0), check_v_clues(x0) にて行う。
func check_h_clues(y0 : int): # 水平方向チェック
.....
# 部分確定判定
# lst: 可能なビットパターンリスト（配列）
# ユーザ入力パターン（d1）を連続1ごとにスライスし、それと lst[] の各要素とを比較し、
# 全要素と一致していれば、その部分がマッチしている（はず）
var uu = usedup_clues(lst, d1, h_clues[y0].size()) # 使い切った手がかり数字部分検出
for x in range(h_clues[y0].size()): # 各手がかり数字文字について
# 使い切っている場合は、背景をグレイにする
$BoardBG/TileMapBG.set_cell(-x-1, y0, (TILE_BG_GRAY if uu[x] else TILE_NONE))
check_v_clues(x0) についても同様の処理を行う。
■間違った手がかり数字強調
ユーザが入れた黒またはバツが明らかに間違っている場合、下図のようにその部分の手がかり数字背景が黄色で強調される。
入力された黒やバツが手がかり数字と矛盾しているかどうかは check_h_conflicted(y0), check_v_conflicted(x0) で行う。
アルゴリズムは単純で、行・列の入力された黒バツのビットパターンを取得し、それと矛盾する可能なパターンリストを削除し、 可能なパターンが残っていない場合は解が無いということなので、その行・列を黄色背景で強調する、とう流れだ。
func check_h_conflicted(y0):
var d1 = get_h_data(y0) # y0行の黒部分のビットパターン取得
var d0 = get_h_data0(y0) # y0行のバツ部分のビットパターン取得
var lst = g_map[h_clues[y0]].duplicate() # 可能なパターンリスト取得
remove_conflicted(d1, d0, lst) # 入力されたパターンに矛盾するものを削除
if lst.empty(): # 可能なパターンが残っていない場合
for x in range(h_clues[y0].size()):
$BoardBG/TileMapBG.set_cell(-x-1, y0, TILE_BG_YELLOW) # 背景を黄色に
else:
for x in range(h_clues[y0].size()):
if $BoardBG/TileMapBG.get_cell(-x-1, y0) != TILE_BG_GRAY:
$BoardBG/TileMapBG.set_cell(-x-1, y0, TILE_NONE) # グレイでなければ透明に
remove_conflicted() の実装を下記に示す。
func remove_conflicted(d1, d0, lst): # d1, d0 と矛盾する要素を削除
for i in range(lst.size()-1, -1, -1):
if (lst[i] & d1) != d1 || (~lst[i] & d0) != d0:
lst.remove(i)
d1 は黒であるべき、d0 はバツであるべきビットパターンを表す。なので、各候補のそのビットを調べ、 矛盾する場合は候補リストから削除している。
■クリア判定
ユーザが絵を完成させ、問題をクリアしたかどうかを判定するために、h_usedup, v_usedup という配列を用意する。 これは、横方向・縦方向の各行・列の手がかり数字をすべて使い切り、なおかつエラーが無いときに要素が true となるものだ。
宣言・初期化は以下のように行われる。
var h_usedup = [] # 水平方向手がかり数字を使い切った＆エラー無し
var v_usedup = [] # 垂直方向手がかり数字を使い切った＆エラー無し
.....
func _ready():
.....
h_usedup.resize(N_IMG_CELL_VERT)
v_usedup.resize(N_IMG_CELL_HORZ)
for y in N_IMG_CELL_VERT:
h_usedup[y] = false
v_clues.resize(N_IMG_CELL_HORZ)
for x in N_IMG_CELL_HORZ:
v_usedup[x] = false
ユーザが盤面に黒またはバツを入れたとき check_h_clues(y0) が呼ばれるので、そこで h_usedup[y0] を更新する。 まずば
func check_h_clues(y0 : int): # 水平方向チェック
var d1 = get_h_data(y0)
var d0 = get_h_data0(y0)
var lst = g_map[h_clues[y0]].duplicate() # 可能な解候補取得
remove_conflicted(d1, d0, lst) # 現在の状態に矛盾する候補を削除
if !lst.empty(): # 候補が残っている場合
if lst.has(d1): # d1 が正解に含まれる場合
h_usedup[y0] = true # y0 行は手がかり数字を使い切った＆エラーが無い
....
以上で準備が出来たので、問題をクリアしたかどうかを判定する is_solved() は以下のように実装できる。
func is_solved():
for y in range(N_IMG_CELL_VERT):
if !h_usedup[y]: # 使っていない手がかり数字が残っている、またはエラーがある
return false;
for x in range(N_IMG_CELL_HORZ):
if !v_usedup[x]: # 使っていない手がかり数字が残っている、またはエラーがある
return false;
return true; # 全行・レスの手がかり数字が使い切られており、なおかつエラーもない
すべての行・列を調べ、全部の手がかり数字が使い切られていて、なおかつエラーがなければクリアというわけだ。
TechProjin Godot入門 関連連載リンク
Godotで学ぶゲーム制作
さくさく理解するGodot入門 連載目次
標準C++ライブラリの活用でコーディング力UP!
「競技プログラミング風」標準C++ライブラリ 連載目次
