以下のように数字が決定している7x7の矩形がある。1〜7の数字を連結するように埋めるにはどうすれば良いか。
7の次は1が続くようにする。
いやー，思い切りはまった。なんとこれだけのプログラムなのに600行以上になってしまった。
コメントやデバッグ行を含むとはいえ多すぎ。もっとすっきり書き換えないとダメだな。
以下のような配列を作成して，候補値を潰していけば簡単にできるかなと思って作り始める。
const int M = 7; int mat[M][M][M+1]; // [*][*][0]に決定数字，[*][*][1-7]に候補数字を入れる
問題文をダンプすると以下のようになる。左の括弧書きは括弧内の数字が残り数字の数，それ以外の部分が候補値になる。
(1) 6 | (7)1234567 | (7)1234567 | (1) 2 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (1) 2 | (7)1234567 | (7)1234567 | (1) 6 | (7)1234567 | (1) 2 | (7)1234567 | (7)1234567 | (1) 6 | (7)1234567 | (7)1234567 | (1) 2 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (1) 6 | (7)1234567 | (7)1234567 | (1) 2 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (1) 6 | (7)1234567 | (1) 2 | (1) 6 | (7)1234567 | (1) 2 | (1) 6 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 |
配列を虱潰して候補値を削減していけば良いかなと思った。例えば最初のステップでは以下のように削減できた。
(1) 6 | (2) 5 7 | (7)1234567 | (1) 2 | (7)1234567 | (7)1234567 | (7)1234567 | (2) 5 7 | (1) 2 | (7)1234567 | (7)1234567 | (1) 6 | (7)1234567 | (1) 2 | (7)1234567 | (7)1234567 | (1) 6 | (7)1234567 | (7)1234567 | (1) 2 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (1) 6 | (7)1234567 | (7)1234567 | (1) 2 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (1) 6 | (7)1234567 | (1) 2 | (1) 6 | (7)1234567 | (1) 2 | (1) 6 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 | (7)1234567 |
こんな調子でプログラムを拡張していけば出来るかなと思ったが考えが甘かった。なかなか減らない。
朝6:00を過ぎても減らない。がんばって削除したけど以下が限界。
(1) 6 | (2) 5 7 | (4)12 4 6 | (1) 2 | (1) 3 | (1) 4 | (2)1 3 | (2) 5 7 | (1) 2 | (2)1 3 | (5)12 4 67 | (1) 6 | (1) 5 | (1) 2 | (3) 2 4 6 | (2)1 3 | (1) 6 | (2) 5 7 | (3)1 67 | (1) 2 | (2)1 3 | (2)1 3 | (3) 2 4 6 | (2) 5 7 | (7)1234567 | (1) 6 | (7)1234567 | (7)1234567 | (1) 2 | (2)1 3 | (2)1 3 | (7)1234567 | (7)1234567 | (7)1234567 | (2) 5 7 | (1) 6 | (2) 5 7 | (1) 2 | (1) 6 | (7)1234567 | (1) 2 | (1) 6 | (2) 5 7 | (2) 4 6 | (2)1 3 | (7)1234567 | (7)1234567 | (3)1 4 6 | (2) 5 7 |
うーん，どう見てもこれ以上減らせない。
ここまで来ると再帰的に探しても良いかなと思って，以下のようにプログラムする。こうなってしまうと簡単。
void find( int level, int row, int col, int val)
{
if( val > M) val = 1; // 7より大きくなったら1に戻る
if( !exist(row,col)) return; // 存在しない場所を指定されたら困る
if( visit[row][col]) return; // 既に訪問している
if( !mat[row][col][val]) return; // valは候補値に無い
if( level >= MM) {
// Find
return;
}
visit[row][col] = 1;
find( level+1, row-1, col+0, val+1);
find( level+1, row+1, col+0, val+1);
find( level+1, row+0, col-1, val+1);
find( level+1, row+0, col+1, val+1);
visit[row][col] = 0;
}
void find()
{
//--------------------------------------------------------------------
// 1を候補値に持つものを探す。
//--------------------------------------------------------------------
int row, col;
for( row=0; row< M; row++) {
for( col=0; col< M; col++) {
if( mat[row][col][1]) {
//--------------------------------------------------------------
// ここから虱潰す。
//--------------------------------------------------------------
find( 1/*level*/, row, col, 1/*val*/);
}
}
}
}
答えは1件出力されました。
プログラムを作り終えてこれを書いているとき，ふと思った。図中の２と６って，もう既に7個ずつあるじゃん。
ということは候補値に残った２と６は削除できるってこと。
もしかしてそれを追加したらヒューリスティックに出来るかも。
２と６を候補値から削除するようにしたら，相当候補値は減った。しかし結局解まで到達できなかった。
もう少し深いルールを考える必要があるんだろうけど，単発問題なのでそこまでやる気にならなかった。
(2006.10.2)うーん，プログラムを綺麗に整理しようと思って書き換えていくうち，ヒューリスティックな部分をどんどん削っていって，再帰だけにしてもあっという間に答えが出てしまった。時間が掛かると思っていたんだけどショック。
ヒューリスティックな部分は汚いし，今回は再帰だけのプログラムで答えとする(プログラムが綺麗になる)。
今年の栗は本当にうまい。食事の度に食べている。といっても今は2日に一度しか食事をしないようにしているから回数的には少ない。
それでもおしっこは栗の甘い香りがするようになった。
昨日郵便局で郵便を出して家に帰った後にメールを見て気づいた。出した郵便物は要求されたものと違った。マズイ。
郵便局に電話してみたら既に発送済みと言われた。本当かよ。さっき出したばかりなのにー。
取り戻せないかと聞いたら取り戻し請求すれば出来ると言うことだ。
但し500円ほど掛かると言われた。
メールと違って取り戻しが出来る。メールは一度送ってしまうと取り返しが付かないけど，その点郵便物はありがたいと思った。
郵便局に出かけたら，「まだこちらにありました」ってさ。
結局お金はかからなかったけど，取り戻し請求書みたいのは書かされた。
解速度
即