# October, 2008

• #### An algorithm to solve a matrix game

There is a nice game called Enlight from FeejoSoft. I have it on my PocketPC phone and for the life of me I just couldn't get past level 33. So yesterday I finally sat down and implemented an algorithm to solve this game automatically.

Of course, I used C# and Visual Studio (as a tester, I used our latest internal build of Visual Studio 2010, although it will run just as fine on 2008 as well).

The game

The rules are really simple. There is a boolean matrix 10x10, and you can invert cells. When you invert a cell, all its neighbors (usually four) are inverted with it. Given this operation, you are required to nullify the matrix (turn off all the lights):

The game is freeware and you can use your favorite search engine to find and download it (e.g. from freewareppc.com, no responsibility for links). If you'd like to run it in an emulator, here are the steps:

1. On a machine with ActiveSync, install the game executable.
2. Use dir /s setup*.cab to find the .cab file (usually it will unpack to \Windows\WindowsMobile\TapIsland)
3. Open Visual Studio and create a new SmartPhone application
4. Run (F5) to launch the emulator
5. In the emulator menu, click File -> Configure -> Shared path and specify the path to the .cab file from step 2
6. Open File Explorer in the emulator and go to the Storage card folder
7. Install the game by running the .cab file from there
8. Run the game!

The algorithm

