Finding valid words in a set random grid

[dkl]

Recently, I downloaded a word game that has a small 4x4 grid made up of random letters. The aim was to find as many words as possible by selecting adjacent letters to make a word. A fairly standard game.

The player was told how many words could be made from the random grid.

The basic game is relatively easy to programme. What I don't understand is how does one work out how many words can be made from the grid, especially as each tile has only certain directions one is able to go, depending on its position on the board.

Is each tile allotted its own available 'exits' to go? Meaning if you are in the top left corner a word can only be made if you go

'East', 'South East' or South OR based on my attached diagram - 4, 5, 6.

NB - I think tsh73 used something similar in his Retro 'Color Lines' Game, but it was easier as there were only 3 available directions to move (left, right or down).

However, in this situation it would mean the computer has to take each tile and move in every possible combination of directions available and check if a word can be made. I suppose, a word check would be made at every tile move so that if its illegal (no valid word possible with selected letters) then it starts again in a new direction.

Looking at it another way, one could simply take all the selected letters and run a check through a word list to see how many words can be made from the random letters (as I did in my Anagram programme), but that is going to produce some invalid words not available on the grid. Then one would have to filter those words out from the list somehow.

I really would like to know how this problem is approached. I would appreciate anyone response and input.

Thank you.

[tsh73]

Inbteresting.
Is it kind of this game?
en.wikipedia.org/wiki/Boggle

[dkl]

Yes that's right - the one i downloaded was called WORDLY on IOS and its free.

On re-reading the first post I haven't really explained myself very well, because I talk about 'moves'. The grid is Fixed and one chooses each adjacent tile to make word by sliding your finger (or Stylus) around the grid.

But it's just how to calculate the number of words available that I'm particularly interested in.

[dkl]

I can easily check for words horizontally and vertically

In Wordsworth, a game I posted a while back, I used the following format below to check the letters/grid reference and compare with a word list

123,234,345,1234,2345,12345

This checked all lines horizontally on a 5x5 letter grid from left to right

123,234,345 <- search for all 3 letter words
1234,2345 <- search for all 4 letter words
12345 <- search for 5 letter word

But I'm looking to work out how it can be done from left to right, right to left, top to bottom, bottom to top. That part is OK.

However, its once the diagonals come into play and the numerous variations when able to go in ALL directions that puzzles me. As on can go - left, right, up, down, diagonal left,up & down, diagonal right,up & down depending on the position of the letter on the grid. Top left, bottom right, centre left, centre right, middle, etc.

There must be some sort of algorithm for this? Or another way? So any ideas on how to go about it would be much appreciated, if anyone has time?

Thank you.

[tsh73]

I think it is backtracking
You number directions (say clockwize)
start with some cell,
move some direction
get a string of directions, like
"left up left"
on each turn you check if you are still in grid (not out of it)
and if it is, is where some words starting with it
(I wonder if it should not allow pass same cell several times as well)
If some of checks fail you increment last direction, say from left to lower-left
If you cannot increment it more, you go one step back
in this case, "left up"
and try to increment last direction here.
If you have no more things to increment then you chacked all possibilities from that cell.

[dkl]

Yes, tsh73........ I'm working on 9 different types of tile each with its own characteristic directional moves

tile 1 top left corner 3 directional moves 4/5/6
tile 2/3 top wall 5 directional moves 4/5/6/7/8
tile 4 top right corner 3 directional moves 6/7/8

etc........

Start on tile 1 then test direction 4/5/6 with a word check after each move to check word validity. If valid move then to next tile etc.....

I think if I use my Anagram programme to test for maximum amount of words available from 16 selected letters, before I start the check then that'll save time during the word check instead of having to use a full word list
Hmm... I think I may be getting into the swing of this now - fingers crossed!

If the above idea gets too complicated then I do have another idea. After having found all possible words through the Anagram programme then search for them in the grid, but haven't thought how I'll go about that yet, but I suppose it'll be similar to what I'm already trying.
But if anyone else out there has a brainwave, please feel free to contribute as tsh73 kindly did! It all helps:)

[Rod]

So a five by five grid. I presume words must be three letters or more. So that means there are 5 horizontal, 5 vertical and 10 diagonal letter lines to pull out. Each letter line will be between 3 - 5 letters long. I would check them in a pattern.

12345
1-5
1-4
1-3
2-5
2-4
3-5

Then the reverse. The three letter limit quickly reduces the numbers. Each letter line from the 20 options gets checked the same way

[bplus]

<"I really would like to know how this problem is approached. I would appreciate anyone response and input.">

Yeah I did anagrams too, this is a little different.

I did Boggle in QB64, I was going to show 2 main Functions for confirming if a word is constructible from the board but better I think to just describe it.

