Tiger Lights Out Algorithm.... / Computer Science / Forums

Forums

4hv.org :: Forums :: Computer Science

« Previous topic | Next topic »

Tiger Lights Out Algorithm....

Move Thread

LAN_403

Slava

Fri Mar 04 2016, 01:50AM

Registered Member #518 Joined: Tue Feb 13 2007, 05:20AM
Location: New York
Posts: 168

I am currently trying to write an algorithm that solves the lights out game...

I am writing it in C# ... the idea is this...

start at the top and toggle the light under the one that is turned on. Work your way down to the bottom. If the pass doesn't solve the puzzle start at the top again with a random light at the top turned on.

Here is a web based version of the game to try it out.

Here is my C# code... (Yes, I can make a "DidWin()" function faster but it works for now, the game should solve in only a few iteration...)

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

namespace LightsOut002
{
    class Program
    {
        static void Main(string[] args)
        {

            LightsOutBoard lo1 = new LightsOutBoard();
            lo1.Grid[1, 2] = true;
            lo1.Grid[2, 2] = true;
            lo1.Grid[3, 2] = true;

            Console.Clear();
            Console.WriteLine("PRESS ENTER TO START...");
            Console.ReadLine();



            while (true)
            {

                for (int yy = 1; yy < 5; yy++)
                {
                    

                    for (int xx = 0; xx < 5; xx++)
                    {


                        // show while working
                        Console.Clear();
                        Console.ForegroundColor = ConsoleColor.Yellow;
                        Console.WriteLine(lo1.ToStr());
                        Thread.Sleep(50);


                        if (lo1.Grid[xx, yy - 1] == true)
                        {
                            lo1.Press(xx, yy);
                        }
                    }


                    

                }

                if (lo1.DidWin() == false)
                {
                    Random rnd1 = new Random(Environment.TickCount);
                    int top_num = rnd1.Next(0, 4);
                    lo1.Grid[top_num, 0] = true;
                }
                else
                {
                    Console.WriteLine("YOU WIN!!!!!");
                    Console.ReadLine();
                }


                Thread.Sleep(500);
            }



        }














        class LightsOutBoard
        {
            public bool[,] Grid = new bool[5, 5];

            public bool DidWin()
            {
                int cnt = 0;
                for (int y = 0; y < 5; y++)
                {
                    for (int x = 0; x < 5; x++)
                    {
                        if (Grid[x, y] == true) { cnt++; }
                    }
                }

                bool ret = false;
                if (cnt < 1) { ret = true; } else { ret = false; }
                return ret;
            }


            public void Press(int x, int y)
            {
                if (Grid[x, y] == true) { Grid[x, y] = false; } else { Grid[x, y] = true; }




                if ((x - 1) >= 0)
                {
                    Grid[x - 1, y] = !Grid[x - 1, y];
                }

                if ((x + 1) <= 4)
                {
                    Grid[x + 1, y] = !Grid[x + 1, y];
                }

                if ((y - 1) >= 0)
                {
                    Grid[x, y - 1] = !Grid[x, y - 1];
                }

                if ((y + 1) <= 4)
                {
                    Grid[x, y + 1] = !Grid[x, y + 1];
                }

            }



            public string ToStr()
            {
                string ret = "";
                for (int y = 0; y < 5; y++)
                {
                    for (int x = 0; x < 5; x++)
                    {
                        if (Grid[x, y] == true)
                        {
                            ret += "X ";
                        }
                        else
                        {
                            ret += "- ";
                        }
                    }

                    ret += "\n\n";

                }

                return ret;
            }


        }


    }
}

Bjørn

Fri Mar 04 2016, 11:32AM

Registered Member #27 Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058

I can see two flaws in the code.

rnd1.Next(0, 4);

will never generate the number 4 so the rightmost light will never be randomly set.

There exists a pattern that causes your algorithm enter an infinite loop:

Slava

Fri Mar 04 2016, 02:52PM

Registered Member #518 Joined: Tue Feb 13 2007, 05:20AM
Location: New York
Posts: 168

It works now!!!!

Thanks!

Slava

Fri Mar 04 2016, 03:07PM

Registered Member #518 Joined: Tue Feb 13 2007, 05:20AM
Location: New York
Posts: 168

Slava

Fri Mar 04 2016, 05:18PM

Registered Member #518 Joined: Tue Feb 13 2007, 05:20AM
Location: New York
Posts: 168

Here is a more efficient approach based on the algorithm I found in this video... For some reason it still takes a lot of iterations to solve...

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

