Program Realization 2 (2IP20), 2006-2007 ======= =========== = Third Installment: Automatic Solver (week 9) ----- ----------- Goal: Implement an automatic solver Material: Slides of Lectures 7, 8 and 9, archive Puzzle2007_A5.zip Plan: Play with demo program, review the slides, documentation and tutorial, study the design of Main.pas, and fill in some missing parts of the software. Note: This will take longer than one lab session. The submission deadline is Sunday 1 July 2007, 23:00 Step 1: Play with the demo The directory Demo contains a demo executable. Note that the puzzle definition files need to be in the directory ..\Puzzles. Also note that the examples are rather limited, because the box volume and pieces volume are equal. However, in general, this need not be the case. For testing purposes, it is wise to create some additional puzzles. N.B. It may be assumed that the piece volume is at least the box volume. (This can always be accomplished by adding to the puzzle a sufficient number of white one-cell pieces named '.'; also see extra-piece.txt.) Try various settings of the checkboxes when solving a puzzle. Also try solving a puzzle, which was already partially solved by manually placing some pieces. Only solutions that are extensions of that partial solution are now found. Step 2: Review the slides, documentation and tutorial Check that you understand the program requirements. Step 3: Study the design of Solvers.pas In particular, you can inspect TDummySolver. Step 4: Fill in some missing parts The holes in Base.pas, PuzzleIO.pas, and Main.pas have not changed. (Though the other parts may differ from your version. So you may need to copy your solution for these holes into the new version.) The source file Solvers.pas is incomplete. It contains some holes marked by //# BEGIN TODO ... Replace this line by your text. //# END TODO Complete the file to implement the automatic solution of puzzles through backtracking. For EmptyCell, implement a strategy that locates an empty cell by scanning along the _shorter_ side of the box. In general, this is more efficient then scanning along the _longer_ side of the box. E.g. the preferred scan order for the following boxes is indicated by the numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 4 7 10 13 2 5 8 11 14 3 6 9 12 15 Do not forget your name, id.nr., and the date at the top. Do not remove the //#-TODO markers themselves. When properly completed, your program should behave as the demo. Step 5: Check your program Read your code, check formatting, comments, etc. Test your code on appropriate cases. Step 6: Submit your project to PEACH Once you are happy with your work, submit your complete program to PEACH. Details follow. (End)