PVN - The CrossWord Puzzle Generator Technical Page

Technical Details

CrossWords Application Development


Development Platform: NetBeans v7.3
Language: JavaFX v2.2 (Oracle Corporation)
UI Layout: JavaFX Scene Builder v1.0 (Oracle Corporation)
Packaging/Deployment: Launch4j v3.1 (SourceForge.net)


CrossWords consists of three application packages, built on a Model-View-Controller architectural design pattern, as described in the following sections.
  • The MODEL package: cwstore manages the data stores, and provides access to the dictionary word files.
  • The VIEW package: crosswords defines the application user interface, and handles all user interactions, events, and controls.
  • The CONTROLLER package: cwpuzzle provides the "business logic", and classes for performing all puzzle operations.

Package cwstore (the Model)

The DictionaryServices interface class defines the public methods for accessing words in a Dictionary, which is an external file that contains a set of valid words in a format that is known by the implementation of the interface.

The DictionaryAccess class is designed as a Facade to public methods of the classes that implement DictionaryServices. Methods in the DictionaryAccess class establish the access order for a Custom and/or a Standard Dictionary, based on the user's specifications at puzzle initialization. In general, if a valid CustomDictionary is specified, it is searched first, followed by the default StandardDictionary. This class also controls the capability to restrict a search to only a CustomDictionary.

I have implemented three instances of classes that utilize DictionaryServices:

  • The SingleWordRecordFile class provides access to a text file of dictionary words used in solving the puzzle. SingleWordRecordFile extends the Java RandomAccessFile (RAF) class. It exposes methods that treat the underlying RAF as a record-oriented file. Words in the file are listed one to a line (record) and are ordered first by size, then alphabetically, beginning with all valid two-letter words, and continuing through all words of maximum size.

    The MerriamWebsterDictionary class makes use of the SingleWordRecordFile class.

  • The RandomDictionaryWordsFile class provides access to a text file of dictionary words used in solving the puzzle. RandomDictionaryWordsFile extends the Java RandomAccessFile class. It exposes methods that treat the underlying RAF as a record-oriented file. Words in the file are listed one to a line (record) and are unordered, both alphabetically and in length. Only the first word in each line is considered; a word is the first n alphabetic characters in a line of text. The remainder of the text (to end-of-line) may contain anything at all. A word may be all lower or upper case, or begin with a capital letter; it is always processed as a CAPITALIZED word. This construct allows for processing a text file consisting of words along with their definitions.

    Files utilized by the RandomDictionaryWordsFile class are not intended to include a comprehensive dictionary, since there is naturally more processing overhead in a file that is not alphabetized and in random-length order. This type of file is useful for defining a rather small set of specialty words (preferably less than 1,000 records); for example medical terms, proper names, etc that are not found in the standard dictionary files supplied with the puzzle. A RandomDictionaryWordsFile may be built to contain dictionary "words" consisting of multiple conjoined words such as are typically found in larger puzzle grids. Some examples:

    • Arenatheater - a theater arranged with seats around at least three sides of the stage.
    • armsrace - a competition between nations to have the most powerful armaments.
    • inthebuff: naked; without clothing.

    The CustomDictionary class makes use of the RandomDictionaryWordsFile class.

  • The SpreadsheetDictionary class provides access to words in an Excel-type spreadsheet, including services for reading words, identifying candidate words that meet specified constraints (word length, word mask), and providing a "best fit" for a given constraint set. This class utilizes the Apache Portable OLE Interface (POI) library. POI imports include:
    • org.apache.poi.poifs.filesystem.POIFSFileSystem
    • org.apache.poi.hssf.usermodel.HSSFWorkbook
    • org.apache.poi.hssf.usermodel.HSSFSheet
    • org.apache.poi.hssf.usermodel.HSSFRow
    • org.apache.poi.hssf.usermodel.HSSFCell

    The format of the spreadsheet must adhere to the following rules:

    • Each column contains words of a given size: First column contains two-letter words, second column contains three-letter words, etc.
    • Words in each column are ordered alphabetically.
    • The second row of the spreadsheet contains the total number of words in each column.

Package crosswords (the View)

The CrossWords main program extends the Application class, which launches the Application thread. There are no input arguments:

    public static void main(String[] args) {
        Application.launch(CrossWords.class, args);
    }

The start routine overrides the Application superclass method:

    @Override
    public void start(Stage stage) throws Exception {
        Parent root = FXMLLoader.load(getClass().getResource("CrossWordsUI.fxml"));
        
        Scene scene = new Scene(root, Color.LIGHTGREY);
        stage.setTitle("Crossword Puzzle Generator");
        stage.setResizable(false);
        String css = this.getClass().getResource("CWPuzzle.css").toExternalForm();
        scene.getStylesheets().add(css);
        stage.setScene(scene);
        stage.show();
    }

