15 Puzzle

はじめに

Annotation-2019-11-19-172428

まず、この15 パズルを解いてみよう。もし、簡単にできなかったら「Rosetta code の問題を BASIC-256で解く」から読んでほしい。

15パズル初心者は、こちらにある 15 パズル で難しさと並べ方を体験した後、BASIC-256 でコードを動かすとよい。

このパズルを解くために、Play[1] するための「ソースコード」と「データ」を準備しよう。

「ソースコード」と「データ」は、同じディレクトリーにおく。たとえば、デスクトップ。

*「データ」

15 9 0 13 14 11 10 8 1 4 7 5 6 12 3 2

この1行の数字列を、メモ帳でつくり、「15puzzle.dat」のファイル名でデスクトップに保存する。

*「ソースコード」

# 15puzzle_new.kbs - slide the tiles to get them back in order
# this is a conversion from the old gosub to the new function/subroutines
# 2012-10-06 j.m.reneau
# modified by m.s

fastgraphics

global zx, zy, bw, xw, yw

nx = 4 # number of boxes in a row
ny = 4 # number of boxes in a column
dim board(nx, ny)
zx = 0 # position of the empty tile
zy = 0

bw = 5 # border width
xw = (graphwidth - ((nx+1)*bw)) / nx # calculate size of a box
yw = (graphheight - ((ny+1)*bw)) / ny

print "slide puzzle"
print "click on tile to slide.  try to get all tiles in order."

# call initialboard(ref(board))
# call drawboard(ref(board))
# call shuffle(ref(board))

open "15puzzle.dat"
r=0
c=0
do
 for c=0 to 3
  for r=0 to 3
   board[c,r] = read()
  next r
 next c
until eof()
close()
zx=0
zy=2
call drawboard(ref(board))

for i=0 to 3 
for j=0 to 3
print board[i,j];" ";
next j:next i:print

clickclear
moves = 0

print "click tile to move"
do
   # wait for click
   while clickb = 0
      pause .01
   end while
   cx = int(clickx/(xw+bw))
   if cx >= nx then cx = nx-1
   cy = int(clicky/(yw+bw))
   if cy >= ny then cy = ny-1
   clickclear
   # if a real click then make move
   if (zx = cx) or (zy = cy) then
      call makemove(ref(board), cx, cy)
      moves = moves + 1
      call drawboard(ref(board))
   end if
until isdone(ref(board))

print "Game Over - You solved it in "+ moves +"."

end

subroutine shuffle(ref(b))
   #for t = 1 to nx * ny * 10
   for t = 1 to 100
      x = zx
      y = zy
      r = int(rand*4)
      if r = 0 and x > 0 then x--
      if r = 1 and x < b[?,]-1 then x++
      if r = 2 and y > 0 then y--
      if r = 3 and y < b[,?]-1 then y++
      if x<>zx or y<> zy then
         b[zx, zy] = b[x, y]
         b[x, y] = 0
         zx = x
         zy = y
      end if
      call drawboard(ref(b))
      pause .01
   next t
end subroutine

subroutine makemove(ref(b),x,y)
   # shift cells
   if zx<>x then
      # row shift
      if x>zx then
         dx = 1
         dy = 0
      else
         dx = -1
         dy = 0
      end if
   else
      # column shift
      if y>zy then
         dx = 0
         dy = 1
      else
         dx = 0
         dy = -1
      end if
   end if
   # do shift
   while zx <> x or zy <> y
      b[zx, zy] = b[zx+dx, zy+dy]
      b[zx+dx, zy+dy] = 0
      zx += dx
      zy += dy
   end while
end subroutine

subroutine initialboard(ref(b))
   # setup the initial board array
   for x= 0 to b[?,]-1
      for y = 0 to b[,?]-1
         b[x, y] = (y*b[?,]+x+1)
      next y
   next x
   zx = b[?,]-1
   zy = b[,?]-1
   b[zx, zy] = 0
end subroutine

subroutine drawboard(ref(b))
   font "Tahoma", 24, 100
   clg
   color black
   rect 0, 0, graphwidth, graphheight
   for y = 0 to b[,?]-1
      for x = 0 to b[?,]-1
         cell =  b[x, y]
         color white
         rect (x+1)*bw+x*xw, (y+1)*bw+y*yw ,xw, yw
         
         if cell<> 0 then
            if zx = x or zy = y then
               color blue
            else
               color darkblue
            endif
            text (x+1)*bw+x*xw, (y+1)*bw+y*yw, cell
         end if
      next x
   next y
   refresh
end subroutine

function isdone(ref(b))
   # return 1 if we have solved the puzzle
   for x= 0 to b[?,]-1
      for y = 0 to b[,?]-1
         if b[x, y] <>  (y*b[?,]+x+1)  and (x <> zx or y <> zy) then
            isdone = false
            return
         end if
      next y
   next x
   isdone = true
end function

