## Homework 1

### Introduction

"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

• it has a branching factor, b, of 16 (you can toggle 16 different lights)
• the actual depth of the optimal solution (d) varies depending on the starting configuration, BUT...
• it has a maximum depth (m) for the optimal solution of 16 (if you toggle the same light twice you are back where you started and have no net change - even if you have done other things in between.  That is, notice that the sequence 1, 2, 1, produces the exact same end result as the sequence 2.).  Thus, we will make an assumption that 16 is our maximum depth to consider

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:

• Python
• Your search must start via a method called "search" which is in a file called "LightsOut.py"
• Search() expects one string as a parameter.
• This means I will invoke your code via something like:
• Java
• Your search must be in a non-main class called LightsOut.
• This should have a constructor that takes in the board as a parameter.
• The search should be executed if I invoke the "search" function.
• This means that I will invoke your code via something like:
• And it will produce something like:

• Other language:
• You must include a readme file which indicates how I would run your code on a machine in the student lounge (it is your responsibility to make sure it will run in that environment).
• You must include a runtime mechanism for me to enter the input board.
2.
• You must use one of the uninformed search techniques we studied in class to find a solution.  To receive full credit it must be an optimal solution.  Given that constraint, I believe only two search techniques make sense. Your program MUST print which search strategy it is using when the code starts.

• When a solution is found you need to print out the sequence of moves that will get you from the initial state to the goal state.

• Your code must also print the total number of nodes CHECKED so far (gives us an idea of time) and the number of nodes still stored in the frontier (gives us an idea of memory usage).

• For a few bonus points, you may implement more than one search strategy (again, I think that only two of these REALLY make sense). If you do this you should submit two different solutions and clearly label each solution with

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;
child1.modifyOneWay();
child2.modifyAnotherWay();
child3.modifyYETAnotherWay();
```

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,

```0100
1110
0100
0000```

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

```0000
0000
0000
0000```

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.