前編より引き続き、ナンバーリンクソルバーの具体的なコードの解説を行う。
バックトラッキング関数
bool BoardK::doSolveBT(int ix) // ix の状態を決める
{
if( ix > xyToIndex(m_width, m_height) ) { // 全てのセルを無事埋めた場合
return true;
}
if( m_number[ix] == WALL ) ++ix; // 番人をスキップ
if( m_number[ix] != 0 ) { // セルに数字がある場合
if( m_mate[ix] != 0 ) { // リンク済みの場合
return doSolveBT(ix+1);
} else {
if( connectRt(ix) ) { // 右にリンク可能
if( doSolveBT(ix+1) )
return true;
disconnectRt(ix); // 右へのリンク削除
}
if( connectDn(ix) ) { // 下にリンク可能
if( doSolveBT(ix+1) )
return true;
disconnectDn(ix);
}
}
} else { // セルに数字が無い場合
const bool up = m_linkDn[ix-m_aryWidth]; // 上からリンクが来ている
const bool left = m_linkRt[ix-1]; // 左からリンクが来ている
if( up && left ) { // 上・左両方からリンクが来ている → 既に┘が入り、チェック済みのはず
return doSolveBT(ix+1);
} else if( up || left ) {
if( connectRt(ix) ) { // 右にリンク可能
if( doSolveBT(ix+1) )
return true;
disconnectRt(ix); // 右へのリンク削除
}
if( connectDn(ix) ) { // 下にリンク可能
if( doSolveBT(ix+1) )
return true;
disconnectDn(ix);
}
} else { // 上からも左からもリンクが来ていない
if( connectRtDn(ix) ) { // 右・下にリンク可能
if( doSolveBT(ix+1) ) // 解発見
return true;
disconnectRtDn(ix); // 右・下へのリンク削除
}
}
}
return false;
}
上記がバックトラッキングで解を求める、doSolveBT(ix) 関数の定義だ。
再帰関数で、ix から順にリンクを作っていき（壁部分は当然スキップ）、
解を発見した場合は、探索を中止し true を返す。
解を発見できなかった場合は false を返す。
ix 位置に数字が有るか無いか、リンク先に数字・リンクがあるかで場合を分け、
右 and/or 下にリンクを作れるかどうかをチェックし、可能ならリンクを作って先に進む。
リンクを作る、破棄する処理は関数化し、文書性を向上させている。
connectRt(), connectDn(), connectRtDn() はそれぞれ右, 下、右と下にリンクを作る関数、
disconnectRt, disconnectDn(), disconnectRtDn() はそれぞれの方向のリンクを削除する関数だ。
右連結処理関数
bool BoardK::connectRt(int ix) // ix, ix+1 をリンク、mate[] 更新
{
const int DX = 1;
if( m_number[ix+DX] == WALL ) return false;
const auto sz0 = m_mateStack.size();
if( m_number[ix] != 0 ) { // ix に数字がある場合
assert( m_mate[ix] == 0 );
if( m_number[ix+DX] != 0 ) { // 右に数字がある場合
if( m_number[ix+DX] != m_number[ix] ) return false;
} else { // 右に数字が無い場合
if( m_mate[ix+DX] != 0 ) { // 右がリンク末端の場合
if( m_mate[ix] == ix+DX ) // 自分自身の場合
return false;
if( m_number[m_mate[ix+DX]] != 0 && m_number[m_mate[ix+DX]] != m_number[ix] )
return false; // 右リンクの数字が一致しない場合
connectMatePush(ix, m_mate[ix+DX]);
} else { // 右がリンク末端ではない場合
connectMatePush(ix, ix+DX);
}
}
} else { // ix が空欄の場合
assert( m_mate[ix] != 0 );
if( m_number[ix+DX] != 0 ) { // 右に数字がある場合
if( m_mate[ix+DX] != 0 ) return false; // 既に連結済みの場合
if (m_mate[ix] == ix + DX) return false; // 自分自身の場合
if( m_number[m_mate[ix]] != 0 && m_number[m_mate[ix]] != m_number[ix+DX] )
return false; // 数字が一致しない場合
connectMatePush(m_mate[ix], ix+DX);
} else { // 右に数字が無い場合
if( m_mate[ix+DX] != 0 ) { // 右がリンク末端の場合
if( m_mate[ix] == ix+DX ) // 空ループの場合
return false;
if( m_number[m_mate[ix+DX]] != 0 && m_number[m_mate[ix]] != 0 && m_number[m_mate[ix+DX]] != m_number[m_mate[ix]] )
return false; // 右リンクの数字が一致しない場合
connectMatePush(m_mate[ix], m_mate[ix+DX]);
} else { // 右がリンク末端ではない場合
connectMatePush(m_mate[ix], ix+DX);
}
}
}
auto d = m_mateStack.size() - sz0;
m_mateStack.push_back(d);
m_linkRt[ix] = true;
return true;
}
void BoardK::pushMate(int ix) // (ix, mate[ix]) をプッシュ
{
m_mateStack.push_back(ix);
m_mateStack.push_back(m_mate[ix]);
}
右連結を行う場合も、ix 位置に数字があるか空欄かで処理を分け、
さらに右に数字があるか、リンク末端があるかなどで処理を分け、
リンク可能であれば m_link[ix] に true を設定している。
リンク不可能であれば false を返す。
さらに、リンクをたどるために相手末端インデックスを保持する mate[] 配列を更新している。
また、disconnectXX() のとき、mate[] 配列を元の状態に戻すために、
m_mateStack スタックに配列添字・元の値を保存している。
void BoardK::popMate() // m_mate[] を元に戻す
{
assert( !m_mateStack.empty() );
int n = m_mateStack.back(); m_mateStack.pop_back();
while( (n-=2) >= 0 ) {
auto v = m_mateStack.back(); m_mateStack.pop_back();
auto x = m_mateStack.back(); m_mateStack.pop_back();
m_mate[x] = v;
}
}
void BoardK::disconnectRt(int ix) // 右連結解除
{
popMate();
m_linkRt[ix] = false;
}
連結解除処理は連結処理に比べると簡単だ。
スタックに保存してある情報を元に、mate[] 配列を元に戻し、
m_linkRt[ix] に false を設定するだけだ。
下連結、右＆下連結処理は右連結処理と似ているので詳細は省略
コードは github を参照してほしい
◎ 結果
・実際の問題に依存するが、10×10 であれば１秒未満で解くことができた
・同じ盤面サイズであれば数字が少ないほどリンクの選択肢が増えるので、処理時間がかかる
課題
おわりに
ナンバーリンクパズルのソルバープログラムについて解説した。
場合分けが多く、処理が非常に複雑なので、あまり細部の説明は行わなかったが、
枝刈りを高速に行うために利用した、端点情報を持つmate配列データ構造を理解していただければ幸いである。
関連記事
投稿が見つかりません。
 |
筆者：津田伸秀 プロフィール：テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員（主席）。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。 |
