Untitled
unknown
plain_text
5 months ago
15 kB
6
Indexable
"""
Each futoshiki board is represented as a dictionary with string keys and
int values.
e.g. my_board['A1'] = 8
Empty values in the board are represented by 0
An * after the letter indicates the inequality between the row represented
by the letter and the next row.
e.g. my_board['A*1'] = '<'
means the value at A1 must be less than the value
at B1
Similarly, an * after the number indicates the inequality between the
column represented by the number and the next column.
e.g. my_board['A1*'] = '>'
means the value at A1 is greater than the value
at A2
Empty inequalities in the board are represented as '-'
"""
import sys
#======================================================================#
#*#*#*# Optional: Import any allowed libraries you may need here #*#*#*#
#======================================================================#
import time
import numpy as np
#=================================#
#*#*#*# Your code ends here #*#*#*#
#=================================#
ROW = "ABCDEFGHI"
COL = "123456789"
class Board:
'''
Class to represent a board, including its configuration, dimensions, and domains
'''
def get_board_dim(self, str_len):
'''
Returns the side length of the board given a particular input string length
'''
d = 4 + 12 * str_len
n = (2+np.sqrt(4+12*str_len))/6
if(int(n) != n):
raise Exception("Invalid configuration string length")
return int(n)
def get_config_str(self):
'''
Returns the configuration string
'''
return self.config_str
def get_config(self):
'''
Returns the configuration dictionary
'''
return self.config
def get_variables(self):
'''
Returns a list containing the names of all variables in the futoshiki board
'''
variables = []
for i in range(0, self.n):
for j in range(0, self.n):
variables.append(ROW[i] + COL[j])
return variables
def convert_string_to_dict(self, config_string):
'''
Parses an input configuration string, retuns a dictionary to represent the board configuration
as described above
'''
config_dict = {}
for i in range(0, self.n):
for j in range(0, self.n):
cur = config_string[0]
config_string = config_string[1:]
config_dict[ROW[i] + COL[j]] = int(cur)
if(j != self.n - 1):
cur = config_string[0]
config_string = config_string[1:]
config_dict[ROW[i] + COL[j] + '*'] = cur
if(i != self.n - 1):
for j in range(0, self.n):
cur = config_string[0]
config_string = config_string[1:]
config_dict[ROW[i] + '*' + COL[j]] = cur
return config_dict
def print_board(self):
'''
Prints the current board to stdout
'''
config_dict = self.config
for i in range(0, self.n):
for j in range(0, self.n):
cur = config_dict[ROW[i] + COL[j]]
if(cur == 0):
print('_', end=' ')
else:
print(str(cur), end=' ')
if(j != self.n - 1):
cur = config_dict[ROW[i] + COL[j] + '*']
if(cur == '-'):
print(' ', end=' ')
else:
print(cur, end=' ')
print('')
if(i != self.n - 1):
for j in range(0, self.n):
cur = config_dict[ROW[i] + '*' + COL[j]]
if(cur == '-'):
print(' ', end=' ')
else:
print(cur, end=' ')
print('')
def __init__(self, config_string):
'''
Initialising the board
'''
self.config_str = config_string
self.n = self.get_board_dim(len(config_string))
if(self.n > 9):
raise Exception("Board too big")
self.config = self.convert_string_to_dict(config_string)
self.domains = self.reset_domains()
self.forward_checking(self.get_variables())
def __str__(self):
'''
Returns a string displaying the board in a visual format. Same format as print_board()
'''
output = ''
config_dict = self.config
for i in range(0, self.n):
for j in range(0, self.n):
cur = config_dict[ROW[i] + COL[j]]
if(cur == 0):
output += '_ '
else:
output += str(cur)+ ' '
if(j != self.n - 1):
cur = config_dict[ROW[i] + COL[j] + '*']
if(cur == '-'):
output += ' '
else:
output += cur + ' '
output += '\n'
if(i != self.n - 1):
for j in range(0, self.n):
cur = config_dict[ROW[i] + '*' + COL[j]]
if(cur == '-'):
output += ' '
else:
output += cur + ' '
output += '\n'
return output
def reset_domains(self):
'''
Resets the domains of the board assuming no enforcement of constraints
'''
domains = {}
variables = self.get_variables()
for var in variables:
if(self.config[var] == 0):
domains[var] = [i for i in range(1,self.n+1)]
else:
domains[var] = [self.config[var]]
self.domains = domains
return domains
def update_domain(self, neighbor, value, sign):
if self.config[neighbor] == 0:
update = []
if sign == '<':
for val in self.domains[neighbor]:
if val > value:
update.append(val)
elif sign == '>':
for val in self.domains[neighbor]:
if val < value:
update.append(val)
self.domains[neighbor] = update
def get_neighbors(self, var):
row_index = ROW.index(var[0])
row_neighbors = []
for j in range(self.n):
if COL[j] != var[1]:
row_neighbors.append(ROW[row_index] + COL[j])
col_neighbors = []
for i in range(self.n):
if ROW[i] != var[0]:
col_neighbors.append(ROW[i] + var[1])
return row_neighbors + col_neighbors
def forward_checking(self, reassigned_variables):
for var in reassigned_variables:
value = self.config[var]
if value == 0:
continue
neighbors = self.get_neighbors(var)
for neighbor in neighbors:
if self.config[neighbor] == 0 and value in self.domains[neighbor]:
self.domains[neighbor].remove(value)
if not self.prune_if_needed(neighbor, value):
return False
if var + '*' in self.config:
ineq = self.config.get(var + '*', '-')
if ineq != '-':
neighbor = ROW[ROW.index(var[0])] + COL[COL.index(var[1]) + 1]
self.update_domain_with_inequality(neighbor, value, ineq)
if var[0] + '*' + var[1] in self.config:
ineq = self.config.get(var[0] + '*' + var[1], '-')
if ineq != '-':
neighbor = ROW[ROW.index(var[0]) + 1] + var[1]
self.update_domain_with_inequality(neighbor, value, ineq)
return True
#=================================================================================#
#*#*#*# Optional: Write any other functions you may need in the Board Class #*#*#*#
#=================================================================================#
def select_var(self):
ua_var = [var for var in board.get_variables() if board.config[var] == 0]
if not ua_var:
return None
ua_var.sort(key=lambda var: len(board.domains[var]))
return ua_var[0]
def copy_domains(self):
return {var: list(values) for var, values in self.domains.items()}
def update_config_str(self):
config_string = ""
for i in range(self.n):
for j in range(self.n):
config_string += str(self.config[ROW[i] + COL[j]])
if j != self.n - 1:
config_string += self.config[ROW[i] + COL[j] + '*']
if i != self.n - 1:
for j in range(self.n):
config_string += self.config[ROW[i] + '*' + COL[j]]
self.config_str = config_string
return config_string
#=================================#
#*#*#*# Your code ends here #*#*#*#
#=================================#
#================================================================================#
#*#*#*# Optional: You may write helper functions in this space if required #*#*#*#
#================================================================================#
#=================================#
#*#*#*# Your code ends here #*#*#*#
#=================================#
def backtracking(board):
'''
Performs the backtracking algorithm to solve the board
Returns only a solved board
'''
#==========================================================#
#*#*#*# TODO: Write your backtracking algorithm here #*#*#*#
#==========================================================#
if all(board.config[var] != 0 for var in board.get_variables()):
return board
var = board.select_var()
if var is None:
return None
domain = board.domains[var][:]
for value in domain:
board.config[var] = value
saved_domains = board.copy_domains()
board.forward_checking([var])
failure = any(len(board.domains[v]) == 0 for v in board.get_variables())
if not failure:
result = backtracking(board)
if result is not None:
return result
board.domains = saved_domains
board.config[var] = 0
return None
#=================================#
#*#*#*# Your code ends here #*#*#*#
#=================================#
def solve_board(board):
'''
Runs the backtrack helper and times its performance.
Returns the solved board and the runtime
'''
#================================================================#
#*#*#*# TODO: Call your backtracking algorithm and time it #*#*#*#
#================================================================#
start_time = time.time()
solved_board = backtracking(board)
solved_board.update_config_str()
end_time = time.time()
runtime = end_time - start_time
return solved_board, runtime
return None, -1
#=================================#
#*#*#*# Your code ends here #*#*#*#
#=================================#
def print_stats(runtimes):
'''
Prints a statistical summary of the runtimes of all the boards
'''
min = 100000000000
max = 0
sum = 0
n = len(runtimes)
for runtime in runtimes:
sum += runtime
if(runtime < min):
min = runtime
if(runtime > max):
max = runtime
mean = sum/n
sum_diff_squared = 0
for runtime in runtimes:
sum_diff_squared += (runtime-mean)*(runtime-mean)
std_dev = np.sqrt(sum_diff_squared/n)
print("\nRuntime Statistics:")
print("Number of Boards = {:d}".format(n))
print("Min Runtime = {:.8f}".format(min))
print("Max Runtime = {:.8f}".format(max))
print("Mean Runtime = {:.8f}".format(mean))
print("Standard Deviation of Runtime = {:.8f}".format(std_dev))
print("Total Runtime = {:.8f}".format(sum))
if __name__ == '__main__':
if len(sys.argv) > 1:
# Running futoshiki solver with one board $python3 futoshiki.py <input_string>.
print("\nInput String:")
print(sys.argv[1])
print("\nFormatted Input Board:")
board = Board(sys.argv[1])
board.print_board()
solved_board, runtime = solve_board(board)
print("\nSolved String:")
print(solved_board.get_config_str())
print("\nFormatted Solved Board:")
solved_board.print_board()
print_stats([runtime])
# Write board to file
out_filename = 'output.txt'
outfile = open(out_filename, "w")
outfile.write(solved_board.get_config_str())
outfile.write('\n')
outfile.close()
else:
# Running futoshiki solver for boards in futoshiki_start.txt $python3 futoshiki.py
# Read boards from source.
src_filename = 'futoshiki_start.txt'
try:
srcfile = open(src_filename, "r")
futoshiki_list = srcfile.read()
srcfile.close()
except:
print("Error reading the sudoku file %s" % src_filename)
exit()
# Setup output file
out_filename = 'output.txt'
outfile = open(out_filename, "w")
runtimes = []
# Solve each board using backtracking
for line in futoshiki_list.split("\n"):
print("\nInput String:")
print(line)
print("\nFormatted Input Board:")
board = Board(line)
board.print_board()
solved_board, runtime = solve_board(board)
runtimes.append(runtime)
print("\nSolved String:")
print(solved_board.get_config_str())
print("\nFormatted Solved Board:")
solved_board.print_board()
# Write board to file
outfile.write(solved_board.get_config_str())
outfile.write('\n')
# Timing Runs
print_stats(runtimes)
outfile.close()
print("\nFinished all boards in file.\n")
Editor is loading...
Leave a Comment