68
\$\begingroup\$

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>

\$\endgroup\$
  • 9
    \$\begingroup\$ If you're interested in this kind of puzzle games, have a look at Simon Tatham's Portable Puzzle Collection. Apart from this type (called Flip there), you can find variants of many Japanese and other puzzles. Everything is under BSD license and probably an interesting read. \$\endgroup\$ – Dubu Feb 8 '18 at 11:22
  • 10
    \$\begingroup\$ How about reverse-engineering it? Start with a blank board, then automate, say 20 clicks on random squares. That way you know there must be a solution at the end. \$\endgroup\$ – AJFaraday Feb 9 '18 at 12:48
  • 3
    \$\begingroup\$ I want to keep playing, but due to your question, the uncertainty of whether or not I'll actually win is eating at me! Fun game :) \$\endgroup\$ – MrDuk Feb 9 '18 at 15:54
  • \$\begingroup\$ @MrDuk codepen.io/qwertyquerty/pen/WMGwVW here's the finished project! This one is fixed, and polished up. I've also made an electron app. \$\endgroup\$ – Qwerty Feb 9 '18 at 18:17
  • \$\begingroup\$ @Qwerty when I tried to view your Pen in full page view, I got the message "The owner of this Pen needs to verify their email address to enable Full Page View." Please verify your email address on CodePen so I can enjoy your game in the full window! :) \$\endgroup\$ – stephenwade Feb 11 '18 at 21:33
161
\$\begingroup\$

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.

\$\endgroup\$
  • 22
    \$\begingroup\$ @Qwerty: for your specific problem, clicking the same square twice cancels itself out, so there's never any reason to click any square more than once. You might want to choose a certain number of squares to click without repeating, or consider a solution that assigns an XX% chance-of-click to each square on the board. (Ed: Nice answer, +1!) \$\endgroup\$ – Jeff Bowman Feb 8 '18 at 0:08
  • 3
    \$\begingroup\$ I've made almost the exact same game before and ended up using this approach. I included an animation at the start showing the solved state going to the unsolved state in a quick fashion; it was pretty. \$\endgroup\$ – Jared Goguen Feb 8 '18 at 2:47
  • 1
    \$\begingroup\$ @JaredGoguen odd, I added that and came back here to see your comment. \$\endgroup\$ – Qwerty Feb 8 '18 at 3:56
  • 4
    \$\begingroup\$ @JeffBowman Indeed, the set of solvable games can be treated as a 25-bit value, with each bit corresponding to a square that is the number of times it's been flipped mod 2. So one can generate a random number in the range 0..33,554,432 and then calculate the value of each square on the board from it in short order. \$\endgroup\$ – Monty Harder Feb 8 '18 at 20:06
  • 7
    \$\begingroup\$ For what it's worth, while this is the correct answer to the mathematical question of how to answer this problem, this is usually a dubious practice from a design standpoint. This sort of generation, without any particular plan to it, generally leads to puzzles that feel very 'samey', without any particular points of interest or any unifying themes. It's possible to 'procedurally generate' interesting problem instances for a puzzle game, but it usually requires a much harder look at what the interesting features of your puzzles are. \$\endgroup\$ – Steven Stadnicki Feb 9 '18 at 1:53
92
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ It's kind of sad to find out that it's already been made. I thought I was on to something. \$\endgroup\$ – Qwerty Feb 8 '18 at 4:05
  • 39
    \$\begingroup\$ @Qwerty there are very few original ideas, and you certainly don't need to have one to be successful (c.f. Rovio, King). \$\endgroup\$ – OrangeDog Feb 8 '18 at 9:48
  • 14
    \$\begingroup\$ This particular game exists, but you can always expand on the idea! Add more features! Add different rules for what happens when you click somewhere, like colors that add together based on which direction it was activated/deactivated from. Add different “tools” that you have to use. Add non-rectangular boards! Lots of fun stuff to do. Just remember that a move must always reverse itself. \$\endgroup\$ – Ed Marty Feb 8 '18 at 13:25
  • 7
    \$\begingroup\$ @OrangeDog: Even 'Lights Out' wasn't original, that's just the brand name that got popular in the 90's. The wikipedia article, for example, lists this and this \$\endgroup\$ – BlueRaja - Danny Pflughoeft Feb 8 '18 at 17:17
  • 1
    \$\begingroup\$ Which answers are you referring to as "the above answers"? It's completely unclear, since on my screen, there's only one answer above yours. Remember that answers change order depending on votes and user options. You should always link to specific answers instead of referring to something "above". \$\endgroup\$ – David Richerby Feb 12 '18 at 16:50
13
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ More than half are "inverses" - besides horizontal reflections, you have vertical reflections and rotations. \$\endgroup\$ – Clockwork-Muse Feb 8 '18 at 3:31
  • \$\begingroup\$ @Clockwork-Muse, yes, but that's harder to calculate an exact number for, because while asymmetric designs can be rotated and flipped in 8 permutations, symmetric designs have fewer permutations. So I only mentioned the white/black inverting, since every solution has exactly 1 inverse. (Although for that inverse to work, you do have to prove that you can flip the entire board) \$\endgroup\$ – Arcanist Lupus Feb 8 '18 at 5:32
  • \$\begingroup\$ It turns out, as Robert Mastragostino mentioned in his answer, this is actually a well known, well studied problem. Each solvable puzzle has exactly 4 solutions, and the majority of random boards are not solvable. Searching all of that space might be fun, but since there already exists a proof (math.ksu.edu/math551/math551a.f06/lights_out.pdf) you could also do a couple of dot products and have the same answer in a few microseconds. :) \$\endgroup\$ – GrandOpener Feb 8 '18 at 8:13
  • \$\begingroup\$ Math time: If you want to calculate the number of distinct boards (regardless of solvability), taking all symmetries into account, then Burnside's lemma is the way to go: There are 16 symmetries (one trivial, three rotations, four reflections, and then each of those 8 combined with inversion of on/off), and for each of those symmetries some number of boards are entirely unchanged. If you take the average of entirely unchanged boards per symmetry, that's equal to the number of distinct boards. \$\endgroup\$ – Arthur Feb 8 '18 at 10:06
  • 1
    \$\begingroup\$ @PeterTaylor It will definitely take far longer to code the simulator than it will to run the results. \$\endgroup\$ – corsiKa Feb 8 '18 at 23:39
4
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.