はじめに
まず、この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」をつけて保存する。
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 のグラフィック画面では次のようになる。
このように1行で、盤面の配列を与え、それを解くソルバーを作る。
ロゼッタコードは、空白で数字を区切るやり方ではなく、10をAのように16進数で表現して詰めて並べているため、そのやり方に合わせることにする。
すると、(1)は
15D0369A428EBC7F
となる。実際のロゼッタコードでは、小文字で表記されている。それに合せると次のようになる。
15d0369a428ebc7f
練習問題 15パズルのデータをつくる
データ 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 関連リンク
- www.jaapsch.net : 解法もある
- 三姉妹 : 昔、道後のにぎたつ会館の窓際にあった人形をもとに作った絵並べ
- 15 Puzzle - code from Rosetta code : ロゼッタコードにあるソースコードをもとに制作したゲーム 何回でできるか？
１５パズルと関連する解説
パズルを解くコード(Solver)
下記リンク先にあるロゼッタ・コードの15パズルを解くPhix のコードを実行する。
- PhixのDownloadをクリックする。
- Linux または Windows から、Windows のラジオボタンをクリックし、インストーラをダウンロードする。
- phix.0.7.9.setup.exe をダブルクリックする。
- インストーラの指示にしたがうと、実行プログラムは Program files (x86)\Phix フォルダにインストールされる。
- C:\Program Files (x86)\Phix\demo\rosetta フォルダにあるSolve15puzzle.exwが１５パズルを解くコードである。
- C:\ ... > p ファイル