はじめに
テンヨーの「CHECKER PUZZLE」というパズルをプログラムで問く、という話のまとめです。
入手したのは1980年代で、親戚からもらったような気がします。
ケースの裏には、8x8に収め、かつチェス盤模様にする解は「２通り」しかないと、書かれています。
幸運にも、当時小学生だった自分がそのうちの１つの解を見つけました。
冒頭の図、左の解です。
ケースの裏には、回答を入手する方法が書かれているのですが、郵送する大事な部分は切り取られたあとでした。多分親戚が使ったのでしょう。
それから、ずっと35年?くらい、もう一つの解はなんだろう？と気になっていました。
で、プログラムで問いてみようと思って、うまくいったので、記念に投稿します。
環境
Processing 4
Mac M1 Pro
条件
まず、ピースは１３種類あり、１つのピースは５つの正方形でできています。
そのうち、１ピースは４つの正方形でできた、正方形のピースです。
こんな式が成り立ちます。
12x5+4 = 64 = 8x8
またピースは２色で塗り分けられており、ピースをどこにでも置けるわけではありません。
よって、単に8x8マスに収めるよりも、ずっと条件は絞られます。
計算量はどのくらいか。
下の図のように、置ける場所をすべて挙げてみました。
そして、掛け算してみると、
約34794636387116000000000通り
という、結果になりました。この中から、２つの解を探します。
大きい数字です。解けるか不安です。
プログラムを掲載する前に、どのようにデータを保持して、計算するか、前提となる話をします。
データの持ち方
なんとなく、bit演算が速そうだというイメージで、盤面が64マスであることもあり、１つのピースの置き方１パターンを、long(64bit)で表すことにしました。例えば、長いピースは次のように定義します。
long I = 0b11111000_00000000_00000000_00000000_00000000_00000000_00000000_00000000L;
これは、以下のようなイメージで、ピースが左上にあることを意味します。
| 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
計算方法
ピースを置く操作はビット演算の|を使います。
long I = 0b11111000_00000000_00000000_00000000_00000000_00000000_00000000_00000000L;
long K = 0b00000111_00000001_00000001_00000000_00000000_00000000_00000000_00000000L;
print(Long.toBinaryString(I|K));
1111111100000001000000010000000000000000000000000000000000000000
一度置いたピースを取り除くにはビット演算の^を使います。
long I = 0b11111000_00000000_00000000_00000000_00000000_00000000_00000000_00000000L;
long K = 0b00000111_00000001_00000001_00000000_00000000_00000000_00000000_00000000L;
print(Long.toBinaryString(I|K^K));
1111100000000000000000000000000000000000000000000000000000000000
また、ピース同士が重なってしまう場合、ビット演算の&の結果が０にならない、という性質もあります。
long I = 0b11111000_00000000_00000000_00000000_00000000_00000000_00000000_00000000L;
long K = 0b11100000_10000000_10000000_00000000_00000000_00000000_00000000_00000000L;
print(Long.toBinaryString(I&K));
1110000000000000000000000000000000000000000000000000000000000000
最終的に、64個、すべてのbitが1になっていれば、正解ということになります。
プログラム
コードの99%が、ピースの置きパターンの定義です。
表示が重くなるので、文字の色つけは、やめました。
long[] I = new long[32];
long[] X = new long[16];
long[] C = new long[72];
long[] P = new long[82];
long[] F = new long[68];
long[] J = new long[68];
long[] W = new long[68];
long[] S = new long[34];
long[] Z = new long[66];
long[] T = new long[68];
long[] K = new long[72];
long[] E = new long[68];
long[] O = new long[49];
void setup(){
I[0] = 0b11111000_00000000_00000000_00000000_00000000_00000000_00000000_00000000L;
I[1] = I[0]>>>2;
I[2] = I[1]>>>7;
I[3] = I[2]>>>2;
I[4] = I[3]>>>5;
I[5] = I[4]>>>2;
I[6] = I[5]>>>7;
I[7] = I[6]>>>2;
I[8] = I[7]>>>5;
I[9] = I[8]>>>2;
I[10] = I[9]>>>7;
I[11] = I[10]>>>2;
I[12] = I[11]>>>5;
I[13] = I[12]>>>2;
I[14] = I[13]>>>7;
I[15] = I[14]>>>2;
I[16] = 0b10000000_10000000_10000000_10000000_10000000_00000000_00000000_00000000L;
I[17] = I[16]>>>2;
I[18] = I[17]>>>2;
I[19] = I[18]>>>2;
I[20] = I[19]>>>3;
I[21] = I[20]>>>2;
I[22] = I[21]>>>2;
I[23] = I[22]>>>2;
I[24] = I[23]>>>1;
I[25] = I[24]>>>2;
I[26] = I[25]>>>2;
I[27] = I[26]>>>2;
I[28] = I[27]>>>3;
I[29] = I[28]>>>2;
I[30] = I[29]>>>2;
I[31] = I[30]>>>2;
X[0] = 0b00100000_01110000_00100000_00000000_00000000_00000000_00000000_00000000L;
X[1] = X[0]>>>2;
X[2] = X[1]>>>5;
X[3] = X[2]>>>2;
X[4] = X[3]>>>2;
X[5] = X[4]>>>5;
X[6] = X[5]>>>2;
X[7] = X[6]>>>2;
X[8] = X[7]>>>3;
X[9] = X[8]>>>2;
X[10] = X[9]>>>2;
X[11] = X[10]>>>5;
X[12] = X[11]>>>2;
X[13] = X[12]>>>2;
X[14] = X[13]>>>5;
X[15] = X[14]>>>2;
C[0] = 0b11000000_10000000_11000000_00000000_00000000_00000000_00000000_00000000L;
C[1] = C[0]>>>2;
C[2] = C[1]>>>2;
C[3] = C[2]>>>5;
C[4] = C[3]>>>2;
C[5] = C[4]>>>2;
C[6] = C[5]>>>3;
C[7] = C[6]>>>2;
C[8] = C[7]>>>2;
C[9] = C[8]>>>5;
C[10] = C[9]>>>2;
C[11] = C[10]>>>2;
C[12] = C[11]>>>3;
C[13] = C[12]>>>2;
C[14] = C[13]>>>2;
C[15] = C[14]>>>5;
C[16] = C[15]>>>2;
C[17] = C[16]>>>2;
C[18] = 0b11100000_10100000_00000000_00000000_00000000_00000000_00000000_00000000L;
C[19] = C[18]>>>2;
C[20] = C[19]>>>2;
C[21] = C[20]>>>5;
C[22] = C[21]>>>2;
C[23] = C[22]>>>2;
C[24] = C[23]>>>3;
C[25] = C[24]>>>2;
C[26] = C[25]>>>2;
C[27] = C[26]>>>5;
C[28] = C[27]>>>2;
C[29] = C[28]>>>2;
C[30] = C[29]>>>3;
C[31] = C[30]>>>2;
C[32] = C[31]>>>2;
C[33] = C[32]>>>5;
C[34] = C[33]>>>2;
C[35] = C[34]>>>2;
C[36] = 0b00000000_10100000_11100000_00000000_00000000_00000000_00000000_00000000L;
C[37] = C[36]>>>2;
C[38] = C[37]>>>2;
C[39] = C[38]>>>5;
C[40] = C[39]>>>2;
C[41] = C[40]>>>2;
C[42] = C[41]>>>3;
C[43] = C[42]>>>2;
C[44] = C[43]>>>2;
C[45] = C[44]>>>5;
C[46] = C[45]>>>2;
C[47] = C[46]>>>2;
C[48] = C[47]>>>3;
C[49] = C[48]>>>2;
C[50] = C[49]>>>2;
C[51] = C[50]>>>5;
C[52] = C[51]>>>2;
C[53] = C[52]>>>2;
C[54] = 0b01100000_00100000_01100000_00000000_00000000_00000000_00000000_00000000L;
C[55] = C[54]>>>2;
C[56] = C[55]>>>2;
C[57] = C[56]>>>5;
C[58] = C[57]>>>2;
C[59] = C[58]>>>2;
C[60] = C[59]>>>3;
C[61] = C[60]>>>2;
C[62] = C[61]>>>2;
C[63] = C[62]>>>5;
C[64] = C[63]>>>2;
C[65] = C[64]>>>2;
C[66] = C[65]>>>3;
C[67] = C[66]>>>2;
C[68] = C[67]>>>2;
C[69] = C[68]>>>5;
C[70] = C[69]>>>2;
C[71] = C[70]>>>2;
P[0] = 0b11000000_11100000_00000000_00000000_00000000_00000000_00000000_00000000L;
P[1] = P[0]>>>2;
P[2] = P[1]>>>2;
P[3] = P[2]>>>5;
P[4] = P[3]>>>2;
P[5] = P[4]>>>2;
P[6] = P[5]>>>3;
P[7] = P[6]>>>2;
P[8] = P[7]>>>2;
P[9] = P[8]>>>5;
P[10] = P[9]>>>2;
P[11] = P[10]>>>2;
P[12] = P[11]>>>3;
P[13] = P[12]>>>2;
P[14] = P[13]>>>2;
P[15] = P[14]>>>5;
P[16] = P[15]>>>2;
P[17] = P[16]>>>2;
P[18] = P[17]>>>3;
P[19] = P[18]>>>2;
P[20] = P[19]>>>2;
P[21] = 0b01100000_01100000_01000000_00000000_00000000_00000000_00000000_00000000L;
P[22] = P[21]>>>2;
P[23] = P[22]>>>2;
P[24] = P[23]>>>3;
P[25] = P[24]>>>2;
P[26] = P[25]>>>2;
P[27] = P[26]>>>2;
P[28] = P[27]>>>3;
P[29] = P[28]>>>2;
P[30] = P[29]>>>2;
P[31] = P[30]>>>3;
P[32] = P[31]>>>2;
P[33] = P[32]>>>2;
P[34] = P[33]>>>2;
P[35] = P[34]>>>3;
P[36] = P[35]>>>2;
P[37] = P[36]>>>2;
P[38] = P[37]>>>3;
P[39] = P[38]>>>2;
P[40] = P[39]>>>2;
P[41] = 0b01110000_00110000_01000000_00000000_00000000_00000000_00000000_00000000L;
P[42] = P[41]>>>2;
P[43] = P[42]>>>2;
P[44] = P[43]>>>3;
P[45] = P[44]>>>2;
P[46] = P[45]>>>2;
P[47] = P[46]>>>5;
P[48] = P[47]>>>2;
P[49] = P[48]>>>2;
P[50] = P[49]>>>3;
P[51] = P[50]>>>2;
P[52] = P[51]>>>2;
P[53] = P[52]>>>5;
P[54] = P[53]>>>2;
P[55] = P[54]>>>2;
P[56] = P[55]>>>3;
P[57] = P[56]>>>2;
P[58] = P[57]>>>2;
P[59] = P[58]>>>5;
P[60] = P[59]>>>2;
P[61] = P[60]>>>2;
P[62] = 0b00010000_00110000_00110000_00000000_00000000_00000000_00000000_00000000L;
P[63] = P[62]>>>2;
P[64] = P[63]>>>2;
P[65] = P[64]>>>3;
P[66] = P[65]>>>2;
P[67] = P[66]>>>2;
P[68] = P[67]>>>3;
P[69] = P[68]>>>2;
P[70] = P[69]>>>2;
P[71] = P[70]>>>2;
P[72] = P[71]>>>3;
P[73] = P[72]>>>2;
P[74] = P[73]>>>2;
P[75] = P[74]>>>3;
P[76] = P[75]>>>2;
P[77] = P[76]>>>2;
P[78] = P[77]>>>2;
P[79] = P[78]>>>3;
P[80] = P[79]>>>2;
P[81] = P[80]>>>2;
F[0] = 0b11110000_01000000_00000000_00000000_00000000_00000000_00000000_00000000L;
F[1] = F[0]>>>2;
F[2] = F[1]>>>2;
F[3] = F[2]>>>5;
F[4] = F[3]>>>2;
F[5] = F[4]>>>5;
F[6] = F[5]>>>2;
F[7] = F[6]>>>2;
F[8] = F[7]>>>5;
F[9] = F[8]>>>2;
F[10] = F[9]>>>5;
F[11] = F[10]>>>2;
F[12] = F[11]>>>2;
F[13] = F[12]>>>5;
F[14] = F[13]>>>2;
F[15] = F[14]>>>7;
F[16] = F[15]>>>2;
F[17] = 0b00100000_01100000_00100000_00100000_00000000_00000000_00000000_00000000L;
F[18] = F[17]>>>2;
F[19] = F[18]>>>2;
F[20] = F[19]>>>3;
F[21] = F[20]>>>2;
F[22] = F[21]>>>2;
F[23] = F[22]>>>2;
F[24] = F[23]>>>3;
F[25] = F[24]>>>2;
F[26] = F[25]>>>2;
F[27] = F[26]>>>3;
F[28] = F[27]>>>2;
F[29] = F[28]>>>2;
F[30] = F[29]>>>2;
F[31] = F[30]>>>3;
F[32] = F[31]>>>2;
F[33] = F[32]>>>2;
F[34] = 0b00100000_11110000_00000000_00000000_00000000_00000000_00000000_00000000L;
F[35] = F[34]>>>2;
F[36] = F[35]>>>7;
F[37] = F[36]>>>2;
F[38] = F[37]>>>5;
F[39] = F[38]>>>2;
F[40] = F[39]>>>2;
F[41] = F[40]>>>5;
F[42] = F[41]>>>2;
F[43] = F[42]>>>5;
F[44] = F[43]>>>2;
F[45] = F[44]>>>2;
F[46] = F[45]>>>5;
F[47] = F[46]>>>2;
F[48] = F[47]>>>5;
F[49] = F[48]>>>2;
F[50] = F[49]>>>2;
F[51] = 0b01000000_01000000_01100000_01000000_00000000_00000000_00000000_00000000L;
F[52] = F[51]>>>2;
F[53] = F[52]>>>2;
F[54] = F[53]>>>3;
F[55] = F[54]>>>2;
F[56] = F[55]>>>2;
F[57] = F[56]>>>2;
F[58] = F[57]>>>3;
F[59] = F[58]>>>2;
F[60] = F[59]>>>2;
F[61] = F[60]>>>3;
F[62] = F[61]>>>2;
F[63] = F[62]>>>2;
F[64] = F[63]>>>2;
F[65] = F[64]>>>3;
F[66] = F[65]>>>2;
F[67] = F[66]>>>2;
J[0] = 0b11110000_00010000_00000000_00000000_00000000_00000000_00000000_00000000L;
J[1] = J[0]>>>2;
J[2] = J[1]>>>2;
J[3] = J[2]>>>5;
J[4] = J[3]>>>2;
J[5] = J[4]>>>5;
J[6] = J[5]>>>2;
J[7] = J[6]>>>2;
J[8] = J[7]>>>5;
J[9] = J[8]>>>2;
J[10] = J[9]>>>5;
J[11] = J[10]>>>2;
J[12] = J[11]>>>2;
J[13] = J[12]>>>5;
J[14] = J[13]>>>2;
J[15] = J[14]>>>7;
J[16] = J[15]>>>2;
J[17] = 0b00100000_00100000_00100000_01100000_00000000_00000000_00000000_00000000L;
J[18] = J[17]>>>2;
J[19] = J[18]>>>2;
J[20] = J[19]>>>3;
J[21] = J[20]>>>2;
J[22] = J[21]>>>2;
J[23] = J[22]>>>2;
J[24] = J[23]>>>3;
J[25] = J[24]>>>2;
J[26] = J[25]>>>2;
J[27] = J[26]>>>3;
J[28] = J[27]>>>2;
J[29] = J[28]>>>2;
J[30] = J[29]>>>2;
J[31] = J[30]>>>3;
J[32] = J[31]>>>2;
J[33] = J[32]>>>2;
J[34] = 0b10000000_11110000_00000000_00000000_00000000_00000000_00000000_00000000L;
J[35] = J[34]>>>2;
J[36] = J[35]>>>7;
J[37] = J[36]>>>2;
J[38] = J[37]>>>5;
J[39] = J[38]>>>2;
J[40] = J[39]>>>2;
J[41] = J[40]>>>5;
J[42] = J[41]>>>2;
J[43] = J[42]>>>5;
J[44] = J[43]>>>2;
J[45] = J[44]>>>2;
J[46] = J[45]>>>5;
J[47] = J[46]>>>2;
J[48] = J[47]>>>5;
J[49] = J[48]>>>2;
J[50] = J[49]>>>2;
J[51] = 0b01100000_01000000_01000000_01000000_00000000_00000000_00000000_00000000L;
J[52] = J[51]>>>2;
J[53] = J[52]>>>2;
J[54] = J[53]>>>3;
J[55] = J[54]>>>2;
J[56] = J[55]>>>2;
J[57] = J[56]>>>2;
J[58] = J[57]>>>3;
J[59] = J[58]>>>2;
J[60] = J[59]>>>2;
J[61] = J[60]>>>3;
J[62] = J[61]>>>2;
J[63] = J[62]>>>2;
J[64] = J[63]>>>2;
J[65] = J[64]>>>3;
J[66] = J[65]>>>2;
J[67] = J[66]>>>2;
W[0] = 0b00110000_01100000_01000000_00000000_00000000_00000000_00000000_00000000L;
W[1] = W[0]>>>2;
W[2] = W[1]>>>2;
W[3] = W[2]>>>3;
W[4] = W[3]>>>2;
W[5] = W[4]>>>2;
W[6] = W[5]>>>5;
W[7] = W[6]>>>2;
W[8] = W[7]>>>2;
W[9] = W[8]>>>3;
W[10] = W[9]>>>2;
W[11] = W[10]>>>2;
W[12] = W[11]>>>5;
W[13] = W[12]>>>2;
W[14] = W[13]>>>2;
W[15] = W[14]>>>3;
W[16] = W[15]>>>2;
W[17] = W[16]>>>2;
W[18] = 0b01100000_00110000_00010000_00000000_00000000_00000000_00000000_00000000L;
W[19] = W[18]>>>2;
W[20] = W[19]>>>5;
W[21] = W[20]>>>2;
W[22] = W[21]>>>2;
W[23] = W[22]>>>5;
W[24] = W[23]>>>2;
W[25] = W[24]>>>2;
W[26] = W[25]>>>3;
W[27] = W[26]>>>2;
W[28] = W[27]>>>2;
W[29] = W[28]>>>5;
W[30] = W[29]>>>2;
W[31] = W[30]>>>2;
W[32] = W[31]>>>5;
W[33] = W[32]>>>2;
W[34] = 0b00010000_00110000_01100000_00000000_00000000_00000000_00000000_00000000L;
W[35] = W[34]>>>2;
W[36] = W[35]>>>2;
W[37] = W[36]>>>3;
W[38] = W[37]>>>2;
W[39] = W[38]>>>2;
W[40] = W[39]>>>5;
W[41] = W[40]>>>2;
W[42] = W[41]>>>2;
W[43] = W[42]>>>3;
W[44] = W[43]>>>2;
W[45] = W[44]>>>2;
W[46] = W[45]>>>5;
W[47] = W[46]>>>2;
W[48] = W[47]>>>2;
W[49] = W[48]>>>3;
W[50] = W[49]>>>2;
W[51] = W[50]>>>2;
W[52] = 0b01000000_01100000_00110000_00000000_00000000_00000000_00000000_00000000L;
W[53] = W[52]>>>2;
W[54] = W[53]>>>5;
W[55] = W[54]>>>2;
W[56] = W[55]>>>2;
W[57] = W[56]>>>5;
W[58] = W[57]>>>2;
W[59] = W[58]>>>2;
W[60] = W[59]>>>3;
W[61] = W[60]>>>2;
W[62] = W[61]>>>2;
W[63] = W[62]>>>5;
W[64] = W[63]>>>2;
W[65] = W[64]>>>2;
W[66] = W[65]>>>5;
W[67] = W[66]>>>2;
S[0] = 0b00110000_00100000_01100000_00000000_00000000_00000000_00000000_00000000L;
S[1] = S[0]>>>2;
S[2] = S[1]>>>2;
S[3] = S[2]>>>3;
S[4] = S[3]>>>2;
S[5] = S[4]>>>2;
S[6] = S[5]>>>5;
S[7] = S[6]>>>2;
S[8] = S[7]>>>2;
S[9] = S[8]>>>3;
S[10] = S[9]>>>2;
S[11] = S[10]>>>2;
S[12] = S[11]>>>5;
S[13] = S[12]>>>2;
S[14] = S[13]>>>2;
S[15] = S[14]>>>3;
S[16] = S[15]>>>2;
S[17] = S[16]>>>2;
S[18] = 0b01000000_01110000_00010000_00000000_00000000_00000000_00000000_00000000L;
S[19] = S[18]>>>2;
S[20] = S[19]>>>5;
S[21] = S[20]>>>2;
S[22] = S[21]>>>2;
S[23] = S[22]>>>5;
S[24] = S[23]>>>2;
S[25] = S[24]>>>2;
S[26] = S[25]>>>3;
S[27] = S[26]>>>2;
S[28] = S[27]>>>2;
S[29] = S[28]>>>5;
S[30] = S[29]>>>2;
S[31] = S[30]>>>2;
S[32] = S[31]>>>5;
S[33] = S[32]>>>2;
Z[0] = 0b00010000_00110000_00100000_00100000_00000000_00000000_00000000_00000000L;
Z[1] = Z[0]>>>2;
Z[2] = Z[1]>>>2;
Z[3] = Z[2]>>>3;
Z[4] = Z[3]>>>2;
Z[5] = Z[4]>>>2;
Z[6] = Z[5]>>>3;
Z[7] = Z[6]>>>2;
Z[8] = Z[7]>>>2;
Z[9] = Z[8]>>>2;
Z[10] = Z[9]>>>3;
Z[11] = Z[10]>>>2;
Z[12] = Z[11]>>>2;
Z[13] = Z[12]>>>3;
Z[14] = Z[13]>>>2;
Z[15] = Z[14]>>>2;
Z[16] = 0b01110000_00011000_00010000_00000000_00000000_00000000_00000000_00000000L;
Z[17] = Z[16]>>>2;
Z[18] = Z[17]>>>5;
Z[19] = Z[18]>>>2;
Z[20] = Z[19]>>>2;
Z[21] = Z[20]>>>5;
Z[22] = Z[21]>>>2;
Z[23] = Z[22]>>>5;
Z[24] = Z[23]>>>2;
Z[25] = Z[24]>>>2;
Z[26] = Z[25]>>>5;
Z[27] = Z[26]>>>2;
Z[28] = Z[27]>>>5;
Z[29] = Z[28]>>>2;
Z[30] = Z[29]>>>2;
Z[31] = Z[30]>>>5;
Z[32] = Z[31]>>>2;
Z[33] = 0b00010000_00010000_00110000_00100000_00000000_00000000_00000000_00000000L;
Z[34] = Z[33]>>>2;
Z[35] = Z[34]>>>2;
Z[36] = Z[35]>>>3;
Z[37] = Z[36]>>>2;
Z[38] = Z[37]>>>2;
Z[39] = Z[38]>>>3;
Z[40] = Z[39]>>>2;
Z[41] = Z[40]>>>2;
Z[42] = Z[41]>>>2;
Z[43] = Z[42]>>>3;
Z[44] = Z[43]>>>2;
Z[45] = Z[44]>>>2;
Z[46] = Z[45]>>>3;
Z[47] = Z[46]>>>2;
Z[48] = Z[47]>>>2;
Z[49] = 0b01100000_00111000_00000000_00000000_00000000_00000000_00000000_00000000L;
Z[50] = Z[49]>>>2;
Z[51] = Z[50]>>>5;
Z[52] = Z[51]>>>2;
Z[53] = Z[52]>>>2;
Z[54] = Z[53]>>>5;
Z[55] = Z[54]>>>2;
Z[56] = Z[55]>>>5;
Z[57] = Z[56]>>>2;
Z[58] = Z[57]>>>2;
Z[59] = Z[58]>>>5;
Z[60] = Z[59]>>>2;
Z[61] = Z[60]>>>5;
Z[62] = Z[61]>>>2;
Z[63] = Z[62]>>>2;
Z[64] = Z[63]>>>5;
Z[65] = Z[64]>>>2;
T[0] = 0b11100000_01000000_01000000_00000000_00000000_00000000_00000000_00000000L;
T[1] = T[0]>>>2;
T[2] = T[1]>>>2;
T[3] = T[2]>>>5;
T[4] = T[3]>>>2;
T[5] = T[4]>>>2;
T[6] = T[5]>>>3;
T[7] = T[6]>>>2;
T[8] = T[7]>>>2;
T[9] = T[8]>>>5;
T[10] = T[9]>>>2;
T[11] = T[10]>>>2;
T[12] = T[11]>>>3;
T[13] = T[12]>>>2;
T[14] = T[13]>>>2;
T[15] = T[14]>>>5;
T[16] = T[15]>>>2;
T[17] = 0b00001000_00111000_00001000_00000000_00000000_00000000_00000000_00000000L;
T[18] = T[17]>>>2;
T[19] = T[18]>>>5;
T[20] = T[19]>>>2;
T[21] = T[20]>>>2;
T[22] = T[21]>>>3;
T[23] = T[22]>>>2;
T[24] = T[23]>>>2;
T[25] = T[24]>>>5;
T[26] = T[25]>>>2;
T[27] = T[26]>>>2;
T[28] = T[27]>>>3;
T[29] = T[28]>>>2;
T[30] = T[29]>>>2;
T[31] = T[30]>>>5;
T[32] = T[31]>>>2;
T[33] = T[32]>>>2;
T[34] = 0b00010000_00010000_00111000_00000000_00000000_00000000_00000000_00000000L;
T[35] = T[34]>>>2;
T[36] = T[35]>>>5;
T[37] = T[36]>>>2;
T[38] = T[37]>>>2;
T[39] = T[38]>>>3;
T[40] = T[39]>>>2;
T[41] = T[40]>>>2;
T[42] = T[41]>>>5;
T[43] = T[42]>>>2;
T[44] = T[43]>>>2;
T[45] = T[44]>>>3;
T[46] = T[45]>>>2;
T[47] = T[46]>>>2;
T[48] = T[47]>>>5;
T[49] = T[48]>>>2;
T[50] = T[49]>>>2;
T[51] = 0b10000000_11100000_10000000_00000000_00000000_00000000_00000000_00000000L;
T[52] = T[51]>>>2;
T[53] = T[52]>>>2;
T[54] = T[53]>>>5;
T[55] = T[54]>>>2;
T[56] = T[55]>>>2;
T[57] = T[56]>>>3;
T[58] = T[57]>>>2;
T[59] = T[58]>>>2;
T[60] = T[59]>>>5;
T[61] = T[60]>>>2;
T[62] = T[61]>>>2;
T[63] = T[62]>>>3;
T[64] = T[63]>>>2;
T[65] = T[64]>>>2;
T[66] = T[65]>>>5;
T[67] = T[66]>>>2;
K[0] = 0b01110000_01000000_01000000_00000000_00000000_00000000_00000000_00000000L;
K[1] = K[0]>>>2;
K[2] = K[1]>>>2;
K[3] = K[2]>>>3;
K[4] = K[3]>>>2;
K[5] = K[4]>>>2;
K[6] = K[5]>>>5;
K[7] = K[6]>>>2;
K[8] = K[7]>>>2;
K[9] = K[8]>>>3;
K[10] = K[9]>>>2;
K[11] = K[10]>>>2;
K[12] = K[11]>>>5;
K[13] = K[12]>>>2;
K[14] = K[13]>>>2;
K[15] = K[14]>>>3;
K[16] = K[15]>>>2;
K[17] = K[16]>>>2;
K[18] = 0b01110000_00010000_00010000_00000000_00000000_00000000_00000000_00000000L;
K[19] = K[18]>>>2;
K[20] = K[19]>>>2;
K[21] = K[20]>>>3;
K[22] = K[21]>>>2;
K[23] = K[22]>>>2;
K[24] = K[23]>>>5;
K[25] = K[24]>>>2;
K[26] = K[25]>>>2;
K[27] = K[26]>>>3;
K[28] = K[27]>>>2;
K[29] = K[28]>>>2;
K[30] = K[29]>>>5;
K[31] = K[30]>>>2;
K[32] = K[31]>>>2;
K[33] = K[32]>>>3;
K[34] = K[33]>>>2;
K[35] = K[34]>>>2;
K[36] = 0b00010000_00010000_01110000_00000000_00000000_00000000_00000000_00000000L;
K[37] = K[36]>>>2;
K[38] = K[37]>>>2;
K[39] = K[38]>>>3;
K[40] = K[39]>>>2;
K[41] = K[40]>>>2;
K[42] = K[41]>>>5;
K[43] = K[42]>>>2;
K[44] = K[43]>>>2;
K[45] = K[44]>>>3;
K[46] = K[45]>>>2;
K[47] = K[46]>>>2;
K[48] = K[47]>>>5;
K[49] = K[48]>>>2;
K[50] = K[49]>>>2;
K[51] = K[50]>>>3;
K[52] = K[51]>>>2;
K[53] = K[52]>>>2;
K[54] = 0b01000000_01000000_01110000_00000000_00000000_00000000_00000000_00000000L;
K[55] = K[54]>>>2;
K[56] = K[55]>>>2;
K[57] = K[56]>>>3;
K[58] = K[57]>>>2;
K[59] = K[58]>>>2;
K[60] = K[59]>>>5;
K[61] = K[60]>>>2;
K[62] = K[61]>>>2;
K[63] = K[62]>>>3;
K[64] = K[63]>>>2;
K[65] = K[64]>>>2;
K[66] = K[65]>>>5;
K[67] = K[66]>>>2;
K[68] = K[67]>>>2;
K[69] = K[68]>>>3;
K[70] = K[69]>>>2;
K[71] = K[70]>>>2;
E[0] = 0b00010000_00110000_00011000_00000000_00000000_00000000_00000000_00000000L;
E[1] = E[0]>>>2;
E[2] = E[1]>>>5;
E[3] = E[2]>>>2;
E[4] = E[3]>>>2;
E[5] = E[4]>>>3;
E[6] = E[5]>>>2;
E[7] = E[6]>>>2;
E[8] = E[7]>>>5;
E[9] = E[8]>>>2;
E[10] = E[9]>>>2;
E[11] = E[10]>>>3;
E[12] = E[11]>>>2;
E[13] = E[12]>>>2;
E[14] = E[13]>>>5;
E[15] = E[14]>>>2;
E[16] = E[15]>>>2;
E[17] = 0b00010000_00111000_00100000_00000000_00000000_00000000_00000000_00000000L;
E[18] = E[17]>>>2;
E[19] = E[18]>>>5;
E[20] = E[19]>>>2;
E[21] = E[20]>>>2;
E[22] = E[21]>>>3;
E[23] = E[22]>>>2;
E[24] = E[23]>>>2;
E[25] = E[24]>>>5;
E[26] = E[25]>>>2;
E[27] = E[26]>>>2;
E[28] = E[27]>>>3;
E[29] = E[28]>>>2;
E[30] = E[29]>>>2;
E[31] = E[30]>>>5;
E[32] = E[31]>>>2;
E[33] = E[32]>>>2;
E[34] = 0b11000000_01100000_01000000_00000000_00000000_00000000_00000000_00000000L;
E[35] = E[34]>>>2;
E[36] = E[35]>>>2;
E[37] = E[36]>>>5;
E[38] = E[37]>>>2;
E[39] = E[38]>>>2;
E[40] = E[39]>>>3;
E[41] = E[40]>>>2;
E[42] = E[41]>>>2;
E[43] = E[42]>>>5;
E[44] = E[43]>>>2;
E[45] = E[44]>>>2;
E[46] = E[45]>>>3;
E[47] = E[46]>>>2;
E[48] = E[47]>>>2;
E[49] = E[48]>>>5;
E[50] = E[49]>>>2;
E[51] = 0b00100000_11100000_01000000_00000000_00000000_00000000_00000000_00000000L;
E[52] = E[51]>>>2;
E[53] = E[52]>>>2;
E[54] = E[53]>>>5;
E[55] = E[54]>>>2;
E[56] = E[55]>>>2;
E[57] = E[56]>>>3;
E[58] = E[57]>>>2;
E[59] = E[58]>>>2;
E[60] = E[59]>>>5;
E[61] = E[60]>>>2;
E[62] = E[61]>>>2;
E[63] = E[62]>>>3;
E[64] = E[63]>>>2;
E[65] = E[64]>>>2;
E[66] = E[65]>>>5;
E[67] = E[66]>>>2;
O[0] = 0b11000000_11000000_00000000_00000000_00000000_00000000_00000000_00000000L;
O[1] = O[0]>>>1;
O[2] = O[1]>>>1;
O[3] = O[2]>>>1;
O[4] = O[3]>>>1;
O[5] = O[4]>>>1;
O[6] = O[5]>>>1;
O[7] = O[6]>>>2;
O[8] = O[7]>>>1;
O[9] = O[8]>>>1;
O[10] = O[9]>>>1;
O[11] = O[10]>>>1;
O[12] = O[11]>>>1;
O[13] = O[12]>>>1;
O[14] = O[13]>>>2;
O[15] = O[14]>>>1;
O[16] = O[15]>>>1;
O[17] = O[16]>>>1;
O[18] = O[17]>>>1;
O[19] = O[18]>>>1;
O[20] = O[19]>>>1;
O[21] = O[20]>>>2;
O[22] = O[21]>>>1;
O[23] = O[22]>>>1;
O[24] = O[23]>>>1;
O[25] = O[24]>>>1;
O[26] = O[25]>>>1;
O[27] = O[26]>>>1;
O[28] = O[27]>>>2;
O[29] = O[28]>>>1;
O[30] = O[29]>>>1;
O[31] = O[30]>>>1;
O[32] = O[31]>>>1;
O[33] = O[32]>>>1;
O[34] = O[33]>>>1;
O[35] = O[34]>>>2;
O[36] = O[35]>>>1;
O[37] = O[36]>>>1;
O[38] = O[37]>>>1;
O[39] = O[38]>>>1;
O[40] = O[39]>>>1;
O[41] = O[40]>>>1;
O[42] = O[41]>>>2;
O[43] = O[42]>>>1;
O[44] = O[43]>>>1;
O[45] = O[44]>>>1;
O[46] = O[45]>>>1;
O[47] = O[46]>>>1;
O[48] = O[47]>>>1;
calc();
println("done");
println(millis());
}
void out(long l){
long n = l;
String bin = Long.toBinaryString(n);
while(bin.length()<64){//左の方の０がなくなるので補充
bin="0"+bin;
}
//書き出し
for(int i=0; i<64; i+=8){
println(bin.substring(i,i+8));
}
println();
}
//重なっていないならtrueを返す
boolean possible(long now, long add){
if((now&add)==0)
return true;
else
return false;
}
void calc(){
long sum=0;
for(int i=0; i<32; i++){
if(possible(sum,I[i])) {sum = sum|I[i];
for(int x=0; x<16; x++){
if(possible(sum,X[x])) {sum = sum|X[x];
for(int c=0; c<72; c++){
if(possible(sum,C[c])) {sum = sum|C[c];
for(int p=0; p<82; p++){
if(possible(sum,P[p])) {sum = sum|P[p];
for(int f=0; f<68; f++){
if(possible(sum,F[f])) {sum = sum|F[f];
for(int j=0; j<68; j++){
if(possible(sum,J[j])) {sum = sum|J[j];
for(int w=0; w<68; w++){
if(possible(sum,W[w])) {sum = sum|W[w];
for(int s=0; s<34; s++){
if(possible(sum,S[s])) {sum = sum|S[s];
for(int z=0; z<66; z++){
if(possible(sum,Z[z])) {sum = sum|Z[z];
for(int t=0; t<68; t++){
if(possible(sum,T[t])) {sum = sum|T[t];
for(int k=0; k<72; k++){
if(possible(sum,K[k])) {sum = sum|K[k];
for(int e=0; e<68; e++){
if(possible(sum,E[e])) {sum = sum|E[e];
for(int o=0; o<49; o++){
if(possible(sum,O[o])) {sum = sum|O[o];
out(sum);println(i+","+x+","+c+","+p+","+f+","+j+","+w+","+s+","+z+","+t+","+k+","+e+","+o);println();
sum = sum^O[o];}
}
sum = sum^E[e];}
}
sum = sum^K[k];}
}
sum = sum^T[t];}
}
sum = sum^Z[z];}
}
sum = sum^S[s];}
}
sum = sum^W[w];}
}
sum = sum^J[j];}
}
sum = sum^F[f];}
}
sum = sum^P[p];}
}
sum = sum^C[c];}
}
sum = sum^X[x];}
}
sum = sum^I[i];}
}
}
結果
以下の２つの結果が得られます。
この結果をもとにピースの配置を、わかりやすくしたものが、冒頭の画像です。
計算時間はおよそ16秒でした。
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0,14,35,18,50,23,11,2,1,19,3,43,28
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
22,9,20,18,30,0,63,21,35,49,9,16,7
まとめ
テンヨーのCHECKER PUZZLEをプログラムで解きました。力任せなプログラムで、全探索し、重なった場合はスキップ、16秒で無事に２つの解を得ました。
作者は35年前のコンピュータで問いているでしょうから、もっと工夫したプログラムだと思います。今は、正解を知りたいだけなので、高速化は狙いません。
2つしか解がないということがはっきりしたことと、長年の疑問であったもう一つの解を得ることができて、感動です。もう一つの解は、一番長いピースが、端ではなく真ん中の方にあるので、自力では、たどり着きにくそうに感じました。
類似のパズル
色違いで「迷宮入りのテーマ」というのもあるようです。（自分のは赤白です）
ネットの画像を見る限りでは「たった13コマで16146通り」あると書かれていますが、おそらくこれは、ピースを反転して使ってもOKなルールだとおもいます。（本稿のピースは、反転できません）また、中央に正方形のピースを置いた場合は「65通り」と記載されています。
備考
ビットが１の数を出す関数がありますが、使わなくても、書けたので、使いませんでした。
Long.bitCount(long l)
当たり前だが、模様を気にせず、8x8に収めるのは、もっとパターンが存在する。
そして、各ピースの紅白パターンも変わってくる。
その場合の、完全な配置回答数は、どのように変化するのだろうか。
３，４と増える場合もあるだろうし、１しかない場合もありうる。
このパズルの２通りというのが、どのような位置づけにあるのかは気になるところである。