原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科 計算ブロックパズルの問題例生成 9 8 1 4 3 6 原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科

計算ブロックパズルとは？ セル ブロック 合計値 1 3 4 2 6 9 1 3 4 2 下の条件を満たすように 1 から n の整数を セルに埋めよ (i) ラテン方陣条件 (ii) 部分和条件 3 8 3 1 2 4 4 2 4 1 3 9 1 4 2 3 1 n  n のセルから成る盤面

発表内容 唯一解を持つ中で最も「難しい」問題例の生成 (WAAC08で発表済) パターンの獲得に関する実験

生成の方針 +  L P 解となるラテン方陣 L を決定 n  nセル集合の分割 P を決定 L を唯一の解として持ち、 6 9 1 3 4 2 3 8 +  4 9 1 L P L を唯一の解として持ち、 最も「難しい」問題例? ラテン方陣 L は given  分割 P が問題例に対応

準備  解集合 唯一解 分割上の半順序 分割 P（に対応する問題例）において 解となるラテン方陣の集合を SOL(P) 明らかに for P, LSOL(P) 解集合 分割 P（に対応する問題例）において 解となるラテン方陣の集合を SOL(P) 唯一解 SOL(P) = {L} ならば、Pは唯一解分割という 分割上の半順序  Q P

40 分割の Hasse 図 P  唯一解分割でない 1 3 4 2 3 1 2 4 2 4 1 3 唯一解分割 P 4 2 3 1

40 明らかに、 P  Q ならば SOL(P)  SOL(Q) P  極大な唯一解分割 1 3 2 4 唯一解分割 P

極大な唯一解分割 の求め方     P  P 隣接する 2ブロックを選択 すべて試したら終了 唯一解分割の判定 YESならば採用 1 へ戻る     4 2 3 1 1 3 4 2 3 1 2 4 2 4 1 3 P 4 2 3 1

[宮本, ”強育パズル vol.3,” Discover, 2004] との比較 人が作った問題例との比較 [宮本, ”強育パズル vol.3,” Discover, 2004] との比較 難しすぎることも しばしば試行錯誤を要する 簡単 論理的に解くことができる

極大な唯一解分割による 面白いパズルの例 20 55

発表内容 (cont.) 唯一解を持つ中で最も「難しい」問題例の生成 (WAAC08で発表済) パターンの獲得に関する実験

パターンとは パズルのルールから論理的に導かれる セルを埋めるためのテクニック 多大な試行錯誤（探索木）を必要とせず パターンの適用で解ける問題例が 一般に「面白い」とされる プレイヤーはパターンをどう獲得するのか 自明なパターンからそうでないものまで5つに分類 被験者にパズルを解いてもらい パターンが獲得される様子を観察

パターン (P1) 単一のセルから成るブロック 7 6 4 3 6 4 3 2 3 2 5

パターン (P2) ブロックの残り１セル 7 6 4 3 6 4 3 2 1 3 2 5 3

パターン (P3) 行 or 列の残り１セル 7 6 4 3 6 4 3 2 4 1 3 2 5 3

パターン (P4) 行 or 列内のブロックの合計値および 確定した値から導出 7 6 4 3 6 4 3 2 4 1 3 2 5 3 1

パターン (P5) 同じ値がn1個のセルで確定 7 6 4 1 3 1 6 4 3 2 4 1 3 2 5 3 1

データ収集 データ収集のシステム 使用する問題例 収集されたデータ 学内イントラネット上に構築 被験者はブラウザを通じてパズルを解く 類似の問題例に対する傾向を観察したい 一辺のセル数を n=4, ブロックの最大サイズを 2 に限定 収集されたデータ 2週間、約6000件（63名の被験者） 1件のデータは1被験者が1問題例を解いた記録 データの項目 被験者ID, 問題例番号, 開始時刻, 各セルを埋めた時刻, ...

7 6 4 3 6 4 3 2 5 セルを埋めた順序を 追跡可能 (P1)から(P5)のうち 適用可能かつ 最小indexのパターンを 適用したものとみなす 適用可能なパターンが なければ(P6) i.e., その他 パターンの適用に 要した時間を推定 01:25 01:20 01:50 01:40 3 01:15 01:10 01:45 01:35 6 4 (P6) 3 (P1) 2 (P1) 00:45 00:35 00:10 00:05 [00:25] [00:05] [00:05] (P2) 5 00:50 00:40 01:55 02:00 [00:10] ゲーム開始から 埋められるまでに要した時間

（パターンの適用に要した時間：秒） （解いた問題例の数）

（パターンの適用に要した時間：秒） （解いた問題例の数）

実験のまとめ 何人かの被験者について パターンを獲得する過程が観察された 計算時間から問題例の難しさを 評価するのは容易ではない 被験者によって習熟度が異なる 「習熟した」とみなす基準?

今後の課題 人が解いて「面白い」問題例の生成 プレイヤーがパターンをどう適用するかを 考慮に入れて Hasse 図 を上れないか パターンにはどのようなものがあるのか 実験方法の検討