MsFit

MsFit is a crossword construction tool.

Warning: MsFit is currently undergoing organizational changes, and changes to the fill algorithm. To try a tentative version of the softwrae, run cmake and make inside the test directory, to build an executable msfit-test.

Getting started

git clone --recursive https://github.com/nzfeng/MsFit

Dependencies

Installing gtkmm4 on Mac is as simple as

brew install gtkmm4

This page was helpful in getting gtkmm to compile with CMake. This StackOverflow answer was also helpful.

gtkmm documentation is here. Better documentation (more up-to-date with gtkmm4) is here.

Interface controls

• Shift-P: Toggle pencil.

Grid crossword

Controls for navigating a grid crossword:

• Space: Toggle across/down.
• Tab: Skip to the next open square in the next uncompleted word.
• Esc: Enter more than one letter in a box.
• Arrow keys: move one box in the corrresponding direction (skipping black squares)

For any box in the grid, black or white:

• Right-click: Toggle black/white.

Organization

• The interface directory contains code that pertains purely to building the GUI to the screen. Specifically, this means building and laying out the container widgets for the panels, menus, etc. However, objects in the puzzle directory still have their own functions defining how they are rendered. I don't envision there being enough demand for flexibility & precise control of rendering crossword puzzles that it calls for de-coupling the core puzzle engine from rendering (at least not yet.)
• The puzzle directory contains code for the PuzzleGrid object, which represents an ordinary crossword puzzle grid. There is also the PuzzleGraph object, which is used when the puzzle has non-square cells and thus requires more navigation overhead. Basically, a PuzzleGraph is represented as a graph that can be traversed a manner similar to a halfedge mesh (the cells being faces.)
• A PuzzleGrid is represented as single Gtk::DrawingArea, rather than as a Gtk::Grid comprised of many individual widgets representing the squares. I figured that although I would have to write many functions myself relating to square selection, etc., at least I would be able to exactly control how mouse/key commands behave, and how the grid is rendered, rather than having to deal with dozens of widgets and the interaction between their signal handlers.
• The engine directory contains code that helps the user fill the puzzle.
• The utilities directory contains generally useful functions, like ones to assist in drawing things to screen.

Datasets

MsFit comes with my own manually curated dataset: https://github.com/nzfeng/crossword-dataset

TODO

• Export .puz file format
• Support other major crossword types, such as British style, Japanese style, diagramless, etc.
• Cell shapes besides squares (mainly hexagons)
• 3D crosswords not on my to-do list anytime soon, since I think crosswords are meant to be 2D where they can be played on a piece of paper.
• Make crossword area scrollable, in case the grid is too large to be displayed in its entirety.
• Maybe switch from GTK to Qt, which has better cross-platform support, and platform-specific UI.
• Co-optimize both the grid and fill quality (I belive this is very hard)

• Automatically show "illegal" grids, i.e. 2-letter words, cells shared by only one word, etc. (can toggle this option)
• Automatically detect duplicate entries. Also have option to display repeated substrings.
• Keyboard shortcuts for everything.
• Options to sort fill list: Alphabetical, search bar, order by average # of fills for all crossing words.
• For "get most constrained" option: implement a variant of k-ply lookahead; i.e. pick the entry that has the fewest fill options (that allow at least 1 fill for all crossing words) after removing fills that result in 0 fills if chosen. I.e. attempting to prune dead-end sub-trees. k should balance accuracy vs. computation time per evaluation.
• Novelty puzzles
  • Other tilings
  • Tilings of surfaces
  • Mobius band (need symmetric letters)
  • I liked this puzzle: https://crosshare.org/crosswords/oC5KN16iBGMncNxU4ie5/2x3x4-3. TODO: Option for multiple chars per cell (i.e. use .* in regex.)
  • Polyhedral Patterns

Limitations

• Only English is supported.

Credits

Software engineering-wise, I took organizational inspiration from Geometry Central and Polyscope.