スケルトンパズル

スケルトンパズルとは

単語の一覧(リスト)と空欄の組合せの図があって，空欄に一覧にある単語を埋めていく。

例えば単語が，スケルトン，パズルで，以下のような図があったとき，

解答は以下のようになる。

コンピュータで解くには

空の単語の一覧を図から抽出する。

空の単語の一覧と単語の一覧を組み合わせる。

単語の一覧をwiとし空の単語の一覧をpiとする。

これを組み合わせる関数は以下の通り。

kumiawase( int level)
{
  for( int i=0; i< N; i++) {
    p[level] = w[i];
    kumiawase( level+1);
  }
}

確かに組み合わせているんだけどこれではダメ。

何がダメか。以下の３点がダメ。

これらの条件を追加して関数を改良すると以下のようになる。

kumiawase( int level)
{
  if( level >= N) { 解が見つかった }
  for( int i=0; i< N; i++) {
    if( w[i].used) continue;
    if( p[level].length ) != w[i].length ) continue;
    used[i] = 1;
    p[level] = w[i];
    kumiawase( level+1);
    used[i] = 0;
  }
}

これでOKでしょうか?

まだまだダメです。空の単語には組合せがあって，先の例では以下の赤部分の文字が一致しなければならない。

問題の図では以下の位置の文字が２つの空の単語の組合せになる。

これを組み込んで初めて完成となる。問題を矩形とみなし矩形内の位置をチェックする。

kumiawase( int level)
{
  if( level >= N) { 解が見つかった }
  for( int i=0; i< N; i++) {
    if( w[i].used ) continue;
    if( p[level].length != w[i].length ) continue;
    if( p[level] に w[i] を配置したとき既に別の文字が置いてあれば ) continue;
    used[i] = 1;
    p[level] = w[i];
    kumiawase( level+1);
    used[i] = 0;
  }
}

これでプログラムは大体完成である。

問題の読み込み

スケルトンパズルは雑誌にも数多く掲載されている。雑誌に載っているスケルトンパズルを解いて応募するとなると，簡単に入力できる必要がある。

テンキー(キーボードの右側に付いている数字だけのキーボード)だけで入力できるのが望ましい。

以下のようなデータを定義する。

文字がある部分のマス数.文字が無い部分のマス数.文字がある部分のマス数...
#
単語の一覧
#
解答文字列の位置

上記例の場合の入力データは以下の通り。上記例では解答文字列が無かったが，「パス」になるように解答欄を設定すると，以下のようになる。

0.2.1.2
0.2.1.2
2.1.2
#
パズル
スケルトン
#
1.3
3.1

単語は短い順に指定しなければならない。

実行結果

上記サンプルファイルでのプログラムの実行結果は以下の通り。

MAT[3][5]
■■※■■
■■□■■
※□□□□
3 : パズル
5 : スケルトン
有効単語数 : 2
2 : 横[ 2][ 0] : 5 
1 : 縦[ 0][ 2] : 3 
Find GOAL
----------------------------------------------------------------------
■■パ■■
■■ズ■■
スケルトン
パス

ソースファイル

ソースファイルはこちら。ソースはあまり綺麗でないのでちょっと読むのに苦労するかも知れないがやる気のある人は頑張って読んでくれ。