Developer

さくさく理解する Godot 入門(ただし2Dに限る)応用編 お絵かきパズル【第11回】
2021.12.21
Lv1

さくさく理解する Godot 入門(ただし2Dに限る)応用編 お絵かきパズル【第11回】

目次

  • ヒント機能

■ヒント機能

本アプリの目玉機能のひとつが上図のヒント機能だ。 確定する黒またはバツがどこにあるのかわからず、途中で詰まってしまった場合にヒントアイコンを押すとよい。 他のアプリでは、ヒントと称して答えの一部を示すものもあるが、答えとヒントは似て非なるものだ。 本アプリのヒントは上図の例のように、答えの一部ではなくあくまでもユーザが答えを導き出すための適切なヒントを表示してくれる優れものだ。
にもかかわらず、数10人の人にテストプレイをしていただいたところ、意地でも使おうとしない人が多かった。何故なんでしょうね・・・

ヒント機能の初期の実装では黒またはバツの確定があることだけを表示していたのだが、 それでは分かりづらいのでどの解法を用いることができるのかを判定し、それを表示するようにした。 筆者が知る限り、このように親切なヒント機能は他には無いと思うのだが、どうだろうか?

以下、ヒント機能の実装について説明する。

まずは下記のように、ヒントのタイプ(使用する解法)を宣言しする。

enum {
    HINT_ALL_FIXED = 1,     # 全て入る
    HINT_SIMPLE_BOX,        # 重なったら黒(手がかり数字がひとつだけ)
    HINT_SIMPLE_BOXES,      # 重なったら黒(手がかり数字が複数)
    HINT_X_BOTH_END,        # 確定したら両端にバツ
    HINT_CAN_NOT_REACH,     # 届かない
    HINT_GLUE,              # くっつき
    HINT_BLACK,             # 黒確定あり
    HINT_CROSS,             # バツ確定あり
}

各解法の具体的な説明は ここ を参照。

現在の状態、各行・列の可能な解候補から、ヒント位置・種別を判定する search_hint_line_column() の定義を下記に示す。

func search_hint_line_column() -> Array:    # [line, column, hint], -1 for none
    init_arrays()           # 各作業用配列初期化
    init_candidates()       # 行列解候補配列初期化
    remove_h_candidates_conflicted()        # 現在の状態に矛盾する行列解候補を配列から削除
    update_h_fixedbits()    # h_candidates[] を元に h_fixed_bits_1, 0 を計算
    remove_v_candidates_conflicted()
    update_v_fixedbits()    # v_candidates[] を元に v_fixed_bits_1, 0 を計算
    var y = allFixedLine()      # 全部入れれる行を探す
    if y >= 0:
        return [y, -1, HINT_ALL_FIXED]
    var x = allFixedColumn()    # 全部入れれる列を探す
    if x >= 0:
        return [-1, x, HINT_ALL_FIXED]
    y = simpleBoxLine()   # SimpleBox 確定セルがある行を探す
    if y >= 0:
        return [y, -1, HINT_SIMPLE_BOX]
    x = simpleBoxColumn()   # SimpleBox 確定セルがある列を探す
    if x >= 0:
        return [-1, x, HINT_SIMPLE_BOX]
    .....
    y = fixedLine()   # 確定セルがある行を探す
    if y >= 0:
        return [y, -1, 0]
    x = fixedColumn()   # 確定セルがある列を探す
    return [-1, x, 0]

最初に各種配列を初期化(init_arrays() の実装はソルバーの章を参照)。 ついで、各行・列の可能な解のリストを h_candidates, v_candidates に格納し、 remove_h_candidates_conflicted(), remove_v_candidates_conflicted() で現在の入力状態に矛盾するものを取り除き、 update_h_fixedbits(), update_v_fixedbits() を呼んで、 各行・列で黒またはバツが確定している部分を h_fixed_bits_1, h_fixed_bits_0 に格納する。

update_h_fixedbits() の実装を下記に示す。

const BITS_MASK = (1<<N_IMG_CELL_HORZ) - 1
# h_candidates[] を元に h_fixed_bits_1, 0 を計算
func update_h_fixedbits():
    for y in range(N_IMG_CELL_VERT):
        var lst = h_candidates[y]
        if lst.size() == 1:		# 解候補がひとつだけの場合
            h_fixed_bits_1[y] = lst[0]
            h_fixed_bits_0[y] = ~lst[0] & BITS_MASK
        else:		# 解候補が複数ある場合は、それぞれの論理和をとり、黒またはバツが確定する部分を得る
            var bits1 = BITS_MASK
            var bits0 = BITS_MASK
            for i in range(lst.size()):
                bits1 &= lst[i]
                bits0 &= ~lst[i]
            h_fixed_bits_1[y] = bits1
            h_fixed_bits_0[y] = bits0

