Freigeben über

An algorithm to solve a matrix game

  • Artikel

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):

FeejoSoft Enlight

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 (https://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.

image

You can download the full source code here:

https://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:

image

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.

Comments

  • Anonymous
    October 06, 2008
    Nice post. If I have time I'll try to whip up a solution in F#.

  • Anonymous
    July 29, 2010
    I've been stuck on level 33 for more than a year and half and try at least a few times every week. I didn't even think of writing a program to solve it. Well done!