How to get this C program running on my computer?

[charchar88]

I'm trying to get a C version of this game working on my computer using gcc on ubuntu.

http://www.lemoda.net/c/boggle/boggle.html

I have no need for a pearl script or anything since I just have a simple dictionary text file and want to be able to just load in the text file and do the same thing as it would do on that site but just on my computer like a basic c program.

However when I compile it, it gives a lot of errors such as "redeclaration of bg with no linkage" and undefined reference to 'dictionary' and 'n_words' ect.

How do I get this working on my computer? What modifications do I make?

I have no experience with make files and pearl scripts and such. Are a lot of modifications needed? Or do I just need to do things using basic file in/out in C?

[turkey999]

You just need to make a file called "dict.c" from your words. Look at the Perl script from where it says <<EOF to where it says EOF and copy that bit of it, then your words in double quotes, then finally "0};" at the end.

However when I compile it, it gives a lot of errors such as "redeclaration of bg with no linkage" and undefined reference to 'dictionary' and 'n_words' ect.

I don't know what operating system you are using, but there's a makefile at the bottom of the page which gives compilation instructions.

[charchar88]

Yeah, Im trying to modify it so I can use a dictionary.txt file and run it in C without the make file or pearl script

[Adak]

You don't need the Pearl script at all. Do you have the dictionary file yet?

Forget the Pearl script, get the dictionary file, and take just copy the first 10 words of so, out, for a test file.

Now, what problems do you have?

[turkey999]

Yeah, Im trying to modify it so I can use a dictionary.txt file and run it in C without the make file or pearl script

As it stands the program is set to build using the dictionary compiled into a data segment. So you need to write some kind of parser for "dictionary.txt" to read it and put it into the appropriate data structure.

By the way, that is "makefile" and "Perl" not "make file" and "pearl".

[turkey999]

You don't need the Pearl script at all. Do you have the dictionary file yet?

Forget the Pearl script, get the dictionary file, and take just copy the first 10 words of so, out, for a test file.

Now, what problems do you have?

The way that code is set up, that will not work. You need to write some parser to read the dictionary file in. The program is set up to put its data into the program itself.

[charchar88]

So I can't just parse the dictionary.txt file into the dictionary array variable and pass that in?

extern const char * dictionary[];

I was thinking of using a file pointer and other stdio.h functions to read in the text file and put each word into an array index somehow. That way won't work?

[turkey999]

So I can't just parse the dictionary.txt file into the dictionary array variable and pass that in?

extern const char * dictionary[];

I was thinking of using a file pointer and other stdio.h functions to read in the text file and put each word into an array index somehow. That way won't work?

I think you are stuck on more than just that program, you don't seem to know C very well. How about getting a copy of "The C programming language" by Kernighan and Ritchie and working through some examples. I don't think there is much else I can suggest.

[abhimanipal]

Quick question do you know the relevance of the keyword extern ?

I removed extern and the program compiled with just 1 warning

[charchar88]

Yeah I removed extern since extern was needed for the pearl script which I'm trying to do without. That was part of the original errors. But still trying to figure out how to get the wordlist into the array.

And yes, I do have the book "C programming A Modern Approach" which is a great book. However I like seeing how some programs work and I learn my tinkering around and doing stuff and I feel that doing what I want to do is simple and easy. I guess not.

[chrjs]

Quick question do you know the relevance of the keyword extern ?

I removed extern and the program compiled with just 1 warning

The extern keyword means that the variable is defined outside of that source file. The warning you got probably came from using the variables that were declared as extern without defining any value for them.

[charchar88]

Yeah I know that now, I fixed that. Do you have any suggestions of how to load a dictionary text file full of words into an array/list of some sort?

[TrustyTony]

I do not know how much you learn from just looking other's code, better do it on your own. I can say it as I did it myself in Python language: http://www.daniweb.com/software-development/python/code/299470. you could try to use my approach in c and see how it compares with the ready program or my Python code.

[charchar88]

Alright thanks, I don't know python at all but I'll take a look. It's actually a little difficult to (for me at least) to translate higher level languages down to C but your python might help me with the matrix traversal logic.

