How can I know if my puzzle game is always possible?

Question

I've made a sort of a puzzle game where the goal is to get rid of all of the white tiles. You can try it at the end of the question.

Each time, the board is randomly generated with white tiles in random places on a 5*5 grid. You can click any tile on that grid and it will toggle the color of it and all of the tiles touching it on its sides. My dilemma is the fact that I don't know if it will generate an impossible board. What is the best way to check things like this?

function newgame() {
 moves = 0;
    document.getElementById("moves").innerHTML = "Moves: "+moves;

  for (var i = 0; i < 25; i++) {
   if (Math.random() >= 0.5) {
$(document.getElementsByClassName('block')[i]).toggleClass("b1 b2")
   }
}
}
newgame();
function toggle(a,b) {  
  moves += 1;
  document.getElementById("moves").innerHTML = "Moves: "+moves;
$(document.getElementsByClassName('block')[a+(b*5)]).toggleClass("b1 b2");

if (a<4) {$(document.getElementsByClassName('block')[(a+1)+(b*5)]).toggleClass("b1 b2")}
  
  
if (a>0) {$(document.getElementsByClassName('block')[(a-1)+(b*5)]).toggleClass("b1 b2")}
  
  
if (b<4) {$(document.getElementsByClassName('block')[a+((b+1)*5)]).toggleClass("b1 b2")}
  
if (b>0) {$(document.getElementsByClassName('block')[a+((b-1)*5)]).toggleClass("b1 b2")}
}

body {
  background-color: #000000;
}

.game {
  float: left;
  background-color: #000000;
  width: 300px;
  height: 300px;
  overflow: hidden;
  overflow-x: hidden;
  user-select: none;
  display: inline-block;
}

.container {
  border-color: #ffffff;
  border-width: 5px;
  border-style: solid;
  border-radius: 5px;
  width: 600px;
  height: 300px;
  text-align: center;
}

.side {
  float: left;
  background-color: #000000;
  width: 300px;
  height: 300px;
  overflow: hidden;
  overflow-x: hidden;
  user-select: none;
  display: inline-block;
}

.block {
  transition: background-color 0.2s;
  float: left;
}

.b1:hover {
  background-color: #444444;
  cursor: pointer;
}

.b2:hover {
  background-color: #bbbbbb;
  cursor: pointer;
}

.row {
  width: 300px;
  overflow: auto;
  overflow-x: hidden;
}

.b1 {
  display: inline-block;
  height: 50px;
  width: 50px;
  background-color: #000000;
  border-color: #000000;
  border-width: 5px;
  border-style: solid;
}




.b2 {
  display: inline-block;
  height: 50px;
  width: 50px;
  background-color: #ffffff;
  border-color: #000000;
  border-width: 5px;
  border-style: solid;
}



.title {
  width: 200px;
  height: 50px;
  color: #ffffff;
  font-size: 55px;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  vertical-align: middle;
}

.button {
  cursor: pointer;
  width: 200px;
  height: 50px;
  background-color: #000000;
  border-color: #ffffff;
  border-style: solid;
  border-width: 5px;
  color: #ffffff;
  font-size: 25px;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  vertical-align: middle;
  border-radius: 5px;
  transition: background-color 0.3s, color 0.3s;
}

.button:hover {
  background-color: #ffffff;
  color: #000000;
}

.sidetable {
  padding: 30px 0px;
  height: 200px;
}


#moves {
  width: 200px;
  height: 50px;
  color: #aaaaaa;
  font-size: 30px;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  vertical-align: middle;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<center>
  <div class="container">
  
  
  <div class="game"><div class="row"><div onclick="toggle(0,0);" class="block b1"></div><div onclick="toggle(1,0);" class="block b1"></div><div onclick="toggle(2,0);" class="block b1"></div><div onclick="toggle(3,0);" class="block b1"></div><div onclick="toggle(4,0);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,1);" class="block b1"></div><div onclick="toggle(1,1);" class="block b1"></div><div onclick="toggle(2,1);" class="block b1"></div><div onclick="toggle(3,1);" class="block b1"></div><div onclick="toggle(4,1);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,2);" class="block b1"></div><div onclick="toggle(1,2);" class="block b1"></div><div onclick="toggle(2,2);" class="block b1"></div><div onclick="toggle(3,2);" class="block b1"></div><div onclick="toggle(4,2);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,3);" class="block b1"></div><div onclick="toggle(1,3);" class="block b1"></div><div onclick="toggle(2,3);" class="block b1"></div><div onclick="toggle(3,3);" class="block b1"></div><div onclick="toggle(4,3);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,4);" class="block b1"></div><div onclick="toggle(1,4);" class="block b1"></div><div onclick="toggle(2,4);" class="block b1"></div><div onclick="toggle(3,4);" class="block b1"></div><div onclick="toggle(4,4);" class="block b1"></div></div></div>
    
    <div class="side">
      <center class="sidetable">
        <div class="title">Tiles</div>
        <br>
        <div class="button" onclick="newgame()">New Game</div>
        <br><br>
        <div id="moves">Moves: 0</div>
      </center>
    </div>
    
  </div>
    </center>

