Solving Word Puzzles in Linear Time (C# Version)

• Download wpuzzle - 1.2 KB
• Download program - 2.9 KB

Introduction

NOTE: This article documents the C# version of the C++ code published by The Code Project on January 7 2015. The description of the code is about the same. However, there are important differences. In particular, the use of unsafe and fixed to replicate in C# what the C++ code does to pass the address of a row or column of the puzzle or the solution arrays to the relevant functions. I have also renamed all the functions and added comments to make the code more understandable.

The word-search puzzle is a string-search problem in which several words are to be located within an n ? m array filled with letters. The following table shows a 30 ? 30 array (stored in a text file such as wpuzzle.txt) and some words (stored in a text file such as words.txt) that must be found in it.

Each word must occur entirely in a row, a column or a diagonal, that is, it cannot be bent from one direction into another. Words can be placed forward or backward, but not scrambled. Furthermore, words can share characters. The following function KarpRabinSearch, implements a variation of the “fingerprinting” method of Karp-Rabin for string search (see Sedgewick, Robert, Algorithms, 1990, pp. 289-291). All the code described in this article runs within a Visual Studio C# console application.

Function Fingerprint is used to compute the fingerprint of a word (or pattern) and the initial fingerprint of the corresponding prefix in the target (the word puzzle). The fingerprint is simply the sum of the ASCII codes of the characters.

  /// <summary>
  /// Compute the fingerprint of a substring of a given string.
  /// The fingerprint is the sum of the ASCII codes of the characters in the substring.
  /// </summary>
  /// <param name="str">The string containing the substring.</param>
  /// <param name="i">The starting position of the substring of str.</param>
  /// <param name="m">The upper bound on the value of i.</param>
  /// <returns>The sum of the ASCII codes of the characters str[ i ] ... str[ m-1 ].</returns>
  static int Fingerprint( string str, int i, int m )
  {
     int j, sum;

     sum = 0;
     for ( j = i; j < m; ++j )
     {
        sum += (int)( str[ j ] );
     }
     return sum;
  }
}

The variation on the Karp-Rabin search would then be implemented as follows:

/// <summary>
/// Search for the starting position in a target string where
/// a pattern string occurs.
/// </summary>
/// <param name="pattern">The pattern string to search for.</param>
/// <param name="target">The target string on which the search takes place.</param>
/// <returns>The index in the target string where the pattern starts;
///          -1 if the pattern does not exist in the target
/// </returns>
static int KarpRabinSearch( string pattern, string target )
{
   int i, j, k, m = pattern.Length, n = target.Length,
       patternFP = Fingerprint( pattern, 0, m ),
       targetFP = Fingerprint( target, 0, m );

   for ( i = 0; i <= n - m; ++i )
   {
      if ( patternFP == targetFP )
      {
         // Verify an exact match

         for ( j = 0, k = i; j < m; ++j, ++k )
         {
            if ( pattern[ j ] != target[ k ] )
            {
               break; // mismatch
            }

         }
         if ( j == m ) // Exact match
         {
            return i;
         }
      }
      else if ( i + m < n )
      {
         // Slide the target one character position to the right over the pattern
         // and update the target's fingerprint

         targetFP += (int)( target[ i + m ] ) - (int)( target[ i ] );
      }
      else
      {
         break;
      }
   }

   return -1;
}

If the fingerprints are the same (patternFP == targetFP), an exact match of the pattern against the target is attempted. A mismatching character causes the matching loop to be aborted, while a complete match makes the function return with the position of the pattern in the target string. If the fingerprints are not equal, the fingerprint substring of the target being matched (targetFP) is updated by considering the effect of “sliding” the pattern under the target one character position to the right. The beauty of the fingerprint approach is that words have the same fingerprint whether they are forward or backward in any direction.

Assume that the puzzle is given in the text file wpuzzle.txt, which contains n lines of m characters each. The characters on each line are separated by a blank space. Assume that the words to be found are given in the text file words.txt, one word per line. No assumptions should be made as to whether or not the words appear in the puzzle. The program must fill (and print) a solution array with the words in the position and direction in which they were found, as shown below for the example puzzle.