y を for ループで回し、h_candidates[y] から、h_fixed_bits_1[y], h_fixed_bits_0[y] を計算する。 解候補がひとつだけの場合は、その候補が解となるので、1・0のビットを、 解候補が複数ある場合は、1・0のビットの全体の論理和を計算し、 h_fixed_bits_1[y], h_fixed_bits_0[y] の値とする。

以上で準備が出来たので、次に各ヒント種別ごとに、条件が成立しているかどうかをチェックする。 チェック処理はそれぞれ関数化されている。 allFixedLine(), allFixedColumn() は、盤面サイズが15×15で手がかり数字が 15 や 10, 4 の場合などのように、行・列の解が一意に決まっている場合を検出する。 その定義は下記の通り。

func allFixedLine():    # 全部入れれる行を探す
    for y in range(N_IMG_CELL_VERT):
        if h_clues[y].empty():      # 手がかりなし → 0 → 全部バツ、ほんとはありえないけど一応チェック
            return y
        if h_candidates[y].size() == 1 && get_h_data(y) != h_candidates[y][0]:
            return y;
    return -1

各行について、候補リストの要素が一つだけで、現在の状態がそれとは異なる場合は、その行のセルが全部確定なので、 その行インデックスを値として返す。候補リストの要素が一つだけというのは、行・列の解が一意に決まっているということだ。 また、それが現在の状態と一致していればそれ以上黒を入れる必要はないので、ヒントの対象とはならない。

下記は is_simple_box() の実装だ。

func is_simple_box(clues, data) -> bool:
    if clues.size() != 1 || clues[0] < 8:	# simple で無い or 単純な重なりが無い
        return false;
    var ln = (clues[0] - 8) * 2 + 1
    var bits = ((1<<ln) - 1) << (15 - clues[0])
    return (data & bits) != bits	# 重なり部分に黒でない箇所があるか?
func simpleBoxLine():
    for y in range(N_IMG_CELL_VERT):
        if is_simple_box(h_clues[y], get_h_data(y)):
            return y
    return - 1

「simple box」とは単純な重なりのことで、15×15 であれば手がかり数字が8以上であれば中央が黒に確定することを言う。 最初に単純な重なりがあるかどうかをチェックし、さらにその部分にまだ入っていない黒があるかどうかをチェックしている。
simpleBoxLine() は is_simple_box() を呼んでいるだけだ。また、 simpleBoxColumn() も定義しているが、同様なので説明は省略する。

ヒントのタイプはさらにいくつかあるのだが、説明が長くなるので、最後に fixedLine() だけを説明しておく。 省略したものについては github 上のソースコードを読んでいただきたい。

fixedLine() は黒またはバツが確定する行のインデックスを返す関数で、下記のように実装できる。

func fixedLine():   # 確定セルがある行を探す
    for y in range(N_IMG_CELL_VERT):
        var d = get_h_data(y)   # 現状、黒が入っている箇所のビットパターン取得
        if (d & h_fixed_bits_1[y]) != h_fixed_bits_1[y]:    # 確定ビットと異なる場合
            return y;
        var d0 = get_h_data0(y) # 現状、バツが入っている箇所のビットパターン取得
        if (d0 & h_fixed_bits_0[y]) != h_fixed_bits_0[y]:   # 確定ビットと異なる場合
            return y;
    return -1

各行について、現状の入力されている黒のビットパターンを取得し、それと確定ビットパターンとの論理和をとったものと、 確定ビットパターンを比較し、不一致であれば黒が確定するセルが存在することになるので、その行のインデックスを返す。 バツについても同様の処理を行う。

以上で準備が整った。ヒントボタンが押された場合のハンドラ _on_HintButton_pressed() は下記のように実装できる。

enum {
    HINT_IX_LINE = 0,       # 行にヒントがある場合、-1 for ヒント無し
    HINT_IX_COLUMN,         # 列にヒントがある場合、-1 for ヒント無し
    HINT_IX_TYPE,           # ヒントタイプ
}
func _on_HintButton_pressed():
    var lc = search_hint_line_column()      # ヒントを表示する行・列インデックスと種別を取得
    var y = lc[HINT_IX_LINE]
    if y >= 0:
        if lc[HINT_IX_TYPE] == HINT_ALL_FIXED:
            help_text = "%d行目が全て確定します。" % (y+1)
        elif lc[HINT_IX_TYPE] == HINT_SIMPLE_BOX:
            help_text = "%d行目に「重なったら黒」があります。" % (y+1)
        .....
        $MessLabel.add_color_override("font_color", Color.black)
        $MessLabel.text = help_text
        for x in range(N_IMG_CELL_HORZ):
            $BoardBG/TileMapBG.set_cell(x, y, TILE_BG_YELLOW)   # 当該行を黄色背景強調

最初に search_hint_line_column() をコールし、ヒントを出せる行または列があるかどうかをチェックし、 あれはその情報をもとにヒントテキストを生成し、最後にラベルに表示している。

このように、ユーザにとって親切な機能の実装は、条件分岐が多くダラダラとしたコードになりがちだが、 仕方がないものなのではないかと考えている。