javaalgorithmbacktrackingbrute-force

Writing a program that solves crosswords efficiently

I have a crossword puzzle and a list of words which can be used to solve it (words can be placed multiple times or not even once). There is always a solution for the given crossword and word list.

I searched for clues on how to solve this problem and found out that it is NP-Complete. My maximal crossword size is 250 by 250, the maximal length of the list (amount of words which can be used to solve it) is 200. My goal is to solve crosswords of this size by brute force/backtracking, which should be possible within a few seconds (this is a rough estimation by me, correct me if I am wrong).

For example:

A list of given words which can be used to solve the crossword:

The given empty crossword (X are fields which cannot be filled out, the empty fields need to be filled):

An empty crossword which needs to be solved

The solution:

The solution of the problem above

Now my current approach is to represent the crossword as a 2-D array and search for empty spaces (2 iterations over the crossword). Then I match words to empty spaces depending on their length, then I try all combinations of words to empty spaces which have the same length. This approach got very messy very fast, I got lost trying to implement this, is there a more elegant solution?

Solution

  • The basic idea you have is pretty sensible:

    1. Identify slots on the board.
    2. Try each slot with each word that fits.
    3. If every slots can be filled without conflict, it is solved.

    It's an excellent plan. The next step is to translate it into a design. For small program like this we can go straight to pseudo code. The gist of it, as explained by other answers, is recursion:

    1  Draw a slot from the slot pool.
2     If slot pool is empty (all slots filled), stop solving.
3  For each word with correct length:
4     If part of the slot is filled, check conflict.
5        If the word does not fit, continue the loop to next word.
      // No conflict
6     Fill the slot with the word.
      // Try next slot (down a level)
7     Recur from step 1.
8     If the recur found no solution, revert (take the word back) and try next.
   // None of them works
9  If no words yield a solution, an upper level need to try another word.
   Revert (put the slot back) and go back.

    Below is a short but complete example that I cooked up from your requirements.

    There is more than one way to skin a cat. My code swapped step 1 and 2, and combines step 4 to 6 in one fill loop.

    Key points:

    Source:

    import java.awt.Point;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Supplier;
import java.util.stream.Stream;

public class Crossword {

   public static void main ( String[] args ) {
      new Crossword( Arrays.asList( "5 4 4\n#_#_#\n_____\n#_##_\n#_##_\ntuna\nmusic\ncan\nhi".split( "\n" ) ) );
      new Crossword( Arrays.asList( "6 6 4\n##_###\n#____#\n___#__\n#_##_#\n#____#\n##_###\nnice\npain\npal\nid".split( "\n" ) ) );
   }

   private final int height, width; // Board size
   private final char[] board; // Current board state.  _ is unfilled.  # is blocked.  other characters are filled.
   private final Set<String> words; // List of words
   private final Map<Point, Integer> vertical = new HashMap<>(), horizontal = new HashMap<>();  // Vertical and horizontal slots

   private String indent = ""; // For formatting log
   private void log ( String message, Object... args ) { System.out.println( indent + String.format( message, args ) ); }

   private Crossword ( List<String> lines ) {
      // Parse input data
      final int[] sizes = Stream.of( lines.get(0).split( "\\s+" ) ).mapToInt( Integer::parseInt ).toArray();
      width = sizes[0];  height = sizes[1];
      board = String.join( "", lines.subList( 1, height+1 ) ).toCharArray();
      words = new HashSet<>( lines.subList( height+1, lines.size() ) );
      // Find horizontal slots then vertical slots
      for ( int y = 0, size ; y < height ; y++ )
         for ( int x = 0 ; x < width-1 ; x++ )
            if ( isSpace( x, y ) && isSpace( x+1, y ) ) {
               for ( size = 2 ; x+size < width && isSpace( x+size, y ) ; size++ ); // Find slot size
               horizontal.put( new Point( x, y ), size );
               x += size; // Skip past this horizontal slot
            }
      for ( int x = 0, size ; x < width ; x++ )
         for ( int y = 0 ; y < height-1 ; y++ )
            if ( isSpace( x, y ) && isSpace( x, y+1 ) ) {
               for ( size = 2 ; y+size < height && isSpace( x, y+size ) ; size++ ); // Find slot size
               vertical.put( new Point( x, y ), size );
               y += size; // Skip past this vertical slot
            }
      log( "A " + width + "x" + height + " board, " + vertical.size() + " vertical, " + horizontal.size() + " horizontal." );
      // Solve the crossword, horizontal first then vertical
      final boolean solved = solveHorizontal();
      // Show board, either fully filled or totally empty.
      for ( int i = 0 ; i < board.length ; i++ ) {
         if ( i % width == 0 ) System.out.println();
         System.out.print( board[i] );
      }
      System.out.println( solved ? "\n" : "\nNo solution found\n" );
   }

   // Helper functions to check or set board cell
   private char get ( int x, int y ) { return board[ y * width + x ]; }
   private void set ( int x, int y, char character ) { board[ y * width + x ] = character; }
   private boolean isSpace ( int x, int y ) { return get( x, y ) == '_'; }

   // Fit all horizontal slots, when success move to solve vertical.
   private boolean solveHorizontal () {
      return solve( horizontal, this::fitHorizontal, "horizontally", this::solveVertical );
   }
   // Fit all vertical slots, report success when done
   private boolean solveVertical () {
      return solve( vertical, this::fitVertical, "vertically", () -> true );
   }

   // Recur each slot, try every word in a loop.  When all slots of this kind are filled successfully, run next stage.
   private boolean solve ( Map<Point, Integer> slot, BiFunction<Point, String, Boolean> fill, String dir, Supplier<Boolean> next ) {
      if ( slot.isEmpty() ) return next.get(); // If finished, move to next stage.
      final Point pos = slot.keySet().iterator().next();
      final int size = slot.remove( pos );
      final char[] state = board.clone();
      /* Try each word */                                                   indent += "  ";
      for ( String word : words ) {
         if ( word.length() != size ) continue;
         /* If the word fit, recur. If recur success, done! */              log( "Trying %s %s at %d,%d", word, dir, pos.x, pos.y );
         if ( fill.apply( pos, word ) && solve( slot, fill, dir, next ) )
            return true;
         /* Doesn't match. Restore board and try next word */               log( "%s failed %s at %d,%d", word, dir, pos.x, pos.y );
         System.arraycopy( state, 0, board, 0, board.length );
      }
      /* No match.  Restore slot and report failure */                      indent = indent.substring( 0, indent.length() - 2 );
      slot.put( pos, size );
      return false;
   }

   // Try fit a word to a slot.  Return false if there is a conflict.
   private boolean fitHorizontal ( Point pos, String word ) {
      final int x = pos.x, y = pos.y;
      for ( int i = 0 ; i < word.length() ; i++ ) {
         if ( ! isSpace( x+i, y ) && get( x+i, y ) != word.charAt( i ) ) return false; // Conflict
         set( x+i, y, word.charAt( i ) );
      }
      return true;
   }
   private boolean fitVertical ( Point pos, String word ) {
      final int x = pos.x, y = pos.y;
      for ( int i = 0 ; i < word.length() ; i++ ) {
         if ( ! isSpace( x, y+i ) && get( x, y+i ) != word.charAt( i ) ) return false; // Conflict
         set( x, y+i, word.charAt( i ) );
      }
      return true;
   }
}

    Exercise: You can rewrite recursion to iteration; faster and can support bigger boards. Once that's done it can be converted to multi-thread and run even faster.