10

Regardless of the layout being used for the tiles, is there any good way to divvy out the tiles so that you can guarantee the user that, at the beginning of the game, there exists at least one path to completing the puzzle and winning the game?

Obviously, depending on the user's moves, they can cut themselves off from winning. I just want to be able to always tell the user that the puzzle is winnable if they play well.

If you randomly place tiles at the beginning of the game, it's possible that the user could make a few moves and not be able to do any more. The knowledge that a puzzle is at least solvable should make it more fun to play.

Buns of Aluminum
  • 2,439
  • 3
  • 26
  • 44

8 Answers8

20

Place all the tiles in reverse (ie layout out the board starting in the middle, working out)

To tease the player further, you could do it visibly but at very high speed.

cagcowboy
  • 30,012
  • 11
  • 69
  • 93
  • 1
    That doesn't guarantee victory, you can still end up with a situation where some tiles are impossible to get e.g., ABAB - there is no way to get the A's until you have gotten the B's and vice versa – 1800 INFORMATION Oct 01 '08 at 20:33
  • 1
    If you "play" the game in reverse, that formation would be impossible to create, unless the two A's are actually parts of two pairs, where the player removed the "wrong" one earlier. – Lasse V. Karlsen Oct 01 '08 at 20:34
  • Note that if you do it this way, you need to place the tiles in pairs rather than one-by-one. You could still create an impossible-to-win situation if you placed a tile, then placed its pair right on top of it. (Or you could just write code to specifically exclude this possibility.) – Ryan Lundy Dec 17 '09 at 18:35
10

Play the game in reverse.

Randomly lay out pieces pair by pair, in places where you could slide them into the heap. You'll need a way to know where you're allowed to place pieces in order to end up with a heap that matches some preset pattern, but you'd need that anyway.

Lasse V. Karlsen
  • 380,855
  • 102
  • 628
  • 825
  • I'm sorry but I would not be able to spend enough time on this problem to do it justice. I'd rather avoid getting into a "ok, but have you thought about ..." discussion in the comment after editing in pseudo-code and thus bumping a 11 year old question to the front page every now and then. – Lasse V. Karlsen Oct 14 '19 at 10:32
  • sorry for that. I wrote some code to generate suits, but sometimes It reached to a dead situation. so I'm wonder how to generate suit in reverse. – caochao Oct 14 '19 at 11:16
8

I know this is an old question, but I came across this when solving the problem myself. None of the answers here are quite perfect, and several of them have complicated caveats or will break on pathological layouts. Here is my solution:

Solve the board (forward, not backward) with unmarked tiles. Remove two free tiles at a time. Push each pair you remove onto a "matched pair" stack. Often, this is all you need to do.

If you run into a dead end (numFreeTiles == 1), just reset your generator :) I have found I usually don't hit dead ends, and have so far have a max retry count of 3 for the 10-or-so layouts I have tried. Once I hit 8 retries, I give up and just randomly assign the rest of the tiles. This allows me to use the same generator for both setting up the board, and the shuffle feature, even if the player screwed up and made a 100% unsolvable state.

Another solution when you hit a dead end is to back out (pop off the stack, replacing tiles on the board) until you can take a different path. Take a different path by making sure you match pairs that will remove the original blocking tile.

Unfortunately, depending on the board, this may loop forever. If you end up removing a pair that resembles a "no outlet" road, where all subsequent "roads" are a dead end, and there are multiple dead ends, your algorithm will never complete. I don't know if it is possible to design a board where this would be the case, but if so, there is still a solution.

To solve that bigger problem, treat each possible board state as a node in a DAG, with each selected pair being an edge on that graph. Do a random traversal, until you find a leaf node at depth 72. Keep track of your traversal history so that you never repeat a descent.

Since dead ends are more rare than first-try solutions in the layouts I have used, what immediately comes to mind is a hybrid solution. First try to solve it with minimal memory (store selected pairs on your stack). Once you've hit the first dead end, degrade to doing full marking/edge generation when visiting each node (lazy evaluation where possible).

I've done very little study of graph theory, though, so maybe there's a better solution to the DAG random traversal/search problem :)

Edit: You actually could use any of my solutions w/ generating the board in reverse, ala the Oct 13th 2008 post. You still have the same caveats, because you can still end up with dead ends. Generating a board in reverse has more complicated rules, though. E.g, you are guaranteed to fail your setup if you don't start at least SOME of your rows w/ the first piece in the middle, such as in a layout w/ 1 long row. Picking a completely random (legal) first move in a forward-solving generator is more likely to lead to a solvable board.

