Question

Word Find A popular diversion in the United States, “word find” (or “word search”) puzzles ask the player to find each of a given set of words in a square table filled with single letters. A word can read horizontally (left or right), vertically (up or down), or along a 45 degree diagonal (in any of the four directions) formed by consecutively adjacent cells of the table; it may wrap around the table’s boundaries, but it must read in the same direction with no zigzagging. The same cell of the table may be used in different words, but, in a given word, the same cell may be used no more than once. Write a computer program in C++ for solving this puzzle.

Answer 1

---------------------------------------Program to solve word puzzle Word Puzzle---------------------------------

(files to read and initial data.....must be made sure)

/* Store the puzzle in file "Wordpuzzle.txt"
* First line initially contains two characters n amd m representing the Row and Column.
* (Solution/word to be found) of the Word Puzzle will be displayed in the file - words.txt
*/

//-----------------------------------------The Main Class For Testing the program-------------------------------------

#define maxN 50
#define maxM 50

char puzzle[ maxN ][ maxM ], // Array to store the puzzle
puzsol[ maxN ][ maxM ], // Array to show the solution
line[ maxM + 1 ]; // Providing Input
int n, // Declaring the no. of Rows
m, // Declaring the no.f Column
maxOFnm, // Total no of elements in main Diagonal
pfile; // Pattern of the Storage of the words.

void main()
{
FILE *file;
int len;

if ( LoadPuzzle() ) {
ShowPuzzle();
if ( (file = fopen( "words.txt", "r" )) != NULL ) {
while ( fgets( line, maxM + 1, file ) != NULL ) {
len = removeNL( line );
FindWord( line, len );
}
fclose( file );
ShowSolution();
}
}
}

//------------------------------------------Loading the Puzzle---------------------------file-(WordPuzzle.com)

int LoadPuzzle()
{
FILE *file;
int ok = 0, i, j;

if ( (file = fopen( "Wordpuzzle.txt", "r" ))
!= NULL ) {
fscanf( file, "%d %d\n", &n, &m );
if ( 0 < n && n <= maxN
&& 0 < m && m <= maxM ) {
maxOFnm = n < m ? m: n;
for ( i = 0; i < n; ++i ) {
fgets( line, maxM+1, file );
removeNL( line );
strcpy( &(puzzle[ i ][ 0 ]),
line );
}
fclose( file );
ok = 1;
}
}
return ok;
}

int removeNL( char *str )
{
int l = strlen( str ) - 1;
str[ l ] = '\0';
return l;
}

//-------------------------------------------------------Show Puzzle-------------------------------------------------

void ShowPuzzle()
{
int i, j;

printf( "Puzzle array: (%dx%d)\n",
n, m );
for ( i = 0; i < n; ++i ) {
for ( j = 0; j < m; ++j ) {
printf( "%c ", puzzle[ i ][ j ] );
puzsol[ i ][ j ] = ' ';
}
printf( "\n" );
}
}

//-------------------------------------------------------Show the Solutions-------------------------------------------

void ShowSolution()
{
int i, j;

printf( "\nWords found:\n" );
for ( i = 0; i < n; ++i ) {
for ( j = 0; j < m; ++j )
printf( "%c ",
puzsol[ i ][ j ] );
printf( "\n" );
}
}

//-------------------------------------------------------Finding the Word----------------------------------------------

void FindWord( char *w, int wLen )
{
pfile = hvfile( w, 0, wLen, 1 );
printf( "searching for '%s', file = %d", w, pfile );

if ( !( hKRsearch( w, wLen ) // horizontal search
||
vKRsearch( w, wLen ) // vertical search
||
seKRsearch( w, wLen ) // south-east search
||
swKRsearch( w, wLen ) ) ) // south-west search
printf( " not" );
printf( " found\n" );
}

// --------------------------------Storing the Pattern of the words stored in the file------------------------------------

typedef enum { forw, back } FillDir; // Direction to fill a wordin the solution

typedef struct { // Fill information (FI) structure
int pos; // Position to start filling a word
FillDir dir; // Fill direction
} FIstr;

FIstr finfo;

int hvFP( char s[], int i, int len, int d )
{
int j, sum;

sum = 0;
for ( j = i; j < len; j += d )
sum += s[ j ];
return sum;
}

