1 of 53

GNOME Crosswords

Jonathan Blandford <jrb@gnome.org>

https://gitlab.gnome.org/jrb/crosswords

http://libipuz.org/

year three

2 of 53

Agenda

Crosswords�
Writing Crosswords�
Writing Crossword Writers

3 of 53

Part 1

Crosswords

4 of 53

What is GNOME Crosswords?

GNOME Crosswords is two things: A standalone crossword game for solving crosswords, and a separate authoring tool for writing puzzles

Started 3.5 years ago:

I'm a passionate crossword enthusiast, and wanted to try my hand at setting crosswords.

Started doing Times of London crosswords as a kid with my parents and grandparents
Now I do them with my family!�

I needed a new hobby and Linux needed a good crossword app. I also wanted to write code again.�
I had a vision in my head as to what a good crossword authoring tool could look like

5 of 53

6 of 53

What is GNOME Crosswords?

Code base is currently pushing ~80 kloc.

Mostly written in C. Some python as well. We are slowly rewriting the core in Rust
22k words worth of design docs as well�

Translations in four languages, and would love to see this number grow�
We've had 28 different contributors over time��

Special thanks to Federico, Tanmay, Davide, Philip, �and Pranjal who help me maintain this!

So, what is GNOME Crosswords?

- It's two separate programs. First, it's a standalone game that lets you solve crosswords for fun

- Second, it's a separate editor that lets one write and edit crosswords

I started this almost exactly three years ago. For my entire life, I've loved doing crosswords, and wanted to try my hand at writing some. The pandemic was starting to wind down a little, and I was looking for a new hobby beyond baking sourdough. This seemed like an interesting little project.

Fast forward three years, and it's not so little anymore. The code base is now pushing 50kloc. It's mostly in C, with some python, and, we are rewriting portions of the core in rust

We have translations in four languages, and I'd love to see more, so if you can help with this I'd love to hear from you.

And it's grown into a robust Open source project. We have had 28 different contributors over time, and I especially appreciate those listed who help me maintain this

7 of 53

What is GNOME Crosswords?

Code base split between an internal library — libipuz — and the UI

libipuz loads, saves, and manipulates crossword files�
Supports .ipuz files natively; some support for importing .puz, .jpz, and .xd files�
libipuz has gobject-introspection support:

Near-term goal to publicly support API in C, Rust, Python, and Typescript
gobject-introspection exports to over 25 different bindings�

Supports eight different puzzle kinds�
We are slowly rewriting it in Rust.

Thanks Pranjal and GSoC!

On the implementation side, the code is split between an internal core library and the interface. That internal library, called libipuz, lets you load, save, and especially manipulate crossword files. It supports the ipuz file format natively, and we have some basic support for importing other file formats as well.

Since I'm sure most people are unfamiliar with crossword file formats, the ipuz spec is an open spec built on top of json. Most puzzle file formats are undocumented and proprietary.

libipuz is entirely internal at the moment, but in the medium term I'd like to support it publicly. There are plenty of simple puzzle loading libraries, but I haven't found a good one yet that supports manipulating crosswords like we do. We are in the middle of adding gobject-introspection support to take advantage of all language bindings and documentations support, and I'm targeting a public release by EOY.

Note, we're also migrating libipuz to rust. I love and trust Emmanuele a bunch for json-glib, but we do waay too much string/file manipulation in C for me to be comfortable with C in the long run. Pranjal, my GSoC intern, is doing a fabulous job on that right now.

On the UI front, there's a lot of widgetry shared between the two programs. The editor is probably twice as big code-wise though.

8 of 53

What is GNOME Crosswords?

The UI code base is shared between the Game and Editor

There's a lot of shared widgetry
The editor is a lot more complex�

Written using GTK4 and libadwaita�
Possible to get it running on a Mac

