4

I am trying to create a solvability function for a game algorithm. Basically a function that returns true or false for a given game if it is solvable or not.

The game is a type of lights-out game. Basically You have a M*N grid of buttons. When the game starts, a random number or a stored pattern of these lights is switched on. Pressing any of the lights will toggle a square of four buttons including the pressed button.

so I'm looking for an algorithm that returns true if we can turn off all the lights and return false if we can't do this.

AshKan
  • 779
  • 2
  • 8
  • 22
  • "A square of four including the pressed button" -- are there other constraints? For a button not on an edge, there are four possible 'squares of 4'. – Jongware Nov 16 '14 at 11:05
  • there are no other constraints and there is no different between these four possible squares of 4. – AshKan Nov 16 '14 at 11:13
  • I don't get it. How is decided *which square* of 4 gets toggled, relative to the pressed button? – Jongware Nov 16 '14 at 11:26
  • Let's say in this way that we have a big hand and in each step we press a square of 4 buttons together instead of one. – AshKan Nov 16 '14 at 11:47
  • Or, in each step we choose a square of four buttons and toggle the states of it's buttons – AshKan Nov 16 '14 at 11:52
  • Okay--apologies for misunderstanding. One always presses a square of four buttons (rather than "one with 3 around it). I think you can brute-force test it by having the computer always press (x,y),(x+1,y),and the row below it, for every lighted button (x,y). If you end up with a light at the very right or bottom, it can't be done. – Jongware Nov 16 '14 at 12:11
  • The game in the duplicate seems different; it toggles neighbouring lights, not any 4x4 square. – Jongware Nov 16 '14 at 14:00
  • @Jongware: The answers given to that question will work regardless of which lamps each button toggles, though. Still, your answer gives a simple solvability criterion for this particular instance of the game that *doesn't* apply to more general variants, so I do agree that it's worth keeping them separate. – Ilmari Karonen Nov 16 '14 at 14:09

1 Answers1

5

The number of on-lights in each row and each column must be even (where '0' is considered 'even' as well).

Proof: suppose you must press 2 horizontal adjacent buttons. If you start out with 1 light only, at the far left, no matter what you do, you will end up with a single light on. On the other hand, as soon as you have 2 lights at any distance, you can 'move' one light close to the other until they are adjacent, at which point you can switch them both off.

The same is true for vertically adjacent buttons, and by extension for a 2x2 button grid: whenever you switch off any single certain light, the other toggles ensure the number of on-lights stays a multiple of 2 per row and column.

This, for example, is solvable:

solvable toggles

and this one is not (note the odd numbers in some columns and rows):

unsolvable toggles

Jongware
  • 22,200
  • 8
  • 54
  • 100
  • 1
    +1. Your answer could be even better, though, if you also proved this solvability criterion to be sufficient as well as necessary (i.e. that the methodical solution method demonstrated in your animations really does solve all boards satisfying the criterion). – Ilmari Karonen Nov 16 '14 at 14:13
  • @Ilmari: I briefly considered that ... but my maths is not sufficient to extend it! I tried a number of totally random boards and could not find a counter-example, so at least my logic holds heuristically. – Jongware Nov 16 '14 at 21:04
  • @Jongware What did you use to create these gifs? – Shridhar R Kulkarni Dec 22 '20 at 13:35