[PYTHON] How to solve slide puzzles and 15 puzzles
Overview
I would like to try the slide puzzle / 15 puzzle solution.
The language used is python.
You can play here (with a link).
The purpose is to arrange the numbers in the order of 1, 2, 3, ... by moving the number cells to the vacant cells.
Completely random
Move 20 times, and if they don't match, move again. Print the current status every 100 sets.
Coordinate system
Function of class
slide.move(direction)
Move the operating mass in the direction of direction 0: Above 1: Right 2: Below 3: Left
slide.shuffle(num)
Move randomly num times
result
I turned it for about 10 minutes, but there was no match.
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]
The executable program looks like this:
import random
import numpy as np #Numpy library
class Slide():
"""
0 is the operation mass
The origin is the upper left
Next to x
Vertically y
Tosul
"""
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)
While fixing the matching part ・ Random
Use the method of fixing from the square that can be moved to the correct position. However,
[1, 2, 3, 11]
[5, 6, 7, 8]
[12, 11, 10, 9]
[15, 13, 4, 0]
So, if you fix 1,2,3, you can move 4 to the correct position.
Therefore,
- 3 corners (because the lower right corner is empty)
- 2 squares between 3 corners (out if not appearing at the same time): top side, left side
- 2 lines
- 2 rows
Complete in the order of. (Turn at random, fix when established, go to the next) At this stage, there are only 4 squares in the lower left, so there are 6 ways (maybe confirmed), and you can solve this randomly.
As a result, it's pretty good.
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]
It was completed with 3652 sets (3652 * 20 moves). If it is completely random, it will not be completed even if it exceeds 10105500 sets, so I think it is quite good. I've done it several times and it takes less than a second, but the number of sets is sparse.
(Addition) I changed it because I got a better program in the comments. Thank you very much.
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()
Move to the target position by calculation, not randomly
Consider how to create a procedure to move the "number" in any place A to any place B. To move A to the left, move the operation cell (0 cell) to the left of A and move the operation cell to the right.
The route to move the operating cell is solved by the A * algorithm so as not to move A or the fixed cell. Finally, I will paste the created A * algorithm.
Astar(goal_x,goal_y,start_x,start_y,obstacle)
If is given, the shortest route is returned. Based on this route, attach the operation cell next to the cell you want to move and move it up, down, left, and right. This function allows you to move A anywhere.
Next, decide from which square you want to confirm.
- 1
- 2
- 4 and 3: If 3 is fixed, 4 will not fit.
- 5
- 9 and 13 6.6 (From here on, you can solve it by searching the game tree, I want to implement it later)
- 7 and 8
- 10 and 14
- 11 and 12 and 15: Here, if you move 0 to the lower right corner, there are only three ways:
Therefore, it will be completed if you divide each pattern into cases.
Shows the algorithm for two locations that need to be filled at the same time (3, 4, etc.).
As an exception, if 3 was moved to the upper right corner when 4 was placed next to 2.
Considering the replacement procedure, it is as follows.
The procedure is to move 3 farther and then make a vertical row of 4-3.
Now you can solve it completely. The number of steps is about 200 to 50. I used about 80,000 at random while fixing it, so I think it's a considerable improvement.
If you program the above
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 29 13:35:47 2020
@author: kisim
"""
"""
Find a solution to a slide puzzle
Ultimately, I want to apply it to Puzzle & Dragons. And aim for 10 combo
"""
"""
Move while avoiding fixed by Astar algorithm
Case classification is troublesome due to the cause of the error
"""
import random
import numpy as np #Numpy library
import copy
import Astar as As
class Slide():
"""
0 is the operation mass
The origin is the upper left
Next to x
Vertically y
Tosul
"""
def __init__(self):
self.puzzle = [[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,0]]
self.x = 3 #Location of operation mass 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
If you fail to move-1
If it moves, 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):
"""
Operation mass("0"trout)X,Move to y
Think about the route first, and then move after you know that you won't get caught in the fix.
This is a kind of maze.
A to solve the maze with another function*Implement the algorithm and use it to solve
"""
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]
"""
any"number"(x,y)Move in the direction of direction
0
3 1
2
If you fail to move-1
If it moves, 0
"""
if direction == 0: #Move up Attach the operation cell on top
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: #Move down
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: #Move to the right
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: #Move to the left
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):
any"number"(x,y)Move in the direction of direction
0
3 1
2
If you fail to move-1
If it moves, 0
"""
position2 = self.find_position(number)
now_x = position2[0]
now_y = position2[1]
"""
Find the number route with the Astar algorithm
Follow the route and move_Move with any
However, it will not be established unless the road is wide, so move_any can fail
－＞Astar ,Deal with the order of fixing
"""
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
Replace with
"""
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])
#For 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
#Since it is 6 squares, can it be solved by searching for a game tree?
#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
#I thought I could go with this, but it was a little different
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:
#Around counterclockwise
hoge.move(0)
hoge.move(3)
hoge.move(2)
hoge.move(1)
elif hoge.puzzle[3][2] == 12:
#Around clockwise
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 * algorithm
Aster.py
import numpy as np #Numpy library
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 #Current node
self.route = []
self.goal = -1 #gaal node
self.finished = 0 #Whether you did the 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 around
"""
Cannot open when there is a wall / obstacle-> obstacle_list
Haven't you made it already? -> Maded_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])
"""
#debug
print("test")
for i in self.Node_list:
print(i.state)
"""
#Calculate what is 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
#List the ones that are open and have the lowest score
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 can't
"""
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()
Recommended Posts