- クロスワードなどのパズル
267 ：□７×７＝４□□[sage]：2021/01/15(金) 14:30:59.57 ID:KPtc5BOO - クロスワード ギバー4.6.4
https://katahiromz.web.fc2.com/xword/
黒マスパターン生成の高速化
辞書メニューにテーマ機能を追加
ことわざ辞書の追加
|
- 【解答】パズルのプログラミング【作成】
771 ：蟻人間 ◆T6xkBnTXz7B0 [sage]：2021/01/15(金) 19:32:50.96 ID:KPtc5BOO - アルファベットの集合をAと表す。
壁の集合をBと表す。空白の集合をEと表す。
アルファベットと壁をあわせてC==A∪B∪E.
サイズm×nの盤の解空間S(m,n)は盤集合(C^m)^nに含まれる。
よって与えられた問題は、盤集合のなかから、解を探し出す探索問題に帰する。
盤が解となる条件はスケルトンであること、すなわち各マスが空白ではなく、かつ、単語集合Wがあって、盤において2文字以上の壁ではない並びがあって、、、
|
- 【解答】パズルのプログラミング【作成】
772 ：蟻人間 ◆T6xkBnTXz7B0 [sage]：2021/01/15(金) 19:53:09.63 ID:KPtc5BOO - 現代的でリッチなプログラム言語なら、関数再帰は可能であろう。以下は疑似C++コードで説明する。
static 盤 g_answer; //グローバル変数
static bool g_solved = false; //解があるか？
// 戻り値は成功か失敗。
bool 再帰求解関数(const 盤& board) {
if (g_solved) return true;
if (boardは正当でない) return false;
if (boardは解) {
g_answer = board; //ただし排他制御が必要
return true;
}
盤 clone;
盤boardを盤cloneにコピー。
盤cloneを何マスか埋める。
if (再帰求解関数(clone)) return true;
return false;
}
|
- 【解答】パズルのプログラミング【作成】
773 ：蟻人間 ◆T6xkBnTXz7B0 [sage]：2021/01/15(金) 20:05:35.66 ID:KPtc5BOO - 盤 clone;
盤boardを盤cloneにコピー。
盤cloneを何マスか埋める。
if (再帰求解関数(clone)) return true;
↑この部分を次のように書き換えると再帰で分岐ができる。
盤 clone1;
盤boardを盤clone1にコピー。
盤clone1を何マスか埋める。
if (再帰求解関数(clone1)) return true;
盤 clone2;
盤boardを盤clone2にコピー。
盤clone2を別の方法で何マスか埋める。
if (再帰求解関数(clone2)) return true;
|
- 【解答】パズルのプログラミング【作成】
774 ：蟻人間 ◆T6xkBnTXz7B0 [sage]：2021/01/15(金) 20:06:13.45 ID:KPtc5BOO - さらにマルチスレッドを使うとより効率よく探索できる。
|