Week 12 documentation
Overview
I worked on a basic interface for my final project you can read about it at the end of the page hereSo uh, I don't have anything for this week, but instead I made the sliding block puzzle solver for my final project maybe you can look at that instead :D
"""
HTMAA sliding block puzzle game implementation and solver
"""
import time
import random
direction_vector = {
"up": (-1, 0),
"down": (+1, 0),
"left": (0, -1),
"right": (0, +1),
}
######## implementation details ############
# board uses a dictionary with an entry for each tile in an nxn grid
# additionally it has 'n' the side length of the board, and '0' which has the location of the missing tile
# generate a random board and test solvability
#globals used in solver
SEQUENCE = 2
TILE_VALUES = 1
LOC_0 = 0
def convert_index(index, n):
return index//n, index%n
def convert_rc(r, c, n):
return r*n+c
def solvable_check(board):
"""
checks the board for solvability
for odd n, the number of inversions must be even
for even n, the parity of inversions and row_index of tile 0 (from bottom) must be different
"""
inversions = 0
board_len = board['n']**2 # nb of tiles is nxn
n = board['n']
#find number of inversions in board
for i in range(board_len):
for j in range(i+1, board_len):
current_val = board[i]
test_val = board[j]
# print(i, j, 'indices')
# print(current_val, test_val, 'values')
if current_val and test_val:
# print('both values are not 0')
if current_val > test_val:
# print('inversion detected')
inversions += 1
# print(inversions, 'inversion')
#find the row number counting from the bottom of index_0
ref_parity = n%2 # 0 if even, 1 if odd
if ref_parity: #if odd
return not inversions%2 #if inversions is even return 1, 0 if odd
else: #if even
index_0 = board['0']
index_0_row_from_bottom = n-index_0//n #bottom row is 1
parity_0 = index_0_row_from_bottom%2
inversion_parity = inversions%2
# print(index_0,'index_0', index_0_row_from_bottom,'index from bottom')
#board is solvable if parity_0
return parity_0 ^ inversion_parity # return 1 if one of them is even and the other is odd
def step_coordinates(coordinates, direction, n, index = True):
"""
returns the new coordinates of the player as if it moved in the specified direction.
returns the ROW and the COL,
"""
r_coord, c_coord = convert_index(coordinates, n)
r_dir, c_dir = direction_vector[direction]
new_row, new_col = (r_coord + r_dir, c_coord + c_dir)
# assert new_row >= 0, f'row out of bounds row: {r_coord}, col: {c_coord}, direction: {direction}'
# assert new_col >= 0, f'col out of bounds row: {r_coord}, col: {c_coord}, direction: {direction}'
if index:
return convert_rc(new_row, new_col, n)
else:
return new_row, new_col
def move_player(board, dir):
"""
Returns a new board where the player has moved given a board state and direction.
Assumes player can move.
Parameters:
board, dict
all tiles and associated IDs 1 through n
'0' stores location of the missing tile
'n' stores dimension information
direction, string command, decoded by direction_vector dictionary
Returns:
new gamebaord, dict
"""
new_board = board.copy()
loc_0 = board['0']
n = board['n']
new_loc_0 = step_coordinates(board['0'], dir, n) #find target index
new_board['0'] = new_loc_0 #update missing tile location
new_board[loc_0], new_board[new_loc_0] = new_board[new_loc_0], new_board[loc_0] #swap tiles
return new_board
def can_move(board, dir):
"""
Tests if the player can move in the given direction.
Parameters:
board, dict
all tiles and associated IDs 1 through n
'0' stores location of the missing tile
'n' stores dimension information
direction, string command, decoded by direction_vector dictionary
Returns:
bool, can the player move?
"""
n = board['n']
new_row, new_col = step_coordinates(board['0'], dir, board['n'], index=False) #returns row col form
# check bounds
if not (
(0 <= new_row and new_row < n)
and (0 <= new_col and new_col < n)
):
return False
return True
def new_game(n):
"""
generates a new solvable board of side length n
Parameter:
n, int
"""
numbers = list(range(n*n))
random.shuffle(numbers)
test_game = {'n':n, '0':numbers.index(0)} |{ind: num for ind, num in enumerate(numbers)}
while not solvable_check(test_game):
random.shuffle(numbers)
test_game = {'n':n, '0':numbers.index(0)} |{ind: num for ind, num in enumerate(numbers)}
return test_game
def victory_check(board):
"""checks if a board is solved"""
for key, val in board.items():
if not isinstance(key, int):
continue
elif val == 0:
if key != board['n']**2-1: #must be on the last tile
return False
elif key != val-1: #true if value = key+1
return False
return True
def render(board, display_all = 0):
"""
returns a printable representation of the game
Parameters:
board, dict containing all tile values,
'n' : dimension of the board, and
'0' : location of player
display_all, bool, displays dimension and location of 0 as well
"""
out = ''
for i in range(board['n']**2):
out += str(board[i])
if (i+1) % board['n'] == 0:
out += '\n'
else:
out += ' '
if display_all:
out += f"'n' = {board['n']} \n"
out += f"'0' = {board['0']}"
print(out)
return out
def step_game(board, direction):
"""
Given a game representation (of the form returned from new_game), return a
new game representation (of that same form), representing the updated game
after running one step of the game. The user's input is given by
direction, which is one of the following: {'up', 'down', 'left', 'right'}.
This function should not mutate its input.
"""
# copy the game board and move player location
assert board is not None
if can_move(board, direction):
return move_player(board, direction)
else:
return board
def solve_puzzle(board):
"""
Given a game representation (of the form returned from new game), find a
solution.
Return a list of strings representing the shortest sequence of moves ("up",
"down", "left", and "right") needed to reach the victory condition.
If the given level cannot be solved, return None.
"""
def convert(board):
"""
dictionaries are not hashable
convert to nested tuples so that visited can store the game info as a set
"""
return tuple( tuple(board[col+row*n] for col in range(n))
for row in range(n))
def revert(state):
"""
reverts back to dictionary representation
Parameter:
state, tuple of the form (location of 0, tile_val, dir_vector)
"""
loc_0, board_info,_ = state
dict_out = {'0': loc_0, 'n':n}
for r in range(n):
for c in range(n):
i = convert_rc(r, c, n)
dict_out[i] = board_info[r][c]
return dict_out
#check if already solved
if victory_check(board):
return []
# store redundant information
n = board['n']
# hashable version of the game
start_state = (board['0'], convert(board), ())
state_sequences = [start_state]
visited = set((start_state[1],))
considered = 0
while state_sequences:
candidate = state_sequences.pop(0)
considered += 1
stored_loc_0 = candidate[LOC_0]
stored_dir_sequence = candidate[SEQUENCE] # since this gets lost when converting
usable_state = revert(candidate)
for direction in direction_vector: # try every direction
if can_move(usable_state, direction):
stepped_candidate = move_player(usable_state, direction)
storable_state = convert(stepped_candidate)
if storable_state not in visited:
new_dir_sequence = stored_dir_sequence + (direction,)
new_loc_0 = step_coordinates(stored_loc_0, direction, n)
new_path = (new_loc_0, storable_state, new_dir_sequence)
visited.add(storable_state)
state_sequences.append(new_path)
# add to end for BFS
if victory_check(stepped_candidate):
print(considered, "considered paths")
return list(new_dir_sequence)
print('no solution found')
return None
#Some test code:
test2_solved = {
'n': 2,
'0': 3,
0:1,
1:2,
2:3,
3:0,
}
test3_solved = {
'n': 3,
'0': 8,
0:1,
1:2,
2:3,
3:4,
4:5,
5:6,
6:7,
7:8,
8:0,
}
test = new_game(4)
render(test)
print(solvable_check(test), "solvability")
start_time = time.time()
solution_vector = solve_puzzle(test)
solve_time = time.time() - start_time
if solution_vector:
for dir in solution_vector:
render(test)
test = move_player(test, dir)
# print(dir)
render(test)
print(len(solution_vector))
print(solve_time)
# print(solve_puzzle(test3_solved))
# print(bool(victory_check(test2_solved)))
# game = new_game(4)
# converted_board = convert(test2_solved, 2)
# print(converted_board)
# render(revert((3, converted_board, ()), 2))
# render(test3_solved)
# print(convert(game, 4))
# print(step_coordinates(3, 'left', 2))
# for i in range(10):
# game = new_game(4)
# print(render(game))