今回は Go 言語のビット操作について説明します。
Go 言語のビット演算子を下表に示します。
| 演算子 | 操作 |
|---|---|
| x & y | ビットごとの論理積 (AND) |
| x | y | ビットごとの論理和 (OR) |
| x ^ y | ビットごとの排他的論理和 (XOR) |
| ^y | ビットごとの否定 (NOT) |
| x &^ y | x AND (NOT y) |
| x << y | x を y ビット左シフト |
| x >> y | x を y ビット右シフト |
演算子 & はビットごとの論理積を返します。
5 & 3 => 1
0101
AND 0011
---------
0001
演算子 l はビットごとの論理和を返します。
5 | 3 => 7
0101
OR 0011
--------
0111
二項演算子 ^ はビットごとの排他的論理和を返します。
5 ^ 3 => 6
0101
XOR 0011
---------
0110
単項演算子 ^ はビットごとの論理的な否定を返します。
^1 => -2 ^0 => -1
x &^ y は x & (^y) を返します。
5 &^ 3 => 4
<<, >> はビットをシフトする演算子です。左シフトの場合、下位ビットには 0 が挿入されます。右シフトの場合、正の整数 (または無符号整数) では上位ビットに 0 が挿入されます。負の整数では 1 が挿入されます。これを「算術シフト」といいます。
1 << 8 => 256 1 << 16 => 65536 256 >> 8 => 1 65536 >> 8 => 256 -256 >> 8 => -1
それでは簡単な例題として、基本的なビット操作関数を作ってみましょう。次のリストを見てください。
リスト : 基本的なビット操作 (sample3201.go)
package main
import "fmt"
func testBit(x, n int) bool {
return x & (1 << n) != 0
}
func setBit(x, n int) int {
return x | (1 << n)
}
func clearBit(x, n int) int {
return x &^ (1 << n)
}
func main() {
fmt.Printf("%t\n", testBit(256, 7));
fmt.Printf("%t\n", testBit(256, 8));
fmt.Printf("%t\n", testBit(256, 9));
for i := 0; i < 8; i++ {
x := setBit(0, i)
fmt.Printf("%d\n", x)
fmt.Printf("%d\n", clearBit(x, i));
}
}
testBit は整数 x の n 番目のビットが 1 ならば true を返します。最下位 (LSB) のビットが 0 番目になります。int (64 bit) の場合、n は 0 から 63 になります。1 を n ビット左シフトして、x との論理積が 0 でなければ、n 番目のビットは 1 であることがわかります。
setBit は x の n 番目のビットを 1 にセットします。1 を n ビット左シフトして、x との論理和を計算すれば、n 番目のビットを 1 にすることができます。clearBit は x の n 番目のビットを 0 にクリアします。これは n 番目以外のビットを 1 に、n 番目のビットを 0 にして、それと x の論理積を計算すれば、n 番目のビットをクリアすることができます。1 を n ビット左シフトして、その否定を計算すると、n 番目のビット以外は 1 になります。Go 言語には演算子 &^ があるので簡単です。
それでは実際に試してみましょう。
$ go run sample3201.go false true false 1 0 2 0 4 0 8 0 16 0 32 0 64 0 128 0
組み合わせの生成は拙作のページ Yet Another Golang Problems 問題 19 で取り上げました。このほかに、n 個の中から m 個を選ぶ組み合わせは、ビットの 0, 1 で表すことができます。たとえば、5 個の数字 (0 - 4) から 3 個を選ぶ場合、数字を 0 番目 から 4 番目のビットに対応させます。すると、1, 3, 4 という組み合わせは 11010 と表すことができます。簡単な例題として、ビットを使って組み合わせを求めてみましょう。
組み合わせを求めるプログラムは次のようになります。
リスト : 組み合わせの生成 (sample3202.go)
package main
import "fmt"
func combSub(f func(int), n, m, a int) {
if m == 0 {
f(a)
} else if m == n {
f(a | ((1 << m) - 1))
} else {
combSub(f, n - 1, m, a)
combSub(f, n - 1, m - 1, a | (1 << (n - 1)))
}
}
func combinations(f func(int), n, m int) {
combSub(f, n, m, 0)
}
func main() {
combinations(func(x int) {fmt.Printf("%b\n", x)}, 5, 3)
}
関数 combinations は n 個の中から m 個を選ぶ組み合わせを生成して、引数の関数 f に渡します。実際の処理は関数 combSub で行います。組み合わせは引数 a にセットします。m が 0 になったら、組み合わせがひとつできたので f(a) を呼び出します。n が m と等しくなったならば、残り m 個を全て選びます。(1 << m) - 1 で m 個のビットをオンにして関数 f を呼び出します。
あとは combSub を再帰呼び出しします。最初の呼び出しは n 番目の数字を選ばない場合です。n - 1 個の中から m 個を選びます。次の呼び出しが n 番目の数字を選ぶ場合で、a の n - 1 番目のビットをオンにします。そして、n - 1 個の中から m - 1 個を選びます。
それでは 5 個の中から 3 個を選ぶ組み合わせの実行例を示します。
$ go run sample3202.go 111 1011 1101 1110 10011 10101 10110 11001 11010 11100
この場合、最小値は 111 (0x07)1) で最大値は 11100 (0x1c) になります。このように、combinations は組み合わせを表す数を昇順で出力します。
次は、N 通りある組み合わせに 0 から N - 1 までの番号を付ける方法を紹介しましょう。たとえば、6 個の中から 3 個を選ぶ組み合わせは 20 通りありますが、この組み合わせに 0 から 19 までの番号を付けることができます。1 1 1 0 0 0 を例題に考えてみましょう。次の図を見てください。
5 4 3 2 1 0
─────────
0 0 0 1 1 1 ↑
0 0 1 0 1 1 │
0 0 1 1 0 1 │
0 0 1 1 1 0 │
0 1 0 0 1 1 │
0 1 0 1 0 1 5Ｃ3 = 10 通り
0 1 0 1 1 0 │
0 1 1 0 0 1 │
0 1 1 0 1 0 │
0 1 1 1 0 0 ↓
─────────
1 0 0 0 1 1 ↑
1 0 0 1 0 1 │
1 0 0 1 1 0 │
1 0 1 0 0 1 4Ｃ2 = 6 通り
1 0 1 0 1 0 │
1 0 1 1 0 0 ↓
────────
1 1 0 0 0 1 ↑
1 1 0 0 1 0 3Ｃ1 = 3 通り
1 1 0 1 0 0 ↓
───────
1 1 1 0 0 0 19 番目
─────────
図 : 6Ｃ3 の組み合わせ
最初に 5 をチェックします。5 を選ばない場合は \({}_5 \mathrm{C}_3\) = 10 通りありますね。この組み合わせに 0 から 9 までの番号を割り当てることにすると、5 を選ぶ組み合わせの番号は 10 から 19 までとなります。
次に、4 をチェックします。4 を選ばない場合は、\({}_4 \mathrm{C}_2\) = 6 通りあります。したがって、5 を選んで 4 を選ばない組み合わせに 10 から 15 までの番号を割り当てることにすると、5 と 4 を選ぶ組み合わせには 16 から 19 までの番号となります。
最後に、3 をチェックします。同様に 3 を選ばない場合は 3 通りあるので、これに 16 から 18 までの番号を割り当て、5, 4, 3 を選ぶ組み合わせには 19 を割り当てます。これで組み合わせ 1 1 1 0 0 0 の番号を求めることができました。
では、0 0 0 1 1 1 はどうなるのでしょうか。左から順番にチェックしていくと、最初の 1 が見つかった時点で、その数字を選ばない組み合わせは存在しません。つまり、残りの数字をすべて選ぶしかないわけです。したがって、これが 0 番目となります。
このように、数字を選ぶときに、数字を選ばない場合の組み合わせの数を足し算していけば、その組み合わせの番号を求めることができるのです。
組み合わせを番号に変換するプログラムは次のようになります。
リスト : 組み合わせを番号に変換
// 組み合わせの数
func combNum(n, r int) int {
if n == r || r == 0 {
return 1
} else {
return combNum(n, r - 1) * (n - r + 1) / r
}
}
// 組み合わせを番号に変換
func combToNumSub(c, n, r, value int) int {
if r == 0 || n == r {
return value
} else if testBit(c, n - 1) {
return combToNumSub(c, n - 1, r - 1, value + combNum(n - 1, r))
} else {
return combToNumSub(c, n - 1, r, value)
}
}
func combToNum(c, n, r int) int {
return combToNumSub(c, n, r, 0)
}
関数 combNum は組み合わせの数を求めます。combToNum の引数 c はビットのオンオフで表した組み合わせ、引数 n と r は \({}_n \mathrm{C}_r\) の n と r を表しています。実際の処理は combToNumSub で行います。引数 value は求める番号を表します。n と r の値が同じになるか、もしくは r が 0 になれば、組み合わせの番号を計算できたので value を返します。
そうでない場合、c の n - 1 ビットの値を調べます。ビットがオンであれば、value に combNum(n - 1, r) の値を足し算し、r を -1 して combToNumSub を再帰呼び出しします。そうでなければ、value と r の値はそのままで combToNumSub を再帰呼び出しします。
逆に、番号から組み合わせを求めるプログラムも簡単に作ることができます。次のリストを見てください。
リスト : 番号を組み合わせに変換
// 番号を組み合わせに変換
func numToCombSub(value, n, r, c int) int {
if r == 0 {
return c
} else if n == r {
return c | ((1 << n) - 1)
} else {
k := combNum(n - 1, r)
if value >= k {
return numToCombSub(value - k, n - 1, r - 1, setBit(c, n - 1))
} else {
return numToCombSub(value, n - 1, r, c)
}
}
}
func numToComb(value, n, r int) int {
return numToCombSub(value, n, r, 0)
}
引数 value が番号で、引数 n と r は \({}_n \mathrm{C}_r\) の n と r を表しています。実際の処理は numToCombSub で行います。引数 c が求める組み合わせです。たとえば、n = 5, r = 3 の場合、ビットが 1 になるのは \({}_4 \mathrm{C}_2\) = 6 通りあり、0 になるのは \({}_4 \mathrm{C}_3\) = 4 通りあります。したがって、数値が 0 - 3 の場合はビットを 0 にし、4 - 9 の場合はビットを 1 にすればいいわけです。
ビットを 0 にした場合、残りは \({}_4 \mathrm{C}_3\) = 4 通りになるので、同様に次のビットを決定します。ビットを 1 にした場合、残りは \({}_4 \mathrm{C}_2\) = 6 通りになるので、value から 4 を引いて numToComb を再帰呼び出しして次のビットを決定します。
r が 0 の場合は、組み合わせが完成したので c を返します。n と r が等しい場合は、残りのビットをすべて 1 にセットしてから c を返します。それ以外の場合は、\({}_{n-1} \mathrm{C}_r\) の値を combNum(n - 1, r) で求めて変数 k にセットします。value が k 以上であれば変数 c のビットを 1 にセットし、value から k を引き算して numToCombSub を再帰呼び出しします。そうでなければ、numToCombSub を再帰呼び出しするだけです。
それでは、n = 5, r = 3 の場合の実行例を示します。
リスト : 簡単なテスト
func main() {
for i := 0; i < 10; i++ {
a := numToComb(i, 5, 3);
fmt.Printf("%d -> %d -> %d\n", i, a, combToNum(a, 5, 3))
}
}
$ go run sample3203.go 0 -> 7 -> 0 1 -> 11 -> 1 2 -> 13 -> 2 3 -> 14 -> 3 4 -> 19 -> 4 5 -> 21 -> 5 6 -> 22 -> 6 7 -> 25 -> 7 8 -> 26 -> 8 9 -> 28 -> 9
正常に動作していますね。この方法を使うと、n 個ある組み合わせの中の i 番目 (0 <= i < n) の組み合わせを簡単に求めることができます。
最も右側 (LSB 側) にある 1 を 0 にクリアする、逆に最も右側にある 0 を 1 にセットすることは簡単にできます。
(1) 右側にある 1 をクリア => x & (- x) x : 1 1 1 1 x - 1 : 1 1 1 0 ---------------- AND : 1 1 1 0 x : 1 0 0 0 x - 1 : 0 1 1 1 ---------------- AND : 0 0 0 0 (2) 右側にある 0 を 1 にセット => x | (x + 1) x : 0 0 0 0 x + 1 : 0 0 0 1 ---------------- OR : 0 0 0 1 x : 0 1 1 1 x - 1 : 1 0 0 0 ---------------- OR : 1 1 1 1
上図 (1) を見てください。x から 1 を引くと、右側から連続している 0 は桁借りにより 1 になり、最初に出現する 1 が 0 になります。したがって、x & (x - 1) を計算すると、最も右側にある 1 を 0 にクリアすることができます。(2) の場合、x に 1 を足すと、右側から連続している 1 は桁上がりにより 0 になり、最初に出現する 0 が 1 になります。x | (x + 1) を計算すれば、最も右側にある 0 を 1 にセットすることができます。
また、最も右側にある 1 を取り出すことも簡単にできます。簡単な例として 4 ビットの整数値を考えてみます。負の整数を 2 の補数で表した場合、4 ビットで表される整数は -8 から 7 になります。次の図を見てください。
0 : 0000
1 : 0001 -1 : 1111 1 & (-1) => 0001
2 : 0010 -2 : 1110 2 & (-2) => 0010
3 : 0011 -3 : 1101 3 & (-3) => 0001
4 : 0100 -4 : 1100 4 & (-4) => 0100
5 : 0101 -5 : 1011 5 & (-5) => 0001
6 : 0110 -6 : 1010 6 & (-6) => 0010
7 : 0111 -7 : 1001 7 & (-7) => 0001
-8 : 1000
図 : 最も右側にある 1 を取り出す方法
2 の補数はビットを反転した値 (1 の補数) に 1 を加算することで求めることができます。したがって、x と -x の論理積 x & (-x) は、最も右側にある 1 だけが残り、あとのビットはすべて 0 になります。
次は、ビットが 1 の個数を数える処理を作ってみましょう。データ型を uint とすると、プログラムは次のようになります。
リスト : ビットカウント
func bitCount(n uint) int {
c := 0
m := n
for m != 0 {
m &= m - 1
c++
}
return c
}
整数 n の右側から順番に 1 をクリアしていき、0 になるまでの回数を求めます。とても簡単ですね。32 個のビットを順番に調べるよりも高速です。
uint を 32 bit とする場合、次の方法で 1 の個数をもっと高速に求めることができます。
リスト : ビットカウント (2)
func bitCount1(n uint32) int {
a := (n & 0x55555555) + ((n >> 1) & 0x55555555)
b := (a & 0x33333333) + ((a >> 2) & 0x33333333)
c := (b & 0x0f0f0f0f) + ((b >> 4) & 0x0f0f0f0f)
d := (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff)
return (d & 0xffff) + (d >> 16)
}
最初に、整数を 2 bit ずつに分割して、1 の個数を求めます。たとえば、整数 n を 4 bit で考えてみましょう。5 を 2 進数で表すと 0101 になり、n と論理積を計算すると 0, 2 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。同様に n を 1 ビット右シフトして論理積を計算すると、1, 3 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。あとは、それを足し算すれば 2 bit の中にある 1 の個数を求めることができます。
変数 a には 2 ビットの中の 1 の個数が格納されています。左隣の 2 ビットの値を足し算すれば、4 ビットの中の 1 の個数を求めることができます。次に、左隣の 4 ビットの値を足し算して 8 ビットの中の 1 の個数を求め、左隣の 8 ビットの値を足し算して、というように順番に値を加算していくと 32 ビットの中にある 1 の個数を求めることができます。
bit_count は 1 の個数が多くなると遅くなりますが、bit_count1 は 1 の個数に関係なく高速に動作します。興味のある方は試してみてください。なお、Go 言語の標準ライブラリ math/bits にはビット操作用の関数が多数用意されています。ビットをカウントする関数 OnesCount もあります。興味のある方はリファレンス bits package をお読みください。
簡単な実行例を示します。
リスト : ビットカウント (sample3204.go)
package main
import (
"fmt"
"math/bits"
)
func bitCount(n uint) int {
c := 0
m := n
for m != 0 {
m &= m - 1
c++
}
return c
}
func bitCount1(n uint32) int {
a := (n & 0x55555555) + ((n >> 1) & 0x55555555)
b := (a & 0x33333333) + ((a >> 2) & 0x33333333)
c := (b & 0x0f0f0f0f) + ((b >> 4) & 0x0f0f0f0f)
d := (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff)
return int((d & 0xffff) + (d >> 16))
}
func main() {
for _, n := range []uint32 {0,1, 4-1, 8-1, 16-1, 256-1, 65536-1, (1<<31)-1} {
fmt.Printf("bitCount %x = %d\n", n, bitCount(uint(n)))
fmt.Printf("bitCount1 %x = %d\n", n, bitCount1(n))
fmt.Printf("OnesCount %x = %d\n", n, bits.OnesCount32(n))
}
}
$ go run sample3204.go bitCount 0 = 0 bitCount1 0 = 0 OnesCount 0 = 0 bitCount 1 = 1 bitCount1 1 = 1 OnesCount 1 = 1 bitCount 3 = 2 bitCount1 3 = 2 OnesCount 3 = 2 bitCount 7 = 3 bitCount1 7 = 3 OnesCount 7 = 3 bitCount f = 4 bitCount1 f = 4 OnesCount f = 4 bitCount ff = 8 bitCount1 ff = 8 OnesCount ff = 8 bitCount ffff = 16 bitCount1 ffff = 16 OnesCount ffff = 16 bitCount 7fffffff = 31 bitCount1 7fffffff = 31 OnesCount 7fffffff = 31
それでは、例題として Puzzel DE Programming で取り上げた「ライツアウト」というパズルを Go 言語で解いてみましょう。ライツアウトは光っているボタンをすべて消すことが目的のパズルです。ルールはとても簡単です。あるボタンを押すと、そのボタンと上下左右のボタンの状態が反転します。つまり、光っているボタンは消灯し消えていたボタンは点灯します。次の図を見てください。
□□□□□ □□□□□ ０ １ ２ ３ ４
□□□□□ □□■□□ ５ ６ ７ ８ ９
□□□□□ ─→ □■■■□ 10 11 12 13 14
□□□□□ □□■□□ 15 16 17 18 19
□□□□□ □□□□□ 20 21 22 23 24
（Ａ）中央のボタンを押した場合 （Ｂ）座標
図 : ライツアウトの点灯パターン
ボタンは 5 行 5 列に配置されています。上図のように、中央のボタン 12 を押すとそのボタンと上下左右のボタンの状態が反転します。ライツアウトはライトオン・オフの 2 種類の状態しかないので、盤面はリストよりもビットを使って表した方が簡単です。ライトオン・オフの状態を 1 と 0 で表し、各ビットとボタンの座標を対応させると、盤面は 0 から 33554431 の整数値で表すことができます。
ボタンを押してライトの状態を反転する処理も簡単です。たとえば、中央のボタン 12 を押した場合、7, 11, 12, 13, 17 のライトを反転させます。この場合、5 つのボタンのビットをオンにした値 0x23880 と、盤面を表す整数値の排他的論理和 (xor) を求めれば、5 つのライトの状態を反転することができます。次の例を見てください。
0 xor 0x23880 => 0x23880 % 消灯の状態でボタン 12 を押す（点灯する） #x23880 xor 0x23880 => 0 % もう一度同じボタンを押す（消灯する）
このように、ライツアウトは同じボタンを二度押すと元の状態に戻ります。したがって、同じボタンは二度押さなくてよいことがわかります。また、実際にボタンを押してみるとわかりますが、ボタンを押す順番は関係がないことがわかります。たとえば、ボタン 0 と 1 を押す場合、0 -> 1 と押すのも 1 -> 0 と押すのも同じ結果になります。
この 2 つの法則から、ボタンを押す組み合わせは全部で 2 ^ 25 通りになります。ライツアウトを解くいちばん単純な方法は、ボタンを押す組み合わせを生成して、実際にライトが全部消えるかチェックすることです。最近のパソコンは高性能で、Go 言語の実行速度も速いので、単純な方法でも簡単に解くことができます。
プログラムは次のようになります。
リスト : ライツアウトの解法
package main
import (
"fmt"
"math/bits"
)
// ボタンを押したときの反転パターン
var pattern []int = []int {
0x0000023, 0x0000047, 0x000008e, 0x000011c, 0x0000218,
0x0000461, 0x00008e2, 0x00011c4, 0x0002388, 0x0004310,
0x0008c20, 0x0011c40, 0x0023880, 0x0047100, 0x0086200,
0x0118400, 0x0238800, 0x0471000, 0x08e2000, 0x10c4000,
0x0308000, 0x0710000, 0x0e20000, 0x1c40000, 0x1880000,
}
// 組み合わせの生成
func combSub(f func(int), n, m, a int) {
if m == 0 {
f(a)
} else if m == n {
f(a | ((1 << m) - 1))
} else {
combSub(f, n - 1, m, a)
combSub(f, n - 1, m - 1, a | (1 << (n - 1)))
}
}
func combinations(f func(int), n, m int) {
combSub(f, n, m, 0)
}
// 解答の表示
func printAnswer(board int) {
for i, j := 0, 1; i < 25; i++ {
if board & j != 0 {
fmt.Printf("O ")
} else {
fmt.Printf(". ")
}
if (i + 1) % 5 == 0 {
fmt.Println("")
}
j <<= 1
}
fmt.Println("")
}
func check(board, x int) {
for m := x; m != 0; m &= m - 1 {
n := bits.TrailingZeros(uint(m))
board ^= pattern[n]
}
if board == 0 {
printAnswer(x)
}
}
func solver(board int) {
for i := 1; i <= 25; i++ {
fmt.Printf("----- %d -----\n", i)
combinations(func(x int) {check(board, x)}, 25, i)
}
}
func main() {
solver(0x1ffffff) // 全点灯パターン
}
関数 solver で関数 comnbinations を呼び出して、25 個の中から i 個のボタンを押す組み合わせを生成します。関数 check の引数 board が盤面を表し、引数 x が押すボタンの位置を表します。ボタンはビットの位置で表されているので、それを math/bits の関数 TrailingZeros で番号に変換します。
func TrailingZeros(x uint) int
TrailingZeros は引数 x の LSB 側の 0 の個数を返します。たとえば、3 番目のボタンの位置は 0b1000 なので、LSB 側の 0 の個数 (3) と同じになります。これでボタンの位置から番号 n を求めることができます。あとは board と pattern[n] の排他的論理和を求めれば、そのボタンを押したことになります。選んだボタンを全部押して board が 0 になれば関数 printAnswer で解を表示します。
あとは特に難しいところはないと思います。それでは実行してみましょう。ライトが全部点灯している状態 (0x1ffffff) を解いてみます。
$ go run lightsout.go ----- 1 ----- ----- 2 ----- ----- 3 ----- ----- 4 ----- ----- 5 ----- ----- 6 ----- ----- 7 ----- ----- 8 ----- ----- 9 ----- ----- 10 ----- ----- 11 ----- ----- 12 ----- ----- 13 ----- ----- 14 ----- ----- 15 ----- . O O . O . O O O . . . O O O O O . O O O O . . . . . . O O O O . O O O O O . . . O O O . O . O O . O O . . . O O . O O . . O O O . O O O . . O O . O O . O O . . O O O . O O O . . O O . O O . . . O O ----- 16 ----- ----- 17 ----- ----- 18 ----- ----- 19 ----- ----- 20 ----- ----- 21 ----- ----- 22 ----- ----- 23 ----- ----- 24 ----- ----- 25 -----
4 通りの解が出力されました。ボタンが全部点灯している場合、ボタンを押す回数はどの解も 15 回になります。実は、これがライツアウトの最長手数なのです。ライトの点灯パターンは 2 ^ 25 = 33554432 通りありますが、実際に解が存在するパターンは、その 1 / 4 の 8388608 通りしかありません。その中で最短回数が 15 回で解けるパターンは 7350 通りあり、そのうちのひとつがライトが全部点灯しているパターンなのです。
ライツアウトの最長手数に興味のある方は、Puzzle DE Programming:「ライツアウト - 最長手数を求める」をお読みくださいませ。
ライツアウトは次の図に示すように、ボタンを上から 1 行ずつ消灯していくという、わかりやすい方法で解くことができます。
ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ
１□■□■□ １□□□□□ １□□□□□ １□□□□□
２□□□□□ ２■■□■■ ２□□□□□ ２□□□□□
３□□□□□ ３□■□■□ ３□■□■□ ３□□□□□
４□□□□□ ４□□□□□ ４■■□■■ ４□□□□□
５□□□□□ ５□□□□□ ５□□□□□ ５□■□■□
（１） （２） （３） （４）
図 : 1 行ずつボタンを消灯していく方法
(1) では、1 行目のボタンが 2 つ点灯しています。このボタンを消すには、真下にある 2 行目の B と D のボタンを押せばいいですね。すると (2) の状態になります。次に、2 行目のボタンを消します。3 行目の A, B, D, E のボタンを押して (3) の状態になります。
あとはこれを繰り返して 4 行目までのボタンを消したときに、5 行目のボタンも全部消えていれば成功となります。(4) のように、5 行目のボタンが消えない場合は失敗です。この場合は、1 行目のボタンを押して、点灯パターンを変更します。
2 - 5 行目のボタンの押し方は、1 行目の点灯パターンにより決定されるので、けっきょく 1 行目のボタンの押し方により、解けるか否かが決まります。この場合、ボタンの押し方は、2 ^ 5 = 32 通りしかありせん。つまり、たった 32 通り調べるだけでライツアウトの解を求めることができるのです。
プログラムは次のようになります。
リスト : ライツアウトの高速化
func solver1(board int) {
for i := 0; i < 32; i++ {
b := board
p := 0
// 一行目を押す
for j := 0; j < 5; j++ {
if i & (1 << j) != 0 {
b ^= pattern[j]
p |= 1 << j
}
}
// 2 - 5 行目を消す
for j := 0; j < 20; j++ {
if b & (1 << j) != 0 {
b ^= pattern[j + 5]
p |= 1 << (j + 5)
}
}
if b == 0 {
printAnswer(p)
}
}
}
1 行目のボタンの押し方は 32 通りあるので、ボタンの押し方を 0 から 31 までの数値で表すことにします。値は 5 ビットで表すことができるので、ビットとボタンの位置を対応させて、ビットがオンであればそのボタンを押すことにします。盤面 board を変数 b にセットして、演算子 ^= で b の点灯パターンを変更します。押したボタンの位置は変数 p にセットします。
次は、1 行ずつ盤面 b のライトを消していきます。変数 j がチェックするボタンの位置を表します。b & (1 << j) で j の位置のビットを調べ、それがオンであればライトが点灯しいるので 1 行下のボタンを押します。押すボタンの位置は j + 5 で求めることができます。そして最後に盤面 b の値をチェックします。b が 0 であればライトが全部消えています。関数 printAnswer で解を出力します。
実行結果は同じなので省略させていただきます。興味のある方は試してみてください。なお、下記 URL によると、ライツアウトの解法は連立一次方程式を解くことに帰着させることができるそうです。
拙作のページ「お気楽 Numpy プログラミング超入門」や「Julia Programming: Puzzle DE Julia!!」でも連立方程式によるライツアウトの解法を取り上げています。よろしければお読みくださいませ。
ビットが 1 の個数を数える方法はフィンローダさんの「初級Ｃ言語Ｑ＆Ａ(15)」を参考にさせていただきました。フィンローダさんに感謝いたします。