Overview of the program structure

Despite the differences in the games, the structure of their programs is essentially the same. These notes outline the common organisation and structure of the programs, but where necessary, to simplify the description, the Sudoku program is used as an example.


The overall architecture is that known as Model, View and Controller. Here that means that the program has three main classes named Model, View and Controller and that they relate to one another in the following ways.

The Model contains all the data for a puzzle and the algorithms for its manipulation (eg for sudoku, the state of all the candidates for the current puzzle and the algorithms used for supplying hints). The View knows nothing about the data. It draws stuff on the screen when instructed to by the Controller. It tells the Controller when buttons have been pressed, but it doesn't know what the buttons relate to. In fact, the command to execute for each button press or keyboard input is set up as a callback by the Controller. Having initialised all the necessary callbacks for the View, the Controller initiates a game by instructing the Model to load a puzzle into its data structures. The Controller then instructs the View to start its clock display ticking and to display the corresponding values on the screen. The Controller makes the relevant View callbacks active and waits for user input.

As an example of user input: if the user left-clicks on the sudoku hint button the View will execute the Controller's service_toolbar callback which takes the button index and mouse index as arguments. For mouse index 1 and button index 1, service_toolbar calls the Controller give_hint function. This calls the Model do_hint function and also tells the View to show the current status of the Model (if the model data is inconsistent, the View will display the thumbs down icon, etc). If a hint is found the View is instructed to flip the Toolbar wand icon, display the two letter algorithm name and colour the appropriate candidates. And so on.


All of the games involve a grid of some kind. The basic unit of Model data is the Datum class which contains data and algorithms for an element of the grid. For sudoku a Datum stores only: symbol_index (the solution), guess (the players current guess for the solution), index (the element index in the whole grid), given (True or False, having the value True if the datum is an initial clue), and a set type containing the remaining candidates for the datum. The list of items is short because every element in the grid is essentially the same. For kakuro, as grid elements can be of several different types, a Datum stores 22 different items including a set and a callback function (for setting data about the Datum's position in the grid, about which only the Model knows.)

The Datum class has many functions to deal with setting and unsetting candidates and guesses and for checking on its internal consistency (eg does the Datum's set of candidates include the solution).

The Model class has a list of Datums, one for each element in the grid; so 81 for sudoku. The Model also has data about the larger structure of the grid, for example, in sudoku, lists of the Datum indexes for all the rows, columns and boxes; so for each of these 3, it has 9 lists of 9 Datums. These lists enable hint algorithms to be applied, in turn, to each row, column and box; the algorithms just being presented with the corresponding list of Datums.

Model uses the Editor class to handle hint data produced by the hint algorithms. For a hint we need to know which Datums and which of their candidates are involved, whether a Datum is a cause or effect. A cause is a reason why a hint exists, say the pattern of Datums and candidates which make up an X-Wing. An effect is the list of Datums and their candidates which can be deleted. If in the corresponding mode, the Editor needs to save the best hint found. The Editor also applies the hint to the Datums by deleting the effect candidates.

Model uses the UserEdits class to store edits made by the user if they are errors, and to undo them when requested. Both Editor and UserEdits use the data structure class EditPair for storing individual Datum, candidate editing operations.

The hint algorithms are used to offer the player hints and to solve external puzzles. In sudoku, set operations are used throughout. For example, hidden_singles are found for a list containing the indexes for a row, column or box by comparing the set containing the candidates for a Datum to a set containing the union of the candidates for all the other Datums in the list. Model also handles the reading and writing of puzzles.


The View class, written in Tk, handles the user interface. It has to lay out what the user sees on the screen and bind the necessary procedures to the parts that the user interacts with. These procedures are callbacks supplied by the Controller. The Toolbar widgets are Buttons; the grid and any of its constituent parts like candidate "buttons" are Label widgets, not Buttons. The program makes them act like buttons by binding the necessary actions to them; for example to make them change colour when the mouse cursor crosses them. For most games an Entry box is used to allow the user to type in a puzzle number.

View also uses a number of other classes: EntryBox, MyClock, Buttons, BoundObjects, EnterPuzzle and Flasher. All the images displayed in the games are built into the program code as base64 strings and stored in the class SGImage.


The Controller initialises the Settings class, the ModelData class, the View and calls its start_game function, which, in turn, initialises a Model, loads a puzzle and adds it to The View; it also sets up the callbacks for the View. Then it waits for feedback from the View callbacks. It has to service the Toolbar, the menu and the "buttons" on the grid.


Almost all of the programs contain built-in puzzles; generally 5000 per program. These puzzles are generated by external programs which also prepare them for inclusion in the game program. First this puzzle data is written in a simple form, say for sudoku, a long comma separated list of 82 items per puzzle: the difficulty score followed by the 81 solutions for each grid element; the given clues preceeded by a minus sign. So, a total of 5000 x 82, comma separated items. Next the data is compressed using zlib, then base64 encoded. This encoded form is loaded into the program code in the ModelData class. When the program is started the Controller initialises ModelData which unencodes and uncompresses the data to get the 5000 x 82, comma separated list. When Model is told to load a puzzle it uses a ModelData function which returns the appropriate elements of its long list.

Boggle and scrabbler do not have built-in puzzles but need to use a big dictionary, or rather, word list. In its raw form this is nearly 3MB in size. When represented as a Directed Acyclic Word Graph, compressed and base64 encoded it is nearly 900KB. For boggle and scrabbler ModelData contains this encoded word list which is decoded and uncompressed when the programs are started.


The Settings class contains variables which define the sizes and colours of all the components shown in the display, some fixed and some that can be changed by the user. Those that can be changed by the user are stored in a dictionary, and Settings uses the dictionary to load the puzzle menu. When the program starts Settings reads the player's preferences from disk and loads them into the dictionary. It also saves preferences.


Sgg stores constants and global variables. It also works out the operating system being used and handles the opening of the files used by the program. The program's files are stored in the directory ~/.pzl/program_name, where ~ is the users home directory and program_name is the name of the program. For example ~/.pzl/sudoku will contain sudoku.log, preferences.txt and SAVES. The log file is a file which will accumulate diagnostic messages to help the support team to understand any errors which occur, preferences.txt is the player's option choices, and SAVES is a directory for saving puzzles. No program installation procedure is required: each program will create any additional files it needs the first time it is run.


As distributed, the programs are set to produce no console messages, however the Python Logger system enables the programs to record user actions and error messages. These messages are saved in the log file mentioned in the Sgg section. The file is "rotated" when it reaches 0.5MB in size and a single backup is maintained (which also will never exceed 0.5MB in size).


To produce screenshots of the programs, especially the ones used to make the animated gifs, it is convenient if the programs make them automatically, say after each key press. The ScreenShot class enables that. If enabled, for the designated events, it calls the ImageMagick import program and saves to files using a simple naming convention.


If anyone is sufficiently interested, the pzl_launcher program conforms to the design outlined above and contains all of its major components but in under 500 lines of code.


The original intention, despite the fact that much of the code is common to many games, was that each game should be a single file so that users could install only the games they wanted, each as a single download file. However, when scrabbler was written and needed to use the very large word list already contained in boggle, it seemed sensible that the compressed list should be included as a separate file so it could be shared. Having broken the single file idea it was only natural that other common code should be shared.

The current situation is that for each game there is a main file, say sudoku.pyw, and that imports modules from a common library pzl_lib.py. In addition boggle and scrabbler import the compressed word list from dawg.py. The installer and launcher have been left complete as single files. Because of this splitting, the uninstall options within the individual programs was removed from their menus and the launcher is now used for this purpose.