All elements of the CrossWords User Interface are built on a single main "Window", or Stage in JavaFX terminology.

  • The CrossWordsUI class is the main user interface (UI) class for the CrossWords Puzzle Generator. I used SceneBuilder to layout all of the visual components of the application. SceneBuilder generates an FXML file which is accessed by the JavaFX Application thread to construct a window. The small cell containing the letter A and clue number in the upper left of the layout is a template for defining the puzzle grid. The template cell is removed after it is used for the layout.

    CrossWords application main window in SceneBuilder

    (Note: Hover over the image to expand it)

    CrossWordsUI instantiates all the UI elements (referenced or not), using the construct @FXML [object-type] [object-name], initializes all element data, generates the puzzle grid, displays the initial puzzle solution attempt, and subsequent update attempts, and handles all user interactions (puzzle cell character entries, movements, and button selections) and displays hints and result information.

  • The SolvePuzzleService is an implementation of the JavaFX Service interface. It performs the initial solution attempts running on a background thread, reporting its progress to the UI. The service is instantiated as an inner class in CrossWordsUI.
  • The UpdatePuzzleService is an implementation of the JavaFX Service interface. It performs the update solution attempts running on a background thread, reporting its progress to the UI. The service is instantiated as an inner class in CrossWordsUI.
  • The CustomDictionaryFileManager class provides the dialog and infrastructure to select, maintain, and reference the CUSTOM DICTIONARY file. This class takes advantage of the JavaFX FileChooser class to let the user specify the file system path to the Custom Dictionary.
  • The Square13PreFills class defines a set of pre-filled 13x13 CrossWord puzzle layouts. Similar classes are built for the 15x15, 17x17, 19x19, and 21x21 puzzle layouts. They define a grid layout in terms of a matrix of {0, 1} values, where 0 indicates a white square and 1 a black square. These classes are strictly workarounds; a better approach is to maintain puzzle grids in source files. A future version will provide the capability to define, access, and load grid layouts from the user's local file system.
  • The CWPuzzle.css file contains all Cascading Style Sheets data for styling the UI features.

Package cwpuzzle (the Controller)

Classes in cwpuzzle include:
  • The PuzzleOps class provides methods for performing puzzle operations, for initializing the puzzle, and making the initial puzzle solution attempt. The bulk of the algorithmic code is provided in several methods in this class, as documented in the Javadoc, below.
  • The IterationOps class provides methods for iterating the puzzle words towards a complete solution.
  • The PuzzleState class maintains original information about the Puzzle that changes or evolves during the iterative update phase, and needs to be restored or reset under various circumstances. Specific information includes the ArrayList PuzzleWords and ArrayList squares.
  • The Square class defines the properties of the contents of a single Crossword Puzzle square, as well as its location properties, and provides getter/setter methods to access and control these properties.
  • The Word class defines the properties of a single word in the Crossword Puzzle, and provides getter/setter methods for saving and retrieving a word and its associated properties.

Application Documentation

A complete set of JavaDoc web pages for CrossWords is located here. The documentation includes class descriptors, public and private method descriptors and signatures, and instance declarations.

To-Do List

Bugs and Annoyances

There are a number of issues that need investigation, including:

  • I'm still trying to tune the update algorithms to function optimally. This is a challenging task! Every change (even to a single short word) ripples through the puzzle, and typically results in additional invalid words, resulting in a lower score. The CrossWord Puzzle Generator discards these solutions, of course. Also, the dictionary search may only find a limited number of valid words (candidates) that meet the puzzle constraints, resulting in repetition in the puzzle iterations. I've implemented various techniques to overcome these limitations, but they don't always work as well as they could. I don't have any theoretical guidance here, I've played around with various combinations of things to discover what works best, and so this is a work in progress!
  • The CrossWord Puzzle Generator has even more difficulty in achieving modest success in the update process with larger puzzle grids (17, 19, and 21 square). Of course, the more words you enter (and therefore fix), the easier time the generator has. But to date I haven't successfully generated a puzzle without major intervention.
  • There seem to be issues with the icon spinner functionality (starting and stopping). I haven't explored why this is the case, it is possibly a JavaFX problem; as a workaround I make the spinner invisible when it's supposed to be stopped.

Improvements

Likewise, there are a number of improvements I'd like to make for the next version:

  • The source dictionary cannot be changed; ideally any word source that conforms to the format used to search and read words should be able to be used.
  • I don't perform any verification of the format of the Custom Dictionary. I presume it to be a text file conforming to the conventions listed above. I need to make use of some of the methods for restricting file types, etc that the FileChooser class provides.
  • There are only a couple of "random" grids for each puzzle size, and these are all loaded in memory at startup. It would be more efficient to maintain grids in a file and load one at random when requested.
  • It would then be easy (and useful) to be able to save a puzzle layout on the local file system, and be able to recall it.
  • Best practice is to use Resource Bundles to maintain UI text data; as it is all text is hard-coded.