LightGameSolver

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LightsGameSolver
{
    class Program
    {
        struct Step
        {
            public byte x;
            public byte y;
            public Step(byte x, byte y)
            {
                this.x = x;
                this.y = y;
            }
        }

        static Random rnd = new Random();

        static void Main(string[] args)
        {

            Console.WriteLine("Creating Lights");

            bool[,] lights = new bool[3 + rnd.Next(3), 3 + rnd.Next(3)];

            for (int x = 0; x < lights.GetLength(0); x++)
            {
                Console.WriteLine();
                for (int y = 0; y < lights.GetLength(1); y++)
                {
                    lights[x, y] = rnd.Next(2) == 0;
                    if (lights[x, y]) Console.Write("X"); else Console.Write("O");
                }
            }

            Step[] steps = Solve(ref lights);

            Console.WriteLine(); Console.WriteLine();

            Console.WriteLine("Solved in " + steps.Length + " steps:");

            for (int x = 0; x < lights.GetLength(0); x++)
            {
                Console.WriteLine();
                for (int y = 0; y < lights.GetLength(1); y++)
                {
                    if (lights[x, y]) Console.Write("X"); else Console.Write("O");
                }
            }
            Console.WriteLine(); Console.WriteLine();
            for (int i = 0; i < steps.Length; i++)
            {
                Console.WriteLine("Step " + (i + 1) + ": " + steps[i].x + " , " + steps[i].y);
                Console.ReadLine();
            }

            Console.ReadLine();
        }

        static Step[] Solve(ref bool[,] lights)
        {
            List<Step> steps = new List<Step>();

            while (!Solved(lights))
            {
                var x = rnd.Next(lights.GetLength(0));
                var y = rnd.Next(lights.GetLength(1));
                steps.Add(new Step((byte)x, (byte)y));

                lights[x, y] = !lights[x, y];

                if (x - 1 > 0) lights[x - 1, y] = !lights[x - 1, y];
                if (y - 1 > 0) lights[x, y - 1] = !lights[x, y - 1];
                if (x + 1 < lights.GetLength(0)) lights[x + 1, y] = !lights[x + 1, y];
                if (y + 1 < lights.GetLength(1)) lights[x, y + 1] = !lights[x, y + 1];

                if (steps.Count % 100000 == 0) Console.WriteLine("Solver: Maybe...");
                if (steps.Count == 10000000)
                {
                    Console.WriteLine("Solver: Probably Not.");
                    Console.ReadLine();
                    Environment.Exit(42);
                }
            }
            return steps.ToArray();
        }

        static bool Solved(bool[,] lights)
        {
            foreach (var light in lights)
                if (light) return false;
            return true;
        }
    }
}