CONSTRAINT SATISFACTION PROBLEMS Consider a traditional crossword puzzle, where

Question

CONSTRAINT SATISFACTION PROBLEMS

Consider a traditional crossword puzzle, where each square contains a single letter of the alphabet (case insensitive). In a crossword puzzle, certain squares are blacked out, and certain rows and columns are numbered, corresponding to clues that hint as to the word that fills that contiguous set of squares.

a) What are the variables in a crossword puzzle?

b) What are the possible values (the domain) of the variables?

c) Suppose for each square we have a constraint such that consecutive vertical and horizontal cells must form a word within some lexicon. Does this formulation necessarily specify a unique solution to the crossword?

Explanation / Answer

a.) The unblacked sqaures are the variables in a crossword puzzle.

b.) The domain of each variable is the set of letters of alphabet ,i.e the set {a,b,c,d,...........x,y,z}

c.) The contrainst that consecutive vertical and horizontal cells must form a word within some lexicon doesn't necessarily specify a unique solution to the crossword as it depends on the dictionary/lexicon.

Consider a 2 x 2 crossword puzzle, where set of words in the lexicon are = {ab,ac,ba,bd,cd,dc }

Now xijrepresents the character at row i and column j

if we set the crossword as

a b

c d where x11 = a , x12 = b , x21 = c and x22 = d , we see it's a valid solution satisfying the constraints as ab, cd, ac and bd are present in the lexicon above.

Now consider the other crossword formulation where the crossword is set as

b a

d c where x11 = b, x12 = a , x21 = d and x22 = c we see it's a valid solution satisfying the constraints as the words ba,dc,bd and ac are in the lexicon

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.