Merlyn Morgan-Graham
  • 58,163
  • 16
  • 128
  • 183
  • 1
    This is old, I know, but I pumped up my reputation only so I can come back and upvote this. Solving in reverse has many issues, whereas solving using this forward method is both easy and has other use cases as you mentioned. This is the way to go. – DannyB Apr 27 '13 at 11:11
  • @DannyB: Thanks, Danny :) I really appreciate it! – Merlyn Morgan-Graham Apr 29 '13 at 16:19
  • I don't see what's wrong with doing it in reverse. Sure, there are some properties to pay attention to and invariants to maintain, but they're not particularly hard. Basically you decompose the target layout into horizontal lines (there may be multiple such lines in the same row and the same depth if the target layout is not convex, say a donut shape). Then you randomly select matching pairs to place legally on the board, paying attention (A) not to place them on top of each other, (B) in lines with existing tiles only place them next to existing tiles and not both on the same side, – blubberdiblub Oct 12 '16 at 13:47
  • (C) when you place both tiles into an empty line, only place them next to each other. That's all there is to it, I think. And using this method, you shouldn't ever hit a dead end. – blubberdiblub Oct 12 '16 at 13:49
  • 1
    @blubberdiblub - example pathological case: 4 slots all in a row next to each other. If you're randomly placing the two tiles to start with so that they match rule (C), then you have 2:3 odds of requiring a violation to rule (B) to proceed, in which case you will have an unsolvable board. What are your rules for stalemate cases in your algorithm? – Merlyn Morgan-Graham Oct 13 '16 at 01:55
  • 1
    Replying to this ancient thread: this appears to be the correct answer. Someone wrote a research paper about this in 2007 which gives pseudocode and discusses this entire topic at length: http://iivq.net/scriptie/scriptie-bsc.pdf – katzenklavier Dec 23 '20 at 15:43
  • "Unfortunately, depending on the board, this may loop forever." I have a solution for this. The setup is the same, but I run a recursive brute-force solver. If it finds itself in an unsolvable state, it backtracks. This allows it to always find a solution if one exists, and also reliably determine if a board has become unsolvable, producing a game over. – edave Apr 24 '21 at 09:49
  • 1
    @edave yeah definitely. I tried to say the same thing you did in the paragraph after the one you quoted, but my lack of confidence made my writing unclear. Traverse a DAG (thoroughly, without repeats). No heuristic for picking the path to take. Epitome of brute force :) – Merlyn Morgan-Graham Apr 24 '21 at 20:46
5

The only thing I've been able to come up with is to place the tiles down in matching pairs as kind of a reverse Mahjong Solitaire game. So, at any point during the tile placement, the board should look like it's in the middle of a real game (ie no tiles floating 3 layers up above other tiles).

If the tiles are place in matching pairs in a reverse game, it should always result in at least one forward path to solve the game.

I'd love to hear other ideas.

Buns of Aluminum
  • 2,439
  • 3
  • 26
  • 44
  • Holy crap... how freaking fast are these people?! This is awesome. I immediately started posting this answer after I posted the question and by the time I submitted it, there were already TWO answers. – Buns of Aluminum Oct 01 '08 at 20:33
  • That, my friend, is the power of STACKOVERFLOW – Wes P Oct 01 '08 at 20:58
0

I believe the best answer has already been pushed up: creating a set by solving it "in reverse" - i.e. starting with a blank board, then adding a pair somewhere, add another pair in a solvable position, and so on...

If you a prefer "Big Bang" approach (generating the whole set randomly at the beginning), are a very macho developer or just feel masochistic today, you could represent all the pairs you can take out from the given set and how they depend on each other via a directed graph.

From there, you'd only have to get the transitive closure of that set and determine if there's at least one path from at least one of the initial legal pairs that leads to the desired end (no tile pairs left).

Implementing this solution is left as an exercise to the reader :D

Joe Pineda
  • 5,521
  • 3
  • 31
  • 40
0

Here are rules i used in my implementation.

When buildingheap, for each fret in a pair separately, find a cells (places), which are:

  • has all cells at lower levels already filled
  • place for second fret does not block first, considering if first fret already put onboard
  • both places are "at edges" of already built heap:
    • EITHER has at least one neighbour at left or right side
    • OR it is first fret in a row (all cells at right and left are recursively free)

These rules does not guarantee a build will always successful - it sometimes leave last 2 free cells self-blocking, and build should be retried (or at least last few frets) In practice, "turtle" built in no more then 6 retries.

Most of existed games seems to restrict putting first ("first on row") frets somewhere in a middle. This come up with more convenient configurations, when there are no frets at edges of very long rows, staying up until last player moves. However, "middle" is different for different configurations.

Good luck :)

P.S. If you've found algo that build solvable heap in one turn - please let me know.

0

You have 144 tiles in the game, each of the 144 tiles has a block list.. (top tile on stack has an empty block list)

All valid moves require that their "current__vertical_Block_list" be empty.. this can be a 144x144 matrix so 20k of memory plus a LEFT and RIGHT block list, also 20 k each.

Generate a valid move table from (remaning_tiles) AND ((empty CURRENT VERTICAL BLOCK LIST) and ((empty CURRENT LEFT BLOCK LIST) OR (empty CURRENT RIGHT BLOCK LIST)))

Pick 2 random tiles from the valid move table, record them Update the (current tables Vert, left and right), record the Tiles removed to a stack

Now we have a list of moves that constitute a valid game. Assign matching tile types to each of the 72 moves.

for challenging games, track when each tile becomes available. find sets that have are (early early early late) and (late late late early) since it's blank, you find 1 EE 1 LL and 2 LE blocks.. of the 2 LE block, find an EARLY that blocks ANY other EARLY that (except rightblocking a left side piece)
Once youve got a valid game play around with the ordering.

storm
  • 1
-2

Solitaire? Just a guess, but I would assume that your computer would need to beat the game(or close to it) to determine this.

Another option might be to have several preset layouts(that allow winning, mixed in with your current level.

To some degree you could try making sure that one of the 4 tiles is no more than X layers below another X.

Most games I see have the shuffle command for when someone gets stuck.

I would try a mix of things and see what works best.

J.J.
  • 4,856
  • 1
  • 24
  • 29