namespace LightsOut002
{
    class Program
    {
        static void Main(string[] args)
        {

            LightsOutBoard lo1 = new LightsOutBoard();
            lo1.Grid[1, 2] = true;
            lo1.Grid[2, 2] = true;
            lo1.Grid[3, 2] = true;

            Console.Clear();
            Console.WriteLine("PRESS ENTER TO START...");
            Console.ReadLine();



            while (true)
            {

                for (int yy = 1; yy < 5; yy++)
                {


                    for (int xx = 0; xx < 5; xx++)
                    {


                        // show while working
                        Console.Clear();
                        Console.ForegroundColor = ConsoleColor.Yellow;
                        Console.WriteLine(lo1.ToStr());
                        Thread.Sleep(50);


                        if (lo1.Grid[xx, yy - 1] == true)
                        {
                            lo1.Press(xx, yy);
                        }
                    }




                }

                if (lo1.DidWin() == false)
                {

                    bool gotit = false;

                    if ((lo1.Grid[0, 4] == true) & (gotit == false))
                    {
                        gotit = true;
                        lo1.Grid[3, 0] = true;
                        lo1.Grid[4, 0] = true;
                    }
                    if ((lo1.Grid[1, 4] == true) & (gotit == false))
                    {
                        gotit = true;
                        lo1.Grid[1, 0] = true;
                        lo1.Grid[4, 0] = true;
                    }
                    if ((lo1.Grid[2, 4] == true) & (gotit == false))
                    {
                        gotit = true;
                        lo1.Grid[3, 0] = true;
                    }

                    if (gotit == false)
                    {
                        Random rnd1 = new Random(Environment.TickCount);
                        int top_num = rnd1.Next(0, 5);
                        lo1.Grid[top_num, 0] = true;
                    }



                }
                else
                {
                    Console.WriteLine("YOU WIN!!!!!");
                    Console.ReadLine();
                }


                Thread.Sleep(500);
            }



        }














        class LightsOutBoard
        {
            public bool[,] Grid = new bool[5, 5];

            public bool DidWin()
            {
                int cnt = 0;
                for (int y = 0; y < 5; y++)
                {
                    for (int x = 0; x < 5; x++)
                    {
                        if (Grid[x, y] == true) { cnt++; }
                    }
                }

                bool ret = false;
                if (cnt < 1) { ret = true; } else { ret = false; }
                return ret;
            }


            public void Press(int x, int y)
            {
                if (Grid[x, y] == true) { Grid[x, y] = false; } else { Grid[x, y] = true; }




                if ((x - 1) >= 0)
                {
                    Grid[x - 1, y] = !Grid[x - 1, y];
                }

                if ((x + 1) <= 4)
                {
                    Grid[x + 1, y] = !Grid[x + 1, y];
                }

                if ((y - 1) >= 0)
                {
                    Grid[x, y - 1] = !Grid[x, y - 1];
                }

                if ((y + 1) <= 4)
                {
                    Grid[x, y + 1] = !Grid[x, y + 1];
                }

            }



            public string ToStr()
            {
                string ret = "";
                for (int y = 0; y < 5; y++)
                {
                    for (int x = 0; x < 5; x++)
                    {
                        if (Grid[x, y] == true)
                        {
                            ret += "X ";
                        }
                        else
                        {
                            ret += "- ";
                        }
                    }

                    ret += "\n\n";

                }

                return ret;
            }


        }


    }
}

jdub1581hv

Fri Mar 04 2016, 06:28PM

Registered Member #55219 Joined: Tue Jun 09 2015, 11:21PM
Location:
Posts: 80

not sure if it's the same in C#, but it is usually a good idea in for loops to have the following:
for( int i = 0; i <= 5; i++){ code }
adding the 'or equals' helps to avoid memory leaks..

I'm a java whore so it may be different... But have you thought of Java? the JavaFX is a really clean UI, and easy to use..
There is also the added bonus of lambdas, FXML (UI markup), and javascript all built in.. Syntax is 'almost' identical..
Almost forgot the Stream api as well, it's Very fast with list sorting, mapping, etc...

I did a lot of 3d work with it, and with the Stream api, I could iterate 5 million+ vertices in no time at all, on top of the other items / textures in the scenegraph

Moderator(s): Chris Russell, Noelle, Alex, Tesladownunder, Dave Marshall, Dave Billington, Bjørn, Steve Conner, Wolfram, Kizmo, Mads Barnkob