目次
- ロジカルに解けるかのチェック(前半)
ロジカルに解けるかのチェック(前半)
前章で示したユニーク解チェックを行えば、解をひとつだけ持つ適切な問題を生成できるのだが、 仮定法を使わないと解けない問題になる場合がある。
仮定法とは、ロジカルに数字を入れることが出来ず、仮に数字を入れ、それがあとで矛盾すると、仮に入れた数字が間違いとするものだ。
実は、筆者が最初に作成したナンプレアプリでは、ユニーク解チェックしかしておらず、空欄数で難易度を決めていた。
なので、ロジカルに解けない問題を生成する場合があり、数独愛好家からクレームが入ったことがあった。
問題がロジカルに解けるかどうかをチェックするには、 与えられた問題を人間が使用する解法だけで解けるかどうかを調べるとよい。
解法は多数あり、簡単なものから適用するのがかなり難しいものがある。 本アプリでは、候補数字を使わなくても適用できる初級解法のみを使用するものとする。
初級解法には以下のものがある。
- フルハウス
- 隠れたシングル
- 裸のシングル
これらの説明は後で簡単に行うが、詳しい説明や例を見たい場合は wikipedia などを参照されたい。
「フルハウス」とは、縦・横・3×3ブロック内に数字が8個入っていて、空欄が1個だけの場合を指す。 当然なから、空欄にはまだ入ってない数字が入ることになる。
以下にフルハウスを検索するコードを示す。
func search_fullhouse() -> Array: # [] for not found, [pos, bit, type], type: HORZ | VERT | BOX
var pos
# 横方向のフルハウス探索
for y in range(N_VERT):
var t = ALL_BITS # 空欄ビット
for x in range(N_HORZ):
if cell_bit[xyToIX(x, y)] == 0: # 空欄箇所の場合
pos = xyToIX(x, y) # その場所を覚えておく
else: # 非空欄の場合
t &= ~cell_bit[xyToIX(x, y)] # その数字の空欄ビットをOFFに
if t != 0 && (t & -t) == t: # 1ビットだけ → フルハウス
return [pos, t, HORZ]
# 縦方向フルハウス探索
for x in range(N_HORZ):
.....
# 3x3 ブロックフルハウス探索
for y0 in range(0, N_VERT, 3):
for x0 in range(0, N_HORZ, 3):
var t = ALL_BITS
for v in range(3):
for h in range(3):
if cell_bit[xyToIX(x0+h, y0+v)] == 0:
pos = xyToIX(x0+h, y0+v)
else:
t &= ~cell_bit[xyToIX(x0+h, y0+v)]
if t != 0 && (t & -t) == t: # 1ビットだけ → フルハウス
return [pos, t, BOX]
return []
各縦・横・3×3ブロックにおいて、空欄が1個だけかどうかをチェックしている。
その判定を高速化するため、いつものようにビット演算を使用している。
変数 t の全数字ビットを1にしておき、各セルの数字のビットを0にしていく。 9箇所の処理を行ったあとに、1になっているビットが１箇所だけであればフルハウスということになる。
(t & -t) という演算は非常によく使う処理で、t においてビットの値が1で最も右にあるものだけを取り出す演算だ。 それと t が等しければ、立っているビットがそれだけということになる。 これは知らないと思いつくことは非常に難しいし、説明されても理解が難しいとは思うが、 ビット演算による高速化の基本なので、是非マスターしてほしい。
なお、search_fullhouse() は、フルハウスを発見した場合は [位置, 入る数字ビット] 配列を、 発見できなかった場合は空配列 [] を値として返す。
「裸のシングル」とは、空欄に入る可能性のある数字が１個だけの場合を指す。 つまり、空欄の候補数字がひとつだけということだ。
以下に裸のシングルを検索するコードを示す。
var candidates_bit = [] # 候補数字格納用配列
func search_nakid_single() -> Array: # [] for not found, [pos, bit]
for ix in range(N_CELLS):
var b = candidates_bit[ix]
if b != 0 && (b & -b) == b:
return [ix, b]
return []
裸のシングルのコードは非常に単純だ。 各セルの候補数字を調べ、数字がひとつだけ、つまり立っているビットが１個だけかどうかをチェックするとよい。 その方法は、何度も出てくる便利なビット演算 (b & -b) を使用する。これと b を比較し、 一致していれば立っているビットがひとつだけだということだ。
なお、candidates_bit[ix] には ix 位置の候補数字が数字ビット列として格納されている。
これを計算する init_candidates() 関数のコードは以下の通りで、search_nakid_single() がコールされる前に呼ばれているものとする
func init_candidates(): # cell_bit から各セルの候補数字計算
for i in range(N_CELLS):
candidates_bit[i] = ALL_BITS if cell_bit[i] == 0 else 0
for y in range(N_VERT):
for x in range(N_HORZ):
var b = cell_bit[xyToIX(x, y)]
if b != 0: # セルに数字が入っている場合
for t in range(N_HORZ):
candidates_bit[xyToIX(t, y)] &= ~b # 候補数字の当該ビットを0に
candidates_bit[xyToIX(x, t)] &= ~b
var x0 = x - x % 3 # 3x3ブロック左上位置
var y0 = y - y % 3
for v in range(3):
for h in range(3):
candidates_bit[xyToIX(x0 + h, y0 + v)] &= ~b
「隠れたシングル」とは縦・横・3×3ブロックにある数字が入る箇所が１箇所しかない場合を指す。
以下に隠れたシングルを探すコードを示す。
func search_hidden_single() -> Array: # [] for not found, [pos, bit]
# 3x3 ブロックで探索
for y0 in range(0, N_VERT, 3):
for x0 in range(0, N_HORZ, 3):
# (x0, y0) の 3x3 ブロック内で、可能なビットの数を数える
var b0 = 0
var b1 = 0
for v in range(3):
for h in range(3):
var b = candidates_bit[xyToIX(x0+h, y0+v)]
b1 |= (b0 & b)
b0 ^= b
b0 &= ~b1 # 隠れたシングルのビットがあるか
if b0 != 0: # 隠れたシングルがある場合
b0 = b0 & -b0 # 最右ビットを取り出す
for v in range(3):
for h in range(3):
if (b0 & candidates_bit[xyToIX(x0+h, y0+v)]) != 0:
return [xyToIX(x0+h, y0+v), b0]
# 水平方向検索
for y in range(N_VERT):
var b0 = 0
var b1 = 0
for x in range(N_HORZ):
var b = candidates_bit[xyToIX(x, y)]
b1 |= (b0 & b)
b0 ^= b
b0 &= ~b1 # 隠れたシングルのビットがあるか
if b0 != 0: # 隠れたシングルがある場合
b0 = b0 & -b0 # 最右ビットを取り出す
for x in range(N_HORZ):
if (b0 & candidates_bit[xyToIX(x, y)]) != 0:
return [xyToIX(x, y), b0]
# 垂直方向検索
for x in range(N_HORZ):
var b0 = 0
var b1 = 0
for y in range(N_VERT):
var b = candidates_bit[xyToIX(x, y)]
b1 |= (b0 & b)
b0 ^= b
b0 &= ~b1 # 隠れたシングルのビットがあるか
if b0 != 0: # 隠れたシングルがある場合
b0 = b0 & -b0 # 最右ビットを取り出す
for y in range(N_VERT):
if (b0 & candidates_bit[xyToIX(x, y)]) != 0:
return [xyToIX(x, y), b0]
return []
人間的には「隠れたシングル」の方が「裸のシングル」よりもはるかに発見しやすいのだが、 コードで書くと、上記のように「隠れたシングル」の方が処理が長く難しくなるのは、個人的にはちょっと興味深い。
それはともかく、処理としては縦・横・3×3ブロック内の候補数字の各数字ビットの数を数え、 それがちょうど１であれば隠れたシングル発見ということになる。
その処理はちょっとむずかしい。単純に候補数字を加算すると桁上りが発生し、ひとつ上のビットに干渉してしまうからだ。 そのために b0, b1 という桁ごとに変数を用意し、これを使って加算を行って、ビットをカウントしている。 欲しい情報は立っているビットの数が１なのかどうかだけなので、0, 1, 2以上 を識別できればよいので b0, b1 の２つで十分というわけだ。
「b1 |= (b0 & b)」で２桁目を先に計算し、「b0 ^= b」で１桁目を計算している。
最後に、「b0 &= ~b1」で隠れたシングルのビットがあるかを判定している。
TechProjin Godot入門 関連連載リンク
Godotで学ぶゲーム制作
さくさく理解するGodot入門 連載目次
標準C++ライブラリの活用でコーディング力UP!
「競技プログラミング風」標準C++ライブラリ 連載目次