The global variables to be used and the main function are as follows:

// Global data members

public static char[ , ] puzzle = new char[ Constants.maxN, Constants.maxM ],   // puzzle array
                        solution = new char[ Constants.maxN, Constants.maxM ]; // solution array

public static int n,       // actual number of rows in puzzle and solution arrays
                  m,       // actual number of columns in puzzle and solutionn arrays
                  max_n_m, // number of elements in main diagonals of puzzle and solutionn arrays
                  wordFP;  // fingerprint of a word (pattern)

static void Main( string[] args )
{
   FileStream fs = null;
   StreamReader sr = null;
   string word;

   if ( LoadPuzzle() )
   {
      ShowPuzzle();

      try
      {
         fs = new FileStream( Constants.wordsFile, FileMode.Open );
         sr = new StreamReader( fs );

         while ( ( word = sr.ReadLine() ) != null )
         {
            FindWord( word, puzzle );
         }
         sr.Close();
         fs.Close();

         ShowSolution();
      }
      catch ( Exception exc )
      {
         Console.WriteLine( exc.Message );
      }
      finally
      {
         if ( sr != null )
         {
            sr.Close();
         }
         if ( fs != null )
         {
            fs.Close();
         }
      }
   }
}

The trivial auxiliary functions are defined as follows:

  static bool LoadPuzzle()
  {
     bool ok = false;
     FileStream fs = null;
     StreamReader sr = null;
     string line;

     try
     {
        fs = new FileStream( Constants.puzzleFile, FileMode.Open );
        sr = new StreamReader( fs );

        n = m = 0;

        while ( ( line = sr.ReadLine() ) != null )
        {
           int len = line.Length;

           if ( m == 0 )
           {
              m = len - ( len >> 1 );
           }
           for ( int j = 0, k = 0; j < len; j += 2, ++k )
           {
              puzzle[ n, k ] = line[ j ];
           }
           ++n;
        }
        max_n_m = n < m ? m : n;
        sr.Close();
        fs.Close();
        ok = true;
     }
     catch ( Exception exc )
     {
        Console.WriteLine( exc.Message );
     }
     finally
     {
        if ( sr != null )
        {
           sr.Close();
        }
        if ( fs != null )
        {
           fs.Close();
        }
     }
     return ok;
  }

  static void ShowPuzzle()
  {
     Console.WriteLine( String.Format( "\nPuzzle array ({0} x {1}):\n", n, m ) );

     for ( int i = 0; i < n; ++i )
     {
        for ( int j = 0; j < m; ++j )
        {
           Console.Write( String.Format( "{0} ", puzzle[ i, j ] ) );
           solution[ i, j ] = ' ';
        }
        Console.WriteLine();
     }
     Console.WriteLine();
  }

  static void ShowSolution()
  {
     Console.WriteLine( String.Format( "\nSolution ({0} x {1}):\n", n, m ) );

     for ( int i = 0; i < n; ++i )
     {
        for ( int j = 0; j < m; ++j )
        {
           Console.Write( String.Format( "{0} ", solution[ i, j ] ) );
           solution[ i, j ] = ' ';
        }
        Console.WriteLine();
     }
     Console.WriteLine();
  }
}

To find a word, conduct a search in the horizontal, vertical, and diagonal directions, stopping the search when the word is found in any direction. The diagonal directions involve a search either in the southeast (upper-left corner to lower-right corner) or in the southwest (upper-right corner to lower-left corner) directions.

static void FindWord( string word, char[ , ] puzzle )
{
   int wordLenght = word.Length;

   wordFP = WordFingerprint( word, wordLenght );

   Console.Write( String.Format( "Searching for '{0,12}', fingerprint == {1,6}",
                                 word, wordFP ) );

   if ( !( HorizontalKRsearch( word, wordLenght )
           ||
           VerticalKRsearch( word, wordLenght )
           ||
           SouthEastKRsearch( word, wordLenght )
           ||
           SouthWestKRsearch( word, wordLenght ) ) )
   {
      Console.Write( " not" );
   }
   Console.WriteLine( " found" );
}

