Similar to boggle game

[urfa2]

Need help to edit this code to allow user to find words in the grid that are touching horizontally, vertically, and diagonally adjacent. For example, the board:

Q W E R T
A S D F G
Z X C V B
Y U A O P
G H J K L

contains the magic words WAS, WAXY, JOB.

# include <stdio.h>
# include <math.h>
# include <stdlib.h>

int x;
int y;
char grid [10] [10];
int z;
int j;

int main()
{
// declare array with alphabet
char alphabet[26] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g',
'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u',
'v', 'w', 'x', 'y', 'z' };

printf ("Insert the width (x) and height (y) of the grid \n");
scanf ("%d %d", &x, &y);

for (z = 0; z < x; z++)
{
for (j=0; j < y; j++)
{
// print letters instead of dots
grid [z] [j] = alphabet[rand() % 26];
}
}
for (z = 0; z < x; z++)
{
for (j=0; j < y; j++)
{
printf ("%c", grid [z] [j]);
}
printf ("\n");
}
}

[ne555]

some pseudocode

def find_in_grid(word):
	for K = [0:nrows-1]:
		for L = [0:ncols-1]:
			if can_form_word(K, L, word):
				return true
	return false

def can_form_word(x, y, word):
	if word.is_empty(): //base case, can always form ''
		return true
	if grid[x][y] == word[0]: //found first character
		for K = [-1:1]:
			for L = [-1:1]:
				if can_form_word(x+K, y+L, word[1:]): //check the neighbours for the rest
					return true
	return false

it's missing bound checking
you may use a bigger matrix, and fill the border with an invalid value, such that once it reaches a border the function will end

also, it allows to use the same cell several times and even never moving, if that's not allowed you need to mark the visited cell somehow.

[jonnin]

*diagonals were not allowed in classic boggle. if you care.


it may be more efficient to generate every possible word from your grid up front, and then look for each one using the rules, rather than look at each letter and then each pair and then each surviving triplet and then each surviving quad.. etc .. over and over. I haven't worked out if that is true or not, but adding the diagonal dimension to it makes me lean that way.

[urfa2]

It's similar to boggle but not exactly like boggle, so diagonally is allowed. The grid has to be random letters each time, its not constant so I can't do all words possible.

[jonnin]

yes, you can :) I am unsure if its the best way, but you certainly can look up all the possible words first. Or you can build up and check each thing you cook up to see if its a word. Both work, not sure which is faster. You wouldn't make all the permutations. … something like char letters[256] = 0; for each letter in the grid, increment letters [letter] eg if you have 'a' then letters['a']++. Now that you have it in this form, iterate it from 'a' to 'z' … choose the letter you are on as your starting letter if its in the array. pull all the words that start with that from your dictionary into a sorted list. grab the first word, check letter by letter if letters[letter] is true. If its true for all the letters, the word is a candidate. Its a lot of iteration, but its CHEAP iteration.... then take all the candidates and see if you can make them by forming a path in the grid (this is expensive but you have weeded out a lot of trash this way, and what is left will go quickly, I think?)