The idea I used is commonly used for such problems (e.g. eight queens puzzle (http://en.wikipedia.org/wiki/8_queens) is usually solved using depth-first search with backtracking). I encourage you to visit this wikipedia article, it is very interesting read.

We'll visit every cell column by column. Every cell will have it's next cell which is down in the next row, or the first cell of the next column to the right. For brute force, you would recurse to visit the next cell, then come back, toggle the cell and recurse again. This way every cell will be tried in both combinations. However this will yield 2^100 iterations. We can considerably trim down the search if we don't recurse for knowingly invalid boards. This way we prune the "phase space" of the problem significantly. Here's the complete code for the solver:

```namespace MatrixGame
{
public class Solver
{
private Field sourceField;
private Field solution = new Field();
private Field currentSolution = new Field();

private Solver(Field field)
{
this.sourceField = new Field(field);
}

public static Field FindSolution(Field field)
{
Solver solver = new Solver(field);
solver.Search(FieldCoordinates.StartingPoint);
return solver.solution;
}

private int steps = 0;

/// <summary>
/// Main algorithm
/// </summary>
void Search(FieldCoordinates current)
{
steps++;

// we traverse the cells column by column,
// left to right, top to bottom
var next = current.GetNextCell(sourceField);

// we've reached the end of the field
if (next.Column == sourceField.Width)
{
if (LeftCellIsEmpty(current))
{
CheckSolutionCandidate();
}
return;
}

// pruning - only continue searching if this is a plausible board so far
if (current.Column == 0 || LeftCellIsEmpty(current))
{
Search(next);
}

// let's invert the current cell and search again
currentSolution.InvertCell(current);
sourceField.Invert5Cross(current);

if (current.Column == 0 || LeftCellIsEmpty(current))
{
Search(next);
}
}

/// <summary>
/// If the cell to the left from current is not empty,
/// the current board cannot be a solution -
/// no point to continue down this branch.
/// Prune this and backtrack to another branch.
/// </summary>
bool LeftCellIsEmpty(FieldCoordinates current)
{
return !sourceField[current.Row, current.Column - 1];
}

/// <summary>
/// We've traversed all elements -
/// let's check if what we've come up with is actually a solution
/// we checked almost all cells in LeftCellIsEmpty
/// let's just check the last (rightmost) column
/// </summary>
void CheckSolutionCandidate()
{
if (sourceField.GetColumn(sourceField.Width - 1).IsNull())
{
SolutionFound();
}
}

/// <summary>
/// We got it! Do something with the solution!
/// </summary>
void SolutionFound()
{
solution = new Field(currentSolution);
}
}
}```

The solution program

Here's what I came up with. On the left board, you set up the level like you see in the game (the picture shows The Notorious Level 33!). Left-click to toggle a cell, drag the mouse to "draw" adjacent cells.

On the right, you have a chance to play this level, however, the orange dots show which cells you need to click to turn off the lights. If you feel honest, you can turn off the orange dots using the checkbox.

http://code.msdn.microsoft.com/EnlightGameSolver

The research

First of all, I was amazed how efficient the pruning is. The fact that we don't check for knowingly invalid boards brings us down from 2^100 to just 93183 times the Search method is executed. On my machine this is so fast, that I manage to recalculate the hint solution in real time, as the user clicks in the left board.

Also, building this project raised more questions than it answered. I'm sure there is a whole science behind this seemingly simple domain - Conway's Game of Life is just around the corner, not to mention MineSweeper, cellular automata, even-odd-logic, 0,1-matrices, constraint programming, etc. etc. It is fascinating how complex solutions exist to invert a single pixel on the board:

What is the pattern here? Is the solution always unique? Why is there no solution for some configurations? What if you apply the solution to the solution? What about unlimited two-dimensional plane? Which single-cell source board have a solution? Which don't? What is special about a board consisting of such cells? What is the ratio of yellow cells for such boards? All these are interesting questions I'd love to think about, if only someone would do my main job for me :)

The challenge

As usual, better/faster/shorter solutions are welcome. I'd be especially curious to see a solution in F# or Prolog. Feel free to reuse my UI code.

• #### Live Geometry project updated to Silverlight 2 final release

Finally I had time again to continue working on my Live Geometry project on CodePlex. While I was busy with other stuff, Silverlight 2 has officially released and the rest of the world has already upgraded from Beta 2 to the release version. Now I'm catching up: I've updated the source code for both Silverlight (online) and WPF (desktop) editions, so it should build fine. As usual, you can preview the Silverlight (online) edition at:

http://geometry.osenkov.com

As you can see, I started implementing the coordinate grid and axes. I'm thinking to implement pan/zoom functionality by dragging the coordinate system and using the mouse wheel. Also I need to have a toggle button to show/hide the grid/axes, and numbers (-2, -1, 0, 1, 2, ...) to show up along the coordinate axes. Then I can start working on plotting function graphs and charts.

I've also updated the desktop (WPF) version, although I didn't have time to make it look beautiful:

The beauty of WPF is composability. The toolbar icons use the same logic for drawing points/lines/circles as the main canvas. This way the icons are vector graphics and can be scaled if I want to make the toolbar buttons larger in the future. Also, the buttons in the toolbar are generated automatically using Reflection and data-binding, so when I add a class for a new tool, I don't need to do anything else - reflection will pick it up and create a toolbar button for it using WPF databinding.

Also the good news is that the WPF edition shares the same source code with the Silverlight version. Only at two or three places in code I had to use the #if SILVERLIGHT compiler directives, mostly because WPF VisualTreeHelper.HitTest is called VisualTreeHelper.FindElementsInHostCoordinates in Silverlight (because of slightly different semantics). Andy Beaulieu blogs about this breaking change here: http://www.andybeaulieu.com/Default.aspx?tabid=67&EntryID=95

• #### Kirill's Visual Studio Tips

I decided to compile a small list of Visual Studio features that I use a lot.

Code Editor

1. Code Snippets for ‘prop’, ‘foreach’, ‘if’, ‘class’, ‘interface’, Tab-Tab completion
2. Surround with (snippets) - try, if
3. Ctrl+K,D – FormatDocument
4. Ctrl+Left/Right arrows in code editor – jump between words faster
5. Ctrl+K,C – Ctrl+K,U – comment/uncomment selection
6. Dynamic Snippets in the XML Editor - I bet a lot of people don't know about this one

1. F12 (Go To Definition) – position the caret on an identifier and hit F12
2. Shift+F12 (Find All References) – then hit F8 to step through the results in the Find Symbol results window
3. Click the “back” button on the Microsoft Explorer mouse with your thumb navigates back (under C# profile)
4. Right-click on a document Tab – Copy Full Path, Open Containing Folder

Refactoring

1. Position the caret on an identifier and hit F2 (Refactor -> Rename)

Code generation

1. Generate Method Stub (Smart Tag) - Ctrl+. and enter
2. WindowsContextMenuButton + O + ENTER + A – quick way to organize, remove and sort usings

Debugging

1. Debug -> Exceptions (allows breaking on a first-chance exception)
2. Right-click on a breakpoint brings up a context-menu which not everyone knows about ;-)
3. Tools -> Options -> Debugging -> Enable just my code
4. Attach to process -> Cross Platform Debugging (Managed, Native)
5. .load sos, !clrstack, !dumpheap, !gcroot, etc.

Solution Explorer

1. Tools -> Options -> Projects and Solutions -> Track Active Item in Solution Explorer
2. Right-click on an item in Solution Explorer – Open Folder in Windows Explorer
3. Right-click on a project -> Unload -> edit .csproj file in XML

Macros and automation:

P.S. Sara Ford has much much more in her famous Did you know series.

Page 1 of 1 (3 items)