I've programmed java for about a year before C and stuff like str.charAt() and list.add() and other object oriented aspects, you have to make or find yourself on the web in C. I guess it's not that hard if you can make these functions but things we take for granted like arraylist in java and Vector in C++ you have to create on your own in C.

I'll spend a few more hours on this program over the next 2 days and see what I can do and I'll post back, but as of now I"m just still trying to figure out how to load and parse the dictionary.txt file. I'm still wondering if I just put it in the char dictionary[] array.

[TrustyTony]

I compiled the file with the suggested installation process in windows under mingw, but the resulting compiled program produced wrong input it produced this output:

$ boggle
LOEV
UXNI
UIXQ
KPWB
XI
NO
NE
NI
NINE
NIX
NI
NIX
NINE
NIP
IE
IN
INO
IN
INO
XI
XI
PU
PI
PIX
PIN
PINO
PINE
PIK
PIP
WI
WIN
WINE

Nine is not possible as it folds back over itself, my newer version of program produce with same input:

Default language: US, dictionary: us.txt
Preparations: 127.661 ms

    Give your boggle,
    dimension number for random square,
    two letter dictionary code
    or q to quit:

      loevuxniuixqkpwb

  0:  L O E V
  4:  U X N I
  8:  U I X Q
 12:  K P W B

95 candidates  found in 1061.898 ms of which final check took 2.647 ms
Total 37 solutions.
NIXIE   PIXIE   ENOL    EXON    KINO    LONE    LUXE    OXEN    PINE    PINO
VEIN    VINE    VINO    WINE    EON     INO     KIN     KIP     KUI     LOU
LOX     LUI     LUO     LUX     NEI     NEO     NIP     NIX     NOU     ONE
PIK     PIN     PIX     VEI     VEX     VIE     WIN

The linked browser version does not however produce NINE as result. Also minimum length of solutions should be 3: http://en.wikipedia.org/wiki/Boggle

Here is the perled dict.c as zip attached.

[charchar88]

That's odd, because when you try it on the link they give you online and input a grid, it seems to pick out dictionary words.

[Adak]

It's not that difficult. We just have to change the code a bit to make it work this way.

Why don't you post up the first ten lines of text from the dictionary file, and I'll show you how it can be done? Same format and everything.

Tinkering with code, is not a bad thing.

[charchar88]

Ok the first 10 words from the dictionary text file :

aback
abaft
abandon
abandoned
abandoning
abandonment
abandons
abase
abased
abasement

I figure that I first need to figure out how to successfully load the entire text file of 30,000 or so words into the dictionary [] array. Using malloc or some define number perhaps. Then I need to figure out a way to terminate each word at each index with a '/0'. Or somehow make it dynamic so it terminates the end of a word using a strlength function (memory efficiency).

So eventually dictionary[] will contain the entire dictionary in memory which will make it easier for searching/other algorithms to use it in the program.

That's my approach to this so far.

[abhimanipal]

Ok.... Dont start straight away for 30,000 words ...
Write code for the your approach for 10 words and then scale it to 30,000

[TrustyTony]

Notice: I am not the OP. I posted zipped the result of perl script: dict.c

