CSCI.4430/6969 Programming Languages Spring 2011
Programming Assignment #1

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

Solving Lights Out in Prolog

Your goal is to solve the game Lights Out in Prolog. The game consists of a 5 by 5 grid of BLACK or WHITE points. When the game starts, a set of points will be set to BLACK, the others will show WHITE. Turning one point will toggle it and the four surrounding neighbor points (up, down, left, right; no wrapping to other sides of the board) WHITE and BLACK (WHITE->BLACK, BLACK ->WHITE). The final goal is to make all the points in the grid BLACK.

You may find the following link from Wikipedia be helpful in describing the game and how it proceeds: http://en.wikipedia.org/wiki/Lights_Out_(game)

Input and Output Format

The program should output a series of moves needed to "win" the game, i.e. to meet the condition that all lights are out (BLACK).

For example an initial board may be: 
BBBBB
BBBBB
BBBBB
BBBBB
WBBBW
Where “B” means it is BLACK, “W” means it is WHITE. Your program should output the following moves and the ending board: 
1,1
1,2
2,3
3,1
3,3
3,4
4,1
4,3
4,5
5,4
5,5

BBBBB
BBBBB
BBBBB
BBBBB
BBBBB

Extra Credit (10% bonus).

Extend your program to solve the puzzle using the fewest possible turns.

Reading Material:

Check the link from Wikipedia, it describes the game “Lights Out”. You can find a plausible algorithm there. http://en.wikipedia.org/wiki/Lights_Out_(game). However, if you are new to Prolog, you might want to start with the tutorial at http://www.learnprolognow.org/.


Due Date: February 11, 2011.
 
Received Time Grade Modification
before Thursday, 02/10, 11:59PM +10%
before Friday, 02/11, 11:59PM no modification (on time)
before Saturday, 02/12, 11:59PM -10%
before Monday, 02/14, 11:59PM -25%
after Tuesday, 02/15, 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 RPILMS user name(s) as the filename, either userid1.zip or userid1_userid2.zip. Only submit one assignment per pair via RPILMS.