オセロやナンバーリンクなど、おなじみのゲームを題材にした実践プログラミング講座。
2020.09.01
Developer Lv3
前編より引き続き、ナンバーリンクソルバーの具体的なコードの解説を行う。 バックトラッキング関数 上記がバックトラッキングで解を求める、doSolveBT(ix) 関数の定義だ。 再帰関数で、ix から順にリンクを作っていき（壁部分は当然スキップ）、 解を発見した場合は、探索を中止し true を返す …More Read
2020.09.01
Developer Lv3
目次 はじめに ナンバーリンク ソルバー L データ構造 L ブルートフォース L バックトラッキング はじめに ナンバーリンク ナンバーリンクとは WxH の矩形盤面に１～Nまでの数字をそれぞれ２個ずつ配置し、 全部のセルを埋めて、縦横方向だけ（斜め線不可）で同じ数字をつなげるというパズルだ。 下 …More Read
2020.06.16
Developer Lv3
ビット演算（ビットマップ）による高速化 前章では配列の配置フラグを使用することで高速化を達成したが、本章ではビット演算によりさらに高速化してみよう。 int cols の各ビットが、各カラムにクイーンを配置可能かどうかを表すものとする。 最初は全てのカラムに配置可能なので、初期値は全ビットが立ってい …More Read
2020.06.12
Developer Lv3
はじめに Ｎクイーン問題（N-Queens puzzle） Ｎクイーン問題とは、NxNの盤面にチェスのクイーンN個を互いに効きが無い（クイーンは縦・横・斜め45度方向に効きがある）ように配置する問題だ。 一般的には8×8のチェス盤を用いる８クイーン問題が有名だが、本稿では盤面の縦横幅を8に …More Read
2020.05.20
Developer Lv3
問題自動生成（承前） 除算問題自動生成 除算問題自動生成のアルゴリズムは乗算問題のそれと同じ流れだ。 ランダムに解答を生成し、できるだけ消去可能な数字を消去する。 数字を消去して、解が無い、または解が複数ある場合は消去不可とする。 商・除数・余りをランダムに生成すれば被除数・計算途中結果は自動的に決 …More Read
2020.05.20
Developer Lv3
承前 問題自動生成 一般的に、数独などの制約充足問題は、以下の手順で問題自動生成することができる。 1) 解をランダムに生成 2) 要素を消し解がユニーク（唯一）かどうかをチェック 3) 可能な限り 2) を繰り返す 可能な限り手がかりを消していくので、上記のアルゴリズムは「貪欲法（greedy a …More Read
2020.05.20
Developer Lv3
ソルバー（承前） 乗算ソルバー 乗算問題も加算ソルバーと同じ様に空欄に ‘0’-‘9’ の数字を入れながら深さ優先探索を行えばよい。 乗算問題の場合は上図の様に空欄の数が多いので、探索時間が膨大になるのではないかと心配されるかもしれない。 しかし、実は …More Read
2020.05.20
Developer Lv3
はじめに 虫食い算 虫食い算とは、「□２＋３□＝４６」の様な数式の空欄に０～９の数字を入れて数式を完成させるパズルだ。 ただし、複数桁の最上位桁に０は入れてはいけない。 例えば、「□＋１＝□□」の場合、答えの２桁目は０は入らないので、９＋１＝１０ が解となる。 加算だけではなく、乗算・除算問題もある …More Read
2020.05.11
Developer Lv3
アルゴリズム（承前） 深さ優先探索 ゲーム木探索は、大きく言うと、深さ優先探索と幅優先探索の２種類がある。 深さ優先探索とは、先へ先へと局面を進めていき、末端に到達したらひとつ前に戻って、 次の手を探索するというアルゴリズムだ。 単純で高速なので、ゲーム木が小さく全探索可能であればこれで充分だ。 下 …More Read
2020.05.11
Developer Lv3
アルゴリズム（承前） すべての空欄に対する処理 オセロのゲーム木探索においてはすべての空欄に対する処理が必要だ。 普通にループで書くと以下のようになる。ループ回数は常に16回となる。 ushort space = ~(black | white); // 空欄の部分だけビットを立てる for(ush …More Read