BASIC 256を起動し、上のコードを Program Editor にコピーし、デスクトップにファイル名「15puzzle」をつけて保存する。


  1. BASIC-256 で、この15パズルをプレイするやり方。「ソースコード」を Program Editor の画面に貼る。File メニューから Save を選び、適当なファイル名 15puzzle などをつけてデスクトップなどに保存する。「データ」はメモ帳で作成しファイル名をつけてデスクトップなどに保存する。BASIC-256のメニューで「Run」をクリックする。ゲームを中断するには、赤い四角「Stop」。 ↩︎

Rosetta code の問題を BASIC-256 で解く

もとの問題についての解説は、15 puzzle solver にある。

以下に、簡単に説明する。

「問題 1.」のように4行・4列の盤の16個ある目の上へ、「1」から「15」の数字の駒がランダムに並べてある。ただし、この並び方はランダムとはいっても一定のルールによって並べたものである。

初期配置、すなわち 1行目に 1,2,3,4を、2行目に 5,6,7,8を、そして最後の4行目に 13,14,15 を並べ、右下は空ける初期状態からスタートする。ルール(R)は、次のとおり。

駒を空いた所へ動かすルール(R)

Left  ... 左の駒を右へ
Up    ... 上の駒を下へ
Right ... 右の駒を左へ
Down  ... 下の駒を上へ

このルール(R)を乱数をつかって上下左右を選びながら何回か繰り返すと、ランダムに並べたような配列の盤ができる。繰返しの回数を増やすと、難易度の高いゲームになる。

ロゼッタコードでは、lurd のように先頭の小文字で表記している。

問題 1.

 15 14  1  6
  9 11  4 12
    10  7  3
 13  8  5  2

「問題 1.」で、盤上の 0 は、空白で表示した。

実際の盤上の並びを、空白で 0 から 15 までを区切り1行にしたデータファイルとして保存する。

15p15-9-0.dat

15 9 0 13 14 11 10 8 1 4 7 5 6 12 3 2

このファイル 15p15-9-0.dat を4行4列の盤上に並べ、表示するための
BASIC 256 のコードは次のようにし、配列 b(4,4) の各要素に数値を入れる。

15data.kbd

# file read
# examples for 15 puzzle
# 1 5 13 0 3 6 9 10 4 2 8 14 11 12 7 15
# 15 9 0 13 14 11 10 8 1 4 7 5 6 12 3 2
# 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 0
#
dim b(4,4)   # b[column, row]
open "15p1-5-9.dat"
r=0
c=0
do
 for c=0 to 3
  for r=0 to 3
   b[c,r] = read()
  next r
 next c
until eof()
close()

for c=0 to 3
 for r=0 to 3
   if b[r,c]=0 then
    print "   "; 
   else
    if b[r,c]>= 10 then
     print " ";b[r,c];
    else
     print "  ";b[r,c];
    end if
   end if
 next r
 print
next c

end

例えば、データ

1 5 13 0 3 6 9 10 4 2 8 14 11 12 7 15      .... (1)

が、BASIC 256 のグラフィック画面では次のようになる。

Annotation-2019-11-18-224004

このように1行で、盤面の配列を与え、それを解くソルバーを作る。

ロゼッタコードは、空白で数字を区切るやり方ではなく、10をAのように16進数で表現して詰めて並べているため、そのやり方に合わせることにする。

すると、(1)は

15D0369A428EBC7F

となる。実際のロゼッタコードでは、小文字で表記されている。それに合せると次のようになる。

15d0369a428ebc7f

練習問題 15パズルのデータをつくる

Annotation-2019-11-19-172428

データ 15p15-9-0.dat を Windows のメモ帳で作る。

15 9 0 13 14 11 10 8 1 4 7 5 6 12 3 2 

コード 15data.kbs を実行し、データ 15p15-9-0.dat を読み込ませ、 TextOutput に表示させる。


練習問題 データを16進数にする

次の「15パズルの問題をつくる」にあるコードを実行する。実行後、「Text Output」に出力された、盤の配列をロゼッタコードの 15パズルソルバー用に16進数に書き換えてみる。

例えば、データ 15p15-9-0.dat をロゼッタコードのように16進数表記にする。

15p15-9-0.dat

15 9 0 13 14 11 10 8 1 4 7 5 6 12 3 2

ヒント

ロゼッタコードは、1行目、2行目、...と横に読むから 15 14 1 6 9 11 ... をそれぞれ16進数表記にし詰める。

fe169b4c0a73d852

練習問題 15パズルの問題をつくる

BASIC-256 の example にある次のコードを使って、15 パズルの問題を作る。

# 15puzzle_new.kbs - slide the tiles to get them back in order
# this is a conversion from the old gosub to the new function/subroutines
# 2012-10-06 j.m.reneau
#
# modified by m.s

fastgraphics

global zx, zy, bw, xw, yw

nx = 4 # number of boxes in a row
ny = 4 # number of boxes in a column
dim board(nx, ny)
zx = 0 # position of the empty tile
zy = 0

bw = 5 # border width
xw = (graphwidth - ((nx+1)*bw)) / nx # calculate size of a box
yw = (graphheight - ((ny+1)*bw)) / ny