int hvKRsearch( char *p, char *t, int pLen, int tLen, int d )
{
int i, j, k, tFP, pMaxIdx = pLen*d, tMaxIdx = (tLen-pLen)*d;

tFP = hvFP( t, 0, pMaxIdx, d );

for ( i = 0; i <= tMaxIdx; i += d ) {
if ( pFP == tFP ) {
for ( j = 0, k = i; j < pLen; ++j, k += d ) // forward match
if ( p[ j ] != t[ k ] )
break;
if ( j == pLen ) {
finfo.pos = i; finfo.dir = forw; return 1;
}
else {
for ( j = pLen-1, k = i; j >= 0; --j, k +=d ) // backward match
if ( p[ j ] != t[ k ] )
break;
if ( j == -1 ) {
finfo.pos = i; finfo.dir = back; return 1;
}
}
}
else
tFP += t[ i + pMaxIdx ] - t[ i ];
}
return 0;
}

//--------------------------------------------To Store the Word Horizontal and Vertical----------------------------------

void hvFillWord( char *psol, char *w, int wLen, int d )
{
int i, j = finfo.pos;

if ( finfo.dir == forw )
for ( i = 0; i < wLen; ++i ) {
psol[ j ] = w[ i ];
j += d;
}
else // finfo.dir == back
for ( i = wLen-1; i >= 0; --i ) {
psol[ j ] = w[ i ];
j += d;
}
}

// ------------------------------------------------ Searching the words horzintally and vertically ----------------------

int hKRsearch( char *w, int wLen )
{
int i;

for ( i = 0; i < n; ++i )
if ( hvKRsearch( w, &(puzzle[ i ][ 0 ]), wLen, m, 1 ) ) {
hvFillWord( &(puzsol[ i ][ 0 ]), w, wLen, 1 );
break;
}
return i < n;
}

int vKRsearch( char *w, int wLen )
{
int j;

for ( j = 0; j < m; ++j )
if ( hvKRsearch( w, &(puzzle[ 0 ][ j ]), wLen, n, maxM ) ) {
hvFillWord( &(puzsol[ 0 ][ j ]), w, wLen, maxM );
break;
}
return j < m;
}

//----------------------------------------------To Store the Word Diagonally------------------------------------------------

void dgFillWord( char *psol, char *w, int wLen, int d )
{
int i, j = finfo.pos;

if ( finfo.dir == forw )
for ( i = 0; i < wLen; ++i ) {
psol[ j ] = w[ i ];
j += d + 1;
}
else // finfo.dir == back
for ( i = wLen-1; i >= 0; --i ) {
psol[ j ] = w[ i ];
j += d + 1;
}
}

//----------------------------------------------To find the Word Diagonally--------------------------------------------------

int seKRsearch( char *w, int wLen )
{
int i, tLen, found = 0;

tLen = maxOFnm;
for ( i = 0; wLen <= tLen; ++i ) {
if ( dKRsearch( w, &(puzzle[ i ][ 0 ]), wLen, tLen, maxM ) ) {
found = 1;
dgFillWord( &(puzsol[ i ][ 0 ]), w, wLen, maxM );
break;
}
--tLen;
}
if ( tLen < wLen ) {
tLen = maxOFnm - 1;
for ( i = 1; wLen <= tLen; ++i ) {
if ( dKRsearch( w, &(puzzle[ 0 ][ i ]), wLen, tLen, maxM ) ) {
found = 1;
dgFillWord( &(puzsol[ 0 ][ i ]), w, wLen, maxM );
break;
}
--tLen;
}
}
return found;
}

int swKRsearch( char *w, int wLen )
{
int i, tLen, found = 0;

tLen = maxOFnm;
for ( i = m-1; wLen <= tLen; --i ) {
if ( dKRsearch( w, &(puzzle[ 0 ][ i ]), wLen, tLen, maxM-2 ) ) {
found = 1;
dgFillWord( &(puzsol[ 0 ][ i ]), w, wLen, maxM-2 );
break;
}
--tLen;
}
if ( tLen < wLen ) {
tLen = maxOFnm - 1;
for ( i = 1; wLen <= tLen; ++i ) {
if ( dKRsearch( w, &(puzzle[ i ][ m-1 ]), wLen, tLen, maxM-2 ) ) {
found = 1;
dgFillWord( &(puzsol[ i ][ m-1 ]), w, wLen, maxM-2 );
break;
}
--tLen;
}
}
return found;
}