Function WordFingerprint implements the variation on the Karp-Rabin fingerprinting algorithm.

static int WordFingerprint( string word, int wordLength )
{
   int sum = 0;

   for ( int i = 0; i < wordLength; ++i )
   {
      sum += (int)( word[ i ] );
   }
   return sum;
}

The implementation of functions HorizontalKRsearch, VerticalKRsearch, SouthEastKRsearch, and SouthWestKRsearch rely on adaptations of the basic KarpRabinSearch function to perform searches over a two-dimensional array.

Since the fingerprint of a word is the same whether it occurs forward or backward in the puzzle, it is convenient to define a class to enable the search functions to return the position of the puzzle array at which a word was found, and the word’s direction.

public enum Direction { forward, backward }; // Direction to fill a word in the solution

public class FillInfo
{
   public int position;        // Position to start filling a word
   public Direction direction; // Fill direction

   public FillInfo( int _position, Direction _direction )
   {
      position = _position;
      direction = _direction;
   }
}

The following figure shows typical searches in the vertical (column 3) and horizontal (row 1) directions.

The computation of the initial fingerprint of the target and the actual search in these directions can be done in the same way. To reach the next character in the horizontal direction an increment of 1 is needed, while for the vertical direction an increment of maxM is needed. Functions HorizontalKRsearch, VerticalKRsearch, HorizontalOrVerticalKRsearch, and HorizontalOrVerticalFingerprint are defined as follows:

static bool HorizontalKRsearch( string word, int wordLength )
{
   int i;
   FillInfo fillInfo;

   unsafe
   {
      for ( i = 0; i < n; ++i )
      {
         fixed ( char* puzzleRow = &puzzle[ i, 0 ], solutionRow = &solution[ i, 0 ] )
         {
            if ( HorizontalOrVerticalKRsearch( word,
                                               puzzleRow,
                                               wordLength,
                                               m,
                                               1,
                                               out fillInfo ) )
            {
               HorizontalOrVerticalFillWord( solutionRow, word, wordLength, 1, fillInfo );
               break;
            }
         }
      }
   }
   return i < n;
}

static bool VerticalKRsearch( string word, int wordLength )
{
   int j;
   FillInfo fillInfo;

   unsafe
   {
      for ( j = 0; j < m; ++j )
      {
         fixed ( char* puzzleCol = &puzzle[ 0, j ], solutionCol = &solution[ 0, j ] )
         {
            if ( HorizontalOrVerticalKRsearch( word,
                                               puzzleCol,
                                               wordLength,
                                               n,
                                               Constants.maxM,
                                               out fillInfo ) )
            {
               HorizontalOrVerticalFillWord( solutionCol, word, wordLength, Constants.maxM,
                                             fillInfo );
               break;
            }
         }
      }
   }
   return j < m;
}

unsafe static bool HorizontalOrVerticalKRsearch( string pattern,
                                                 char* target,
                                                 int patternLenght,
                                                 int targetLength,
                                                 int displacement,
                                                 out FillInfo fillInfo )
{
   int i, j, k, targetFP,
       patternMaxIndex = patternLenght * displacement,
       targetMaxIndex = ( targetLength - patternLenght ) * displacement;

   fillInfo = null;
   targetFP = HorizontalOrVerticalFingerprint( target, 0, patternMaxIndex, displacement );

   for ( i = 0; i <= targetMaxIndex; i += displacement )
   {
      if ( wordFP == targetFP )
      {
         // Must check for an exact match either in the forward or in the backward direction.
         // Even though the word (or pattern) 'alpha' has the same fingerprint as the target
         // 'aplah', they DO NOT match because of the scrambling of characters in the target.

         for ( j = 0, k = i; j < patternLenght; ++j, k += displacement ) // forward match
         {
            if ( pattern[ j ] != target[ k ] ) // no match
               break;
         }
         if ( j == patternLenght ) // match
         {
            fillInfo = new FillInfo( i, Direction.forward );
            return true;
         }
         else
         {
            for ( j = patternLenght - 1, k = i; j >= 0; --j, k += displacement ) // backward match
            {
               if ( pattern[ j ] != target[ k ] ) // no match
                  break;
            }
            if ( j == -1 ) // match
            {
               fillInfo = new FillInfo( i, Direction.backward );
               return true;
            }
         }
      }
      else // "slide" the pattern over the target by one position and
           // adjust the target's fingerprint
      {
         targetFP += target[ i + patternMaxIndex ] - target[ i ];
      }
   }
   return false;
}

