Course from edX:
[ Ссылка ]
Video Sections:
0:14 - usage of structure0, words0
0:35 - usage of structure0, words1
0:48 - usage of structure1, words1
1:04 - usage of structure2, words2
1:23 - usage of structure3, words2
1:39 - usage of structure4, words2
Background
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. We can model this sort of problem as a constraint satisfaction problem. 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).
A CSP consists of 3 components:
- X is a set of variables, {X1, …, Xn}.
- D is a set of domains, {D1, …, Dn}, one for each variable.
- C is a set of constraints that specify allowable combination of values.
This video is a quick demonstration of a crossword puzzle solved by our AI by modeling crossword puzzle as a constraint satisfaction problem. Here, we first enforce node consistency on each variable, and then apply ac-3 algorithm to enforce arc consistency for each variable in a CSP. Finally, we backtrack the partial assignment recursively to find the solution of our crossword puzzle using backtracking algorithm. Backtracking algorithm repeatedly chooses an unassigned variable, and then tries all values in the domain of that variable in turn, trying to find a solution.
SELECT-UNASSIGNED-VARIABLE:
- Minimum-remaining-values (MRV) heuristic
- Degree heuristic
ORDER-DOMAIN-VALUES:
- Least-constraining-value heuristic
INTERLEAVING SEARCH AND INFERENCE:
- MAC (Maintaining Arc Consistency) algorithm
Music: [ Ссылка ]
