概要
スライドパズル・15パズルの解法を試してみたいと思っています。
使用言語はpythonです。
ここで遊べます（リンクあり）。
空いているマスに、数字マスを移動させる事で1,2,3,・・・と順に並べることを目的とします。
完全ランダム
$20$回移動して、一致していなかったらさらに移動を繰り返します。
$100$セットごとに現状をprintします。
座標系
クラスの関数
move
slide.move(direction)
操作マスをdirectionの方向に動かす
direction =
0:上
1:右
2:下
3:左
とします。
shuffle
slide.shuffle(num)
num回、ランダムで移動する
結果
$10$分ほど回しましたが一致する事はありませんでした。
10105300times
[2, 7, 4, 1]
[3, 10, 8, 12]
[6, 5, 14, 15]
[0, 11, 9, 13]
10105400times
[0, 9, 2, 3]
[14, 1, 8, 7]
[13, 15, 11, 12]
[5, 10, 6, 4]
10105500times
[9, 10, 5, 6]
[15, 2, 13, 8]
[12, 7, 0, 1]
[4, 3, 11, 14]
実行プログラムは次のようになります。トグルなのでクリックして開いてみてください。
import random
import numpy as np # Numpyライブラリ
class Slide():
"""
0 が 操作マス
左上を原点とする
横に ｘ
縦に ｙ
トスル
"""
def __init__(self):
self.puzzle = [[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,0]]
self.x = 3
self.y = 3
def shuffle(self,num):
for i in range(num):
j=0
while True:
j = random.randint(0,3)
break
self.move(j)
def move(self,direction):
"""
0
3 1
2
"""
if direction == 0:
if self.y != 0:
if self.fixed[self.y-1][self.x] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y-1][self.x]
self.y = self.y - 1
self.puzzle[self.y][self.x] = 0
if direction == 1:
if self.x != 3:
if self.fixed[self.y][self.x+1] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x+1]
self.x = self.x + 1
self.puzzle[self.y][self.x] = 0
if direction == 2:
if self.y != 3:
if self.fixed[self.y+1][self.x] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y+1][self.x]
self.y = self.y + 1
self.puzzle[self.y][self.x] = 0
if direction == 3:
if self.x != 0:
if self.fixed[self.y][self.x-1] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x-1]
self.x = self.x - 1
self.puzzle[self.y][self.x] = 0
def check(self):
for i in range(4):
for j in range(4):
if self.puzzle[i][j] != j+1+i*4:
return -1
return 0
if __name__ == '__main__' :
hoge = Slide()
hoge.shuffle(500)
print(hoge.puzzle)
n=0
while True:
hoge.shuffle(20)
flag = hoge.check()
if flag == 0:
break
n=n+1
if n%100 == 0:
print(str(n)+"times")
print(hoge.puzzle[0])
print(hoge.puzzle[1])
print(hoge.puzzle[2])
print(hoge.puzzle[3])
print("find")
print(str(n) + "times")
print(hoge.puzzle)
一致している部分を固定しながら・ランダム
完全ランダムは流石に無理がありました。
次は正しい位置に移動できたマスから固定する方法を使います。
この方法には
固定されたコマに挟まれたコマは移動できなくなる
という問題があります。
そこで、
の順に完成させます。（ランダムで回し、成立したら固定し、次に行く）
この段階で、残りは左下4マスのみなので、ランダムでも解けます。
結果
かなり良くなりました。
shuffled puzzle
[11, 5, 2, 7]
[1, 6, 12, 14]
[0, 13, 9, 3]
[8, 15, 4, 10]
start analyze
3652times
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
[13, 14, 15, 0]
3652セット（3652*20回移動）で完成できました。完全ランダムだと、10105500セットを超えても完成しないので、かなりいいと思います。
何回かやりましたが、1秒もかかりませんが、セット数はまばらです。
(追記)コメントでより良いプログラムにしてもらったので変更しました。ありがとうございます。
クリックして開いてみてください。
import random
class Slide:
def __init__(self):
self.puzzle = [
[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9, 10, 11, 12],
[13, 14, 15, 0],
]
self.x = 3
self.y = 3
self.fixed = [False] * 16
def __iter__(self):
return iter(self.puzzle)
def shuffle(self, num):
DIRS = (0, -1), (1, 0), (0, 1), (-1, 0)
for _ in range(num):
dx, dy = random.choice(DIRS)
x = self.x + dx
y = self.y + dy
if 0 <= x <= 3 and 0 <= y <= 3 and not self.fixed[y * 4 + x]:
self.puzzle[self.y][self.x] = self.puzzle[y][x]
self.x = x
self.y = y
self.puzzle[self.y][self.x] = 0
def fix(self, numbers):
if all(self.fixed[number - 1] for number in numbers):
return True
if any(self.puzzle[(number - 1) // 4][(number - 1) % 4] != number
for number in numbers):
return False
for number in numbers:
self.fixed[number - 1] = True
return True
def solve(puzzle):
CORNER = 1, 4, 13
UPPERSIDE = 2, 3
LEFTSIDE = 5, 9
ROW2 = 6, 7, 8
COL2 = 6, 10, 14
RIGHTLOWER = 11, 12, 15
n = 0
while not puzzle.fix(CORNER):
puzzle.shuffle(20)
n += 1
while not puzzle.fix(UPPERSIDE) or not puzzle.fix(LEFTSIDE):
puzzle.shuffle(20)
n += 1
while not puzzle.fix(ROW2) or not puzzle.fix(COL2):
puzzle.shuffle(20)
n += 1
while not puzzle.fix(RIGHTLOWER):
puzzle.shuffle(20)
n += 1
return n
def main():
puzzle = Slide()
puzzle.shuffle(500)
print("shuffled puzzle")
print(*puzzle, sep='\n')
print("start analyze")
n = solve(puzzle)
print(n, "times")
print(*puzzle, sep='\n')
if __name__ == '__main__':
main()
ランダムでなく、計算により目標位置に移動させる
任意の場所Aにある"数字"を任意の場所Bに移動させる手順の作成法を考えます。
Aを左に移動させるには、操作マス（0マス）をAの左に移動させ、操作マスを右に移動させればよいです。
操作マス移動ルート探索について
Aや固定しているマスを動かさないように、操作マスを移動させるルートはA*アルゴリズムによって解きます。
最後に、作成したA*アルゴリズムを貼っておきます。
Astar(goal_x,goal_y,start_x,start_y,obstacle)
を与えると、最短ルートを返します。
このルートに基づき、操作マスを動かしたいマスの隣に付け、上下左右へ動かします。
確定順序
次に、どのマスから確定させていくか決めます。
1
2
4と3 :3を固定すると4が入らなくなるため
5
9と13
6 （ここから先は、ゲーム木探索で解ける、後で実装したい）
7と8
10と14
11と12と15
上から順に確定させていきます。
最後の4マスについて
次の3パターンしかありません。
よって、各パターンで場合分けしてやれば完成します。
2か所同時に埋める手順
$2$か所同時に埋める必要がある場所（3,4など）のアルゴリズムを示します。
例外として、$4$を$2$のとなりに置いた時点で$3$が右上隅に移動していた場合
入れ替え手順を考えると、次のようになります。
$3$を遠くに移動させてから、$4-3$の縦の列を作るという手順です。
結果
以上で完全に解けるようになりました。
手数としては$200 \sim 50$手ぐらいです。
固定しながらのランダムで$8$万手ぐらい使っていたので、かなりの進歩だと思います。
以上をプログラムにすると
トグルなのでクリックして開いてみてください。
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 29 13:35:47 2020
@author: kisim
"""
"""
スライドパズルの解法を探す
最終的には、パズドラに応用したい。そして10combo を目指す
"""
"""
Astar アルゴリズムにより、fixed をよけながら移動する
場合分けはエラーの原因で面倒のため
"""
import random
import numpy as np # Numpyライブラリ
import copy
import Astar as As
class Slide():
"""
0 が 操作マス
左上を原点とする
横に ｘ
縦に ｙ
トスル
"""
def __init__(self):
self.puzzle = [[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,0]]
self.x = 3 #操作マス 0 の場所
self.y = 3
self.fixed = np.zeros((4,4))
self.route = [[self.x,self.y]]
def route_clear(self):
self.route = [[self.x,self.y]]
def shuffle(self,num):
for i in range(num):
j=0
while True:
j = random.randint(0,3)
break
self.move(j)
def move(self,direction):
"""
0
3 1
2
動くのに失敗したら -1
動いたら 0
"""
if direction == 0:
if self.y != 0:
if self.fixed[self.y-1][self.x] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y-1][self.x]
self.y = self.y - 1
self.puzzle[self.y][self.x] = 0
self.route.append([self.x,self.y])
return 0
else:
return -1
if direction == 1:
if self.x != 3:
if self.fixed[self.y][self.x+1] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x+1]
self.x = self.x + 1
self.puzzle[self.y][self.x] = 0
self.route.append([self.x,self.y])
return 0
else:
return -1
if direction == 2:
if self.y != 3:
if self.fixed[self.y+1][self.x] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y+1][self.x]
self.y = self.y + 1
self.puzzle[self.y][self.x] = 0
self.route.append([self.x,self.y])
return 0
else:
return -1
if direction == 3:
if self.x != 0:
if self.fixed[self.y][self.x-1] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x-1]
self.x = self.x - 1
self.puzzle[self.y][self.x] = 0
self.route.append([self.x,self.y])
return 0
else:
return -1
return -1
def move_0(self,x,y):
"""
操作マス("0"マス) を x,y に動かす
先にルートを考え、fixに引っかからないとわかってから、移動を行います。
これはある種の迷路です。
別の関数で 迷路を解くための A* アルゴリズムを実装し、それを利用して解きましょう
"""
hoge = As.Astar(x,y,self.x,self.y,self.fixed)
result = hoge.explore()
route = []
if result == 0:
route = hoge.route
else:
return -1
for i in range(len(route)-1):
if route[i][0] < route[i+1][0]:
self.move(1)
elif route[i+1][0] < route[i][0]:
self.move(3)
elif route[i+1][1] < route[i][1]:
self.move(0)
elif route[i+1][1] > route[i][1]:
self.move(2)
if self.x !=x or self.y != y:
return -1
else:
return 0
def move_any(self,position,direction):
x=position[0]
y=position[1]
"""
任意の "数"(x,y) を direction の方向に動かす
0
3 1
2
動くのに失敗したら -1
動いたら 0
"""
if direction == 0: #上に移動させる 操作マスを上に付ける
self.fixed[y][x] = 1
hoge = self.move_0(x,y-1)
self.fixed[y][x] = 0
if hoge == -1:
return -1
else:
self.move_0(x,y)
return 0
elif direction == 2: # 下に移動させる
self.fixed[y][x] = 1
hoge = self.move_0(x,y+1)
self.fixed[y][x] = 0
if hoge == -1:
return -1
else:
self.move_0(x,y)
return 0
elif direction == 1: # 右に移動させる
self.fixed[y][x] = 1
hoge = self.move_0(x+1,y)
self.fixed[y][x] = 0
if hoge == -1:
return -1
else:
self.move_0(x,y)
return 0
elif direction == 3: # 左に移動させる
self.fixed[y][x] = 1
hoge = self.move_0(x-1,y)
self.fixed[y][x] = 0
if hoge == -1:
return -1
else:
self.move_0(x,y)
return 0
def find_position(self,num):
for i in range(4):
for j in range(4):
if self.puzzle[i][j] == num:
return (j,i)
def move_x(self,number,position):
target_x = position[0]
target_y = position[1]
"""
def move_any(self,position,direction):
任意の "数"(x,y) を direction の方向に動かす
0
3 1
2
動くのに失敗したら -1
動いたら 0
"""
position2 = self.find_position(number)
now_x = position2[0]
now_y = position2[1]
"""
Astar アルゴリズムで number の ルート 見つけ
ルートに従い、move_anyで動かし
但し、道幅が広くないと成立しないので、move_anyが失敗する可能性がある
－＞Astar , fixする順序で対処
"""
hoge = As.Astar(target_x,target_y,now_x,now_y,self.fixed)
result = hoge.explore()
route = []
if result == 0:
route = hoge.route
else:
return -1
for i in range(len(route)-1):
position2 = self.find_position(number)
now_x = position2[0]
now_y = position2[1]
if route[i][0] < route[i+1][0]:
result = self.move_any((now_x,now_y),1)
if result == -1:
return -1
elif route[i+1][0] < route[i][0]:
result = self.move_any((now_x,now_y),3)
if result == -1:
return -1
elif route[i+1][1] < route[i][1]:
result = self.move_any((now_x,now_y),0)
if result == -1:
return -1
elif route[i+1][1] > route[i][1]:
result = self.move_any((now_x,now_y),2)
if result == -1:
return -1
position2 = self.find_position(number)
now_x = position2[0]
now_y = position2[1]
if target_x != now_x or target_y != now_y:
return -1
else:
return 0
def exchange_row(self):
"""
4 3
x 0
y z
で入れ替える
"""
self.move(0)
self.move(3)
"""
0 4
x 3
y z
"""
self.move(2)
self.move(2)
self.move(1)
"""
x 4
y 3
z 0
"""
self.move(0)
"""
x 4
y 0
z 3
"""
self.move(3)
self.move(0)
self.move(1)
"""
4 0
x y
z 3
"""
def exchange_line(self):
"""
13 0 y
9 x z
"""
self.move(3)
self.move(2)
"""
9 13 y
0 x z
"""
self.move(1)
self.move(1)
self.move(0)
"""
9 13 0
x y z
"""
self.move(3)
"""
9 0 13
x y z
"""
self.move(2)
self.move(3)
self.move(0)
"""
0 y 13
9 x z
"""
def route_test(slide,route):
if route == []:
return -1
else:
for i in range(len(route)-1):
if route[i][0] < route[i+1][0]:
slide.move(1)
elif route[i+1][0] < route[i][0]:
slide.move(3)
elif route[i+1][1] < route[i][1]:
slide.move(0)
elif route[i+1][1] > route[i][1]:
slide.move(2)
return slide
if __name__ == '__main__' :
hoge = Slide()
hoge.shuffle(600)
hoge.route_clear()
print(hoge.puzzle[0])
print(hoge.puzzle[1])
print(hoge.puzzle[2])
print(hoge.puzzle[3])
#test用
hoge2 = Slide()
hoge2.puzzle = copy.deepcopy(hoge.puzzle)
hoge2.x = hoge.x
hoge2.y = hoge.y
#1
hoge.move_x(1,(0,0))
hoge.fixed[0][0] =1
#2
hoge.move_x(2,(1,0))
hoge.fixed[0][1] =1
#3,4
hoge.move_x(4,(2,0))
hoge.fixed[0][2] =1
if hoge.x == 3 and hoge.y == 0 and hoge.puzzle[1][3] == 3:
hoge.move(2)
if hoge.puzzle[0][3] == 3:
hoge.fixed[0][2] = 0
hoge.move_0(3,1)
hoge.exchange_row()
print("errored 3-4")
hoge.move_x(3,(2,1))
hoge.fixed[1][2] = 1
hoge.move_0(3,0)
hoge.fixed[1][2] = 0
hoge.fixed[0][2] = 0
hoge.move(3)
hoge.move(2)
hoge.fixed[0][2] = 1
hoge.fixed[0][3] = 1
#5
hoge.move_x(5,(0,1))
hoge.fixed[1][0] =1
#9,13
hoge.move_x(9,(0,3))
hoge.fixed[3][0] =1
if hoge.x == 0 and hoge.y == 2 and hoge.puzzle[2][1] == 13:
hoge.move(1)
if hoge.puzzle[2][0] == 13:
hoge.fixed[3][0] = 0
hoge.move_0(1,2)
hoge.exchange_line()
print("error 9-13")
hoge.fixed[3][0] = 1
hoge.move_x(13,(1,3))
hoge.fixed[3][1] = 1
hoge.move_0(0,2)
hoge.fixed[3][1] = 0
hoge.fixed[3][0] = 0
hoge.move(2)
hoge.move(1)
hoge.fixed[2][0] = 1
hoge.fixed[3][0] = 1
#6
hoge.move_x(6,(1,1))
hoge.fixed[1][1] =1
#7,8
hoge.move_x(8,(2,1))
hoge.fixed[1][2] =1
if hoge.x == 3 and hoge.y == 1 and hoge.puzzle[2][3] == 7:
hoge.move(2)
if hoge.puzzle[1][3] == 7:
hoge.fixed[1][2] = 0
hoge.move_0(3,2)
hoge.exchange_row()
print("error 7-8")
hoge.move_x(7,(2,2))
hoge.fixed[2][2] = 1
hoge.move_0(3,1)
hoge.fixed[2][2] = 0
hoge.fixed[1][2] = 0
hoge.move(3)
hoge.move(2)
hoge.fixed[1][3] = 1
hoge.fixed[1][2] = 1
#6マスなので もう ゲーム木探索でも解けるのでは？
#10,14
result = hoge.move_x(10,(1,3))
print(str(result)+"result")
hoge.fixed[3][1] =1
if hoge.x == 1 and hoge.y == 2 and hoge.puzzle[2][2] == 14:
hoge.move(1)
if hoge.puzzle[2][1] == 14:
hoge.fixed[3][1] = 0
hoge.move_0(2,2)
hoge.exchange_line()
print("error10-14")
hoge.fixed[3][1] = 1
hoge.move_x(14,(2,3))
hoge.fixed[3][2] = 1
hoge.move_0(1,2)
hoge.fixed[3][2] = 0
hoge.fixed[3][1] = 0
hoge.move(2)
hoge.move(1)
hoge.fixed[2][1] = 1
hoge.fixed[3][1] = 1
# これで行けるかと思ったが 、ちょっと違った
hoge.move_0(3,3)
print("a")
print(hoge.puzzle[0])
print(hoge.puzzle[1])
print(hoge.puzzle[2])
print(hoge.puzzle[3])
print(hoge.fixed[0])
print(hoge.fixed[1])
print(hoge.fixed[2])
print(hoge.fixed[3])
if hoge.puzzle[3][2] == 11:
#反時計回り一周
hoge.move(0)
hoge.move(3)
hoge.move(2)
hoge.move(1)
elif hoge.puzzle[3][2] == 12:
#時計回り一周
hoge.move(3)
hoge.move(0)
hoge.move(1)
hoge.move(2)
print(hoge.puzzle[0])
print(hoge.puzzle[1])
print(hoge.puzzle[2])
print(hoge.puzzle[3])
print(len(hoge.route))
hoge2 = route_test(hoge2,hoge.route)
if hoge2 == -1:
print("error")
else:
print(hoge2.puzzle[0])
print(hoge2.puzzle[1])
print(hoge2.puzzle[2])
print(hoge2.puzzle[3])
A*アルゴリズム
あまりうまくないプログラムですが・・・
トグルなのでクリックして開いてみてください。
Aster.py
import numpy as np # Numpyライブラリ
import random
import copy
class Node():
def __init__(self,x,y,cost,parent,num):
self.x = x
self.y = y
self.state = 1 # 0:none 1:open 2:closed
self.score = 0
self.cost = cost
self.parent = parent
self.expect_cost = 0
self.num = num
self.calculated = 0
def close(self):
self.state = 2
class Astar():
def __init__(self,g_x,g_y,s_x,s_y,obstacle):
self.width = obstacle.shape[1]
self.height = obstacle.shape[0]
self.g_x = g_x
self.g_y = g_y
self.s_x = s_x
self.s_y = s_y
self.x = s_x
self.y = s_y
self.obstacle_list = copy.deepcopy(obstacle)
self.maked_list = []
self.num = 0
start = Node(s_x,s_y,0,-1,self.num)
self.Node_list = [start]
self.num = self.num + 1
self.now = start #現在のノード
self.route = []
self.goal = -1 #gaal の ノード
self.finished = 0 #goal したかどうか
if g_x == s_x and g_y == s_y:
self.finished == 1
self.goal = start
self.route = [[s_x,s_y]]
def open(self):
self.now.close()
#周りをopen
"""
壁・障害 が有るときはopen できない －＞obstacle_list
既に作っていないか？－＞maked_list
"""
cost = self.now.cost
parent = self.now.num
if self.x!=0:
if self.maked_list.count([self.x-1,self.y]) == 0 and self.obstacle_list[self.y][self.x-1] == 0 :
self.Node_list.append(Node(self.x-1,self.y,cost+1,parent,self.num))
self.num = self.num + 1
self.maked_list.append([self.x-1,self.y])
if self.x!=self.width-1:
if self.maked_list.count([self.x+1,self.y]) == 0 and self.obstacle_list[self.y][self.x+1] == 0 :
self.Node_list.append(Node(self.x+1,self.y,cost+1,parent,self.num))
self.num = self.num + 1
self.maked_list.append([self.x+1,self.y])
if self.y!=0:
if self.maked_list.count([self.x,self.y-1]) == 0 and self.obstacle_list[self.y-1][self.x] == 0 :
self.Node_list.append(Node(self.x,self.y-1,cost+1,parent,self.num))
self.num = self.num + 1
self.maked_list.append([self.x,self.y-1])
if self.y!=self.height-1:
if self.maked_list.count([self.x,self.y+1]) == 0 and self.obstacle_list[self.y+1][self.x] == 0 :
self.Node_list.append(Node(self.x,self.y+1,cost+1,parent,self.num))
self.num = self.num + 1
self.maked_list.append([self.x,self.y+1])
"""
#デバッグ
print("test")
for i in self.Node_list:
print(i.state)
"""
#open しているものを計算
for i in self.Node_list:
if i.state == 1 and i.calculated == 0:
i.calculated = 1
i.expect_cost = abs(i.x - self.g_x)+abs(i.y-self.g_y)
i.score = i.cost + i.expect_cost
#open しているもののうち、スコアの小さいものをリストにまとめる
min_cost = 100
min_cost_list = []
for i in self.Node_list:
if i.state == 1:
if i.cost < min_cost:
min_cost = i.cost
min_cost_list = [i]
elif i.cost == min_cost:
min_cost_list.append(i)
if min_cost_list != []:
self.now = min_cost_list[random.randint(0,len(min_cost_list)-1)]
self.x = self.now.x
self.y = self.now.y
else:
print("none min")
return -1
if self.now.x == self.g_x and self.now.y == self.g_y:
return 1
else:
return 0
def explore(self):
"""
0 :goal
-1:goal できない
"""
if self.finished == 1:
return 0
else:
while True:
hoge = self.open()
if hoge == 1:
#print("goal!")
self.goal = self.now
self.finished = 1
self.Route()
return 0
elif hoge == -1:
return -1
def Route(self):
if self.finished == 1:
while True:
self.route.append((self.now.x,self.now.y))
if self.now.parent == -1:
break
else:
self.now = self.Node_list[self.now.parent]
self.route.reverse()
#print(self.route)
def Express(self):
if self.finished == 1:
if self.route ==[]:
print("not goaled")
else:
graph = self.obstacle_list
for i in self.route:
graph[i[1]][i[0]] = 2
print(graph)
if __name__ == '__main__' :
width = 5
height = 5
obstacle =np.zeros((height,width))
"""
obstacle[2][1] = 1
obstacle[2][2] = 1
obstacle[1][2] = 1
obstacle[3][2] = 1
"""
obstacle[1][0] = 1
print(obstacle)
g_x = 0
g_y = 2
s_x = 0
s_y = 0
hoge = Astar(g_x,g_y,s_x,s_y,obstacle)
result = hoge.explore()
if result == 0:
hoge.Express()
感想
ほんとはこんな泥臭いやり方ではなく、Q学習とかより最適化した手数の少ない方法を考えたいのですが私には今のところ難しいです。
群論とか学習したらいいのかなぁ～？？？