For example, the overlap between Variable 1 and Variable 2 might be represented as the pair (1, 0), meaning that Variable 1’s character at index 1 necessarily must be the same as Variable 2’s character at index 0 (assuming 0-indexing, again). We can represent that overlap as the character index in each variable’s word that must be the same character. For each pair of neighboring variables, those variables share an overlap: a single square that is common to them both. Variable 2 has two neighbors: Variable 1 and Variable 3. Variable 1 has a single neighbor: Variable 2. The binary constraints on a variable are given by its overlap with neighboring variables. Any values that don’t satisfy a variable’s unary constraints can therefore be removed from the variable’s domain immediately. For Variable 1, for instance, the value BYTE would satisfy the unary constraint, but the value BIT would not (it has the wrong number of letters). The unary constraint on a variable is given by its length.
Variable 1, for example, would be a variable represented by a row of 1 (assuming 0 indexed counting from the top), a column of 1 (also assuming 0 indexed counting from the left), a direction of across, and a length of 4.Īs with many constraint satisfaction problems, these variables have both unary and binary constraints. Each variable is defined by four values: the row it begins on (its i value), the column it begins on (its j value), the direction of the word (either down or across), and the length of the word. In this structure, we have four variables, representing the four words we need to fill into this crossword puzzle (each indicated by a number in the above image). Consider the following crossword puzzle structure. Each sequence of squares is one variable, for which we need to decide on its value (which word in the domain of possible words will fill in that sequence). We can model this sort of problem as a constraint satisfaction problem. How might you go about generating a crossword puzzle? Given the structure of a crossword puzzle (i.e., which squares of the grid are meant to be filled in with a letter), and a list of words to use, the problem becomes one of choosing which words should go in each vertical or horizontal sequence of squares. Ask questions via any of CS50’s communities!.$ python generate.py data/structure1.txt data/words1.txt output.png
0 kommentar(er)
