Untitled

 avatar
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