１円玉，５円玉，１０円玉を組み合わせて12枚を５ｘ５の矩形に配置する。縦横斜めの合計金額が11円になるようするにはどうすれば良いか。
予め以下のように配置されている。
５ｘ５の矩形のうち空いている箇所は２２箇所だから，そこに３種類のコインを置くと，３２２(31,381,059,609)通り。
幾らコンピュータの性能が上がったからといってこの虱潰しは出来ません。
合計が11円だから10円は同じ行，列に置けない。5円と同じ行に置くと15円以上になるので，5円と同じ行にも置けない。
ということは10円を置けるのは以下の場所に限られる。
同様に５円玉を置ける場所も限定される(10円と同じ行，列には置けない)。
実は10円玉と5円玉を置いたとき，合計が10円にならなければダメである(5円玉1枚の行に残り1円玉を全部置いても11円にはならないので)。
よって以下のような虱潰しコードになる。
for( 10円玉を虱潰しで置く) {
10円玉が同じ行，列に2個置かれたらやり直し
for( 5円玉を虱潰しで置く) {
縦，横，名前の合計金額が10にならなければやり直し
ここに来るのは3通りのみ
}
}
全部で12枚置くので，1円玉を置ける枚数が5枚を下回ればダメなことが判る(各行の合計が10になっているはずだから1円玉は各行に1枚は必要)。
for( 10円玉を虱潰しで置く) {
10円玉が同じ行，列に2個置かれたらやり直し
for( 5円玉を虱潰しで置く) {
縦，横，名前の合計金額が10にならなければやり直し
1円玉を置ける枚数が5枚未満ならやり直し
ここに来るのは1通りのみ
}
}
5円玉と10円玉だけの絞り込みで1通りになりました。後は面倒なので1円玉を25箇所虱潰してしまう。
矩形に以下のように番号を振り，１０円玉，５円玉を置ける場所を以下のように番号で考える。
１０円玉がa，５円玉がb，１円玉がcで，各位置に配置すれば，その金額を設定する。位置21には10円玉が配置されているからa21=10になり，b5=5，c4=1である。
プログラムは以下のようになる。
#include "puzutl.h"
int main( int argc, cstring argv[])
{
int a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17,a18,a19,a20,a21,a22,a23,a24;
int b0,b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14,b15,b16,b17,b18,b19,b20,b21,b22,b23,b24;
int c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,c21,c22,c23,c24;
int acnt, bcnt, ccnt;
for( int a=0; a< 256; a++) {
a0=a1=a2=a3=a4=a5=a6=a7=a8=a9=a10=a11=a12=a13=a14=a15=a16=a17=a18=a19=a20=a21=a22=a23=a24=0;
acnt=1; a21=10;
if(a&1) { a2=10; acnt++;}
if(a&2) { a3=10; acnt++;}
if(a&4) { a12=10; acnt++;}
if(a&8) { a13=10; acnt++;}
if(a&16) { a14=10; acnt++;}
if(a&32) { a17=10; acnt++;}
if(a&64) { a18=10; acnt++;}
if(a&128) { a19=10; acnt++;}
if(a2+a3>11) continue;
if(a12+a13+a14>11) continue;
if(a17+a18+a19>11) continue;
if(a2+a12+a17>11) continue;
if(a3+a13+a18>11) continue;
if(a14+a19>11) continue;
for( int b=0; b< 16384; b++) {
b0=b1=b2=b3=b4=b5=b6=b7=b8=b9=b10=b11=b12=b13=b14=b15=b16=b17=b18=b19=b20=b21=b22=b23=b24=0;
bcnt=1; b5=5;
if(b&1) { b0=5; bcnt++;}
if(b&2) { b2=5; bcnt++;}
if(b&4) { b3=5; bcnt++;}
if(b&8) { b7=5; bcnt++;}
if(b&16) { b8=5; bcnt++;}
if(b&32) { b9=5; bcnt++;}
if(b&64) { b10=5; bcnt++;}
if(b&128) { b12=5; bcnt++;}
if(b&256) { b13=5; bcnt++;}
if(b&512) { b14=5; bcnt++;}
if(b&1024) { b15=5; bcnt++;}
if(b&2048) { b17=5; bcnt++;}
if(b&4096) { b18=5; bcnt++;}
if(b&8192) { b19=5; bcnt++;}
// 横
if(a0+a1+a2+a3+a4+b0+b1+b2+b3+b4!=10) continue;
if(a5+a6+a7+a8+a9+b5+b6+b7+b8+b9!=10) continue;
if(a10+a11+a12+a13+a14+b10+b11+b12+b13+b14!=10) continue;
if(a15+a16+a17+a18+a19+b15+b16+b17+b18+b19!=10) continue;
if(a20+a21+a22+a23+a24+b20+b21+b22+b23+b24!=10) continue;
// 縦
if(a0+a5+a10+a15+a20+b0+b5+b10+b15+b20!=10) continue;
if(a1+a6+a11+a16+a21+b1+b6+b11+b16+b21!=10) continue;
if(a2+a7+a12+a17+a22+b2+b7+b12+b17+b22!=10) continue;
if(a3+a8+a13+a18+a23+b3+b8+b13+b18+b23!=10) continue;
if(a4+a9+a14+a19+a24+b4+b9+b14+b19+b24!=10) continue;
// 斜め
if(a0+a6+a12+a18+a24+b0+b6+b12+b18+b24!=10) continue;
if(a4+a8+a12+a16+a20+b4+b8+b12+b16+b20!=10) continue;
if( 12-(acnt+bcnt) < 5) continue; // 各行又は列に最低一つの1が無ければならないので
for( int c=0; c< 33554432; c++) {
c0=c1=c2=c3=c4=c5=c6=c7=c8=c9=c10=c11=c12=c13=c14=c15=c16=c17=c18=c19=c20=c21=c22=c23=c24=0;
ccnt=1; c4=1;
if(c&1) { c0=1; ccnt++;}
if(c&2) { c1=1; ccnt++;}
if(c&4) { c2=1; ccnt++;}
if(c&8) { c3=1; ccnt++;}
if(c&64) { c6=1; ccnt++;}
if(c&128) { c7=1; ccnt++;}
if(c&256) { c8=1; ccnt++;}
if(c&512) { c9=1; ccnt++;}
if(c&1024) { c10=1; ccnt++;}
if(c&2048) { c11=1; ccnt++;}
if(c&4096) { c12=1; ccnt++;}
if(c&8192) { c13=1; ccnt++;}
if(c&16384) { c14=1; ccnt++;}
if(c&32768) { c15=1; ccnt++;}
if(c&65536) { c16=1; ccnt++;}
if(c&131072) { c17=1; ccnt++;}
if(c&262144) { c18=1; ccnt++;}
if(c&524288) { c19=1; ccnt++;}
if(c&1048576) { c20=1; ccnt++;}
if(c&4194304) { c22=1; ccnt++;}
if(c&8388608) { c23=1; ccnt++;}
if(c&16777216) { c24=1; ccnt++;}
if( acnt+bcnt+ccnt == 12) {
// 横
if(a0+a1+a2+a3+a4+b0+b1+b2+b3+b4+c0+c1+c2+c3+c4!=11) continue;
if(a5+a6+a7+a8+a9+b5+b6+b7+b8+b9+c5+c6+c7+c8+c9!=11) continue;
if(a10+a11+a12+a13+a14+b10+b11+b12+b13+b14+c10+c11+c12+c13+c14!=11) continue;
if(a15+a16+a17+a18+a19+b15+b16+b17+b18+b19+c15+c16+c17+c18+c19!=11) continue;
if(a20+a21+a22+a23+a24+b20+b21+b22+b23+b24+c20+c21+c22+c23+c24!=11) continue;
// 縦
if(a0+a5+a10+a15+a20+b0+b5+b10+b15+b20+c0+c5+c10+c15+c20!=11) continue;
if(a1+a6+a11+a16+a21+b1+b6+b11+b16+b21+c1+c6+c11+c16+c21!=11) continue;
if(a2+a7+a12+a17+a22+b2+b7+b12+b17+b22+c2+c7+c12+c17+c22!=11) continue;
if(a3+a8+a13+a18+a23+b3+b8+b13+b18+b23+c3+c8+c13+c18+c23!=11) continue;
if(a4+a9+a14+a19+a24+b4+b9+b14+b19+b24+c4+c9+c14+c19+c24!=11) continue;
// 斜め
if(a0+a6+a12+a18+a24+b0+b6+b12+b18+b24+c0+c6+c12+c18+c24!=11) continue;
if(a4+a8+a12+a16+a20+b4+b8+b12+b16+b20+c4+c8+c12+c16+c20!=11) continue;
// 同じ場所にコインがあったらやり直し
…Find…同じ解を出力しないようにする
}
}
}
}
return 0;
}
答えは1件出力されました。10円玉，5円玉のループで1件に絞り込まれるのは即ですが，1円を見つけるためのループで時間が掛かります。
解を出力するとき同じ解を出力しないようにしないと8件出力されてしまいます。人間が見ても同じ解だと直ぐに判りにくいので，出力する前に絞り込みます。
48時間ダイエット(2日に一度の食事)を続けているがこれ以上体重が減らない。まだまだ腹に肉が付いている。
4日に一度，3日に一度の食事の時もあったんだけど効果無し。恐るべし人体。
食事は基本が果物，納豆，なめこと豆腐のみそ汁だけなんだけど，その後お菓子を食べてしまうのが良くないか？
生活リズムを崩したら強烈なリバウンドが来そうだ。
解速度
PentiumIII500MHzで約13秒。