CSCI.4430/6969 Programming Languages Fall 2006
Programming Assignment #3

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 TA or the instructor. You are encouraged to use the WebCT Discussions page to post questions so that other students can also answer and see the answers. Students are encouraged to work in pairs. Students working individually will be graded in the same manner as students working in pairs. You are encouraged to post to WebCT if you are unable to find someone to work with.

A Nurikabe Solver in Prolog

Your goal is to write a solver for Nurikabe, a binary grid puzzle. Puzzles consist of grids containing empty spaces and numbers. Solving a puzzle consists of determining which of the empty spaces are walls and which are rooms, following several rules. All numbers are given. Your solver is expected to be able to solve simple puzzles such as examples 1-7 reasonably quickly on an RPI T30 (i.e. within 2-3 seconds, with a possible exception for 7 which might take 15 seconds or so on some solvers). Your solver should find all solutions. You may assume that all puzzles have at least 1 wall. The rules: You are strongly advised to define auxiliary functions for each rule. Then, define a main solving function which will fill in the puzzle. You may find Wikipedia to be helpful.Hint: It is possible to detect rule violations without having filled in all squares.

Input and Output Format

The program should accept inputs of the form "solve(X,Y,Z)." X and Y should be the X and Y dimensions of the puzzle and Z should be a list of 3-tuples in the form type(X,Y,Z), where X, Y, and Z are the X and Y coordinates of the number Z. Your output should be in the format used below (omitting the headings). Some example inputs and outputs:
basictest(1) :- solve(5,5,[type(1,1,1),type(3,1,4),type(5,1,1),type(1,3,1),type(5,3,1),type(1,5,1),type(5,5,1)]).
basictest(2) :- solve(4,4,[type(1,1,2),type(3,1,2),type(1,4,2),type(4,4,1)]).
basictest(3) :- solve(4,4,[type(1,1,2),type(3,1,2),type(4,4,5)]).
basictest(4) :- solve(4,4,[type(1,1,2),type(1,4,2),type(4,1,2),type(4,4,4)]).
basictest(5) :- solve(4,4,[type(1,1,2),type(1,4,2),type(4,1,2),type(4,4,2)]).
basictest(6) :- solve(4,4,[type(1,1,2),type(1,4,2),type(4,1,2),type(4,4,3)]).
basictest(7) :- solve(10,10,[type(1,1,1),type(10,10,96)]).
basictest(8) :- solve(9,9,[type(4,4,16),type(4,6,16),type(6,4,16),type(6,6,16)]).


/*
` is used to represent rooms.
X is used to represent walls.
Numbers are used to represent numbered rooms.

test 1
1X4X1
XX`XX
1X`X1
XX`XX
1XXX1

test 2
2X2X
`X`X
XXXX
2`X1

test 3 (two solutions)
2X2`    
`XXX    
XX`X    
```5    

2X2`
`XXX
XX``
X``5

test 4
no solution

test 5
no solution

test 6
no solution

test 7
1X````````
XX````````
``````````
``````````
``````````
``````````
``````````
``````````
``````````
`````````96

test 8 (I do not expect your program to handle this particular puzzle in reasonable time)
Note: Because 16 is two characters in length, the solution below does not line up.  This is OK.
````X````
````X````
````X````
```16X16```
XXXXXXXXX
```16X16```
````X````
````X````
````X````
*/


Extra Credit :

Due Date:
Received Time Grade Modification
before Thursday, November 30, 11:55PM +5%
before Friday, December 1, 11:55PM no modification (on time)
before Saturday, December 2, 11:55PM -10%
before Monday, December 4, 11:55PM -25%
after Monday, December 4, 11:55PM not accepted

The assignment will be graded mostly on correctness, but code clarity / readability will also be a factor (comment, comment, comment!). Be sure your solutions are robust.

Submission Requirements: Your code should consist of a Prolog program as well as a readme.txt file. Combine these into a single ZIP file with your WebCT user name(s) as the filename, either userid1.zip or userid1_userid2.zip. Only submit one assignment per pair (the other does not need to submit anything via WebCT). Please submit your file via WebCT.