-
Notifications
You must be signed in to change notification settings - Fork 10
/
sliding-puzzle.py
146 lines (134 loc) · 5.12 KB
/
sliding-puzzle.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
# Time: O((m * n) * (m * n)!)
# Space: O((m * n) * (m * n)!)
# On a 2x3 board, there are 5 tiles represented by the integers 1 through 5,
# and an empty square represented by 0.
#
# A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.
#
# The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].
#
# Given a puzzle board, return the least number of moves required
# so that the state of the board is solved. If it is impossible
# for the state of the board to be solved, return -1.
#
# Examples:
#
# Input: board = [[1,2,3],[4,0,5]]
# Output: 1
# Explanation: Swap the 0 and the 5 in one move.
# Input: board = [[1,2,3],[5,4,0]]
# Output: -1
# Explanation: No number of moves will make the board solved.
# Input: board = [[4,1,2],[5,0,3]]
# Output: 5
# Explanation: 5 is the smallest number of moves that solves the board.
# An example path:
# After move 0: [[4,1,2],[5,0,3]]
# After move 1: [[4,1,2],[0,5,3]]
# After move 2: [[0,1,2],[4,5,3]]
# After move 3: [[1,0,2],[4,5,3]]
# After move 4: [[1,2,0],[4,5,3]]
# After move 5: [[1,2,3],[4,5,0]]
# Input: board = [[3,2,4],[1,5,0]]
# Output: 14
#
# Note:
# - board will be a 2 x 3 array as described above.
# - board[i][j] will be a permutation of [0, 1, 2, 3, 4, 5].
import heapq
import itertools
# A* Search Algorithm
class Solution(object):
def slidingPuzzle(self, board):
"""
:type board: List[List[int]]
:rtype: int
"""
def dot(p1, p2):
return p1[0]*p2[0]+p1[1]*p2[1]
def heuristic_estimate(board, R, C, expected):
result = 0
for i in xrange(R):
for j in xrange(C):
val = board[C*i + j]
if val == 0: continue
r, c = expected[val]
result += abs(r-i) + abs(c-j)
return result
R, C = len(board), len(board[0])
begin = tuple(itertools.chain(*board))
end = tuple(range(1, R*C) + [0])
expected = {(C*i+j+1) % (R*C) : (i, j)
for i in xrange(R) for j in xrange(C)}
min_steps = heuristic_estimate(begin, R, C, expected)
closer, detour = [(begin.index(0), begin)], []
lookup = set()
while True:
if not closer:
if not detour:
return -1
min_steps += 2
closer, detour = detour, closer
zero, board = closer.pop()
if board == end:
return min_steps
if board not in lookup:
lookup.add(board)
r, c = divmod(zero, C)
for direction in ((-1, 0), (1, 0), (0, -1), (0, 1)):
i, j = r+direction[0], c+direction[1]
if 0 <= i < R and 0 <= j < C:
new_zero = i*C+j
tmp = list(board)
tmp[zero], tmp[new_zero] = tmp[new_zero], tmp[zero]
new_board = tuple(tmp)
r2, c2 = expected[board[new_zero]]
r1, c1 = divmod(zero, C)
r0, c0 = divmod(new_zero, C)
is_closer = dot((r1-r0, c1-c0), (r2-r0, c2-c0)) > 0
(closer if is_closer else detour).append((new_zero, new_board))
return min_steps
# Time: O((m * n) * (m * n)! * log((m * n)!))
# Space: O((m * n) * (m * n)!)
# A* Search Algorithm
class Solution2(object):
def slidingPuzzle(self, board):
"""
:type board: List[List[int]]
:rtype: int
"""
def heuristic_estimate(board, R, C, expected):
result = 0
for i in xrange(R):
for j in xrange(C):
val = board[C*i + j]
if val == 0: continue
r, c = expected[val]
result += abs(r-i) + abs(c-j)
return result
R, C = len(board), len(board[0])
begin = tuple(itertools.chain(*board))
end = tuple(range(1, R*C) + [0])
end_wrong = tuple(range(1, R*C-2) + [R*C-1, R*C-2, 0])
expected = {(C*i+j+1) % (R*C) : (i, j)
for i in xrange(R) for j in xrange(C)}
min_heap = [(0, 0, begin.index(0), begin)]
lookup = {begin: 0}
while min_heap:
f, g, zero, board = heapq.heappop(min_heap)
if board == end: return g
if board == end_wrong: return -1
if f > lookup[board]: continue
r, c = divmod(zero, C)
for direction in ((-1, 0), (1, 0), (0, -1), (0, 1)):
i, j = r+direction[0], c+direction[1]
if 0 <= i < R and 0 <= j < C:
new_zero = C*i+j
tmp = list(board)
tmp[zero], tmp[new_zero] = tmp[new_zero], tmp[zero]
new_board = tuple(tmp)
f = g+1+heuristic_estimate(new_board, R, C, expected)
if f < lookup.get(new_board, float("inf")):
lookup[new_board] = f
heapq.heappush(min_heap, (f, g+1, new_zero, new_board))
return -1