Result of test case included in code (change #if 0 to #if 1) by my Python program with the dict.txt from this program as US dictionary gives as result:

FXIEAMLOEWBXASTU

  0:  F X I E
  4:  A M L O
  8:  E W B X
 12:  A S T U

199 candidates  found in 1140.000 ms of which final check took 10.000 ms
Total 94 solutions.
EMBOLE 	FAMBLE 	SEMBLE 	WAMBLE 	AMBLE 	AWEST 	AXILE 	EMBOX 	LIMAX 	LIMBO 	LIMBU 	LIMES 	SWAMI 	AMBO 	AMIL 	AMLI 	ASEM 	AXIL 	AXLE BLEO 	BOIL 	BOLE 	EAST 	EMIL 	FAME 	LIMA 	LIMB 	LIME 	MESA MEWL 	MILE 	MILO 	OIME 	SAWT 	SEAM 	SEAX 	SEMI 	STUB 	SWAM TWAE 	TWAS 	WAME 	WASE 	WAST 	WEAM 	WEST 	AES 	AME 	AMI ASE 	AST 	AWA 	AWE 	AWL 	BLO 	BUT 	ELB 	ELI 	ELM FAE 	FAM 	IMA 	LEI 	LEO 	LIE 	LIM 	LOB 	LOX 	MAE MAW 	MAX 	MES 	MEW 	MIL 	MIX 	MWA 	OIL 	OLE 	OLM SAW 	SEA 	SEW 	STU 	SWA 	TUB 	TUX 	TWA 	WAE 	WAF WAS 	WAX 	WEA 	WEM 	WES

(sorted result first by length, then alphabet)

dict.txt has by the way 235882 words not, 30000.

I compiled program with above test case enabled with command also in Linux the code with edited Makefile

tony@tony-one:/media/Ysisoft_backup/MinGW/msys/1.0/home/Veijalainen/c$ make
cc -c -g -Wall boggle.c
./dict-to-inc.pl
cc -c -g -Wall dict.c
cc -o boggle -g -Wall boggle.o dict.o
tony@tony-one:/media/Ysisoft_backup/MinGW/msys/1.0/home/Veijalainen/c$ cat Makefile 
cc=gcc
boggle: boggle.o dict.o
	cc -o boggle -g -Wall boggle.o dict.o

boggle.o: boggle.c
	cc -c -g -Wall boggle.c

dict.o: dict.c
	cc -c -g -Wall dict.c

dict.c: dict.txt
	./dict-to-inc.pl
tony@tony-one:/media/Ysisoft_backup/MinGW/msys/1.0/home/Veijalainen/c$ boggle
'boggle' ei ole tällä hetkellä asennettuna.  Voit asentaa sen kirjoittamalla:
sudo apt-get install bsdgames
tony@tony-one:/media/Ysisoft_backup/MinGW/msys/1.0/home/Veijalainen/c$ ./boggle
FXIE
AMLO
EWBX
ASTU
MI
MA
ME
MWA
MWA
LI
LO
LOB
LOX
OE
OLE
OLM
OBOE
OBOL
OBOLE
OX
WA
WE
WA
BO
BOLE
BOB
BU
BUB
BUBO
BUT
SE
SWA
SWA
SA
ST
TWA
TWA
TU
TUB
TUX
TUT
TUTS
UT

Result is bad, but contains few correct answers.

[charchar88]

Hmm, I wonder what it's doing wrong and how can you correct it?
It should only print out found words in the dictionary.

Hey tonyjv, you don't mind walking me through in C code or even psuedo code on how exactly you traversed the 4x4 matrix while at the same time checking if what you have is a word in the dictionary and how you prevent checking things you already checked ect. That's where I"m stuck the most is how exactly you check each index neighbor around you looking for words similar to how a person would when playing this game.

I'm trying to figure this out on paper but I'm not quite grasping how I'd do the algorithm.

Also I'm giving the option in my program of setting the grid size to any NxN matrix. So how does your python program do with a 32x32 matrix tonyjv?

[charchar88]

I got the words in the dictionary array and print_boggle is working but solve_boggle is not. The program stops after printing the randomly generated grid.

After about an hour of putting printf's in various places to see what was getting what, I think I narrowed the cause down to the valid_substr function. For some reason that's not returning anything.

I've been at this for 6 hours, anyone want to take a look?

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define BOGGLE_ROWS 4
#define BOGGLE_COLUMNS 4
#define MAX_WORD_COUNT 38655
#define MAX_WORD_LENGTH 19

/* Define constants from dict.c */

 const int n_words = 38655;
 const char * dictionary[MAX_WORD_COUNT]; 
 const char * word[MAX_WORD_LENGTH];

	
	

/* The grid of boggle letters. */

typedef struct
{
    char letter[BOGGLE_ROWS][BOGGLE_COLUMNS];
}
boggle_grid;

/* Shake the "dice" and create a boggle grid. */

void create_boggle (boggle_grid * bg)
{
    int row;
    unsigned seed = (unsigned) time (0);
    srand (seed);
    for (row = 0; row < BOGGLE_ROWS; row++) {
        int col;
        for (col = 0; col < BOGGLE_COLUMNS; col++) {
            bg->letter[row][col] = rand () % 26 + 'A';
        }
    }
}

/* Print out the boggle grid. */

void print_boggle (boggle_grid * bg)
{
    int row;
    for (row = 0; row < BOGGLE_ROWS; row++) {
        int col;
        for (col = 0; col < BOGGLE_COLUMNS; col++) {
            printf ("%c", bg->letter[row][col]);
        }
        printf ("\n");
    }
}

/* Keep track of the letters in the boggle grid which have already
   been used. */

typedef int used_letter_t[BOGGLE_ROWS][BOGGLE_COLUMNS];

/* The candidate answer. */

#define MAX_ANSWER BOGGLE_ROWS * BOGGLE_COLUMNS + 1

typedef struct
{
    char letters[MAX_ANSWER];
    int length;
}
answer_t;

/* Reset the array of used letters to all zeros. */

void used_letter_init (used_letter_t used_letter)
{
    int start_row;
    for (start_row = 0; start_row < BOGGLE_ROWS; start_row++) {
        int start_col;
        for (start_col = 0; start_col < BOGGLE_COLUMNS; start_col++) {
            used_letter[start_row][start_col] = 0;
        }
    }
}

/* Substring compare for valid_substr's bsearch. */

int compare_substr (const void * vanswer, const void * vword)
{
    const answer_t * answer = vanswer;
    const char * const * word = vword;
    int comp;
    comp = strncmp (answer->letters, *word, answer->length);

    return comp;
}

/* String compare for found_word's bsearch. */

int compare_exact (const void * vanswer, const void * vword)
{
    const answer_t * answer = vanswer;
    const char * const * word = vword;
    return strcmp (answer->letters, *word);
}

/* Initialize the candidate answer to an empty string of zero
   length. */

void answer_init (answer_t * answer)
{
    int letter = 0;
    for (letter = 0; letter < MAX_ANSWER; letter++)
        answer->letters[letter] = '\0';
    answer->length = 0;
}

/* Return a true value if the candidate answer is a substring of any
   word in the dictionary. */

void * valid_substr (answer_t * answer)
{
	 
    return bsearch (answer, dictionary, n_words,
                    sizeof (char *), compare_substr);
}

/* Return a true value if an exact match for this word is in the
   dictionary. */

void * found_word (answer_t * answer)
{
	
    return bsearch (answer, dictionary, n_words - 1,
                    sizeof (char *), compare_exact);
}

/* Add a letter to the candidate answer. */

void add_letter (answer_t * answer, char letter)
{
    answer->length++;
    answer->letters[answer->length - 1] = letter;
}

/* Remove a letter from the candidate answer. */

void remove_letter (answer_t * answer)
{
    answer->length--;
    answer->letters[answer->length] = '\0';
}

/* Given a starting point in the grid, "row" x "col", move along one
   and see if there is another valid word. */

void find_next (boggle_grid * bg, int row, int col,
                used_letter_t used_letters, answer_t * answer)
{
    int next_row;
    if (answer->length >= MAX_ANSWER)
        return;
    for (next_row = row - 1; next_row <= row + 1; next_row++) {
        int next_col;
        if (next_row < 0 || next_row >= BOGGLE_ROWS)
            break;
        for (next_col = col - 1; next_col <= col + 1; next_col++) {
            if (next_col < 0 || next_col >= BOGGLE_COLUMNS)
                break;
            if (used_letters[next_row][next_col]) {
                break;
            }
            used_letters[next_row][next_col] = 1;
            add_letter (answer, bg->letter[next_row][next_col]);
            if (valid_substr (answer)) {
		
                if (found_word (answer)) {      
                    printf ("%s\n", answer->letters);
                }
                find_next (bg, next_row, next_col, used_letters, answer);
            }
            used_letters[next_row][next_col] = 0;
	
            remove_letter (answer);
	   
        }
    }
}

/* Find all the possible words in the grid and print them to stdout. */

void solve_boggle (boggle_grid * bg)
{
    int start_row;
    int used_letters[BOGGLE_ROWS][BOGGLE_COLUMNS];
    answer_t answer;
    used_letter_init (used_letters);
    answer_init (& answer);
    for (start_row = 0; start_row < BOGGLE_ROWS; start_row++) {
        int start_col;
        for (start_col = 0; start_col < BOGGLE_COLUMNS; start_col++) {
            add_letter (& answer, bg->letter[start_row][start_col]);
            find_next (bg, start_row, start_col, used_letters, & answer);
            remove_letter (& answer);

        }
    }
}


int main ()
{

FILE *fp;
	fp = fopen("dictionary.txt", "r");
	if (fp == NULL) {
		printf("Error opening dictionary.");
		exit(1);
	}

int i = 0;
while(!feof(fp))
{

fgets(word, MAX_WORD_LENGTH + 1, fp);
dictionary[i] = word;
//printf("%s \n", dictionary[i]);
i++;

}

printf("%d \n", n_words);

    boggle_grid bg;
    create_boggle (& bg);

    print_boggle (& bg);
    solve_boggle (& bg);
    return 0;
}

[TrustyTony]

The number of available words in grid explodes if you do not put lower limit of length like grid width -1 for minimum word length. That does not make sense for very big grids. I did one my random (boggle dice simulation with normal Q instead of Qu) grid of 25 x 25, and added paging of results to output routine (some first pages of answers):

Give your boggle,
    dimension number for random square,
    two letter dictionary code
    or q to quit:

      25
Dimension 25

  0:  W R H L U A Y O E I Z P M B T L R L V O U T I E V
 25:  L P T V O A U G I E Y Q L E N S A S I M J P G A O
 50:  A E R T A V F E J E L H H A A O Y W N W E R H I E
 75:  A T N T N V H E W L S I E L N E L E Q R T T O P E
100:  A H S E U A H O A L W E X T F L O Z A T A L P R T
125:  K S D F W Y B B E E G O S A S O T G A R D W C G N
150:  E U P N L U G W W H A S S B A Q O V A E I H B Q P
175:  Y R L P A A S E I R W N E S O T H T G T Y E A L L
200:  P P U C I Y O T U Y S I G E S O I R S U E T F V O
225:  U R X N H L P L N V A U H I H E E A N H O S A R T
250:  X N T N A T A W O Y M U E B X Y B F L E D T O R S
275:  U T E N L Y Y I J J E F E I A J F T D T D B S E A
300:  H O W H S I N I O A H W U E D N W E S E R A E H R
325:  O M O A N I T L F E H E V U T O M O T R U T Z N R
350:  P O C A I G U A M O S L P S S T L I T Y J O R I Q
375:  T E L U P R U A Y E S E T I I P Y W S U Z Y I C S
400:  N O H D E I H P R E T P A S R L N U E I U R T I V
425:  U R H R N E O I D O O E O I O T E I R S U H W E Y
450:  I I I S E H R E K V D U G B A D N O S I E T N F E
475:  V F L E M S B A W N X B A Q S I T K T M V E V L E
500:  U R E Y D I O S X O S N B L S T L U E U N N I R A
525:  D Q F R E K P H E S H N W N T E N G P W H W S T C
550:  H P O N Y S R O N T H E S D K G B A C I D E O B D
575:  D W I N C T I R T U H T I E Z A W O F Z I X T Q I
600:  M Y O W E D H I M J E T A Z I A H L I I O D D H T

223997 candidates  found in 130749.979 ms of which final check took 128220.994 ms
Total 8777 solutions.
TEUTOPHOBISM, ABSTINENTLY, BANGWAKETSI, PERIANGITIS, PROTOPEPSIA, SOREHEARTED, TETRABORATE, UNENVIRONED, UNINTRIGUED, X
NOPHOBISM, BALDERDASH, BROIDERESS, CHALINITIS, ENSANGUINE, EPISTOLIST, ESURIENTLY, EUSTATHIAN, HAGIOLATER, HEMOSPASIA,
ATENTNESS, NESTIATRIA, ODORIPHORE, OSTEOTRITE, PISTOLWISE, PRISOMETER, PYOSALPINX, RAPHIDODEA, RESTORATOR, REUNIONIST,
ERPHOIDEA, SOBERSIDES, SOREHEADED, SPIRITLESS, SPIRITSOME, STYLOMETER, TARTARATED, TEUTOPHOBE, TRIPUDIANT, UNEXHORTED,
<Enter>
UNPROBATED, UNVISIONED, VAREHEADED,  ABSTINENT,  ALDHAFARA,  ALERTNESS,  ANCHYLOSE,  APERTNESS,  APPRESSED,  ASININELY,
 ASTROLABE,  ATLANTEAN,  BEANFEAST,  BOASTLESS,  BRASHNESS,  CAULDRIFE,  CHEIRAGRA,  DIABOLIST,  DISTHRONE,  DOLOMEDES,
 EPISTASIS,  EPISTYLIS,  ERYTHROID,  FEDERATOR,  FIRESIDER,  GEMITORES,  HARRISITE,  HEARTSOME,  HEMAPHEIN,  HEMATURIA,
 HESSONITE,  HEXABIOSE,  HOMOCOELA,  HORSESHOE,  INCANDENT,  ISOINDOLE,  LALOPATHY,  LAMESTERY,  LEPTODORA,  LINEARITY,

<Enter>
 LITERATOR,  MISDESIRE,  MISINTEND,  MISRENDER,  NEURONISM,  NEURONIST,  NONSALINE,  OESTRUATE,  OILOMETER,  ORIENTITE,
 OUTREDDEN,  PALINURUS,  PITOMETER,  PLENILUNE,  POSTULATA,  PREINDUCE,  PREINHERE,  PREMATURE,  PRESUPPLY,  PRISTODUS,
 REBESIEGE,  REHEARTEN,  RENDERING,  RESHEARER,  RESIDENCE,  RESIDENCY,  RESILIFER,  RIFLESHOT,  SALINELLE,  SAOSHYANT,
 SARTORITE,  SEMAPHORE,  SEMIPRONE,  SEMISHEER,  SEMISOPOR,  SERAPHINE,  SHORTNESS,  SOLIPSIST,  SOSTENUTO,  SPILOSITE,

<Enter>

223997 candidates ie words with all letter pairs in somewhere in grid, 2 min 11 s running time for total of 8777 solutions. . My search tree limiting does not bite when most letter pairs are available somewhere in grid.

[charchar88]

are you using a trie data structure or just a binary search? Also how are traversing the grid and checking for words? I'm not sure how to go about this.

[TrustyTony]

I do not use any tree structures, only sanity test for any chance that word is possible solution (all letter pairs in word must exist in grid) and checking existence of path for whole word through those pairs by recursive generator funcition.

Here the main functions of my Python program, I limit word list to those words which has all letter pairs available in grid and find if connected path exist to join all the word starting from any of the places in grid where the first two letters of word is available.

It is little difficult to follow because of using of recursive generator function for finding word path.

I put some extra comments in this code, ignore the first lines technicalities, my preparation of neighbours is in many steps, as I developed the code in small steps. Now maybe I could generate the final list form directly without the substeps.

from __future__ import print_function
from time import clock
import random
import string

try:
    input = raw_input
except:
    pass


DICT = {'UK': 'uk.txt','US': 'unixdict.txt', 'FI': 'fi.txt'}
DEF = 'US'
print("Default language: %s, dictionary: %s" % (DEF, DICT[DEF]))

neighbours=(
    (-1,-1),  (-1,0), (-1,1),
    (0,-1),           (0,1),
    (1,-1),   (1,0),  (1,1)
    )

def random_boggle(dimension):
    " Generate random boggle of dimension, from lettercubes "

    die = ("TOESSI",
           "ASPFFK",
           "NUIHMQ", ## Qu replaced by Q for easier processing of letter pairs
           "OBJOAB",
           "LNHNRZ",
           "AHSPCO",
           "RYVDEL",
           "IOTMUC",
           "LREIXD",
           "TERWHV",
           "TSTIYD",
           "WNGEEH",
           "ERTTYL",
           "OWTOAT",
           "AEANEG",
           "EIUNES"
        )

    rand_die = []
    while len(rand_die) < dimension*dimension:
        rand_die.extend([random.choice(this) for this in die])
    random.shuffle(rand_die) ## mix up the order from repeated die
    return ''.join(rand_die[:dimension * dimension])

def word_path(word, dimension, neighbourlist, used=[]):
    """ Find solution path for given word from, dimension and neighbourlist,
        used keeps record of visitted letters

    """
    if word:
        # word not empty, find all neighbours having correct, unvisited value
         
        correct_neighbour = [
            neigh
            for neigh in (neighbourlist[used[-1]] if used else range(dimension * dimension))
                if ( boggle[neigh] == word[0] and (neigh not in used))
            ]
        # try to find solution through those neighbours
        for this in correct_neighbour:
            used_copy = used[:] + [this]
            # success if last letter in neighbour
            if len(word) == 1:
                if boggle[this] == word:
                    yield used_copy
                    # only one solution needed
                    return
            else:
                # if we have more than one letter left we reduce word and recurse to find path from each neighbour 
                for solution in  word_path(word[1:], dimension, neighbourlist, used_copy):
                    # solution is found 
                    yield solution
                    # one is enough
                    return


def solve_boggle(boggle,dimension,wordlist):
    # display the grid
    for i in range(0,len(boggle) - dimension + 1, dimension):
        print("%3i: " % i,' '.join(boggle[i:i + dimension]))

    print()
    # prepare set of index tuple, neighbour tuple pairs
    neighbour_indexpairs = set(((i,j), (i + di, j + dj))
                            for i in range(dimension)
                            for j in range(dimension)
                            for di,dj in neighbours if  0 <= dj + j < dimension and 0 <= di + i < dimension
                            )

    # change to one dimension
    neighbour_set=set((a * dimension + b, c * dimension + d) for (a,b),(c,d) in neighbour_indexpairs)
    # prepare list based off neighbours for every position
    neighbourlist = [[] for _ in boggle]

    for char_index, neigh in neighbour_set:
        neighbourlist[char_index].append(neigh)

    t0=clock()
    # standard grid 4 -> minimum length of word one less, consider however always words minimum 6 letters
    minlength = min(6, dimension - 1)
    # all possible letter pairs existing in grid
    letterpairs = set((boggle[a]+boggle[b]) for a,b in neighbour_set)
    # find which words satisfy minimum length and have all letter pairs in grid somewhere
    words = set(word.upper() for word in wordlist
             if (len(word) >= minlength and
                 all((word[i] + word[i + 1] in letterpairs)
                     for i in range(len(word) - 1))
                 )
             )
    print(len(words),'candidates', end =' ')
    t1 = clock()
    # result is those words for which letter pairs form connected path found by word_path
    result = [(word,solution) for word in words
           for solution in word_path(word, dimension, neighbourlist)
           if solution]

    result.sort()

    result.sort(key = len, reverse = True)
    print(" found in %.3f ms" % (1000 * (clock() - t0)),
          "of which final check took %.3f ms" % (1000 * (clock() - t1)))
    return result

I ran one random grid of 50x50 with little more sane, smaller word dictionary (unixdict.txt), with accepting the words minimum of 6 letters, and got solution in this time:

18744 candidates found in 50464.687 ms of which final check took 50236.336 ms
Total 1655 solutions.

So the program got solutions in under 51 s, which I consider reasonable.

[charchar88]

Yeah the syntax for python is very different from C/C++ and Java of which I'm familiar with. I've seen this used a lot though in some programs

#
neighbours=(
#
(-1,-1), (-1,0), (-1,1),
#
(0,-1), (0,1),
#
(1,-1), (1,0), (1,1)
#
)

How does this work?

[TrustyTony]

It is list of x ofset y ofset pairs to get neighbour in two dimensional grid. You iterate the pairs nd add first value to x, second to y.