unsafe static int HorizontalOrVerticalFingerprint( char* puzzleStr, int start, int length,
                                                   int displacement )
{
   int sum = 0;

   for ( int j = start; j < length; j += displacement )
   {
      sum += puzzleStr[ j ];
   }
   return sum;
}

Filling a word in the solution depends on whether it was found forward or backward in the vertical or horizontal direction. This is taken care of by function HorizontalOrVerticalFillWord.

unsafe static void HorizontalOrVerticalFillWord( char* solutionStr, string word, int wordLen,
                                                 int displacement, FillInfo fillInfo )
{
   int i, j = fillInfo.position;

   if ( fillInfo.direction == Direction.forward )
   {
      for ( i = 0; i < wordLen; ++i )
      {
         solutionStr[ j ] = word[ i ];
         j += displacement;
      }
   }
   else // fillInfo.direction == Direction.backward
   {
      for ( i = wordLen - 1; i >= 0; --i )
      {
         solutionStr[ j ] = word[ i ];
         j += displacement;
      }
   }
}

Searches along the diagonals are performed in a similar way. The following figure shows typical searches:

In the southeast direction, the increment must be maxM + 1 to reach the next character, while in the southwest direction, the increment must be maxM – 1. Because all functions use upper bounds for the indices, it is not a good idea to conduct searches in the north-east direction.

The functions to compute the initial fingerprint, and to search in the diagonal directions are defined below:

unsafe static bool DiagonalKRsearch( string pattern, char* target,
                                     int patternLenght, int targetLength, int displacement,
                                     out FillInfo fillInfo )
{
   int i, j, k, targetFP,
       patternMaxIndex = patternLenght * ( displacement + 1 ),
       targetMaxIndex = ( targetLength - patternLenght ) * ( displacement + 1 );

   fillInfo = null;
   targetFP = DiagonalFingerprint( target, 0, patternMaxIndex, displacement );

   for ( i = 0; i <= targetMaxIndex; i += displacement + 1 )
   {
      if ( wordFP == targetFP )
      {
         // Must check for an exact match either in the forward or in the backward direction.
         // Even though the word (or pattern) 'alpha' has the same fingerprint as the target
         // 'aplah', they DO NOT match because of the scrambling of characters in the target.

         for ( j = 0, k = i; j < patternLenght; ++j, k += displacement + 1 ) // forward match
         {
            if ( pattern[ j ] != target[ k ] ) // no match
               break;
         }
         if ( j == patternLenght ) // match
         {
            fillInfo = new FillInfo( i, Direction.forward );
            return true;
         }
         else
         {
            for ( j = patternLenght - 1, k = i; j >= 0; --j,
                 k += displacement + 1 ) // backward match
            {
               if ( pattern[ j ] != target[ k ] ) // no match
                  break;
            }
            if ( j == -1 ) // match
            {
               fillInfo = new FillInfo( i, Direction.backward );
               return true;
            }
         }
      }
      else // "slide" the pattern over the target by one position
          // and adjust the target's fingerprint
      {
         targetFP += target[ i + patternMaxIndex ] - target[ i ];
      }
   }
   return false;
}

unsafe static int DiagonalFingerprint( char* puzzleStr, int start, int length, int displacement )
{
   int sum = 0;

   for ( int j = start; j < length; j += displacement + 1 )
   {
      sum += puzzleStr[ j ];
   }
   return sum;
}

The function to fill words in the diagonal directions is similar to the one to fill words in the horizontal and vertical directions.

