The puzzle goes like this: in a rectangular 2D grid there are empty spaces (.
), exactly one starting point (S
, s
) and obstacles (denoted below by X
's). The objective of the puzzle is to find a path starting at the starting point and going through each empty space exactly once (a Hamiltonian path). You can't, of course cross the obstacles. You can move horizontally and vertically. A typical puzzle would look like this:
......
.SX...
...X..
.....X
......
XX....
......
And its solution:
11 12 13 14 17 18
10 1 X 15 16 19
9 2 3 X 21 20
8 5 4 23 22 X
7 6 25 24 29 30
X X 26 27 28 31
37 36 35 34 33 32
I wrote a solver in Python 3 (I later learned that this algorithm is actually a simple DFS). It solves the puzzle above in ~0.9 s, which is very good, but I was wondering if I can perhaps optimize it somehow.
import time
EMPTY_SPACE_SYMBOLS = ['.']
STARTING_POINT_SYMBOLS = ['S', 's']
OBSTACLE_SYMBOL = 'X'
PUZZLE_PATH = "grid.txt"
DIRS = [(-1, 0), (1, 0), (0, 1), (0, -1)]
start_time = time.time()
grid = open(PUZZLE_PATH).read().splitlines()
H = len(grid)
W = len(grid[0])
assert all(len(row) == W for row in grid), "Grid not rectangular"
def print_solution(coords):
result_grid = [[OBSTACLE_SYMBOL for _ in range(W)] for _ in range(H)]
for i, (r, c) in enumerate(coords, start=1):
result_grid[r][c] = i
str_grid = [[str(item).ljust(3) for item in row] for row in result_grid]
print('\n'.join(' '.join(row) for row in str_grid))
def extend(path, legal_coords):
res = []
lx, ly = path[-1]
for dx, dy in DIRS:
new_coord = (lx + dx, ly + dy)
if new_coord in legal_coords and new_coord not in path:
res.append(path + [new_coord])
return res
start_pos = None
legal = set()
for r, row in enumerate(grid):
for c, item in enumerate(row):
if item in STARTING_POINT_SYMBOLS:
assert start_pos is None, "Multiple starting points"
start_pos = (r, c)
elif item in EMPTY_SPACE_SYMBOLS:
legal.add((r, c))
assert start_pos is not None, "No starting point"
TARGET_PATH_LEN = len(legal) + 1
paths = [[start_pos]]
found = False
number_of_solutions = 0
while paths:
cur_path = paths.pop()
if len(cur_path) == TARGET_PATH_LEN:
number_of_solutions += 1
if not found:
print_solution(cur_path)
print("Solution found in {} s".format(time.time() - start_time))
found = True
paths += extend(cur_path, legal)
print('Total number of solutions found: {} (took: {} s)'.format(number_of_solutions, time.time() - start_time))