Task 2. Constraint Problem Solving. For solving constra
1 Pages463 Words462 Views
Added on 2019-09-16
Task 2. Constraint Problem Solving. For solving constra
Added on 2019-09-16
ShareRelated Documents
Task 2. Constraint Problem SolvingFor solving constraint satisfaction problems, we learnt backtracking search in the lecture. There is avariety of constraint satisfaction problems with high practical relevance in reality beyondcryptoarithmetic puzzles or Sudoku – all kinds of configuration or scheduling problems can be seen asconstraint satisfaction or constraint optimization problems. In this task, you shall solve a Cross WordPuzzle as a constraint satisfaction problem.Consider the following crossword puzzle:A1D1D2D33A2A3Word List:ADD, ADO, AGE, AGO, AID, AIL, AIM, AIR, AND,ANY, APE, APT, ARC, ARE, ARK, ARM, ART,ASH, ASK, AUK, AWE, AWL, AYE, BAD, BAG,BAN, BAT, BEE, BOA, EAR, EEL, EFT, FAR, FAT,FIT, LEE, OAF, RAT, TAR, TIEYou must find six three letter words: three words read across (A1, A2, A3) and three words read‐down (D1, D2, D3). Each word must be chosen from the given word list and can only appear once inthe puzzle.a) Prepare data structures for variables and domains as well as methods for testing constraints,testing whether specific values to two variables would fit together.[There are two different ways of defining variables/domains in this problem: Each cell could be avariable with letters as domains or the word entries with complete words as variables and‐domains. My suggestion is to have each word entry (A1,..., D3) as a variable and entries of theword list as possible domains.]b) Write a method that generates a crossword puzzle by backtracking search. After eachassignment, do a simple constraint propagation. That means delete values from the domains ofthe remaining unassigned variables that don’t make sense anymore with the assignment.c) Write a method arc‐consistency as given in the lecture on Constraint Satisfaction that testswhether the status of variables and their remaining domains is still solvable. Use this method in afunction that makes the complete crossword puzzle problem arc consistent by applying themethod to each relevant combination of variables.d) Integrate the method that makes the crossword problem arc consistent into the backtracking‐algorithm of task 2b and use it for solving the crossword problem. How many assignments didyou need to do after making the network arc consistent at the beginning?‐Print the results in a readable way.
End of preview
Want to access all the pages? Upload your documents or become a member.