Untitled
unknown
plain_text
6 months ago
18 kB
7
Indexable
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 forward_checking(self, reassigned_variables):
for var in reassigned_variables:
if self.config[var] == 0:
continue # Skip unassigned variables
value = self.config[var]
row = var[0]
col = var[1]
# Save a copy of the current domains to restore if conflicts occur
original_domains = self.copy_domains()
print(f"\nForward checking for {var}={value}")
print(f"Initial domains:\n{self.domains}")
# Check and remove 'value' from domains in the same row
for c in COL:
neighbor = row + c
if neighbor != var and value in self.domains.get(neighbor, []):
self.domains[neighbor].remove(value)
print(f"Removed {value} from domain of {neighbor}. New domain: {self.domains[neighbor]}")
if not self.domains[neighbor]: # Conflict: empty domain
print(f"Conflict! Domain of {neighbor} is empty after removal. Restoring domains.")
self.domains = original_domains # Restore domains on failure
return False
# Check and remove 'value' from domains in the same column
for r in ROW:
neighbor = r + col
if neighbor != var and value in self.domains.get(neighbor, []):
self.domains[neighbor].remove(value)
print(f"Removed {value} from domain of {neighbor}. New domain: {self.domains[neighbor]}")
if not self.domains[neighbor]: # Conflict: empty domain
print(f"Conflict! Domain of {neighbor} is empty after removal. Restoring domains.")
self.domains = original_domains # Restore domains on failure
return False
# Enforce inequality constraints for horizontal inequalities (x < y or x > y)
right_ineq = self.config.get(var + '*', '-')
if right_ineq != '-':
neighbor_col_index = COL.index(col) + 1
if neighbor_col_index < self.n:
neighbor = row + COL[neighbor_col_index]
if self.config[neighbor] == 0: # Only prune domains if neighbor is unassigned
print(f"Applying horizontal inequality constraint {var} {right_ineq} {neighbor}")
if right_ineq == '<':
# Remove values from neighbor that are less than or equal to value of var
max_value = max(self.domains[neighbor])
self.domains[neighbor] = [v for v in self.domains[neighbor] if v > value]
print(f"Removed values <= {value} from {neighbor}. New domain: {self.domains[neighbor]}")
elif right_ineq == '>':
# Remove values from neighbor that are greater than or equal to value of var
min_value = min(self.domains[neighbor])
self.domains[neighbor] = [v for v in self.domains[neighbor] if v < value]
print(f"Removed values >= {value} from {neighbor}. New domain: {self.domains[neighbor]}")
if not self.domains[neighbor]: # Conflict: empty domain
print(f"Conflict! Domain of {neighbor} is empty after inequality enforcement.")
self.domains = original_domains # Restore domains on failure
return False
# Enforce inequality constraints for vertical inequalities (x < y or x > y)
below_ineq = self.config.get(row + '*' + col, '-')
if below_ineq != '-':
neighbor_row_index = ROW.index(row) + 1
if neighbor_row_index < self.n:
neighbor = ROW[neighbor_row_index] + col
if self.config[neighbor] == 0: # Only prune domains if neighbor is unassigned
print(f"Applying vertical inequality constraint {var} {below_ineq} {neighbor}")
if below_ineq == '<':
# Remove values from neighbor that are less than or equal to value of var
max_value = max(self.domains[neighbor])
self.domains[neighbor] = [v for v in self.domains[neighbor] if v > value]
print(f"Removed values <= {value} from {neighbor}. New domain: {self.domains[neighbor]}")
elif below_ineq == '>':
# Remove values from neighbor that are greater than or equal to value of var
min_value = min(self.domains[neighbor])
self.domains[neighbor] = [v for v in self.domains[neighbor] if v < value]
print(f"Removed values >= {value} from {neighbor}. New domain: {self.domains[neighbor]}")
if not self.domains[neighbor]: # Conflict: empty domain
print(f"Conflict! Domain of {neighbor} is empty after inequality enforcement.")
self.domains = original_domains # Restore domains on failure
return False
print("Forward checking successful. No conflicts found.")
return True # No conflicts
#=================================================================================#
#*#*#*# Optional: Write any other functions you may need in the Board Class #*#*#*#
#=================================================================================#
def select_var(self):
ua_var = []
for var in self.get_variables(): # Correct reference
if self.config[var] == 0:
ua_var.append(var)
if not ua_var:
return None
ua_var.sort(key=lambda var: len(self.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):
# Base case: if all variables are assigned, return the board
if all(board.config[var] != 0 for var in board.get_variables()):
print("All variables assigned. Solution found!")
board.print_board()
return board
# Select variable using heuristic (MRV - Minimum Remaining Values)
var = board.select_var()
if var is None:
return None
# Print selected variable and its domain
print(f"\nSelected Variable: {var}")
print(f"Current Domain of {var}: {board.domains[var]}")
# Make a local copy of the current domain for safe iteration
domain_copy = board.domains[var][:]
original_domains = board.copy_domains() # Save the original domains for restoration if needed
for value in domain_copy: # Try each possible value for the selected variable
print(f"\nAttempting to assign {value} to {var}")
board.config[var] = value # Assign the value to the variable
print(f"Assigned {value} to {var}. Performing forward checking...")
# Perform forward checking
if board.forward_checking([var]):
print(f"Forward checking passed for {var}={value}. Continuing to next variable...")
# Recursive call to backtracking
result = backtracking(board)
if result is not None:
return result # Return if successful
# If forward checking or recursion fails, restore domains and reset variable
print(f"Backtracking on {var}={value}. Restoring domains and trying next value.")
board.domains = original_domains # Restore domains to the original state
board.config[var] = 0 # Unassign variable
# If no valid assignments, return None to trigger backtracking
print(f"All values for {var} failed. Returning to previous variable.")
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()
solved_board = backtracking(board)
solved_board.update_config_str()
end = time.time()
runtime = end - start
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