Finding a Word in a Grid of Letters Using Boggle-Style Search

Solar2D Lua Language
#1

I’m working on a new word-search game that uses Boggle-style logic; i.e. the letters don’t have to be in a straight line.

I’m trying to write a function that checks the grid to see if a specific word is there, and I’m having a little trouble organizing all the loops to do the checking, and I was wondering if anyone had a done something like this in the past and could help me out with a code snippet or a push in the right direction.

The letter grid is a 2D table:

local puzzleGrid = {
{ "A", "B", "C" },
{ "D", "E", "F" },
{ "G", "H", "I" }
}

For previous games- straight word search- I would go to each square and strike out in each direction using a pair of arrays to mimic the eight compass points

local directionalArrayX = { -1, -1, -1, 0, 0, 1, 1, 1 }
local directionalArrayY = { -1, 0, 1, -1, 1, -1, 0, 1 }

step through the grid

for i = 1, #puzzleGrid[1] do
	for j = 1, #puzzleGrid do

and gather up all the letters in the grid along those lines and compare them to the word I was looking for. This might not be the most efficient method, but it works fine. It’s a few hundred comparisons on the outside and it happens instantly on device.

This approach will not work with non-linear word finding because things get exponential very quickly. The approach that makes sense is to compare the first letter in the word I’m trying to find with each letter of the grid:

for i = 1,  #puzzleGrid[1] do
	for j = 1, g #puzzleGrid do
		if ( puzzleGrid[j][i] == wordToFind:sub( 1, 1 ) ) then
			print( "******** First letter matches!" )
		end
	end
end

The above code works fine. No surprise, since it isn’t really doing anything interesting. The tricky bit is the next part where it loops through and looks at all the neighbors, snaking around until it a) finds the word it’s looking for or b) checks every sensible combination of letters. Because it will be comparing sub( 2, 2 ), sub( 3, 3 ), etc. and abandoning trees as soon as it hits a non match, we’re back down to a few hundred comparisons. The directional arrays make it easy to check all the neighboring letters in an orderly, clockwise manner and the search stays on the grid by ignoring any column or row that is less than zero or greater than the maximum number of columns or rows.

What I’m having trouble with is the looping- I’m hoping to find a way to do it that’s not 100 lines of if - then statements. If anyone has anything, I would be super grateful. Thanks!

1 Like
#2

I’ll start with some dumb questions. Do you know the word you are trying to search/match before hand?

#3

In any case, this might at least give you some new ideas.

If you do know the word, I would imagine that the player is selecting letters. As they select letters you can gather them up and search against an indexed table of words until you get a positive match.

I have not tested this, it’s just a possible approach.

Indexed table of words could look like:


local words = {

  ["apple"] = true,

  ["stove"] = true,

  ...

}

The values really don’t matter, we just want the index. But setting them to true is a good bet.

As the player selects characters, check against the index:


if words[chars_so_far] then

  print("we got a winner")

end

You don’t need to use any fancy stuff with this approach.

While this may not work specifically for your use case, it might offer some inspiration.

-dev

#4

The word will be known beforehand, but that’s not the crux of the problem I’m having.

There are two main applications for what I’m trying to do- on device, it’s a way of finding the next answer on the list and then lighting up a letter in the grid when the player requests help. On the developer side, I need to be able to check the grid to make sure there aren’t any objectionable words in the grid. (In this case, I’d look into building a Trie to reduce the work of running through a list, but that’s a whole different thing.) Right now, I’m just trying to get the mechanics of looping the grid under control.

#5

So…

  1. The player has entered a certain amount of characters, but now asks for help, and you need to light up a valid character on the grid?

  2. You need to check the grid to make sure what has been entered so far is not a vaild word on your list? How/when does this event occur? Does the player press a “done” button, or are you wanting to evaluate the grid in realtime?

-dev

#6

I think you might be wandering into the weeds… :grin:
Given the string wordToFind, I need to find it in the letter grid.

#7

I would probably approach this by creating a list of unwanted words and then let the player know about it when they try to play such a word. This would make it a lot easier for you when developing your levels.

If you do want to loop through all of the possible words using the rules you’ve described, then the number of combinations will quickly run up to astronomical figures (depending on how large your playable grid is). You can narrow them down a bit by requiring the words to always have a specific length, e.g. between 3 and 8.

After that, it’s really just about looping through each tile and recursively checking their adjacent tiles, as you’ve already described. This shouldn’t take even 100 lines of code to pull off though. This sort of approach, however, may have those astronomical number of combinations and I don’t think you can run these types of checks on a user’s device. If you do want to give hints, you could just run the loop until you find a single word.

#8

To that end, do you have any concrete advice? That is what I’m looking for…

#9

My gut feeling to minimise the amount of total checks needed is for the starting point of each round of hint checks to be from the middle of the grid [2, 2], and not just working through the cells in order from the top left corner [1, 1]. This maximises the chance of finding a valid second letter, allowing you to cull invalid sequences early.

The middle cell has 4 options for finding a valid second letter, whereas the corners only give 2 (and the cells directly adjacent to the middle have 3), so I would check for words in order starting from these positions:

