CSCI.4430/6969 Programming Languages Fall 2007
Programming Assignment #1

This assignment is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. However, you may get all the help you need from the TAs or the instructor. You are encouraged to use the WebCT Discussions page to post problems so that other students can also answer/see the answers.

Part 1. Natural Language Processing with Sliding Block Puzzles: 50%

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 run 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 grabA function. The grammar also provides an unimplemented slide function, which will enable users to slide tiles in any of the four directions ("up", "down", "left", "right"). Do not merely call the move function 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:
  1. "Shuffle [<Number>].": Applies 50 random moves, or Number if one is supplied.
  2. "Where is [tile] <Number> ?": Outputs X and Y coordinate of the tile.
  3. "Move/Push [[tile] <Number>] <Direction>.": If no tile is specified, picks a tile adjacent to the empty tile and moves it in that direction (if possible).
  4. "Move/Push [tile] <Number>.": If possible, moves tile. It is possible to move tiles that are not adjacent to the empty spot.
  5. "Print Status." : Pretty prints the board (using the included prettyprint function.)
Finally, any command which calls for a tile number should be capable of replacing "(tile) [Number]" with any of the following:
  1. "the tile at (position) X,Y"
  2. "the tile [above|below|to the left of|to the right of] (tile) [Number]"
  3. "the empty spot" | "the hole"
As the above replacement has some recursion, a user could enter a command like, "Move the tile above the tile to the left of 3 up." This assignment was changed significantly from the example described in section 7.3 of an extensive Prolog tutorial.

Starting file: code.pl

Part 2. Constraint Satisfaction: 50%

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:

  1. Each member of Puzzle will be a number from 0 to 7.
  2. The final solution will have exactly A zeros, B ones, C twos, D threes, E fours, F fives, G sixes. The rest will be sevens.
  3. Tiles labeled 7 are not tiles, but empty spaces.
  4. All tiles must be adjacent to exactly as many tiles as their value.
  5. Tiles are hexagonal, so input is staggered. So, tiles potentially have no more than 6 adjacent tiles. See Examples.

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.

Part 1 Extra Credit (10%)

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>"

Part 2 Extra Credit (15%)

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.


Due Date:
 
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		 -25%
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.