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.

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.

Thanks. I'll have a go at doing it this way. I think I was making the problem more complicated in my head.

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.

Here's how I was thinking about it, in pseudocode. Maybe it'll give you some ideas:


This doesn't deal with swapping tiles, but if this works, that could be fit in without too much trouble.

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).

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.