On the implementation side, the code is split between an internal core library and the interface. That internal library, called libipuz, lets you load, save, and especially manipulate crossword files. It supports the ipuz file format natively, and we have some basic support for importing other file formats as well.

Since I'm sure most people are unfamiliar with crossword file formats, the ipuz spec is an open spec built on top of json. Most puzzle file formats are undocumented and proprietary.

libipuz is entirely internal at the moment, but in the medium term I'd like to support it publicly. There are plenty of simple puzzle loading libraries, but I haven't found a good one yet that supports manipulating crosswords like we do. We are in the middle of adding gobject-introspection support to take advantage of all language bindings and documentations support, and I'm targeting a public release by EOY.

Note, we're also migrating libipuz to rust. I love and trust Emmanuele a bunch for json-glib, but we do waay too much string/file manipulation in C for me to be comfortable with C in the long run. Pranjal, my GSoC intern, is doing a fabulous job on that right now.

On the UI front, there's a lot of widgetry shared between the two programs. The editor is probably twice as big code-wise though.

9 of 53

A Visual Tour

The Game

Try it yourself!

Download from flathub

10 of 53

A brief tour — main screen

11 of 53

A brief tour — puzzle selection

12 of 53

A brief tour — standard (American) crosswords

13 of 53

A brief tour — cryptic, rebus, and barred

Cryptic crossword

Standard with rebus

Barred crossword

14 of 53

A brief tour — arroword and Filippine crosswords

Arrowword crossword

Filippine puzzle

15 of 53

A brief tour — acrostic puzzle

Thanks Tanmay and GSoC!

16 of 53

A brief tour — adaptive layout support

Fits on a 300x300 display!

17 of 53

A brief tour — preferences

18 of 53

Part 2

Writing Crosswords

19 of 53

How do you write Crosswords?

Pick a theme (optional)
Create a grid
Write the clues

With standard (American) crosswords, creating a grid is really hard

On the other hand, writing clues is tricky for cryptic crosswords

20 of 53

A fundamental rule of crosswords:

�Every cell needs at least two paths to its answer

Crossword setters use the term unch — short for "unchecked" — to describe when there is only one path to answer a cell.

Unches are to be avoided.

Standard and Cryptic crosswords satisfy this rule in different ways.

Acrostics also have at least two paths.

21 of 53

Standard Crosswords

Every cell has an across and down clue to let you know you have the right answer.

Ⓒircled cells have three paths!

L. A. Times – Jul 3, 2024

UNCH: Avoid this pattern

22 of 53

Standard Crosswords — clues

L. A. Times – Jul 3, 2024

1ac. Beneath

1dn. As many as

Assorted clues:

The answer to 1ac could be UNDER or BELOW

We need to try to solve 1dn to be sure

23 of 53

Standard Crosswords — puzzle theme

L. A. Times – Jul 3, 2024

58ac. Closely knit community that provides social

support, or what 16, 23, 36, and 46 across

contain?

Assorted clues:

FOUNDFAMILY describes the words in circles

24 of 53

Standard Crosswords — tools

To aid creating grids:

Autofill
Word suggestion
Word definitions
Frequency lists
Well-curated word list

L. A. Times – Jul 3, 2024

Items in bold already implemented

25 of 53

Cryptic Crosswords — clues

With cryptics, clues are used to provide redundancy. Every clue has a straight definition and some wordplay.

Times of London – Jun 30, 2024

UNCH: Avoid this pattern

26 of 53

Cryptic Crosswords — clues

Times of London – Jun 30, 2024

3dn. Check the gas pedal (8)

THROTTLE

Assorted clues:

18ac. Leader from Harlech, Wales, appointed (4, 6)

LECH WALESA

https://crypticshewrote.wordpress.com/explanations/

So how do cryptic clues work in practice? I'm going to walk you through a couple of clues and their answers:

First, we are going to look at 3 down. The clue for that is "check the gas pedal", and the answer is throttle. Why is that? I'll give you a few seconds to see if you can see why:

