Scrabble -- find words on board?

[kandieman]

I know HOW to find words made on the board... im just not sure what alogithm to use that will work. I've thought of two main ones, neither of which are ideal.

The first is after checking the spot, set a boolean flag to true so that spot is not checked again. The problem with this is that the letter can very well be used in multiple directions to form words.

The second option is to store found words in an array and only add unique ones to it. This is also a problem, because there could be duplicate words.

Any tips or suggestions?

[Barancle]

If you are to use the second option and don't want duplicate entries you can use a Set or a Map

[kandieman]

Sorry -- i never mentioned. Duplicates are OKAY, which is why there would be a problem.. it would only "find" one of them.

[Joe Nellis]

http://www.gtoal.com/wordgames/scrabble.html
has source code and information, prepare for information overload. You can also ween a lot of info from the user group, http://groups.yahoo.com/group/wordgame-programmers/. I am new to the group myself.

[dlorde]

The first is after checking the spot, set a boolean flag to true so that spot is not checked again. The problem with this is that the letter can very well be used in multiple directions to form words.

Why not give each 'spot' a flag for each direction it may be searched in?

Everything should be made as simple as possible, but not simpler...
A. Einstein

[cjard]

i would have thought a simple algorithm might go something like this:

each spot on the board has 4 flags indicating what direction has already been checked. eastwest, northsouth, northwestsoutheast and northeastsouthwest

For each spot on the board, examine all 8 neighbours. If the spot has, on one side, a tile, and on the oopposite, no tile, then it is an endpoint for a word. you can trace it in the deduced direction, if the flag for that direction is not already set.
As you trace, set all the flags.
When you have traced to the end of the tiles, examine the chars you have collected forwards and backwards for a word.
or, collect the tiles. if the word is valid, set the flags, if it is invalid, remove them from the board

Move on to checking the next tile (after the original starting point)

-
when your check comes to the tiles in the middle of the word that you found above, their direction flags will be set, and if the tile has no other deduced directions (i.e. it is not an endpoint for another tile) then it is a mid-word that has already been, or will be checked at some point.

-
Sacnning the board will be very quick, requiring at most X*Y inspections. Many of these inspections will exit early, as there will be nothing to do. If the tile is an endpoint that has already been covered or is a midpoint that will/has been covered, then inspection will terminate early too.. even for very large boards, this routine should move quite rapidly

[Joe Nellis]

Here is the link to probably the most clear thought on this algorithm of move generation for Scrabble.

http://www.gtoal.com/wordgames/jacobson+appel/

It is an excellent read even if you don't like Scrabble but like problem solving. The basic idea is that there are anchor points, places where it is possible to play a word. Where other crossing words begin/end in the path of the possible word, a set of crosschecks, a reduced list of letters from the players tile set, that can only be played in these squares. Iterate through each ancher point searching across looking through a dictionary. Since the same algorithm is used for searching across as down, a convention is made to express the 2D board as one continuous array of tilespaces. Points are counted for the word and the max (new move, old move) get recorded as the candidate for the best move. Now many different heuristics can be added on top of this to implement more strategy. Best moves could be based on known remaining letters, look ahead, Monte Carlo methods of predicting opponent moves, etc, and not necessarily highest scoring word.

[bakhatyar]

I?ve actually implemented similar functionality on my website, scrabblwordfinder.uk, which helps players find the best possible words from their tiles. If you?re experimenting with word-finding algorithms, it might give you a good reference for ideas and performance comparisons.

If you?d like, I can also share a C++ or C# code example showing how to combine the Trie and backtracking approach effectively.
Would you prefer that?

[2kaud]

After 21 years?