Homework 1

Implementing Simple Search to solve a "Challenge"

Due: Friday, September 15th


"Light Out" is a classic game consisting of an nxn grid of lights.  The goal is to turn off all of the lights.  The challenge is that when you select a light bulb to turn on or off, all light bulbs immediately adjacent to that light bulb (directly up, down, left and right if they exist) also change state.

For example, turning off the light circled in blue in the image below:

not only turns that light off, but turns off the light below it, and turns on the light to the left, right, and above it.

Turning off the light in the lower right hand corner also turns off the lights above and to the left of it.  Notice since it doesn't HAVE lights to the right or below it that only those three lights are changed.

You can play the version of the game shown above at http://www.2flashgames.com/play/f-35.htm(sorry about the commercial you have to watch before you play)

You can play another version of the game at http://www.math.uiuc.edu/~rkirov2/lightout/lightout.html 



The Assignment Specifics

Hey, this makes a good problem for agents that employ search.  Write an agent that can take an initial configuration of lights and determine a sequence of lights that will turn off all of the lights in the grid!

For this assignment we will consider a 4x4 array of lights that will be numbered as followed:

If you consider this problem


For this homework you should write a program that fits the following requirements:

  1. Your code must take in the "starting state" of the puzzle as a SINGLE, string of 1s and 0s where 1 is on and 0 is off.  Thus, "1101110101011101010111011" represents the following configuration

    In order to facilitate grading of this you must meet the following requirements:



NOTE: If any of what is listed above is unclear to you than you should talk to me prior to submitting your assignment. Failure to follow these directions will result in lost points.


Hints from past experience with this assignment...

Remember what happens when you "copy" a referential data type in Java... you only get a copy of the reference, not a copy of the object.  This means that if you have a node that you want to copy several times and modify to create the children nodes, you need to be careful what you do to copy the node.  Students have a habit of saying something like:

    Node parent = new Node();
    Node child1 = parent;
    Node child2 = parent;
    Node child3 = parent;

This just gives you FOUR variables all of which point to the same single instant.  Students end up forgetting this and then being surprised when child1, child2, and child3 are identical and TOTALLY screwed up (in essence, they performed 3 different actions on the same single object).

You will need to write code which produces a true, second copy of whatever data structure you use in your tree. 

Similar "copy by value" vs. "copy by reference" problems exist in other languages including python.  Make sure you pay attention to this issue


2)  When it gets to be time to test your code, start with simple problems.  For example,


can EASILY be solved by turning off the light in room 6.  The shortest solution is ONE move.  If your code can't solve this, than you have a significant problem.  Similarly, your code should detect that


is already a solution and requires no moves at all.


Submitting Your Work

Prior to the deadline, use the homework submission system (https://www.cs.uni.edu/~schafer/submit/which_course.cgi) to upload any files you have produced. 

In addition to online copies, please submit hard copies of this at the start of class on the day this is due.