But that's the idea, wait until a word has been presented by the player and then check to see if it was "legally constructible". Or check the dictionary first to see if it is actually a word, that has to be done too but that's the easy part.

For "legally constructible", I had two Functionss the first ultimately says constructible or not, I called it: WordBuildOK. It finds the first letter of word and then calls it's recursive helper friend call FindCell and tells it where the first letter was: column, row, and tells it the word being checked, and tells it the Mid$ index of the letter to FindCell next and finally it passes it a copy of the Boggle Board with all the used letters blanked out so they aren't "Found" again.

If FindCell can find the next letter from the previous location, it calls itself again to find the next letter unless we are at the end of the word then, it tells "legally constructible" true, yes the word can be made from the board. If findCell can't find the next letter from previous position then the word is not constructible and reports back to WordBuildOK a big fat 0!

So WordBuildOK function just needs to find the first letter of the word being checked and pass that to helper FindCell whose first job is to make a copy of the board without the letter just used and check to see if at the end of the word from index passed to it. If not at end of word, actually try and find the next letter.

If a next letter is not found in remaining board, report back to WordBuildOK with big fat nada, 0, False otherwise call itself again to find the next letter with the info from the found letter position, word, next letter index, copy of remaining board of letters available. Repeat until word is completely found (FindCell is at end of word WordBuildOK = 1, True!, success) or a letter can not be found (FindCell = 0 so WordBuildOK = 0, False, Nada).

I made sure this function worked after getting a board created and displayed because this is crucial heart of Boggle, checking if the word can be legally constructed because again, just checking if the word is real is easy part ie binary search of dictionary.

BTW if first letter of word appears more than once in Boggle Board as it often does, you have to of course, check each instance with WordBuildOK. 

Oh I also used 2 arrays dx(), dy() when checking the cells around a given cell ie

       ' load dx(), dy() for testing the legality of words built from board
       dx(0) = -1: dy(0) = -1 ' this is for AI to find words
       dx(1) = 0: dy(1) = -1
       dx(2) = 1: dy(2) = -1
       dx(3) = -1: dy(3) = 0
       dx(4) = 1: dy(4) = 0
       dx(5) = -1: dy(5) = 1
       dx(6) = 0: dy(6) = 1
       dx(7) = 1: dy(7) = 1

a$() is the copy of the Boggle Board minus the letters blanked out but has an extra padding of an extra cell all the way around the board$, this to avoid having to check if subscripts of an array are within boundaries of the array when adding dx(d), dy(d) to cell position.
   For d = 0 To 7  ' d is like direction 8 directions around a given cell
       If a$(x + dx(d), y + dy(d)) = Mid$(w$, i, 1) Then
           test = findCell&(x + dx(d), y + dy(d), w$, i + 1, a$())
           If test Then findCell& = -1: Exit Function
       End If
   Next

[dkl]

Many thanks for your help and response, Rod. Always great to hear from you.
In the game I'm talking about one can go in ANY direction to form the word, not just horizontally, vertically or diagonally (or in reverse direction). I probably explained myself badly as usual!

Here is an example of what I mean.

C S X S
T A Y E

Take these 2 rows of 4. One can make the following words by using the adjacent letter in any available direction.
CAT, CATS, CAST, TAX. SAY, YES, SEX, TAY, AYE, AXE, AXES, SAT, STAY.

I have used the routine you explained before and it works well and is similar to what I tried to explain in my 2nd post above. I used this idea in the programme Wordworth, which I posted but I only used horizontal and vertical in one direction.

What I am interested in is how did the programmer of the game (Wordly) work out all the words available from a (4x4) random grid, before the game started, so the user knows how many words you are aiming to find. It seems very complex?

[dkl]

Thank you, bplus for your explanation and it seems I'm going in the right direction. I had already done something similar to the first code you posted

' load dx(), dy() for testing the legality of words built from board'

I can see from the pic you posted that, it is exactly what I am interested in understanding.

I have almost finished a word game programme which follows the same game pattern, but on a larger scale (9x9) grid (see pic below), but have no intention of trying to predict all the available word on the grid!

I will delve into your explanation some more, but not sure if I'll actually achieve anything as I am still a relative newbie!

But from acorns.........

It was good of you too share some of your code and I appreciate that.

Many thanks:)

[Rod]

Well and good. Can a letter be used more than once in a word? Once used is a letter out of play? How is it scored? Is it better to get lots of small words or longer words? That would define how the search is made. I can envisage that a central blocking play will limit the total if letters can only be used once.

Or is it just a case of find as many words as you can unrestricted?

[dkl]

It'll be similar to the pic above but a 4x4 grid, similar to the pic bplus posted.
A letter can only be used once per turn (for each word found) then it is back in play.
Scoring? Probably along scrabble type lines or just based on length
NO jumps or moving letters around
The aim is simply to find as many words as possible from the given letters by only connecting/moving to the adjacent letter