[2,2],
[1,2],
[3,2],
[2,1],
[2,3],
[1,1],
[1,3],
[3,1],
[3,3]

From those starting points I would then loop through the adjacent tiles as you’ve suggested already.

#10

You’d need to start from your initial premise of iterating through each and every tile.

for row = 1,  #puzzleGrid do
	for column = 1, #puzzleGrid[row] do
		....
	end
end

Then, for each tile, you’d need to run a recursive function to check for all of its adjacent tiles that haven’t been accessed yet. The starting tile would always be considered accessed. In the check, you’d store the current tile’s letter and add it to the string of letters, followed by adding a property to the tile stating that it has been accessed during the current word search so that you don’t check it again in the next recursion.

Then, if you do implement the minimum and maximum word lengths (as it makes no sense to check words that are 1-2 letters long), you’d start checking if the current string of letters is the start of some word in your word list. If you’re creating your game with English in mind, we’re talking about tens of thousands of words or hundreds of thousands of words, depending on your criteria and word list. In that sense, it’d make sense split your word list into sub lists, each containing only words starting with a specific letter.

If a word isn’t found, you terminate the recursion and continue from the starting tile’s next adjacent tile. Same thing if you reach the maximum word length in the recursion. Once one tile has been checked recursively, you’d proceed to the next tile.

Depending on your minimum and maximum word lengths, and your grid size, this type of checking may take billions of operations, making it unfit to run on player’s devices (and slow even on development devices). Personally, I wouldn’t take this approach.

Most word search games have either very limiting rules on how words can be created or they only check the words once the player “plays them”. The latter is often favoured as it frees you from all possible checking and this insane recursion. There you’d just have your list of words and list of banned words, and only words matching those in the allowed list would be accepted.

If your game is about finding specific words, you could just implement a list of desired words per level and ignore all other words, profane or not, and show a message to the user saying stuff like: “XYZ is not a word.” and/or “XYZ is not one of the words you need to find.”

#11

You guys are giving me a lot of great input, for which I am very grateful. I appreciate everyone’s time and effort.

Unfortunately, what you are telling me are things I already know. I have ‘straight’ word search apps on the market- I am familiar with the fundamentals of word search programs, and I know how to write apps that people like playing and don’t crash their phones. I have also already written the core code that runs the Boggle-style word selection. It works great! If I wasn’t interested in having a “hint” function, I could publish the app tomorrow.

What I am trying to do is locate one word in a grid of letters. I’ve already done the back-of-the-napkin math, and it’s only a couple of hundred iterations before it finds the word. The average phone can do it in less than a second.

All I’m looking for is a bit of practical advice about how to set up the the functional heart of that operation. I was hoping not to have to reinvent the wheel… :man_shrugging:

#12

Then I had understood your initial problem wrong.

In that case the easiest way is to probably break down your word into letters and put each table into a table.

local word = ”hello”
local t = { ”h”, ”e”, ”l”, ”l”, ”o” }

Using tables is faster than string operations. Personally I also find the code becomes easier to understand and handle.

And then just do the loop for the adjacent tiles in a single loop. If the first tile matches the first letter, then check recursively for adjacent ones matching the second letter, and always ignore already visited tiles. You can use the level of recursion as a key for what letter to match for in the table.

If there is ever a point where the recursion reaches the length of the table and the final letter matches, then you’ve found the word.

That’s probably ~30-40 lines of code at most.

#13

Putting the word into a table is great advice- thank you. I can definitely see how calling places inside a table within a loop is way easier than fiddling around with string:sub.

#14

I have a M3 game and the problem is the same… prompt the user to a match (they haven’t seen) on a 9x9 grid. A simple recursive algo does this in a fraction of a second.

I’m using ints for colours but the same logic applies to chars, they can be considered ints too

#15

The word search is exponentially more difficult.

With a match 3 game, you can only move one piece on the game grid and you can only move it one tile away in one of four directions. The algorithm only needs to identify a location where moving one piece would result in 3 pieces of the same type being horizontally or vertically next to one another.

With Boggle-style word search, you can move in up to 8 different directions, as many times as the longest allowed word is or until you run out of possible moves. The algorithm needs to find an actual word, which means that the letters need to be in the correct sequence and the length of the word isn’t necessarily defined or it varies. Depending on the dictionary being used, there can be hundreds of thousands of words to check.

#16

Well, you also need to check for matches that make 4 and 5 lengths and it is not just in lines as a match can be an L shape or a T shape. You then have to factor in all the special pieces that can also be used to make a match.

But the iterative process is still the same. Start with one tile and then check adjacent ones for a “match”, repeat until you run out of options, move to next tile and repeat.

#17

Would you mind sending over the chunk of code that does the iteration? I know our nuts and bolts will end up being different, but I would really like to see how you structured the step-and-check portion of the loops.

#18

This is probably a good starting point - https://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/

The js version should be easy to port to lua.

1 Like
#19

That example code worked great- thank you for pointing me at it. The function I developed from it will find an eight-letter word in an 8x8 grid in less than a tenth of a second, so I’m pretty pleased with how it all worked out.