10円玉4枚が横1列に配置されている。
一度に１枚ずつ５回移動させ別の位置に１列に移動する。どうすれば良いか？
但し，移動は２枚の１０円玉に接するように行わなければならず，５回移動後の新しい並びは最初の並びと一つの１０円玉も重ならないものとする。
４枚を５回の移動で新しい位置に移動するから，単純に考えると４5(=1024)回の虱潰し。だけどよく考えると移動先は以下のように複数考えられるのでそう単純ではない。
考え方としては以下のようになる。
4枚の10円玉の初期位置を設定する。
moveCoin( level) {
if( level > 4) { 10円玉の位置が水平で初期状態と重ならないならFind; }
4枚の10円玉の現在位置から次に置ける位置が限定されるのでそれを求める。
求まった全ての位置に4個の10円玉を順に割り当てる。新しい位置は既存の2つの10円玉に隣接しなければならない。
もし置けたら moveCoin( level+1);
}
これをプログラムすれば解が求まる。10円玉の位置を以下のような矩形上の位置と考える。例えば，[2,3]に置かれた10円玉に接する位置は以下の6通り。
これを4枚の10円玉について考えると移動可能な位置が求まる。２枚に接しなければならないので，移動先の廻りに２枚の１０円玉が存在することを確認する。
座標位置がマイナスになったりすると面倒なので，４枚の１０円玉の初期位置を[10,10]，[10,11]，[10,12]，[10,13]とする。
プログラムは以下のようになる。
ulong board[20][20]; // 10円玉を配置する盤
struct struct_coinpos { // 10円玉の位置
int m_irow, m_icol;
};
const int ncoins = 4; // 10円玉の個数
struct Coins {
struct_coinpos p[ncoins];
}; // 配置する10円玉
Coins first; // 最初の位置。最初の位置と5回移動した先の位置が重ならないことを確認するため
Coins history[10]; // 10円玉の移動の履歴
int numFind = 0; // 解の数
…中略…
void move( int level, Coins coins, int icoins, struct_coinpos& newpos)
{
coins.p[icoins] = newpos;
if( level > 4) {
// 横1列に並んでいたらOK
int irow = coins.p[0].m_irow;
for( int i=1; i< ncoins; i++) {
if( irow != coins.p[i].m_irow) return;
}
// 最初の位置と重ならない。
for( irow=0; irow < 20; irow++) for( int icol=0; icol< 20; icol++) board[irow][icol] = 0;
for( i=0; i< ncoins; i++) {
board[first.p[i].m_irow][first.p[i].m_icol]++;
board[coins.p[i].m_irow][coins.p[i].m_icol]++;
}
for( irow=0; irow < 20; irow++) for( int icol=0; icol< 20; icol++) if(board[irow][icol] > 1) return;
history[level] = coins;
print_history( level);
return;
}
find( level, coins);
}
void find( int level, Coins coins)
{
struct_coinpos pos[30]; // 4個の10円玉の廻りに6箇所置き場所があるので次に移動できる位置は最大でも24箇所
history[level] = coins; // 移動手順を出力するため現在位置を記録する
int numpos = coins_getpos( pos, coins); // 4つの10円玉を置ける場所を探す
// 4つの10円玉を実際に新しい位置に置く。
for( int i=0; i< ncoins; i++) {
for( int j=0; j< numpos; j++) {
if( coin_is_setnewpos( pos, j, coins, i)) { // 10円玉を新しい位置に配置できるか?
move( level+1, coins, i, pos[j]); // 配置できるなら移動する
}
}
}
}
int main( int argc, cstring argv[])
{
ProcTime pt;
Coins coins;
coins_init( coins); // 10円玉の初期位置を設定する
first = coins; // 初期位置を記録する
find( 0/*level*/, coins); // 探す
pt.end();
ps( "%d 件，%g 秒\n", numFind, pt.sec());
return 0;
}
答えは16件出力されますが，上に移動する分と下に移動する分が上下対象なので実質8件。それも左右対称なので，実質4件てことかな。
結果は何番目の10円玉がどこに移動したか座標位置を出力するだけなので非常に判りづらい。しかも下駄を履かせて[10,10]の位置からなので更に判りづらくなっている。
最初10円玉の位置を以下のように宣言してひどい目に遭った。
typedef struct_coins Coins[4];
ローカルに宣言するときはよいけど，引数で渡すと値のコピーが作られるのでなく，アドレスが渡されてしまうので…
これに気づくのに結構時間が掛かってしまった。
最近ダイエットペプシを飲む量が極端に減り代わりにコーヒーを飲むようになった。
以前は実家に帰ったときと「眠っちゃいけない」って時だけしか飲まなかった。
最初のうちは眠気が飛んだけど，最近はコーヒーばかり飲んでいるので眠気は関係なくなってしまった。
本当に寝ちゃいけないとき何を飲むようにしたら良いんだ。
解速度
即(0.4秒)