Or is it just a case of find as many words as you can unrestricted?

- Yes

[bplus]

This discussion has me thinking about revising the GUI.

After the first letter is selected, clicked in my case, highlight the square and also gray out the letter to indicate it is not to be used again (for the current word being built), might even highlight the 3x3 grid around the letter for legal moves boundary to the next letter. For the next word, you start with a fresh board of same 16 letters to start from.

In that way, all Rod's questions get answered!

Oh yeah about scoring for Boggle, (ignore the passing of an array of words in following and that you have access to Upper bound of the array, easy enough to work around for LB ie over dimension the array and keep a global MaxIndex tracker to the array. Just tell the Score Function which players word array to add up.)
Function score& (a() As String)
   Dim As Long i, s
   For i = 1 To UBound(a)
       Select Case Len(a(i))
           Case 3, 4: s = s + 1
           Case 5: s = s + 2
           Case 6: s = s + 3
           Case 7: s = s + 5
           Case Is > 7: s = s + 11
       End Select
   Next
   score& = s
End Function
This is loosely based on Boggle scoring by word length and the longer the better! and the other players NOT coming up with the same word.

@dkl that's quite a word game screen you shared! fancy!

OK it now may be helpful to share the code of the two functions I wrote about, just remember it's not LB code but fairly easy to translate to LB code, Basic is Basic, basically! It's how you handle the arrays that will need rework, they are already global in LB so I think you just need a work or temp array for handling the recursive calls which you can't pass in parameters list.

' This function checks to see that the word w$ is legally constructable with the given board.
' This function requires the recurive Function findCell& (startX As Long, startY As Long, word$, index As Long, Arr$())
Function wordBuildOK& (w$)
   Dim As Long r, c, test
   Dim copy$(-1 To 4, -1 To 4), first$
   If Len(w$) < 3 Then Exit Function ' words need to be 3 letters
   For r = 0 To 3
       For c = 0 To 3
           copy$(c, r) = Board$(c, r)
       Next
   Next
   first$ = Mid$(w$, 1, 1)
   For r = 0 To 3
       For c = 0 To 3
           If copy$(c, r) = first$ Then 'cell letter matches first letter in word
               test = findCell&(c, r, w$, 2, copy$())
               If test Then wordBuildOK& = -1: Exit Function ' ah ha! maybe it keeps trying when we are supposed to be done, fix?
           End If
       Next
   Next
End Function

'recursively called starting from wordBuildOK&
Function findCell& (startX As Long, startY As Long, word$, index As Long, Arr$()) ' want to setup recursive searcher
   Dim As Long d, x, y, i, r, c, test
   Dim w$
   'make own set of variables for this function  (attempt to debug but did not fix anything)
   Dim a$(-1 To 4, -1 To 4)
   For r = 0 To 3
       For c = 0 To 3
           a$(c, r) = Arr$(c, r)
       Next
   Next
   i = index: w$ = word$: y = startY: x = startX
   If i > Len(w$) Then findCell = -1: Exit Function
   a$(x, y) = "" 'so wont be used again
   For d = 0 To 7
       If a$(x + dx(d), y + dy(d)) = Mid$(w$, i, 1) Then
           test = findCell&(x + dx(d), y + dy(d), w$, i + 1, a$())
           If test Then findCell& = -1: Exit Function
       End If
   Next
End Function

The beauty of recursive procedures is that they aren't massive but they can be a little tricky. But if that becomes troublesome, tsh73 could probably rewrite it so recursion is NOT needed! ;-))

[bplus]

Man I keep talking about this, I will have to write up an LB version just to verify that it can be done.

Trouble is Boggle does not make a great one player game against the AI. It is a bit humbling how many more (unheard of words) the AI can pull out of the dictionary and more so the longer the word. I made mine into a trainer ostensibly to practice Boggle for playing against other humans closer to my level of play. But really I turned it into a way of learning new words because I hooked up access to the definitions.

The words it turns out come from allot of Old English, Scottish, German, French... usages one is never exposed to in Cleveland, Ohio, USA but is "sorta" allowed, oh hey it is! ;-))

[dkl]

bplus.............Thank you for your last 2 posts. Don't worry about scoring and remember this is NOT boggle (just similar), it's a solo player game.
As you say the dictionaries can turn out some pretty obscure words, so I'm using unixdict (at present) which sticks to 'english' and more commonly used words

I have start formatting some code based on the directional movements/characteristics of the 9 different tile types and although it is beginning to do what I want I can see that I am going to hit problems further down the road. But I'll persevere until I hit a 'wall'. I think that the idea is similar to your explanation, but I'm going to end up with 'variable' problems keeping track of 'done' directions etc.