Not necessarily. With the board empty, your first two tiles can be placed anywhere on the bottom level. (Top row, bottom row, anywhere in between). All he means is that when you add one more pair of tiles to the board, make sure that if you were playing, you could then remove that same set of tiles. Initially, you can place a tile anywhere. After that, you can place a tile anywhere in an empty row, or immediately to the left or right of an existing tile, or above a tile if the next level is empty. (The above and next to another tile is covered by case two.)

-Brian

Dude, I don''t know what game u''re talking about, and how to play it, but here''s a simple way to find the way to win the game in the least number of moves.
Recursion!
The only time this algorithm doesn''t work is when the number of possible moves at a time is huge. So I don''t know if it will work for ur game.
Just make a function make every move possible at a time, check if the game is won, and if it''s not won, make it call itself for every move changed. As simple as that. It might be a bit hard to write, but I''m sure u''ll figure it out.
Hope this helps.

It seems to me that the only way to get a losing game is if a tile covers up its own match, or it covers up a tile that is the match of another tile which is blocking the first''s match:
example A is on its own match:
(A)
(A)

example A is on B which is next to A then B:

(A)
(B) A B

A is blocked by B on both sides, and B is covered by A. So when you are laying your tiles in pairs, check to see if it is covering up it''s own match, or a match of tiles immediately to the left and right of each tile. If you lay the tiles down in paris (I would make TilePair objects) then you can store pionters or references to each tile pair in a list and run throught that list testing to see if each tile of a pair is free to find your remaining moves.

Sorry kill,
The game has over 100 (150?) tiles, removed in pairs. A complete game involves removing all tiles in pairs. Assume 60 pairs (I think that''s low, but I don''t remember.) There''s likely to be an average of 3 or 4 moves at any point. That gives us a search tree with O(3^60) nodes. Not cool. Of course the actual number is less, but that technique definitely won''t work here. (I''d estimate the search complexity somewhere between checkers and chess, probably closer to chess -- more depth, less breadth).

-Brian

Sorry if my post wasn't very clear. osmanb has the right idea: play the game backward when setting up the board.

Here are the rules of Shanghai (because Mah-Jongg, as I understand, is a different game using the same times):
1) You can only remove pairs at a time.
2) Each tile removed has to be on the outer edge of the board, i.e. it is legal only if it is open on its left or right.
3) You cannot remove tiles that are underneath existing tiles.

To assure that a game is winnable, you create the board following the rules in reverse:
1) Place tiles in pairs at a time.
2) Each tile placed has to be placed adjacent to another tile (if that row already has a tile in it).
3) Stack tiles only when there are tiles beneath it.

Each placing rule is the inverse of the game rule. The only trick one is #2, because it's not exactly the inverse until you look at it closely. You want to be certain that the player must not be required to remove tiles from the middle of two tiles (illegal move) to win the game. The way to do this is to always place tiles adjacent to existing tiles.

This doesn't mean you have to start from the middle every time. There are 7 or 9 (I forget) rows on a board, and the first tile in each row can be anywhere in that row. You can start the top row at the far left, far right, or middle, or wherever. But the NEXT tile you put in the top row MUST be next to the last tile you put there; otherwise, you may force the user to make an illegal move to solve your puzzle (unsolvable).

Thinking about this more, the problem is a little tricky because you won't necessarily know when you're able to jump up a level (place a tile on top of another). But since there aren't THAT many tiles (150?), you can just do a pure random thing. Here's a pseudo-loop:

bool firstTileOfPair = true;Tile* pTile;while (numTilesLeft > 0){  if (firstTileOfPair)    pTile = pickRandomTile ();  // pick totally random tile  else    pTile = pickLastTile (pTile);  // picks another tile of same type as the last  firstTileOfPair = !firstTileOfPair; // sorry, left this off first time  bool validLocation = false;  while (!validLocation)  {    BoardLocation* loc = pickRandomLocation ();    if (!loc->tileBeneath ())      continue; // make sure tile isn't being placed in midair    if (!loc->rowIsEmpty ())    {      // row isn't empty, make sure next to new tile      if (!loc->isAdjacentToTile ())        continue; // if not adjacent, illegal placement    }    validLocation = true;  }}  

Not the cleanest, but it's pseudo-code, so it should give you a better idea. Hope that helps.

Edited by - Stoffel on 2/16/00 5:28:43 PM

I shan''t think that having 4 tiles left and none of them touching each other will force me to make any illegal moves. Since each tile is free on both sides, there is nothing wrong with removing them. Using the method that Stoffel described, in which tiles MUST be placed next to existing tiles, it is still possible to get the ABAB result. In that result, A is blocked by B on both sides, and and B is covered up by A''s match. There is no way to win this. That situation could result from Stoffel''s approach unless you restrict pairs of tiles to be on the same vertical level only, which would result in an overly simplistic and unfun game of Shanghai.

Jim,
I think you''re still misunderstanding the approach that Stoffel and I are talking about. When you add tiles, we''re not saying add ANY tile, we''re saying you specifically add a pair of matching tiles, such that if the game were in the state you''re creating by adding them, you would then be able to remove them. This DOES guarantee that the game is winnable.

The whole game is about moving through a graph (actually, a DAG) of states, from the start state, to a winning state (no tiles left.) There are well defined rules for legal transitions in that graph, which are the rules of the game. Those rules are reversible, so from the final state (winning) we can work backwards to the start state, and also know that any player can traverse the state graph we (implicitly) constructed in doing so. Of course, they might screw up and take some other path that happens to exist, but there is at least one path that enables them to reach the winning state.

-Brian

Right-o Brian.

Also, using my method will allow 4 tiles without touching each other as the last 2 moves on the board--provided none are in the same row. You can''t have a game with a "gap" in a row legally--there''s no move to allow that. This is why, in my pseudo code, I check if it''s an adjacent tile ONLY if there are no other tiles in the current row.

I just wanted to give a ''thanks'' to Stoffel and Brian for helping me sort through this mess. Im going to attempt to implement the psuedo stuff asap. And see how it goes.
The current state of the game is ''working''. I know how many ''possible moves'' are left as well as number of tiles and the game can be played through. All the ''making it pretty'' stuff is left to come.. but Im off to a good start. I''ll let ya know how it goes. I was (and probably still will) writing a routine for some AI to actually play itself to try and check for a ''winnable'' layout as well as a nice demo mode.

Thanks a ton for your comments and suggestions guys!

Cygor