[pause][next]

This type of clue is called a double definition clue. To "THROTTLE" something can mean to check it. It also is a term for the gas pedal in a car. In this instance, we have two paths to the answer. Hopefully that made some sense.

[Next]

Let's look at a second clue:

18 across: Leader from harlech wales, appointed. Note that the (4,6) at the end shows that it's two words, with the first four letters and the second six. And the answer is Lech Walesa. See if you can see why.

[pause briefly][next]

Here's the break down. "Lech Walesa" of course is a leader. He was Leader of the Polish solidarity movement and first president of Poland. But why the second half? What's our second path? Do you see it

[next]

It's in there. The word play is that it's literally from the phrase Harlech Wales, Appointed. This type of clue is called a hidden word clue.

Don't worry if you didn't fully get these. They can be really confusing the first time you encounter them, but they're a lot of fun.

27 of 53

Cryptic Crosswords — tools

To aid writing cryptic clues:

Anagrams
Alternations (odd/even)
Hidden words
Word definitions
Frequency lists
Charades
Common sounds (homophones and spoonerisms)
etc.

Times of London – Jun 30, 2024

Items in bold already implemented

Thanks Pratham and GSoC!

28 of 53

A Visual Tour

The Editor

29 of 53

A brief tour — initial greeter

30 of 53

A brief tour — grid editor

Puzzle writing modes

31 of 53

A brief tour — grid editor: word suggestions

Word list suggestions

32 of 53

A brief tour — grid editor: autofill

Autofill controls

33 of 53

A brief tour — clue editor

Cryptic clue tools:

anagrams and alternations

34 of 53

A brief tour — metadata

35 of 53

Part 3

Writing Crossword Writers

36 of 53

What makes writing a crossword editor hard?

Crosswords render like fonts.

They don't scale linearly; grids and cell positions need pixel-alignment
They fight with GTK's sizing assumptions

Good puzzles follow conventions; great puzzles break them

Rebus clues
Hidden answers/circles
Non-rectangular clues

We need specialized tools to avoid unches

This is a major focus of current development

Small edits can lead to big changes in the puzzle

I wanted to highlight a few things that makes the crossword editor tricky.

First off, rendering crosswords is surprisingly hard. They render a bit like fonts: They don't scale linearly as grid and cell positions need pixel-alignment. They also fight with GTK's sizing assumptions.

Second, we can't put too many assumptions into the code. Good puzzles follow conventions but great puzzles break them. We'd like to support some corner cases

Third, there are a lot of specialized tools to avoid those unches. Each one comes with it's own unique challenges, and honestly, I could do a talk on its own about writing these

Finally, small edits can lead to big changes

I want dive into that last one in a little more detail and show an example, because it really affects the architecture of the editor. Keep this example in mind, as we'll refer to it for the rest of the talk

37 of 53

Example: Small edits can lead to big changes in the puzzle

User presses the '#' key

Change (0,0) to a BLOCK

Numbering is wrong

Symmetry isn't maintained

Enumerations are broken

Initial result

What we want

Clues are different

Styles could be different

Consider a simple grid that a setter is writing. Imagine they press the pound key, which will change the cell at the cursor to a block.

When we make that change to the puzzle, we end up with something like this. But the puzzle is all wrong. We now start at 2across and 2down, which is broken. No crossword should work like that. We broke the symmetry of the puzzle, and any enumerations.

We want something that looks like this, but even then there are changes. The clue for 10 across should now be 9across as we've rerendered, and the clue for 1 across now refers to a word that no longer exists. Styles can be broken as well. So that one key press led to dramatic changes to the structure of the puzzle. It's really important to keep common conventions true when editing a puzzle

And I hope you start to get a sense of how complex working with crosswords can be from this

38 of 53

Writing the Editor:

Design Requirements

