Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for 8 Puzzle by tokiojapan55
from typing import List
numpos = lambda p,n: [(r,c) for r in range(len(p)) for c in range(len(p[0])) if p[r][c]==n][0]
def move(puzzle, operation):
MOVE = {'U':(-1,0), 'D':(1,0), 'L':(0,-1), 'R':(0,1)}
for o in operation:
r,c = numpos(puzzle, 0)
rr,cc = MOVE[o][0]+r,MOVE[o][1]+c
puzzle[r][c] = puzzle[rr][cc]
puzzle[rr][cc] = 0
return operation
def rotate(puzzle, start, length):
r,c = numpos(puzzle, 0)
if c==start[1] and r>start[0]:
return move(puzzle, 'U')
if r==start[0] and cstart[1]:
return move(puzzle, 'L')
raise Exception()
def move_1(puzzle):
result = ''
while True:
r0,c0 = numpos(puzzle, 0)
r1,c1 = numpos(puzzle, 1)
if (r1,c1)==(0,0):
return result
if (r0,c0)==(1,1):
result += rotate(puzzle, (1,1), (1,1))
elif (r1,c1)!=(1,1):
result += rotate(puzzle, (0,0), (2,2))
elif c0==0:
result += rotate(puzzle, (0,0), (2,1))
else:
result += rotate(puzzle, (0,1), (2,1))
def move_2(puzzle):
result = ''
while True:
r0,c0 = numpos(puzzle, 0)
r2,c2 = numpos(puzzle, 2)
if (r2,c2)==(0,1):
return result
if r0==0:
result += rotate(puzzle, (0,1), (2, 1))
elif c2==0 or c0==0:
result += rotate(puzzle, (1,0), (1, 2))
else:
result += rotate(puzzle, (0,1), (2, 1))
return result
def move_3(puzzle):
result = ''
while True:
r0,c0 = numpos(puzzle, 0)
r3,c3 = numpos(puzzle, 3)
if (r3,c3)==(0,2):
return result
if (r3,c3)!=(1,2):
result += rotate(puzzle, (1,0), (1,2))
elif (r0,c0)==(0,2):
result += move(puzzle, 'D')
elif (r0,c0)==(2,2):
result += move(puzzle, 'L')
elif (r0,c0)==(1,0):
result += move(puzzle, 'URRDLULD')
else:
result += rotate(puzzle, (1,0), (1,1))
return result
def move_4(puzzle):
result = ''
while numpos(puzzle, 4)!=(1,0):
result += rotate(puzzle, (1,0), (1,2))
return result
def move_7(puzzle):
result = ''
while True:
r0,c0 = numpos(puzzle, 0)
r7,c7 = numpos(puzzle, 7)
if (r7,c7)==(2,0):
return result
if (r0,c0)==(2,0):
result += move(puzzle, 'L')
elif (r7,c7)!=(2,2) or (r0,c0)!=(2,1):
result += rotate(puzzle, (1,1), (1,1))
else:
result += move(puzzle, 'LURDRULLDR')
return result
def checkio(puzzle: List[List[int]]) -> str:
"""
Solve the puzzle
U - up
D - down
L - left
R - right
"""
result = ''
result += move_1(puzzle)
result += move_2(puzzle)
result += move_3(puzzle)
result += move_4(puzzle)
result += move_7(puzzle)
while puzzle != [[1,2,3],[4,5,6],[7,8,0]]:
result += rotate(puzzle, (1,1), (1,1))
return result
if __name__ == '__main__':
print("Example:")
print(checkio([[1, 2, 3],
[4, 6, 8],
[7, 5, 0]]))
#This part is using only for self-checking and not necessary for auto-testing
GOAL = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
MOVES = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
def check_solution(func, puzzle):
size = len(puzzle)
route = func([row[:] for row in puzzle])
goal = GOAL
x = y = None
for i, row in enumerate(puzzle):
if 0 in row:
x, y = i, row.index(0)
break
for ch in route:
swap_x, swap_y = x + MOVES[ch][0], y + MOVES[ch][1]
if 0 <= swap_x < size and 0 <= swap_y < size:
puzzle[x][y], puzzle[swap_x][swap_y] = puzzle[swap_x][swap_y], 0
x, y = swap_x, swap_y
if puzzle == goal:
return True
else:
print("Puzzle is not solved")
return False
assert check_solution(checkio, [[1, 2, 3],
[4, 6, 8],
[7, 5, 0]]), "1st example"
assert check_solution(checkio, [[7, 3, 5],
[4, 8, 6],
[1, 2, 0]]), "2nd example"
print("Coding complete? Click 'Check' to earn cool rewards!")
March 26, 2020
