Automated puzzle testing

Member
Posts: 283
Joined: 2006.05
Post: #1
I'm stuck on a little problem here.

I'm working on an iPhone game (screenshot) where you are given words in a certain order and you have to place them on a grid so that they interlock like a crossword. So every puzzle can be defined by the grid dimensions and an array of words.

I have that working perfectly in the game, but I'd like to make an application (for Mac not iPhone) that tests these puzzles and finds out how many possible solutions there are. I have code that tests whether a move is valid or if there are no more available moves; my trouble is how to cycle through all possible options and build up a 'tree' of outcomes. Does anyone have any ideas (or terms for me to google)? I can imagine this sort of thing being a standard problem in CS courses.

Thanks for any pointers.
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #2
I'd try a simple brute-force search and see how it performs before doing anything fancier. Just have your code evaluate every possibility for placing each tile, and keep track of how many iterations it was able to go through for each list of positions before hitting a dead end.
Quote this message in a reply
Member
Posts: 283
Joined: 2006.05
Post: #3
Thanks. I'll have a go at doing it this way. I think I was making the problem more complicated in my head.
Quote this message in a reply
Member
Posts: 283
Joined: 2006.05
Post: #4
Ok, here are some problems I'm coming across.

A) I don't really know the language to do that. I'd have to loop through every position for the first word, then loop through every position of the second word for every valid position of the first word, and so on. I know how to do it with 2 words, but not with n words.

B) The words come in a certain order, so it's not just a case of finding an arrangement where they all fit, because you might not have been able to reach that situation with the words coming in the order that they do. (Every word after the first one has to share a tile with another, like Scrabble). To further complicate things, the player can at any point swap his current word with the next one, but I'm not going to think about that just yet. If that's confusing, this video should clarify: http://www.youtube.com/watch?v=Iq6Peqk_E14

C) I don't know what to do with my grid object? Should I start with a fresh one each time and work through until it reaches a dead end? Or 'undo' one move when it reaches a dead end and try other solutions?

Any bright ideas would be appreciated.
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #5
Here's how I was thinking about it, in pseudocode. Maybe it'll give you some ideas:

Code:
struct TilePlacement {
  int x;
  int y;
};

void placeTilesRecursively(Board * board, Tile ** tiles, struct TilePlacement * placements, int depth) {
  int x, y;
  
  if (depth >= MAX_TILES) {
    // We've used up all of the available tiles, so this is a solution
    int placementIndex;
    
    printf("Solution found: {\n");
    for (placementIndex = 0; placementIndex < depth; placementIndex++) {
      printf("  %d, %d\n", placements[placementIndex].x, placements[placementIndex].y);
    }
    printf("}\n\n");
    return;
  }
  
  for (y = 0; y < BOARD_HEIGHT - (tiles[depth]->height - 1); y++) {
    for (x = 0; x < BOARD_WIDTH - (tiles[depth]->width - 1); x++) {
      // Assumes Board places the tile and returns true if the move is valid, does nothing and returns false if it isn't
      if (board->placeTile(tiles[depth], x, y)) {
        placements[depth].x = x;
        placements[depth].y = y;
        placeTilesRecursively(board, tiles, placements, depth + 1);
        board->undoLastPlacement();
      }
    }
  }
}

void findAllSolutions() {
  int x, y;
  Board * board;
  Tile ** tiles;
  struct TilePlacement placements[MAX_TILES];
  
  allTiles = getTileList();
  board = Board_create();
  
  for (y = 0; y < BOARD_HEIGHT - (tiles[0]->height - 1); y++) {
    for (x = 0; x < BOARD_WIDTH - (tiles[0]->width - 1); x++) {
      placements[0].x = x;
      placements[0].y = y;
      // First placement should always succeed, right?
      board->placeTile(tiles[depth], x, y);
      placeTilesRecursively(board, tiles, placements, 1);
      board->undoLastPlacement();
    }
  }
}

This doesn't deal with swapping tiles, but if this works, that could be fit in without too much trouble.
Quote this message in a reply
Member
Posts: 283
Joined: 2006.05
Post: #6
Thank you, that looks magnificent! I'd never have thought of using a recursive function. I'll report back once I've made it work (or become stuck).
Quote this message in a reply
Member
Posts: 283
Joined: 2006.05
Post: #7
IGNORE ALL THIS! It's now working perfectly, thanks so much! The problem was with my undo code.

Quote:It's so close to working! But now it messes up after the first successful result. It starts returning incomplete grids as complete.

I've changed the code a bit to fit my objects, but I think it does the same as yours. I've spent a while trying to figure out where it goes wrong, but no luck yet. It seems like the depth value is one higher than it should be after a successful result. I'll keep playing; I'm sure it must be something simple. If anyone wants to see if they can spot any problems, that'd be great.

Code:
// process started by calling this with depth:0
- (BOOL)testWords:(NSArray *)wordList onGrid:(XWGrid *)grid depth:(int)depth  {
    int wordCount = [wordList count];
    if (depth >= wordCount) {
        NSLog([grid description]);
        return NO;
    }
    
    XWWord * testWord = [wordList objectAtIndex:depth];
    for (int y=0; y<grid.height; y++) {
        for (int x=0; x<grid.width; x++) {
            XWLocation testLoc;
            testLoc.x = x;
            testLoc.y = y;
            testLoc.orientation = XWOrientationHorizontal;
            if ([grid word:testWord fitsAt:testLoc]) {
                [grid addCellsFromWord:testWord atLocation:testLoc];
                [self testWords:wordList onGrid:(XWGrid *)grid depth:depth+1];
                [grid undoLastWord];
            }
            testLoc.orientation = XWOrientationVertical;
            if ([grid word:testWord fitsAt:testLoc]) {
                [grid addCellsFromWord:testWord atLocation:testLoc];
                [self testWords:wordList onGrid:(XWGrid *)grid depth:depth+1];
                [grid undoLastWord];
            }
        }
    }
    return YES;
}

If you want to see more context, there's an Xcode project at http://www.maximile.net/stuff/xwtest2.zip

Either way, thanks for your help so far. It works absolutely perfectly for the first result, which is a lot further than I'd have got by now otherwise.

Edit: actually, it's not working perfectly for the first result. I'm checking to make sure it's not a problem with my undo code.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  xcode v3: some explanation of the automated generated code sefiroths 3 4,334 Oct 20, 2010 05:28 AM
Last Post: sefiroths