Codebase easy to reason about�
Make core operations testable�
Build robust undo and redo into the application�
Tools to avoid Unches need to be fast

39 of 53

Unidirectional data flow architecture

UI event and async callbacks don’t modify the model directly; they generate actions which are value-typed commands�
Update the model based on actions�
View is reconstructed from the model

This approach is highly testable and predictable. Actions and results can be replayed

When I started this application, I planned on doing a somewhat traditional MVC-style architecture, but after a long chat with federico, we decided to experiment with unidirectional data flow architecture. This approach is more common in web frameworks, such as react and angular, but is less common in desktop applications due to our in-process nature. However, it has some really nice properties: Namely, it's highly testable and very predictable.

This architecture is based on an action->model->view approach. UI events and callbacks don't modify the model directly. They generate actions instead, which can be represented as values. We then update the model based on the actions. Finally, the view is reconstructed from the updated model.

This approach is good for the web, as control flows from the browser to the server via values over the network. That's not how a desktop app is written though, so we made some adjustments to it

40 of 53

Writing the Editor:

Implementation rules

Converting action-model-view

to GTK

All state is kept in a single value. Updates are discrete�
Widgets are stateless and commutative�
All control flow is centralized in a top-down dispatch model�
Complexity is concentrated

41 of 53

Point 1: All state is kept in a single struct. Updates are discrete

user input

State 1

State 2

Dispatched to rendering

user input

State 3

state_2 = grid_state_guess (self->state,

&self->state->cursor,

"#"));

update_all (self, state_2);

self->state =

grid_state_replace (self->state, state_2);

User presses '#' key

state changes from State1 to State2

42 of 53

Point 1: All state is kept in a single struct.

Updates are discrete

For the game, all state is kept in a simple GridState struct

It includes mixture of semantic and display data�

For the editor, EditState includes over twenty members including four distinct GridStates

States need to be representable as a value. You need to be able to serialize it

typedef struct

{

IpuzCrossword *xword;

GridStateBehavior behavior;

/* Current keyboard state */

IpuzCellCoord cursor;

IpuzClueId clue;

/* Modifiers */

GridRevealMode reveal_mode;

CrosswordsQuirks *quirks;

} GridState;

Every state has its own copy of the puzzle object

43 of 53

Point 1: All state is kept in a single struct. Updates are discrete

State 1

user input

Dispatched to rendering

GridState *

grid_state_guess (GridState *state,

IpuzCellCoord *coord,

const gchar *guess)

