generate.py

import sys

from crossword import *


class CrosswordCreator():

    def __init__(self, crossword):
        """
        Create new CSP crossword generate.
        """
        self.crossword = crossword
        self.domains = {
            var: self.crossword.words.copy()
            for var in self.crossword.variables
        }

    def letter_grid(self, assignment):
        """
        Return 2D array representing a given assignment.
        """
        letters = [
            [None for _ in range(self.crossword.width)]
            for _ in range(self.crossword.height)
        ]
        for variable, word in assignment.items():
            direction = variable.direction
            for k in range(len(word)):
                i = variable.i + (k if direction == Variable.DOWN else 0)
                j = variable.j + (k if direction == Variable.ACROSS else 0)
                letters[i][j] = word[k]
        return letters

    def print(self, assignment):
        """
        Print crossword assignment to the terminal.
        """
        letters = self.letter_grid(assignment)
        for i in range(self.crossword.height):
            for j in range(self.crossword.width):
                if self.crossword.structure[i][j]:
                    print(letters[i][j] or " ", end="")
                else:
                    print("█", end="")
            print()

    def save(self, assignment, filename):
        """
        Save crossword assignment to an image file.
        """
        from PIL import Image, ImageDraw, ImageFont
        cell_size = 100
        cell_border = 2
        interior_size = cell_size - 2 * cell_border
        letters = self.letter_grid(assignment)

        # Create a blank canvas
        img = Image.new(
            "RGBA",
            (self.crossword.width * cell_size,
             self.crossword.height * cell_size),
            "black"
        )
        font = ImageFont.truetype("assets/fonts/OpenSans-Regular.ttf", 80)
        draw = ImageDraw.Draw(img)

        for i in range(self.crossword.height):
            for j in range(self.crossword.width):

                rect = [
                    (j * cell_size + cell_border,
                     i * cell_size + cell_border),
                    ((j + 1) * cell_size - cell_border,
                     (i + 1) * cell_size - cell_border)
                ]
                if self.crossword.structure[i][j]:
                    draw.rectangle(rect, fill="white")
                    if letters[i][j]:
                        w, h = draw.textsize(letters[i][j], font=font)
                        draw.text(
                            (rect[0][0] + ((interior_size - w) / 2),
                             rect[0][1] + ((interior_size - h) / 2) - 10),
                            letters[i][j], fill="black", font=font
                        )

        img.save(filename)

    def solve(self):
        """
        Enforce node and arc consistency, and then solve the CSP.
        """
        self.enforce_node_consistency()
        self.ac3()
        return self.backtrack(dict())

    def enforce_node_consistency(self):
        """
        Update `self.domains` such that each variable is node-consistent.
        (Remove any values that are inconsistent with a variable's unary
         constraints; in this case, the length of the word.)
        """
        for var in self.domains:
            for word in self.domains[var].copy():
                if var.length != len(word):
                    self.domains[var].remove(word)
        return            
 
    def revise(self, x, y):
        """
        Make variable `x` arc consistent with variable `y`.
        To do so, remove values from `self.domains[x]` for which there is no
        possible corresponding value for `y` in `self.domains[y]`.

        Return True if a revision was made to the domain of `x`; return
        False if no revision was made.
        """
        # get the index of the overlap between word var x and word var y
        i, j = self.crossword.overlaps[x, y]
        is_revised = False
        # loop on all word options for var x and var y
        for word1 in self.domains[x].copy():
            found_match = False
            for word2 in self.domains[y]:
                # check if 2 words have same letter at the overlaping index
                if word1[i] == word2[j] and word1 != word2:
                    found_match = True
                    break
            # remove word1 from optional choices for var x
            if found_match == False:
                self.domains[x].remove(word1)
                is_revised = True
        return is_revised

    
    def ac3(self, arcs=None):
        """
        Update `self.domains` such that each variable is arc consistent.
        If `arcs` is None, begin with initial list of all arcs in the problem.
        Otherwise, use `arcs` as the initial list of arcs to make consistent.

        Return True if arc consistency is enforced and no domains are empty;
        return False if one or more domains end up empty.
        """
        if arcs == None:
            arcs = self.get_initial_arcs_list()
         
        for v1, v2 in arcs:
            is_v1_revised = self.revise(v1 ,v2)
            if is_v1_revised == True and len(self.domains[v1]) == 0:
                return False
        return True


    def assignment_complete(self, assignment):
        """
        Return True if `assignment` is complete (i.e., assigns a value to each
        crossword variable); return False otherwise.
        """
        if len(assignment) == len(self.crossword.variables):
            return True
        return False


    def consistent(self, assignment):
        """
        Return True if `assignment` is consistent (i.e., words fit in crossword
        puzzle without conflicting characters); return False otherwise.
        """
        # 1. check all assigned words are distinct
        if len(assignment) != len(set(assignment.values())):
            return False
        # 2. check every value is the correct length   
        for var in assignment:
            if var.length != len(assignment[var]):
                return False
        # 3. check there are no conflicts between neighboring variables.        
        for var in assignment:
            word1 = assignment[var]
            neighbors = self.crossword.neighbors(var)
            for var2 in neighbors:
                if var2 in assignment:
                    word2 = assignment[var2]
                    i, j = self.crossword.overlaps[var, var2]
                    # check if 2 words have same letter at the overlaping index
                    if word1[i] != word2[j] or word1 == word2:
                        return False
        return True
      

    def order_domain_values(self, var, assignment):
        """
        Return a list of values in the domain of `var`, in order by
        the number of values they rule out for neighboring variables.
        The first value in the list, for example, should be the one
        that rules out the fewest values among the neighbors of `var`.
        """
        res_dict = {}
        for word1 in self.domains[var]:
            eliminates = 0
            for var2 in self.crossword.variables:
                if var2 != var:
                    index = self.crossword.overlaps[var, var2]
                    if var2 not in assignment and index != None:
                        for word2 in self.domains[var2]:
                            if word1[index[0]] != word2[index[1]]:
                                eliminates += 1
            res_dict[word1] = eliminates
        return sorted(res_dict, key=res_dict.get)


    def select_unassigned_variable(self, assignment):
        """
        Return an unassigned variable not already part of `assignment`.
        Choose the variable with the minimum number of remaining values
        in its domain. If there is a tie, choose the variable with the highest
        degree. If there is a tie, any of the tied variables are acceptable
        return values.
        """
        # optional_vars = self.domains.copy()
        best_options_set1 = set()
        # find variable(s) with the fewest number of remaining values in its domain
        lowest_remaining_options = len(self.crossword.words)
        for var in self.crossword.variables:
            if var not in assignment:
                if len(self.domains[var]) < lowest_remaining_options: 
                    #found new lower option, reset result
                    best_options_set1 = { var }
                    lowest_remaining_options = len(self.domains[var])
                elif len(self.domains[var]) == lowest_remaining_options:
                    #found var with same num of options as the lowest already found
                    best_options_set1.add(var) 

        # found one best option
        if len(best_options_set1) == 1:
            return best_options_set1.pop()        

        most_neighbors = 0
        best_options_set2 = set()
        for var in best_options_set1:
            neighbors = len(self.crossword.neighbors(var))
            if neighbors > most_neighbors:
                best_options_set2 = { var }
                most_neighbors = neighbors
            elif neighbors == most_neighbors:
                best_options_set2.add(var)

        # return 1 option out of the best options found so far
        return best_options_set2.pop()  


    def backtrack(self, assignment):
        """
        Using Backtracking Search, take as input a partial assignment for the
        crossword and return a complete assignment if possible to do so.

        `assignment` is a mapping from variables (keys) to words (values).

        If no assignment is possible, return None.
        """
        
        # if found completed solution. return it            
        if self.assignment_complete(assignment):
            return assignment

        # select a variable that wasnt assigned yet
        var = self.select_unassigned_variable(assignment)
        # get possible word options for the selected var
        domain = self.order_domain_values(var, assignment)
        outcome = None  
        for word in domain:
            assignment[var] = word
            if self.consistent(assignment):
                outcome = self.backtrack(assignment)

            if outcome is not None:
                break # outcome is finished assignment

        return outcome


    def get_initial_arcs_list(self):
        arcs = []
        for v1, v2 in self.crossword.overlaps:
            if self.crossword.overlaps[v1, v2] is not None:
                arcs.append((v1, v2))
        return arcs    


def main():

    # Check usage
    if len(sys.argv) not in [3, 4]:
        sys.exit("Usage: python generate.py structure words [output]")

    # Parse command-line arguments
    structure = sys.argv[1]
    words = sys.argv[2]
    output = sys.argv[3] if len(sys.argv) == 4 else None

    # Generate crossword
    crossword = Crossword(structure, words)
    creator = CrosswordCreator(crossword)
    assignment = creator.solve()

    # Print result
    if assignment is None:
        print("No solution.")
    else:
        creator.print(assignment)
        if output:
            creator.save(assignment, output)


if __name__ == "__main__":
    main()