print "slide puzzle"
print "click on tile to slide.  try to get all tiles in order."

call initialboard(ref(board))
call drawboard(ref(board))
call shuffle(ref(board))
call drawboard(ref(board))

for i=0 to 3 
for j=0 to 3
print board[i,j];" ";
next j:next i:print

clickclear
moves = 0

print "click tile to move"
do
   # wait for click
   while clickb = 0
      pause .01
   end while
   cx = int(clickx/(xw+bw))
   if cx >= nx then cx = nx-1
   cy = int(clicky/(yw+bw))
   if cy >= ny then cy = ny-1
   clickclear
   # if a real click then make move
   if (zx = cx) or (zy = cy) then
      call makemove(ref(board), cx, cy)
      moves = moves + 1
      call drawboard(ref(board))
   end if
until isdone(ref(board))

print "Game Over - You solved it in "+ moves +"."

end

subroutine shuffle(ref(b))
   #for t = 1 to nx * ny * 10
   for t = 1 to 100
      x = zx
      y = zy
      r = int(rand*4)
      if r = 0 and x > 0 then x--
      if r = 1 and x < b[?,]-1 then x++
      if r = 2 and y > 0 then y--
      if r = 3 and y < b[,?]-1 then y++
      if x<>zx or y<> zy then
         b[zx, zy] = b[x, y]
         b[x, y] = 0
         zx = x
         zy = y
      end if
      call drawboard(ref(b))
      pause .01
   next t
end subroutine

subroutine makemove(ref(b),x,y)
   # shift cells
   if zx<>x then
      # row shift
      if x>zx then
         dx = 1
         dy = 0
      else
         dx = -1
         dy = 0
      end if
   else
      # column shift
      if y>zy then
         dx = 0
         dy = 1
      else
         dx = 0
         dy = -1
      end if
   end if
   # do shift
   while zx <> x or zy <> y
      b[zx, zy] = b[zx+dx, zy+dy]
      b[zx+dx, zy+dy] = 0
      zx += dx
      zy += dy
   end while
end subroutine

subroutine initialboard(ref(b))
   # setup the initial board array
   for x= 0 to b[?,]-1
      for y = 0 to b[,?]-1
         b[x, y] = (y*b[?,]+x+1)
      next y
   next x
   zx = b[?,]-1
   zy = b[,?]-1
   b[zx, zy] = 0
end subroutine

subroutine drawboard(ref(b))
   font "Tahoma", 24, 100
   clg
   color black
   rect 0, 0, graphwidth, graphheight
   for y = 0 to b[,?]-1
      for x = 0 to b[?,]-1
         cell =  b[x, y]
         color white
         rect (x+1)*bw+x*xw, (y+1)*bw+y*yw ,xw, yw
         
         if cell<> 0 then
            if zx = x or zy = y then
               color blue
            else
               color darkblue
            endif
            text (x+1)*bw+x*xw, (y+1)*bw+y*yw, cell
         end if
      next x
   next y
   refresh
end subroutine

function isdone(ref(b))
   # return 1 if we have solved the puzzle
   for x= 0 to b[?,]-1
      for y = 0 to b[,?]-1
         if b[x, y] <>  (y*b[?,]+x+1)  and (x <> zx or y <> zy) then
            isdone = false
            return
         end if
      next y
   next x
   isdone = true
end function

練習問題 マウスをつかって上の15パズルを人間が解く

駒をマウスでクリックすれば、その駒が空白の位置へ移動する。


15 puzzle を解くコード

問題 1.

 15 14  1  6
  9 11  4 12
    10  7  3
 13  8  5  2

をソルバーで解いてみる。

既存のソルバーを実行してみよう。
ロゼッタのThe Solverを実行した結果は、次のようになった。

C:\Users\...>15solver.exe
fe169b4c0a73d852
Solution(s) found in 00.00.00.153 seconds
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd         ...  (A)

The Solver のコードは、free pascal でコンパイルした。

C:\Users\...>fpc -v
Free Pascal Compiler version 3.0.4 [2017/10/06] for i386
Copyright (c) 1993-2017 by Florian Klaempfl and others

さてこの解(A)は、正しいのかどうか検証してみる。

ロゼッタには、52手による最適解が載っている。

練習問題

(A) と「52手による最適解」を比較してみよう。


15 Puzzle 関連リンク

15パズルと関連する解説

パズルを解くコード(Solver)

下記リンク先にあるロゼッタ・コードの15パズルを解くPhix のコードを実行する。

  1. PhixのDownloadをクリックする。

Imgur

  1. Linux または Windows から、Windows のラジオボタンをクリックし、インストーラをダウンロードする。

Imgur

  1. phix.0.7.9.setup.exe をダブルクリックする。
  2. インストーラの指示にしたがうと、実行プログラムは Program files (x86)\Phix フォルダにインストールされる。
  3. C:\Program Files (x86)\Phix\demo\rosetta フォルダにあるSolve15puzzle.exwが15パズルを解くコードである。
  4. C:\ ... > p ファイル