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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
# rush_hour.py - Module for solving Rush Hour game
# coding: utf-8
#
# Copyright (C) 2016 Arthur de Jong
#
# Permission is hereby granted, free of charge, to any person obtaining a
# copy of this software and associated documentation files (the "Software"),
# to deal in the Software without restriction, including without limitation
# the rights to use, copy, modify, merge, publish, distribute, sublicense,
# and/or sell copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
# DEALINGS IN THE SOFTWARE.
"""Solve Rush Hour puzzle.
This module provides solutions to the Rush Hour game. The module expects the
board to be input as a list of rows with each cell either being empty
(denoted by a period (.)) or contain a car (denoted by letters). The letter r
represents the red car.
The goal of the game is to move cars (only back and forth) so that the red
car can be moved to the right of the board.
The find_solutions will generate a number of solutions, the shortest
solutions first.
>>> solution = next(find_solutions([
... '....AA',
... '..BBCC',
... 'rr..EF',
... 'GGHHEF',
... '...IEF',
... '...IJJ']))
A solution consists of a list of moves from the initial board. Each move
consists of a description of the move (e.g. AL2 indicates that car A will be
moved 2 spaces to the left) and a new board configuration.
>>> solution[0][0]
'AL2'
>>> print('\\n'.join(solution[0][1]))
..AA..
..BBCC
rr..EF
GGHHEF
...IEF
...IJJ
>>> ','.join(move for move, board in solution)
'AL2,BL2,CL2,EU2,FU2,HR2,IU1,JL3,ID1,HL2,ED3,FD3,rR4'
>>> print('\\n'.join(solution[-1][1]))
..AA..
BBCC..
....rr
GGHHEF
...IEF
.JJIEF
"""
def clean_board(board):
"""Check that the board is valid."""
# check that each row has the same length
if not all(len(board[0]) == len(row) for row in board[1:]):
raise ValueError('each row should be the same length')
# TODO: check that each cell is either a capital letter, r or a period
# TODO: check that each "car" is 2 or 3 characters long
# TODO: check that each "car" is purely horizontal or vertical
# TODO: check that there is a "r" "car"
return tuple(board)
def split_row(row):
"""Split the row in parts of equal characters."""
value = ''
for c in row:
if value and c != value[0]:
yield value
value = ''
value += c
if value:
yield value
def possible_row_moves(row):
"""Find the possible moves within a row."""
# split in parts
parts = list(split_row(row))
for i in range(len(parts)):
# see if we have some empty space
if parts[i][0] == '.':
# see if there is a horizontal car before this space
if i > 0 and len(parts[i - 1]) > 1:
# we have space to move any "cars" before to the right
space = parts[i]
car = parts[i - 1]
for l in range(1, len(space) + 1):
newrow = ''.join(
parts[:i - 1] +
['.' * l] + [car] + ['.' * (len(space) - l)] +
parts[i + 1:])
yield (
'%sR%d' % (car[0], l), newrow)
# see if there is a horizontal car after this space
if i < len(parts) - 1 and len(parts[i + 1]) > 1:
# we have space to move any "cars" after this to the left
space = parts[i]
car = parts[i + 1]
for l in range(1, len(space) + 1):
newrow = ''.join(
parts[:i] +
['.' * (len(space) - l)] + [car] + ['.' * l] +
parts[i + 2:])
yield (
'%sL%d' % (car[0], l), newrow)
def transpose_board(board):
"""Turn horizontal rows will be turned into vertical columns."""
return tuple(''.join(x) for x in zip(*board))
def transpose_move(move):
"""Tanslate horizontal move strings into vertical moves.
>>> transpose_move('AR2')
'AD2'
>>> transpose_move('OL3')
'OU3'
"""
if move[1] == 'L':
return move[:1] + 'U' + move[2:]
else:
return move[:1] + 'D' + move[2:]
def possible_moves(board):
"""Yield possible moves on the board.
Each move consists of a tuple:
move (e.g. AR1, BU2)
new board
"""
# go over horizontal cars
for row in range(len(board)):
for move, newrow in possible_row_moves(board[row]):
yield (move, board[:row] + tuple([newrow]) + board[row + 1:])
# go over vertical cars
board = transpose_board(board)
for row in range(len(board)):
for move, newrow in possible_row_moves(board[row]):
yield (
transpose_move(move),
transpose_board(
board[:row] + tuple([newrow]) + board[row + 1:]))
def is_solution(board):
"""Check whether the board is a solution (i.e. the red car is on the
most right column)."""
return any(row[-1] == 'r' for row in board)
def find_solutions(board):
"""Find solutions to the board. This function will return the shortest
found solutions first."""
board = clean_board(board)
visited = set([board])
queue = []
queue.insert(0, [('', board)])
while queue:
moves = queue.pop()
board = moves[-1][1]
# find possible moves and see if we get somewhere new
possible = []
for move, newboard in possible_moves(board):
if is_solution(newboard):
yield moves[1:] + [(move, newboard)]
elif newboard not in visited:
queue.insert(0, moves + [(move, newboard)])
visited.add(newboard)
|