unsafe static void DiagonalFillWord( char* solutionStr, string word, int wordLen,
                                  int displacement, FillInfo fillInfo )
{
   int i, j = fillInfo.position;

   if ( fillInfo.direction == Direction.forward )
   {
      for ( i = 0; i < wordLen; ++i )
      {
         solutionStr[ j ] = word[ i ];
         j += displacement + 1;
      }
   }
   else // fillInfo.direction == Direction.backward
   {
      for ( i = wordLen - 1; i >= 0; --i )
      {
         solutionStr[ j ] = word[ i ];
         j += displacement + 1;
      }
   }
}

To find a word in the diagonals, start at the main diagonals, and search for as long as a diagonal contains at least as many characters as the word being sought.

static bool SouthEastKRsearch( string word, int wordLength )
{
   int i, targetLength = max_n_m;
   bool found = false;
   FillInfo fillInfo;

   unsafe
   {
      for ( i = 0; wordLength <= targetLength; ++i )
      {
         fixed ( char* puzzleRowDiagStart = &puzzle[ i, 0 ],
                       solutionRowDiagStart = &solution[ i, 0 ] )
         {
            if ( DiagonalKRsearch( word, puzzleRowDiagStart,
                                   wordLength, targetLength, Constants.maxM, out fillInfo ) )
            {
               found = true;
               DiagonalFillWord( solutionRowDiagStart, word,
                                wordLength, Constants.maxM, fillInfo );
               break;
            }
            --targetLength;
         }
      }
      if ( targetLength < wordLength )
      {
         targetLength = max_n_m - 1;
         for ( i = 1; wordLength <= targetLength; ++i )
         {
            fixed ( char* puzzleColDiagStart = &puzzle[ 0, i ],
                      solutionColDiagStart = &solution[ 0, i ] )
            {
               if ( DiagonalKRsearch( word, puzzleColDiagStart,
                                      wordLength, targetLength, Constants.maxM, out fillInfo ) )
               {
                  found = true;
                  DiagonalFillWord( solutionColDiagStart, word, wordLength,
                                   Constants.maxM, fillInfo );
                  break;
               }
               --targetLength;
            }
         }
      }
   }
   return found;
}

static bool SouthWestKRsearch( string word, int wordLength )
{
   int i, targetLength = max_n_m;
   bool found = false;
   FillInfo fillInfo;

   unsafe
   {
      for ( i = m - 1; wordLength <= targetLength; --i )
      {
         fixed ( char* puzzleRowDiagStart = &puzzle[ 0, i ],
                   solutionRowDiagStart = &solution[ 0, i ] )
         {
            if ( DiagonalKRsearch( word,
                                   puzzleRowDiagStart,
                                   wordLength,
                                   targetLength,
                                   Constants.maxM - 2,
                                   out fillInfo ) )
            {
               found = true;
               DiagonalFillWord( solutionRowDiagStart, word,
                        wordLength, Constants.maxM - 2, fillInfo );
               break;
            }
            --targetLength;
         }
      }
      if ( targetLength < wordLength )
      {
         targetLength = max_n_m - 1;
         for ( i = 1; wordLength <= targetLength; ++i )
         {
            fixed ( char* puzzleColDiagStart = &puzzle[ i, m - 1 ],
                    solutionColDiagStart = &solution[ i, m - 1 ] )
            {
               if ( DiagonalKRsearch( word,
                                      puzzleColDiagStart,
                                      wordLength,
                                      targetLength,
                                      Constants.maxM - 2,
                                      out fillInfo ) )
               {
                  found = true;
                  DiagonalFillWord( solutionColDiagStart, word,
                                   wordLength, Constants.maxM - 2, fillInfo );
                  break;
               }
               --targetLength;
            }
         }
      }
   }
   return found;
}

Execution of the Code

When built as a console application with unsafe code enabled, the code in this article produces the following output (shown in three images):

Enabling Unsafe Code

To enable the execution of unsafe code in the .NET framework, right-click on the bold name of the project, such as the following:

Select Properties, and check the box labeled Allow unsafe code.