計算ブロックパズルの問題例生成 6 9 3 8 9 1 4 原口和也高橋隆一丸岡章石巻専修大学理工学部情報電子工学科計算ブロックパズルとは？セル 1 3 2 4 6 ブロック 3 4 1 4 2 2 4 2 3 1 3 4 9 8 3 9 1 合計値 1 n  n のセルから成る盤面下の条件を満たすように 1 から n の整数をセルに埋めよ (i) ラテン方陣条件 (ii) 部分和条件発表内容 1. 唯一解を持つ中で最も「難しい」問題例の生成 (WAAC08で発表済) 2. パターンの獲得に関する実験生成の方針解となるラテン方陣 L を決定 2. n  nセル集合の分割 P を決定 1. 1 3 4 2 3 1 2 4 2 4 1 3 4 2 3 1 L 6  + 9 3 8 9 1 4 P L を唯一の解として持ち、最も「難しい」問題例?  ラテン方陣 L は given  分割 P が問題例に対応  準備明らかに for P, LSOL(P)  解集合分割 P（に対応する問題例）において解となるラテン方陣の集合を SOL(P)  唯一解 SOL(P) = {L} ならば、Pは唯一解分割という  分割上の半順序 P  Q 分割の Hasse 図 P 40  唯一解分割でない 1 3 2 4 3 1 4 2 4 2 1 3 2 4 3 1 P 唯一解分割 P 明らかに、 P  Q ならば SOL(P)  SOL(Q) 40  極大な唯一解分割 1 3 2 4 3 1 4 2 4 2 1 3 2 4 3 1 P 唯一解分割 P  極大な唯一解分割の求め方 1. 隣接する 2ブロックを選択すべて試したら終了 2. 唯一解分割の判定 YESならば採用   3. 1 へ戻る  4 3 1 2 4 4 2 4 2 1 3 2 4 3 1 P 1 3 2 4 3 1 4 2 4 2 1 3 2 4 3 1 人が作った問題例との比較 [宮本, ”強育パズル vol.3,” Discover, 2004] との比較難しすぎることもしばしば試行錯誤を要する n=5 簡単 0.6 論理的に解くことができる 0.4 0.2 0 2 Ours 4 6 8 10 Miyamoto's 12 14 16 18 20 # blocks 極大な唯一解分割による面白いパズルの例 55 20 発表内容 (cont.) 1. 唯一解を持つ中で最も「難しい」問題例の生成 (WAAC08で発表済) 2. パターンの獲得に関する実験パターンとは  パズルのルールから論理的に導かれるセルを埋めるためのテクニック  多大な試行錯誤（探索木）を必要とせずパターンの適用で解ける問題例が一般に「面白い」とされる  プレイヤーはパターンをどう獲得するのか   自明なパターンからそうでないものまで5つに分類被験者にパズルを解いてもらいパターンが獲得される様子を観察パターン (P1) 単一のセルから成るブロック 7 6 4 3 2 3 6 4 5 3 2 パターン (P2) ブロックの残り１セル 7 6 4 1 3 2 3 5 3 6 4 3 2 パターン (P3) 行 or 列の残り１セル 7 6 4 1 3 2 3 5 3 6 4 4 3 2 パターン (P4) 行 or 列内のブロックの合計値および確定した値から導出 7 6 4 1 3 3 2 3 5 1 3 6 4 4 2 パターン (P5) 同じ値がn1個のセルで確定 7 3 6 6 4 1 1 3 3 2 2 3 5 1 1 4 4 データ収集  データ収集のシステム   学内イントラネット上に構築被験者はブラウザを通じてパズルを解く  使用する問題例   類似の問題例に対する傾向を観察したい一辺のセル数を n=4, ブロックの最大サイズを 2 に限定  収集されたデータ    2週間、約6000件（63名の被験者） 1件のデータは1被験者が1問題例を解いた記録データの項目被験者ID, 問題例番号, 開始時刻, 各セルを埋めた時刻, ... 7 6 4  セルを埋めた順序を追跡可能 01:15 01:10 01:45 01:35  (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] (P1)から(P5)のうち適用可能かつ最小indexのパターンを適用したものとみなす  適用可能なパターンがなければ(P6) i.e., その他  パターンの適用に要した時間を推定 01:25 01:20 01:50 01:40 3 6 4 ゲーム開始から埋められるまでに要した時間（パターンの適用に要した時間：秒）（解いた問題例の数）（パターンの適用に要した時間：秒）（解いた問題例の数）実験のまとめ  何人かの被験者についてパターンを獲得する過程が観察された  計算時間から問題例の難しさを評価するのは容易ではない   被験者によって習熟度が異なる「習熟した」とみなす基準? 今後の課題  人が解いて「面白い」問題例の生成  プレイヤーがパターンをどう適用するかを考慮に入れて Hasse 図を上れないか  パターンにはどのようなものがあるのか  実験方法の検討