1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    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 word in self.crossword.words:
            l = len(word)
            for var in self.crossword.variables:
                if var.length != l:
                    self.domains[var].remove(word)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

    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.
        """
        overlap = self.crossword.overlaps[x,y]  #获得重叠部分
        if overlap is None:  #无重叠时
            return False
        else:
            i,j = overlap  #赋值
            edit = False  #初始化edit，用于判断是否修改并在最后返回
            to_remove = set()  #新建一个set，用于存储记录将要移除的元素，用于最后一块移除
            for x_word in self.domains[x]:  #遍历x
                find = False
                for y_word in self.domains[y]:
                    if x_word[i] == y_word[j]:  #如果x 可以满足某个 y，则不用被删
                        find = True
                if find is False:  #x 里这个 word 不满足弧一致
                    to_remove.add(x_word)
                    edit = True
            for word in to_remove:  #统一进行删除
                self.domains[x].remove(word)
            return edit

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

    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 is None:   #没有输入arcs时，检查全部的arcs，需要注意不要重复，不要找没有关系的
            queue = [(x, y) for x in self.domains for y in self.domains if x != y and self.crossword.overlaps[x, y] is not None]
        else:
            queue = list(arcs)  #传入弧转换为 list
        while queue:  
            (x,y) = queue.pop(0)  #从list中取出一个
            if self.revise(x,y):  #如果经过修改
                if len(self.domains[x]) == 0:   #看看 x 还有没有剩的，为后面遍历做准备
                    return False
                for z in self.crossword.neighbors(x) - {y}:  #遍历“邻居”，把成对的添加到队列中
                    queue.append((z,x))
        return True

1
2
3
4
5
6
7
8
9

    def assignment_complete(self, assignment):
        """
        Return True if `assignment` is complete (i.e., assigns a value to each
        crossword variable); return False otherwise.
        """
        for var in self.domains:   #遍历所有的空
            if var not in assignment:  #看看空有没有填上
                return False
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def consistent(self, assignment):
        """
        Return True if `assignment` is consistent (i.e., words fit in crossword
        puzzle without conflicting characters); return False otherwise.
        """
        #检查单词是否重复
        used_words = set()  
        for var in assignment:
            word = assignment[var]
            if word in used_words:
                return False
            else:
                used_words.add(word)
        #检查长度是否正确
            if len(word) != var.length:
                return False
        #检查相邻变量是否重复
        for var1 in assignment:
            for var2 in assignment:
                if var1 != var2:
                    overlap = self.crossword.overlaps[var1,var2]
                    if overlap != None:
                        i,j = overlap
                        word1 = assignment[var1]
                        word2 = assignment[var2]
                        if word1[i] != word2[j]:
                            return False
        return True