九连环格雷码游戏

格雷序号 341

格雷码 111111111

剩余 341

亮起的环都符合九连环规则，可以自由探索；需要时点“提示下一步”。

Formula trace

格雷码演算

G(m) = m xor (m >> 1)

xor 是按位异或；>> 是按位右移；m 是格雷序号

m >> 1

xor

m >> 1

xor

G(k) = G(k - 1) xor lowbit(k)

k 是本次递推所用的格雷序号；lowbit(k) 是 k 的二进制中最右侧的 1 所代表的值

当前 G

lowbit(k)

下一步 G

m = G xor (G >> 1) xor ... xor (G >> 8)

G 是当前格雷码；m 是当前格雷序号

得到 m

九连环的每个环只有“套上”和“解开”两种状态，可以写成一串 0/1。规则限制了每一步只能改变一个环，因此沿着标准解法前进时，状态序列正好形成格雷码：相邻两步只差一位。

右侧记录里的格雷码显示当前 9 个环的状态；“状态十进制”是把这 9 位状态直接当作二进制数换算出的值。上方的“格雷序号”则表示这个状态在标准格雷码解法序列中的位置。