0

So I've been working on the CS50Ai Crossword problem for about a day and a half, and after pouring through my entire code several times, I have been unable to fix a bug with my consistent function. Upon output of my crossword, there is always ONE issue of transection between words that do not match (i.e. "Teven" or "Angtelligence"). I've tried several ways of changing how the program compares overlaps, but it always appear to miss one. It may be due to some error in my revise or arc functions, but I tend to doubt it. If someone could give it a look and point me in the right direction it would be greatly appreciated.

import sys
from crossword import *
import random


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.textbbox((0, 0), 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 x in self.domains:
            words = []
            for word in self.domains[x]:
                if len(word) != x.length:
                    words.append(word)
            for word in words:
                self.domains[x].remove(word)


        
    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.
        """
        revised = False
        if self.crossword.overlaps[x, y]:
                words = []
                for xword in self.domains[x]:
                    possible = False
                    for yword in self.domains[y]:
                        if xword[(self.crossword.overlaps[x, y][0])] == yword[(self.crossword.overlaps[x, y][1])] and xword != yword:
                            possible = True
                    if possible == False:
                        words.append(xword)
                if words:
                    for word in words:
                        if word in self.domains[x]:
                            self.domains[x].remove(word)
                    revised =  True
        return 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.crossword.overlaps
        singles = []
        for arc in arcs:
            if len(arc) < 1:
                singles.append(arc)
        for arc in singles:
            del arcs[arc]
        while True:
            for arc in arcs:
                for arc in arcs:
                    if len(arc) < 1:
                        singles.append(arc)
                for arc in singles:
                    del arcs[arc]
                new_arcs = []
                if self.revise(arc[0], arc[1]) and len(arc) > 1:
                    for arc_two in arcs:
                        if arc[0] == arc_two[0] or arc[0] == arc_two[1]:
                            new_arcs.append(arc_two)
            if not new_arcs:
                break
            else:
                arcs.update(new_arcs)
        for x in self.domains:
            if self.domains[x] == None:
                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.domains):
            return True
        else:
            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.
        """
        dup_words = []
        for word in assignment:
            if word.length != len(assignment[word]):
                return False
            for second_word in assignment:
                if word != second_word:
                    if self.crossword.overlaps[word, second_word]:
                        word_letter = assignment[word][self.crossword.overlaps[word, second_word][0]]
                        second_word_letter = assignment[second_word][self.crossword.overlaps[word, second_word][1]]
                        if word_letter != second_word_letter:
                            return False
                    if self.crossword.overlaps[second_word, word]:
                        word_letter = assignment[word][self.crossword.overlaps[second_word, word][1]]
                        second_word_letter = assignment[second_word][self.crossword.overlaps[second_word, word][0]]
                        if word_letter != second_word_letter:
                            return False
        
                        

            dup_words.append(assignment[word])
        if len(set(dup_words)) != len(dup_words):
            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`.
        """
        domain_values = {}
        for value in self.domains[var]:
            if value not in assignment:
                neighbors = self.crossword.neighbors(var)
                neighbor_count = 0
                for neighbor in neighbors:
                    if value in self.domains[neighbor]:
                        neighbor_count += 1
                domain_values.update({value : neighbor_count})
        sorted_domain_values = dict(sorted(domain_values.items(), key = lambda x:x[1]))
        sorted_domain_values = list(sorted_domain_values.keys())
        return sorted_domain_values


    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.
        """
        domain_length = {}
        for domain in self.domains:
            if domain not in assignment:
                length = len(self.domains[domain])
                domain_length.update({domain : length})
        sorted_domain_lengths = list(sorted(domain_length.items(), key = lambda x:x[1]))
        ties = {}
        for i in range(len(sorted_domain_lengths)):
            if sorted_domain_lengths[i][1] == sorted_domain_lengths[0][1]:
                ties.update({sorted_domain_lengths[i][0] : self.crossword.neighbors(sorted_domain_lengths[i][0])})
        ties = dict(sorted(ties.items(), key = lambda x:x[1]))
        ties = list(ties)
        if len(ties) > 1:
            for tie in ties:
                if self.crossword.neighbors(tie) != self.crossword.neighbors(ties[-1]):
                    ties.remove(tie)
            ties[0] = random.choice(ties)
        return ties[0]


    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 self.assignment_complete(assignment):
            return assignment
        var = self.select_unassigned_variable(assignment)
        for value in self.order_domain_values(var, assignment):
            if self.consistent(assignment):
                assignment.update({var : value})
                result = self.backtrack(assignment)
                if result != None:
                    return result
                del assignment[var]
        return None


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()

1 Answer 1

1

The issue was within my backtrack function. It had to recheck whether or not the result presented by the recursive backtrack was consistent.

    if self.assignment_complete(assignment):
        return assignment
    var = self.select_unassigned_variable(assignment)
    for value in self.order_domain_values(var, assignment):
        if self.consistent(assignment):
            assignment.update({var : value})
            result = self.backtrack(assignment)
            if result != None and self.consistent(result):
                return result
            del assignment[var]
    return None

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .