You are to take an existing Prolog program and extend it to add new
features and implement missing features.
Code.pl is an
incomplete program that allows the user to manipulate a 3x3 sliding
block puzzle. To execute the program, load it into Prolog, and
move_tiles. While a small number of potentially
useful functions are implemented, the only command currently accepted
by the grammar is the query,
?? Which tile is at <X>,<Y> ?This makes use of the
grabAfunction. The grammar also provides an unimplemented
slidefunction, which will enable users to slide tiles in any of the four directions ("up", "down", "left", "right"). Do not merely call the
movefunction for this; it may be possible to slide a tile that is not adjacent to the empty spot on the puzzle by pushing it against a tile that is. Note that the tile in the upper left corner is considered to be at position 1,1. You are to implement the following natural language commands:
Starting file: code.pl
Hexiom is a simple puzzle produced by Moonkey available on the internet. Implement a Hexiom Solver function. solver(A,B,C,D,E,F,G,Xsize,Ysize,Puzzle). Puzzle is an Xsize by Ysize grid (list of lists), which is initially partially filled with wildcards. Rules:
Warning: Unlike Part1, this puzzle is NOT well-suited to the use of assert/retract. Instead, you should assign values to individual elements of Puzzle one at a time, using backtracking in the event that a constraint is violated.
For full credit, your solution should be able to solve puzzles containing 19 or fewer wildcards within a minute on a 2 GHz machine. Good solutions should solve most such puzzles in about a second. You may assume that all test puzzles will initially have the perimeter of the puzzle marked as 7s. You do not need to find multiple solutions.
Starting file: hexiom.pl Several very useful functions for solving this problem are included in this file.
You cannot receive extra credit for both of the below tasks.
Allow the script to have an
if ... then ... else command.
Allow the script to have a
repeat ... while ... command.
As the current version of the puzzle has no conditionals, you will need to add a conditional, "[tile] <Number> is at <X>, <Y>"
Make your program capable of solving large (e.g. 5 tile edge, as opposed to above 4 tile edge example, which admittedly my program takes a few hours to solve) Hexiom puzzles in minutes. Note that I discourage students from attempting this extra credit unless they have prior experience with similar problems, as it is disproportionately more difficult than the extra credit assignment above, and the author of Hexiom tells me that he himself was unable to do so. The second example is a good way to test your solver, though you make or find additional examples as well.
Reading Material: The assignment builds on an example from section 2.19 and chapter 7 of the tutorial at http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/contents.html .However, if you are new to Prolog, you might want to start with the tutorial at http://www.coli.uni-saarland.de/~kris/learn-prolog-now. Be sure to read chapters 7 and 8 in the second tutorial which talk about natural language processing in prolog.
|Received Time||Grade Modification|
|before Thursday, 09/20, 11:59PM||+10%|
|before Friday, 09/21, 11:59PM||no modification (on time)|
|before Saturday, 09/22, 11:59PM||-10%|
|from Sunday, 09/23, 12:00AM to
Monday, 09/24, 11:59PM
|after Tuesday, 09/25, 12:00AM||not accepted|
Grading: The assignment will be graded mostly on correctness, but code clarity / readability will also be a factor (comment, comment, comment!). See the professor or TAs, if you have ideas for other extensions for this assignment and would like extra credit for implementing them.
Submission Requirements: Please submit a ZIP file with your code, including a README file. In the README file, place the names of each group member (up to two). Your README file should also have a list of specific features / bugs in your solution. Your ZIP file should be named with your WebCT user name(s) as the filename, either userid1.zip or userid1_userid2.zip. Only submit one assignment per pair via WebCT.