{

…

IpuzCell *cell =

ipuz_crossword_get_cell (state->xword, coord);

ipuz_cell_set_cell_type (cell, IPUZ_CELL_BLOCK);

ipuz_crossword_fix_symmetry (state->xword,

IPUZ_SYMMETRY_ROTATIONAL_QUARTER,

coord);

ipuz_crossword_fix_numbering (state->xword);

ipuz_crossword_fix_clues (state->xword);

ipuz_crossword_fix_enumerations (state->xword);

…

user input

Dispatched to rendering

Update puzzle

Fix puzzle

When changing the puzzle:

1. First make all changes to it

2. Then fix the puzzle to follow convention

State 2

44 of 53

Point 1: All state is kept in a single struct. Updates are discrete

State 1

user input

Dispatched to rendering

Push value on Undo/Redo Stack

user input

Dispatched to rendering

Update puzzle

Fix puzzle

Push value on Undo/Redo Stack

Every undoable state is pushed to an Undo/Redo stack object

This object stores the current active state of the editor

State 2

45 of 53

Point 2: Widgets are stateless and commutative

Colin Walters: “Immutable” → reprovisionable, anti-hysteresis�https://blog.verbum.org/2020/08/22/immutable-→-reprovisionable-anti-hysteresis/

Widgets have anti-hysteresis properties.

When given a state, they behave and render the same independent of the path taken to get to that state

46 of 53

Point 2: Widgets are stateless and commutative

Writing commutative widgets:

Single way of setting state: :update(value)
Single way of information getting out: ::changed(optional value)
Store just enough information to render/cache themselves
Widgets never change the state of the application
There are zero lateral signal connections, or signal connections to data

(Hierarchical for propagation purposes in composite widgets is okay)

Anti-hysteresis style widgets are significantly easier to reason about

What does this mean in practice. It means that every custom widget has exactly one way of changing its appearance and behavior: There's an an _update() function that takes a value. We only have one way of information coming out of the widget: it emits a changed signal, with a value as appropriate. Widgets only store just enough state to render and cache themselves.

Widgets also never change the state of the application directly. Since they just get passed in a value, they don't have access to the central state.

Finally, the widgets never have lateral signal connections or signal connections to data. This is a major place where widgets lose their stateless properties in traditional apps.

The end result is that it's significantly easier to reason about widgets; they just have to render themselves to the screen.

47 of 53

Point 2: Widgets are stateless and

commutative

State 1

user input

Dispatched to rendering

Push value on Undo/Redo Stack

user input

Update puzzle

Fix puzzle

Calculate GridLayout

Call _update() on all widgets

An intermediate grid representation is needed to avoid each cell calculating its appearance from first principles

Push value on Undo/Redo Stack

State 2

48 of 53

Point 3: Control is centralized in a

top-down dispatch model

State 1

Dispatched to rendering

Update puzzle

Fix puzzle

Calculate GridLayout

Call _update() on all widgets

Push value on Undo/Redo Stack

EditWindow controls

widget

All widgets emit a ::changed signal

widget

Composite widgets propagate their children's ::changed signals

State 2

::changed

49 of 53

Point 4: Complexity is concentrated

Examples:

edit-window-controller.c (dispatch):

Translates between messy world of gtk and values

grid-state.c (crossword behavior):

Handles all actions on the crossword

puzzle-set-model.c (files):

Translates between messy world of file systems and puzzles

word-list.c (word lookup):

Finds potential word matches

Widgets and data structures are kept as simple as possible

50 of 53

Questions?

https://gitlab.gnome.org/jrb/crosswords/

#crosswords on matrix

Or talk to me! <jrb@gnome.org>

Download

on flathub!

51 of 53

Bonus slides

52 of 53

Issues with traditional application development

State is spread across a huge graph of objects
Extents of state are ambiguous. Is it in your objects? In the toolkit’s?
Callback hell. Event handlers modify your data, and notify of updates!
Testing is hard
Async or multithreading adds significant complexity

We took inspiration from the Unidirectional Data Flow architecture!

53 of 53

Cryptic Crosswords — clues

Times of London – Jun 30, 2024

3dn. Check the gas pedal (8)

THROTTLE

26ac. Second son, crossing pitch, means to walk tall (6)

STILTS

Assorted clues:

18ac. Leader from Harlech, Wales, appointed (4, 6)

LECH WALESA

https://crypticshewrote.wordpress.com/explanations/

So what does this look like in practice? I'm going to walk you through a couple of clues and their answers:

First, we are going to look at 3 down. The clue for that is "check the gas pedal", and the answer is throttle. Why is that? I'll give you a few seconds to see if you can see why:

[pause][next]

This type of clue is called a double definition clue. To "THROTTLE" something can mean to check it. It also is a term for the gas pedal. In this instance, we have two paths to the answer.

Let's look at another clue. 26 across is "Second son, crossing pitch means to walk tall", and the answer is stilts This one is a container clue. I'll give a few more seconds to see if people can figure out why that's the answer:

[pause][next]

This one is a bit more tricky. [hand gesture]In this case, both second and son are commonly abbreviated as 'S'. The word pitch can mean tile — you talk about the pitch of an airplane for example. and both 'S's cross the tilt giving you stilts. That's something that is a means to walk tall.

Don't worry if you didn't get these. It can be really mindboggling and confusing to