Programming Assignment #3

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:

Every square is either a wall or a room. Numbered squares are considered rooms.
Two squares are considered connected if they are of the same type and are horizontally adjacent, vertically adjacent, or transitively connected (i.e. connected(a,b) and connected(b,c) implies connected(a,c)).
No 2x2 square of spaces contains 4 walls.
Every wall square is connected to every other wall square.
A room square with a number N is connected to N room squares, including itself.
No numbered square is connected to any other numbered square.
Every room is either a numbered square or connected to a numbered square.

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 :

Create a more efficient Nurikabe solver. One simple yet effective efficiency improvement is to not immediately increase the depth of the search tree at each step but instead to probe each square to see if making it a wall or a room would cause a contradiction, in which case the opposite (i.e. room or wall, respectively) can be concluded. Most solver optimizations can be simulated by combining this technique with strong contradiction detection. Details the improvements made within your readme file. Provide example puzzles which it solves in reasonable time.

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.

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

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

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