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