Game algorithm lights up

Question

This is homework. I have to develop and turn off the game using the backtracking description below.

The game consists of a 5-by-5 ​​grid; when the game starts, a set of these lights is turned on (random or one of the set of saved puzzle patterns). Pressing one of the lights will turn on and off the four lights next to it. (The diagonal neighbors are not affected.) There is a puzzle in the game: if you have some initial configuration in which some lights are on and some are off, the goal is to turn off all the lights, preferably with as few buttons as possible.

My approach goes from 1 to 25 and checks if all the lights are off or not. If not, then I will check from 1 to 24, and so on, until I get to 1 or find a solution. No, if there is no solution, then I will start from 2 to 24 and follow the process described above until I reach 2 or the solution found.

But through this I do not get the result? for example, is the light in (0,0) (1,1) (2,2) (3,3) (4,4) turned ON?

If someone needs a code, I can post it.

Can someone tell me the correct approach using backtracking to solve this game?

Thanks.

Answer 1

There is a standard algorithm for solving this problem, based on a Gaussian exception over GF (2). The idea is to set up a matrix representing a button that clicks a column vector representing light, and then use standard matrix simplification methods to determine which buttons to click. It works in polynomial time and does not require any return.

I have an implementation of this algorithm, which includes a mathematical description of how it works on my personal site. Hope you find this helpful!

Change If you are forced to use backtracking, you can use the following facts:

• Any solution will never push the same button twice, as this will cancel the previous step.
• Any decision either presses the first button or does not.

Given this approach, you can solve this with backtracking using a simple recursive algorithm that tracks the current state of the board and which buttons you have already made decisions:

• If you decide on each button, then return whether the board is enabled or not.
• Otherwise:
  • Try clicking the next button and see if the recursively resolved board is allowed there.
  • If so, return success.
  • Otherwise, try not to click the next button and not see if board replication is allowed.
  • If so, return success. If not, return the failure.

This will allow you to explore a search space of size 2 ²⁵ which is about 32 million. It is large, but not insurmountably large.

Hope this helps!

Answer 2

Rollback:

Incrementally build a solution, throwing away impossible solutions. 

Here is one approach based on the fact that there is an area of ​​inputs and outputs (pressing the button affects the square around it).

 problem = GIVEN solutions = [[0],[1]] // array of binary matrix answers (two entries, a zero and a one) for (problemSize = 1; problemSize <= 5; problemSize++) { newSolutions = []; foreach (solutions as oldSolution) { candidateSolutions = arrayOfNByNMatriciesWithMatrixAtTopLeft(min(5,problemSize+1), oldSolution); // size of candidateSolutions is 2^((problemSize+1)^2 - problemSize^2) // except last round candidateSolutions == solutions foreach (candidateSolutions as candidateSolution) { candidateProblem = boardFromPressingButtonsInSolution(candidateSolution); if (compareMatrix(problem, candidateProblem, 0, 0, problemSize, problemSize)==0) newSolutions[] = candidateSolution; } } solutions = newSolutions; } return solutions; 

Answer 3

As already suggested, you must first form a set of simultaneous equations.

First of all, it should be noted that a particular lighting button should be pressed no more than once, because it makes no sense to switch twice with the indicator light.

 Let Aij = Light ij Toggled { Aij = 0 or 1 } 

There should be 25 such variables.

Now for each of the lights you can create an equation similar to

 summation (Amn) = 0. { Amn = 5 light buttons that toggle the light mn } 

So, you will have 25 variables and 25 unknowns. You can solve these equations at the same time.

If you need to solve a problem using backtracking or recursion, you can solve the equations this way. Just assume that the initial value of the variables, see If they satisfy all the equations. If not, then go back.

Answer 4

Naive decision

First, you will need a way to represent the state of the board and stack to store all the states. At each step, make a copy of the board, changed to a new state. Compare this state with all the states of the board that you encounter. If you haven’t seen it, click this state on top of the stack and continue to the next step. If you saw him, try the next step. Each level will have to try all possible 64 moves before pulling the state from the stack (backtracking). You will want to use recursion to control the state of the next transition for validation.

There are no more than 2 ⁶⁴ possible board configurations, which means that you can potentially continue a very long chain of unique states and still run out of memory. (For reference, 1 GB is 2 ³⁰ bytes, and a minimum of 8 bytes is required to store the board configuration). This algorithm is unlikely to complete during the life of a known universe.

You need to do something smart to reduce your search space ...

Greedy first search

You can do more by first searching for states that are closest to the allowed configuration. At each step, sort the possible moves in order from most of the lights off to a minimum. Iterate in that order. This should work reasonably well, but an optimal solution is not guaranteed.

Not all puzzles are allowed.

No matter what algorithm you use, there may be no solution, that is, you can search forever (or at least several trillion years) without finding a solution.

You will need to check the solvability fee (this is a much faster algorithm than it turns out) before spending time looking for a solution.