9月2日
正しい結果と間違った結果のtop,left,bottom,rightの値を比較してみる。
間違った結果の方が数が多いので、間違っている方だけsymmetryOpsを突破しているものを抽出して見た。
sym:2:t0:2,t1:5,l0:6,l1:3,b0:3,b1:0,r0:3,r1:5
sym:2:t0:2,t1:6,l0:3,l1:1,b0:2,b1:7,r0:1,r1:3
sym:2:t0:2,t1:6,l0:3,l1:1,b0:2,b1:7,r0:1,r1:5
sym:2:t0:2,t1:6,l0:3,l1:1,b0:3,b1:7,r0:1,r1:5
sym:2:t0:2,t1:6,l0:4,l1:1,b0:2,b1:7,r0:1,r1:5
sym:2:t0:2,t1:6,l0:4,l1:1,b0:4,b1:7,r0:1,r1:4
sym:2:t0:2,t1:6,l0:4,l1:1,b0:4,b1:7,r0:1,r1:5
sym:2:t0:2,t1:6,l0:6,l1:1,b0:3,b1:0,r0:3,r1:5
sym:2:t0:3,t1:1,l0:5,l1:2,b0:3,b1:7,r0:1,r1:6
sym:2:t0:3,t1:6,l0:5,l1:1,b0:3,b1:7,r0:1,r1:4
試しにクイーンの配置を出力してみると
7 6 5 4 3 2 1 0
=============================
0| 00000100
1| 00100000
2| 00000010
3| 01000000
4| 00000001
5| 00000000
6| 10000000
7| 00010000
6で左端にクイーンが置かれているが、これだと時計回りに90度回転すると、1行目のクイーンの位置が右から2列目になる。
1行目のクイーンの配置は右から3列目なので最小にならない。
下部サイド枝刈りが機能していれば6,7の両端にクイーンは置けない。
7 6 5 4 3 2 1 0
=============================
0| 00000100
1| 00100000
2| 00000010
3| 01000000
4| 00000001
5| 00000000
6| x000000x
7| x001000x
これは下部サイド枝刈りで枝刈りされているはずなのにうまく機能していない模様
//【枝刈り】下部サイド枝刈り
}else if(row==BOUND2) {
//printf("sidemask:row:%d BOUND2:%d SIDEMASK:%ld down:%ld\n",row,BOUND2,SIDEMASK,down);
if((down&SIDEMASK)==0){
//printf("eda_1\n");
return;
}
if((down&SIDEMASK)!=SIDEMASK){
//printf("eda_2\n");
//printf("before:%ld",bitmap);
bitmap&=SIDEMASK;
//printf("after:%ld",bitmap);
}
調べたところ、5(row==BOUND2)でクイーンを置かない場合に下部サイド枝刈りが効いていないようだ。
クイーンを置かないで飛ばした場合も下部サイド枝刈りが効くようにする必要がある。
row>BOUND2の時はSIDEMASK(両端)にクイーンを置けないように修正した。
}else if(row > BOUND2){
bitmap&=~SIDEMASK;
}
N12まで数はあったがN13以降逆に少なくなったので調査することにする。
６．CPUR 再帰 バックトラック＋ビットマップ
N: Total Unique hh:mm:ss.ms
4: 2 1 0.00
5: 10 2 0.00
6: 4 1 0.00
7: 40 6 0.00
8: 92 12 0.00
9: 352 46 0.00
10: 724 92 0.00
11: 2680 341 0.01
12: 14200 1788 0.02
13: 73696 9235 0.10
14: 365564 45767 0.42
15: 2278976 285069 2.11
16: 14771576 1847308 12.39
17: 95809192 11978642 1:22.17
