15パズルのパリティー

Programming Math Ruby

15パズルの状態は2つの集合にわけられ、片方からもう片方の状態に遷移することはない。

どちらの集合に所属しているかを、ある値で表現してみる。

15パズルの各部品に0から15の番号をつける。今回は、板は番号そのまま、穴は0とした。

また、15パズルの各位置にも同様の番号をつける。今回は左上から順番にした。

このとき、16x16の行列Mを考え、iの位置にjの部品があるときはM[i,j]=1、そうでなければM[i,j]=0とする。

このとき、行列値|M|が全体の並びのパリティーとなり、2つの部品の場所を逆にするとパリティーが反転する。

盤面を、チェス盤のように市松模様に塗りわける。これをそのまま穴の位置のパリティーとする。

2つのパリティーの排他的論理和(ここでは{-1,1}となる値にしたので、値の積でよい。)をとる。

それがそのまま全体のパリティーになる。

#!ruby

require "matrix"

def table_parity(tsize,table)
  #print table
  puts "given table is:"
  (0...tsize).each do|y|
    print "|"
    (0...tsize).each do|x|
      i = table[y*tsize+x]
      if i == 0 then
        print "[]"
      else
        print "%2d"%i
      end
      print "|"
    end
    puts
  end

  zeroindex = table.index(0)
  zerox = zeroindex % 4
  zeroy = zeroindex / 4
  zeropar = (zerox + zeroy) % 2 * 2 - 1

  mat_ary = (0...table.size).collect {|i|
    table.collect {|j|i==j ? 1 : 0 }
  }
  puts "parity is:"
  p Matrix[*mat_ary].determinant * zeropar
  puts
end

#zero means the "hole"
table_parity(4,
        [ 1, 2, 3, 4,
          5, 6, 7, 8,
          9,10,11,12,
         13,14,15, 0])
table_parity(5,
        [ 1, 2, 3, 4, 5,
          6, 7, 8, 9,10,
         11,12,13,14,15,
         16,17,18,19,20,
         21,22,23,24, 0])
table_parity(4, (0..15).sort_by{rand})

% ruby puzzle15.rb                                                                                                           2009/04/14 21:42:40 18318/pts/3
given table is:
| 1| 2| 3| 4|
| 5| 6| 7| 8|
| 9|10|11|12|
|13|14|15|[]|
parity is:
1

given table is:
| 1| 2| 3| 4| 5|
| 6| 7| 8| 9|10|
|11|12|13|14|15|
|16|17|18|19|20|
|21|22|23|24|[]|
parity is:
-1

given table is:
|14| 9|13| 3|
| 1| 8| 2|12|
| 4|11| 7| 5|
|10| 6|15|[]|
parity is:
1