Chinese Ring Variations

休日に遊びにきた子供夫婦の５歳の子供、つまり、孫が「これはずせる？」と持ってき たのが、このパズル。パズルに詳しいわけではないのですが、「Chinese Ring」 (日本 では九連環)のバリエーションらしいということにはすぐ気づいて、Gray Code で表現で きるシステマティックな操作で解けるはずと見たのはよいのですが、実際に Chinise Ring に触れたことがなかったので、自分で考えざるを得なくなりました。

このパズルの場合は二度手間をさせるように２組の「Chinese Ring」を左右に配置して ありますから、右と左を別々に外せば良いわけですが、外さなければならないリング鎖 の状態を

  鎖が支柱に引っかかっていたら「1」
  鎖が支柱から外れていたら「0」

この場合は左右それぞれ 5 桁の 2 進数で表現できて、初期状態が「10000」、外し終 えた状態が「00000」になりますから、とりあえず、00000 から 10000 まで、つまり、 2^5 = 32 個の Gray Code をプログラム

bin2gray(n)
{
  return n ^ (n >> 1);
}

  31 10000
  30 10001
  29 10011
  ..
   2 00011
   1 00001
   0 00000

とりあえずはコンピュータを使った(日本語の)カンニングで誤魔化しましたが、パズル を解く人は人間の頭だけでやるわけで、どうやるのか気になって、昔購入した Jerry Slocum, Jack Botermans の Puzzles Old and New とか Elwyn R. Berlekamp, John H. Conway, Richard K. Guy の WINING WAYS FOR YOUR MATHEMATICAL PLAYS など を見てみましたが、よくわかりません。

そこで、この際、もう少し考えることにして、いくつか試してみると、可能な操作が

1. /010*$/ <-> /110*$/
2. /0$/ <-> /1$/

つまりこの２つの組み合わせで解けるはずですが、いずれの操作も可逆で、 もとに戻らないためには、この２つを交互に使うしかありません。

そして、後者の規則は常に使えますから、最初のパターンが前者のとき、どちらを使うか が問題ですが、2 進表現のパターンを見ると、パリティで決まることに気づきます。つ まり、1 の個数が偶数なら前者の規則、奇数なら後者の規則を使えばよいわけです。

この方針で書いてみたのが下記の awk スクリプトで、結果は上記の Gray Code と一致 しますが、上記の場合は最終状態から戻るビット演算、下記の場合は初期状態から進む パターン処理となっていて、人間が使う場合は、下記のほうが楽だと思います。これな ら何も見ずに解けますから。

# Chinese Ring
# "1" means that the ring's retainer wire passes through the loop.
/usr/bin/awk '
BEGIN {
  solve("10000")
  exit 0
}
function solve(s,  n, i, k, t) {
  while ((n = chcount(s)) > 0) {
	printf "%3d %s\n", i++, s
	if (n % 2) {	# odd parity, /0$/ <-> /1$/
		k = length(s)
		s = substr(s, 1, k - 1) (substr(s, k) == "0" ? "1" : "0")
	}
	else {		# even parity
		if (match(s, /010*$/))
			t = "11"	# /010*$/ -> /110*$/
		else if (match(s, /110*$/))
			t = "01"	# /110*$/ -> /010*$/
		else
			print "algorithm error", s
		s = substr(s, 1, RSTART - 1) t substr(s, RSTART + 2)
	}
  }
  printf "%3d %s\n", i, s
  exit 0
}
function chcount(s,  a) {
  return split(s, a, "1") - 1
}
'

とりあえず、ここまで考えて終りにしましたが、パズルを解く人々は、もっと簡明な方 法を使っているのかもしれません。