Answer 1

This is the type of game where the same move performed twice reverses the board to its previous state. So to ensure a board is solvable, generate it by playing in reverse. Start with a solved (blank) board, then start programmatically "clicking" randomly either a certain number of times, or until the board has the desired number of white squares. One solution is then to simply perform the same moves in the reverse order. Other shorter solutions may exist, but you are guaranteed to have at least one.

Another, much more complex solution, is to define a solving algorithm that goes through all possible game states from your starting position to try to find the solution. This would take much longer to implement and run, but would allow the boards to be truly randomly generated. I won't go into specifics of this solution, because it's just not as good an idea.

Answer 2

While the above answers are clever (and probably how I would do it anyway), this particular game is very well known. It's called Lights Out, and has been mathematically solved. There is a solution if and only if two sums of various elements (given on the wikipedia page) add to zero mod 2 (i.e. an even number). In general a little linear algebra should give similar solution conditions for games on any board.

Answer 3

Go the other way around when generating your puzzle.

Instead of randomly selecting the tiles and turning them from white to black, start from a blank slate, then select the tiles but instead of turning that tile to black, make it as if the user selected it, resulting in flipping all of the other tiles around it.

This way you'll be guaranteed to have at least one solution: the user will have to undo what you "AI" player did to create the level.

Answer 4

Ed and Alexandre have the right of it.

But if you do want to know if every solution is possible, there are ways.

There are a finite number of possible puzzles

Clicking on the same square twice produces the same result as not clicking on it at all, no matter how many clicks were made between them. That means that every solution can be described by giving each square a binary value of 'clicked' or 'not clicked'. Similarly, each puzzle can be described by giving each square a binary value of 'toggled' or 'not toggled'. That means that there are 2^25 possible puzzles, and 2^25 possible solutions. If you can prove that each solution solves a unique puzzle then there must be a solution to every puzzle. Similarly, if you find two solutions that solve the same puzzle then there cannot be a solution to every puzzle.

Also, 2^25 is 33,554,432. That's quite a lot, but it's not an unmanageable number. A good algorithm and a decent computer could probably brute force that in a couple of hours, especially when you consider that half the puzzles are inverses of the other half.

Answer 5

Generalized answer:

1. Create a matrix of size (# moves) x (# lights).
2. Put a 1 in a cell if making the move corresponding to that row toggles that light corresponding to that column, 0 otherwise.
3. Perform Gauss-Jordan elimination (modulo 2) on the matrix.
4. If the matrix that results has a single 1 in each column, and every row has at most a single 1, then every grid in solvable.

Answer 6

Others have already mentioned ways to find whether your randomly generated puzzle is solvable. the question you should also be asking though, is whether you actually want randomly generated puzzles.

Randomly generated puzzles all have the same core flaw: Their difficulty is pretty much unpredictable. The possible puzzles you might get can range from already solved, to trivial (solution is obvious) to hard (solution is not obvious) to impossible (the puzzle is not solvable at all). Because the difficulty is unpredictable, it makes for an unsatisfactory experience for the player, especially if they do multiple puzzles in a row. They're highly unlikely to get a smooth difficulty curve, which can make them bored or frustrated depending on what puzzles they get.

Another problem of random generation is that the time it takes for the puzzle to initialize is unpredictable. Generally speaking, you're going to get a solvable puzzle (almost) immediately, but with some bad luck, your randomly generated puzzles might end up on a streak of unsolvable puzzles.

One way to solve both of these is by having predefined vectors of every solvable puzzle available, arranged into difficulty groups, and then selecting a random puzzle from the solvable puzzles based on the difficulty. This way, you will be certain that every puzzle is solvable, that the difficulty is predictable and that the generation will be done in constant time.