しかし、頭の体操を兼ねて、意地でもそんなものは見ないで、もう一度全回答を出すプログラムを作ってみようと思うのである。
また、今度は作成の概要を書いておいて記録しておこうと思うのである。
今回作成するのは、以下のようなパズルで、正式な名称は「ペントミノ」というものだそうである。
以下は、「その他いろいろ」−＞「プラパズル」で書いてしまった部分もあるのだが、もう一度書く。
1968年当時、「天洋」という会社が「プラパズル」という名称で出しており、私は新宿駅東口の国鉄の改札（地下１階）からメトロ・プロムナードへ降りる階段の左側にあった「王様のアイデア」という店舗で買ったものである。
このパズルは、一つが５個の正方形で出来ているピース１２個を、６×１０のケースの中に収めるのがこのパズルである。
見てみると、５個の正方形を組み合わせる全種類が揃っているのである。
なにぶん古いもので、踏んづけて割れていたり、ドリルを買ってうれしくて穴を空けてしまったり、汚れたので研究室にあったアセトンで拭いたら印刷も消えてしまったり、ボロボロ状態である。
ケースと、中に入っている紙に解説が書いてあり、「富士通のFACOM270-20で計算して2339通りの回答があることが解った」と出ている。
それを見た私達は、「電子計算機」というからには、何か「解析学」的な回答方法があるのか？と頭を捻っていたのである。
しかし、そもそも当時中学生だった私達の頭では、「電子計算機」というもの自体がどういうものかも知らなかったので、何が何だか全く解らなかったのである。
私はこれを中学２年生の頃からちょくちょくとやっており、大学の４年になる頃には200種類以上の回答を出していたのだった。
大学には当時（1977年）UNIVAC-1108というコンピューターが設置してあり、申請して利用料金（記憶がさだかではないのだが、確かＣＰＵ時間が１分１円、パンチカードが１枚１円）を払えばバッチ処理で使わせてくれたのだった。
そこで早速、念願だったこのパズルを解くプログラムを作ったのだった。
さて、このパズルの回答をいったいどうやって出すのか？
たぶん、いくつかの方法があって、一長一短があるのだろうが、私が考え出した方法は以下のようなものだった。
１、ピースを置くケースについて
まず、ピースを置くケースは６×１０のマス目なので、左上から下に向かってアドレスの番号を付けていく。
１行目は０からスタートして５までになり、６番目は境目として、２行目は７からスタートする。
同様に全部の番地に番号を振って、最後の行も一列７０〜７６番目を境目としておく。
左の図で黄色い部分が境目である。
２、各々のピースについて
次に、各ピースの番地をふっていく、各々のピースの左上を０番地として、どんな番地を占有するのか番号を振っていく。
各々のピースは、点対称で回転すると形が変わるものがあるので、全部の変化を数値化する。
たとえば、左の０番のピースは回転させると形が変わり、４種類あるのだが、裏側にしても形は変わらないので、変化は全部で４種類である。
次の１番のピースは、縦横だけの２種類である。
次の２番のピースは、回転させて４種類、裏返して４種類、合計８種類の変化がある。
データとしては、ピースの番号（０〜１１の１２個）−＞そのピースの変化の種類（最大８種類）−＞占有する番地４つ（０番地はあたりまえなので省略）というデータになる。
Ｃ言語的に書けば、以下のようになる。
char peace_pattern[12]・・・・変化の数が12個分
char peace_data[12][8][4]・・左からピースの番号、変化の番号、そして４つの占有地
３、これらのピースを、ケースの中に入れていく。
ケースは空っぽの状態を０として、左上から下に向かって調べ、０が出たらそこへピースを置く（上記のピースのデータに入れる番地を加算すればよい）
境目は無条件に置けないので０以外で、今回は100を設定しておいた。
計算中のピースが占有する場所が全て０ならば置くのが可能と判断する。
そしてピースを入れたら、そのピースが占有している番地の内容を０意外の数字（実際はピースの番号＋１）を入れていき、既にピースを入れたと記していく。
そして次の０の番地を探していく。
どうしても入らない状態になったら、最後に入れたピースの状態をクリアし、そのピースを回転もしくは裏返して置けるかチェックし、全ての状態を試していく。
それでも入らない場合は次のピースに交換していき、全ピースで全ての回転と裏返しのチェックを行う。
順列組合せ
全ての組合せを行うプログラムというのは、どういうのが一番効率的なのだろうか？
おそらく数学的に正解があるのだろうが、まぁ、私の場合は頭の体操でやるので、勝手に以下のように行った。
１、最初に置くピースは０から１１まで順に置いていく。
２、２番目に置くピースも０から１１まで全て置いていく。
ただし、１番目に使ったピースは除く。
３、以下同様にＮ番目に置くピースも全種類やってみる。
ただし、Ｎ−１番目までに使ったピースは除く。
これらの処理を全て入れ子にして、全ての組合せをチェックする。
イメージとしてはこんな感じであろうか？
これを全ピースで効率よく行うために、以下のような考え方でプログラムを作った。
１、箱を１２個用意する。
２、その箱はそれぞれに最初にケースにはめ込むピースを入れる箱から、二番目に使うピースを入れる箱という感じで用意する。
３、最初は適当な順番でその箱に全てのピースを入れてスタートする。
イメージとしてはこんな感じであろうか？
最初のピースは、現在箱の中に入っているピースをはめてスタートし、処理が終了したら、次のピースは２番目の箱の中身と入れ替える。
それが終わると、もう一度入れ替えなおして元へ戻し、次は３番目の箱の中身と入れ替えて次の処理を行う。
それを１２番目の箱の中身と入れ替えるまで行う。
２番目に使うピースを入れる箱の処理は、現在入っているピースの処理が終わったら、入れ替えが３番目からスタートして１２番目までとなり、一つ減る。
同様に３番目に使うピースを入れる箱の処理は、入れ替えが４番目から１２番目までとなる。
処理のイメージをスードコードで書くと、こんな感じであろうか？
最初の箱のピースを決めるインデックスは０から１１まで繰り返す
｜最初の箱の中身を１番目のインデックスの指し示す箱の中身と交換する。（一回目は自分自身の中身と交換）
｜最初の箱の中のピースの回転裏返しの処理を全て行う。
｜｜そのピースはケースにうまくはめ込めたか？
｜｜｜＜YESの場合は下記の処理、NOの場合は迂回＞
｜｜｜そのピースをケースの中にはめ込む
｜｜｜２番目の箱のピースを決めるインデックスは1から１１まで繰り返す（一つ減る）
｜｜｜｜２番目の箱の中身を２番目のインデックスの指し示す箱の中身と交換する。（一回目は自分自身の中身と交換）
｜｜｜｜２番目の箱の中のピースの回転裏返しの処理を全て行う。
｜｜｜｜｜そのピースはケースにうまくはめ込めたか？
｜｜｜｜｜｜＜YESの場合は下記の処理、NOの場合は迂回＞
｜｜｜｜｜｜そのピースをケースの中にはめ込む
｜｜｜｜｜｜
｜｜｜｜｜｜以下同様に１２番目のピースの処理まで行う。
｜｜｜｜｜｜
｜｜｜｜｜｜ケースから、最後にはめ込んだ２番目のピースのデータをクリア
｜｜｜｜｜IF文のエンド
｜｜｜｜ループのエンド
｜｜｜｜２番目の箱の中身を２番目のインデックスの指し示す箱の中身と交換する。（元へ戻す）
｜｜｜ループのエンド
｜｜｜ケースから、最後にはめ込んだ１番目のピースのデータをクリア
｜｜IF文のエンド
｜ループのエンド
｜最初の箱の中身を１番目のインデックスの指し示す箱の中身と交換する。（元へ戻す）
ループのエンド
この処理は、全く同じ処理をネストしていくので、リカーシブコール（自分で自分自身を呼び出す）の構造にすれば簡単になるのであるが、正直こんな計算にスタックを多量に消費する度胸は私には無かったのである。
重複回答を避ける。
このパズルは一つ正解が出ると、180度回転させても回答となるし、裏返しても回答となる。
つまり、一つの回答が４倍になるのである。
それをどうやって阻止するのか？
学生の頃、手作業で回答を集めていたときには、回答は紙に手書きの絵だったので、最初は当然ながら手作業で今まで出た回答と見比べて重複回答を探していたのである。
全ての突き合わせはけっこうタイヘンだったのである。
回答が増えてくると、見落としも出てくるのである。
散々苦労するうちに、重複回答を避ける方法が解ったのである。
それは、回転させたり裏返しにすると、全て形が変わるピースに注目するのである。
つまり、ある回答が出た時に、そのピースがある形になるように回転させたり裏返したりしてからチェックするのである。
そうすれば、単純な点対称や線対称の回答を防げるのである。
逆に言えば、あるピースの変化形を制限してしまえば、自動的に回転した回答も裏返しの回答も出なくなるのである。
ということで、私はこのピースに制限をかけたのである。
×をかけてあるものは、全てが左の２個の状態からの点対称かまたは裏返し、裏返しの点対称なのである。
プログラムとしては、こんな感じになる。
void Cpentomino5View::all_exec(CDC* pDC)
{
Cpentomino5Doc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
if (!pDoc) return;
SYSTEMTIME systime_s; // 処理の開始時刻
SYSTEMTIME systime_e; // 処理の終了時刻
char temp1;
CString str01;
char ix_temp;
GetSystemTime(&systime_s); // 開始時刻を取得
// ピースを置くケースのクリアと境目を設定
for (temp1 = 0; temp1 < 77; temp1++) {
desk[temp1] = 0;
}
for (temp1 = 6; temp1 < 77; temp1 = temp1 + 7) {
desk[temp1] = 100;
}
for (temp1 = 70; temp1 < 77; temp1++) {
desk[temp1] = 100;
}
ix_desk = 0; // 左上から下へ、空いている場所を探すインデックス
ans_count = 0; // 回答数
for (ix0 = 0; ix0 < 12; ix0++) { // 最初に入れるピースは0〜11まで12回の入れ替えを行う。
ix_temp = part_main[0]; // インデックスの指し示す箱と0番目の箱の中身を入れ替える。
part_main[0] = part_main[ix0];
part_main[ix0] = ix_temp;
ix0_part = part_main[0]; // 0番目の箱の中身を取得
iy0 = part_change[ix0_part]; // そのピースの変化の数を取得
for (ir0 = 0; ir0 < iy0; ir0++) { // 変化数分のループ
if (desk[parts[ix0_part][ir0][0] + ix_desk] == 0 && // ピースはケースに置けるか？
desk[parts[ix0_part][ir0][1] + ix_desk] == 0 &&
desk[parts[ix0_part][ir0][2] + ix_desk] == 0 &&
desk[parts[ix0_part][ir0][3] + ix_desk] == 0) {
temp1 = part_main[0] + 1; // 置けたら置いた場所にピースの番号を埋めておく（ピースの番号が０からなので１加算しておく)
desk[ix_desk] = temp1;
desk[parts[ix0_part][ir0][0] + ix_desk] = temp1;
desk[parts[ix0_part][ir0][1] + ix_desk] = temp1;
desk[parts[ix0_part][ir0][2] + ix_desk] = temp1;
desk[parts[ix0_part][ir0][3] + ix_desk] = temp1;
ans1[0] = ix_desk; // 置いた位置とピース番号、変化番号をセーブしておく
ans2[0] = ix0_part;
ans3[0] = ir0;
ix_desk++; // 次にピースを置くべき場所を探す
for (temp1 = ix_desk; temp1 < 76; temp1++) {
if (desk[temp1] == 0) break;
else ix_desk++;
}
for (ix1 = 1; ix1 < 12; ix1++) { // ２番目に入れるピースは1〜11まで11回の入れ替えを行う。
ix_temp = part_main[1]; // インデックスの指し示す箱と1番目の箱の中身を入れ替える。
part_main[1] = part_main[ix1];
part_main[ix1] = ix_temp;
ix1_part = part_main[1]; // 1番目の箱の中身を取得
iy1 = part_change[ix1_part]; // そのピースの変化の数を取得
for (ir1 = 0; ir1 < iy1; ir1++) { // 変化数分のループ
if (desk[parts[ix1_part][ir1][0] + ix_desk] == 0 && // ピースはケースに置けるか？
desk[parts[ix1_part][ir1][1] + ix_desk] == 0 &&
desk[parts[ix1_part][ir1][2] + ix_desk] == 0 &&
desk[parts[ix1_part][ir1][3] + ix_desk] == 0) {
temp1 = part_main[1] + 1; // 置けたら置いた場所にピースの番号を埋めておく
desk[ix_desk] = temp1;
desk[parts[ix1_part][ir1][0] + ix_desk] = temp1;
desk[parts[ix1_part][ir1][1] + ix_desk] = temp1;
desk[parts[ix1_part][ir1][2] + ix_desk] = temp1;
desk[parts[ix1_part][ir1][3] + ix_desk] = temp1;
ans1[1] = ix_desk; // 置いた位置と変化番号をセーブしておく
ans2[1] = ix1_part;
ans3[1] = ir1;
ix_desk++; // 次にピースを置くべき場所を探す
for (temp1 = ix_desk; temp1 < 76; temp1++) {
if (desk[temp1] == 0) break;
else ix_desk++;
}
そしてＩＦ文とループのエンドは以下のような感じである。
ix_desk = ans1[1]; // ケースに置いてある２番目のピースの部分をクリアし、取り除く
desk[ix_desk] = 0;
desk[parts[ix1_part][ir1][0] + ix_desk] = 0;
desk[parts[ix1_part][ir1][1] + ix_desk] = 0;
desk[parts[ix1_part][ir1][2] + ix_desk] = 0;
desk[parts[ix1_part][ir1][3] + ix_desk] = 0;
} // end if
} // end for ir1
ix_temp = part_main[1]; // ２番目の箱の中身をインデックスが指し示す箱の中身を入れ替え、元に戻す。
part_main[1] = part_main[ix1];
part_main[ix1] = ix_temp;
} // end for ix1
ix_desk = ans1[0]; // ケースに置いてある最初のピースの部分をクリアし、取り除く
desk[ix_desk] = 0;
desk[parts[ix0_part][ir0][0] + ix_desk] = 0;
desk[parts[ix0_part][ir0][1] + ix_desk] = 0;
desk[parts[ix0_part][ir0][2] + ix_desk] = 0;
desk[parts[ix0_part][ir0][3] + ix_desk] = 0;
} // end if
} //end for ir0
ix_temp = part_main[0]; // 最初の箱の中身をインデックスが指し示す箱の中身を入れ替え、元に戻す。
part_main[0] = part_main[ix0];
part_main[ix0] = ix_temp;
}
label01:
pDoc->print_ans_count = ans_count;
GetSystemTime(&systime_e);
str01.Format(_T("全回答 = %d 種類 開始 %u:%u:%u.%u 終了 %u:%u:%u.%u"), ans_count,
systime_s.wHour, systime_s.wMinute, systime_s.wSecond,
systime_s.wMilliseconds,
systime_e.wHour, systime_e.wMinute, systime_e.wSecond,
systime_e.wMilliseconds);
//MessageBox(str01,_T("続行しますか？"));
MessageBox(str01);
}
さて、実行結果としては以下のような結果である。
ＯＫを押す毎に次の回答が出てくる。
全回答をいっぺんに計算するルーチンを走らせると、左のように約1.954秒で全回答が出る。
全回答は2339通りで、一応意図したとおりである。
プロセッサーはインテルのi3プロセッサーで、クロックは3.5G、実装メモリは4Gである。
私が1977年に最初に大学でUNIVAC-1108を使ってFORTRANで作ったときには、全回答を出すのに約45分かかったのである。
UNIVAC-1108は1964年の製造で、当時マニュアルを見ると「超大型コンピューター」と出ていたと記憶しているのである。
私が大学で使ったのは、だいぶ古くなっていた1977年だったのだが、それでも見たこともない速度で動いている印象だった。
次に会社で1979年頃、同じプログラムをIBM3031で動かしたときには7分半くらいだったので、6倍の速度差があったことになる。
2003年の8月に「その他いろいろ」−＞「プラパズル」を書いたときに、インテルの486DX2/66MHzでWindows3.1配下でVC++でプログラムを作り直したもので、5分25秒
新しいパソコンでペンティアム300MHzで動かすと、28秒だったのである。
それが今回は1.95秒である。
昔の超大型コンピューターUNIVAC-1108の1300倍以上の速さが出ているのである。
私が若い頃に仕事で使っていたIBM3031の230倍というのだから、ちょっと驚くのである。
現在私達が使っているパソコンは、一昔前のスーパーコンピューターに匹敵する速度で動作しているのである。
あぁ、あの頃に今のコンピュータがあったら・・・・・と、感慨深いのである。
回答は、ファイルに書き出すことが出来、左のようなテキストファイルになる。
実際は印刷のプログラムも作ってみようかと思ったのだが、親の家にはプリンターが無く、テストがしにくいので保留にしてある。
このプログラムは、Visual studio 2017のVC++で作ったものなので、実行するにはVisual studio 2017をインストールする必要があります。
それでも実行してみたい方は、以下のダウンロードで取得したzipファイルを展開し、適当なフォルダーで実行してみて下さい。
使い方はメニューの「実行」−＞「回答表示」（一つずつ回答が画面に出る）もしくは
「実行」−＞「全回答」−＞「回答表示有り」もしくは
「実行」−＞「全回答」−＞「回答表示無し」
全回答、もしくは回答表示でいくつか回答を出した後にファイルへ書き込みを行うと、左のようなテキストファイルが出ます。
「ここからダウンロード」
今回、以前作って実行ファイル（exe）しか残っていないプログラム（pzl5.exe）も実行してみたのだが、そちらは20秒くらいかかる。
この差は何だろうか？
一番考えられるのが印刷ルーチンで、以前作ったプログラムは（たぶん）回答を得る毎にファイルに書き出していたのである。
そして、今回作ったプログラムは、回答はデータとしてプログラム中に持っており、「印刷」を指示した時点で一斉に書き出しているのである。
そのへんの違いは大きいかもしれない。
それにしても、以前VC++のバージョン５で作ったものと、今回のVC++で作ったものの実行ファイルの大きさの違いに唖然とするのである。
以前作ったものは28KBytesしかなく、今回作ったものは280KBytesもある。
この差はいったになんなんだろうか？