Attached is a Boggle solver (Windows binary) that I wrote with an official Scrabble wordlist. From a command prompt, just run:

boggle 100000

To solve 100000 random boards. The best boards are displayed with their scores. Then the elapsed time is reported. I'm curious to see how fast it is on different CPUs, particularly multi-cores. Report your results! (along with your highest board if you wish)

If you are sufficiently bored, I challenge you to write a faster solver than mine.

I'm looking at it from a statistical perspective to find most common words, partial words, etc. I know other people have already done it, but it's no fun reading other people's results.

Some of the 4x4 boards have over 1,000 words! The Scrabble dictionary is a bit generous and I doubt casual players would allow most of the obscure ones, but it still would be funny to win a "first to 50 points" game in the first round.

The number displayed is the score, not the word count. That is, [1, 1, 2, 3, 5, 11] points for [3, 4, 5, 6, 7, and 8+] letter words.

I don't really feel like rebooting into windows.. But I could test on my Q6600 if you get source using pthreads....

AMD Turion 64 x2 Mobile Technology TL-60 2.00 GHz

100,000 boards in 11.919 seconds <8389.965832/s>

It went nutz at 500,000, what have you done?:o

I think my C64 could solve faster than some of these computers... I'd have to rewrite the program first though to not use 100MB of RAM on the dictionary.

I'll release the source later after I clean it up a bit and add proper support for 'Q' since it's actually 'Qu'. Also right now the scores are erroneously high since I'm not checking for duplicates. The highest known computed score for a 4x4 using the Scrabble word list is around 2,500.

And yes, I am using pthreads to concurrently solve boards since they are all independent of each other.

wow, 100 percent cpu usage and 70+ Mb of RAM used if you go with too many boards

but it's kinda cool

I didn't try for 1,000,000... I have a 2.66 GHz celeron

Maybe the number of threads has something to do with it? Windows performs fairly badly when you start loading up on threads.

Edited: I was using some poor power management on my laptop.

BTW I have a Core 2 Duo @ 2 GHz with 2 GB of ram.

EDIT:

Do you have any proof of that ?

For what it's worth, it works like this:

I load the dictionary as a tree. Each node is a letter with 26 children nodes. CAT, CARE, and CAREER would look like:

     Root
      |
      C
      | 
      A   
     / \
    T   R
    *   |
   CAT  E----E----R
        *         *
       CARE     CAREER

The dictionary is read only and shared among all the threads. Say we have a board like:

C E
A R

I set a node pointer to the dictionary root and check if n->c['c'] exists. It does, so I walk down to it. I check to see if the terminate node (*) exists. It doesn't, so C is not a word. I move to the right on the board, see an e, and therefore check for n->c['e']. It doesn't exist, so no words begin that that combo, and I go back up to the previous node and check the next available letter in the board.

I just use an iteration (no recursion) with a static stack of length rows * cols. If a word node is reached, then its pointer added to the static list of word pointers. This is to minimize any unnecessary string copies from the dictionary to the word list.

That is, once the dictionary is loaded and the board is created, memory is not created or destroyed or moved around.

So if your CPU can handle all of that, then you'll get a nice fast time.

The biggest optimization to my current approach would be to try to get stuff in memory stored in as optimal way as possible, but if anyone has any better algorithms than mine please share.

That sounds pretty optimal to me. I was thinking that your tree dictionary will probably give you good 'locality of reference' since the most common words in the english language use similar letters (ie will the most used parts of the dictionary stay in cache?). You're not allocating/freeing memory. Are there function calls? A lot of function calls?

I'm going to be pissed OFF if this is NOT written in D.

I wrote it in D and then translated it to C. In a real world application, I would use D because I wouldn't need to solve billions of puzzles. But given I want to optimize it for speed, C is a better choice. This is the type of thing I'd write in C as a library and interface it with D or PHP, etc. [Or use D but write the code by managing my own memory.]

All memory allocation is done at initialization. The only function calls are like board_reset() and board_solve() which could really be optimized out. The algorithm itself is just a single for loop.

The D version was significantly slower because I made it more friendly to use. For instance, I had a pathfinder() function that could walk every possible path, taking a boolean delegate as a parameter that would determine whether or not to continue following each node.

So I could so stuff like:

So it looks nice because you can easily share code, but really you're just wasting a lot of function calls. Obviously a similar thing could be done in C with function pointers, but I wanted to maximized speed.

Once I finish it in C, I'll translate it back D in the same form. But it won't really look like a D application. I mostly just want to test out how well the D compiler optimizes.

And how a call to a function pointer is different from a call to that function itself ?

Any details (ie. numbers) on performance differences?