This repository contains the code for a generator and playing website for number puzzles called Str8ts.
Try it out on luiswalter.dev/str8ts!
The puzzle consists of a 9x9 grid of squares (similar to Sudoku). The objective is to fill all empty cells with suitable numbers between 1 and 9.
Although the basic principle is quite similar to Sudoku puzzles, the rules for filling out (and generating) a Str8ts grid is (technically) more complicated because of the random position of the black fields.
At the beginning, each cell of a Str8ts grid is either black or white and either empty or filled with a number. Existing numbers and black fields constrain the possibilities for empty cells. Each row and column must not contain a duplicate number. Because of the empty black fields not all numbers between 1 and 9 must be present in every row and column. Furthermore, the white cells between two black fields have to be filled out with consecutive numbers. The order of those consecutive numbers is not important. This rule applies to vertical and horizontal groups of cells.
Consider, as an example, three white fields between two black fields and one of those white fields already contains the number 3. The other two white fields next to it contain either the numbers 1 and 2 or 2 and 4 or 4 and 5. Which of those is the correct solution depends on already existing numbers in the same row or column.
The code for the game generator is written in C++ because of performance reasons. First attempts to implement the algorithm in python were too slow.
The code for playing the Str8ts puzzles is plain HTML, Javascript, and CSS. If the user wants to generate a new puzzle
a PHP script is called in the background which in turn calls the compiled game generator. That returns the newly generated game encoded as a base64url string. This is displayed in the user interface on the website. The user never needs to reload the page.
The game gets encoded as a 106 character long string which automatically is appended to the URL after a new game was generated. Furthermore, a dialog is shown in which the user can copy the URL containing the just generated game. After sharing it with other users it is possible to compete with them and, for example, compare the required time to solve the puzzle.
Although the involved URLs a quite long this approach does not require storing the generated puzzles on the server.
The generator algorithm can be divided into several steps.
The first step is to randomly generate black fields for an empty grid. The number of those black fields is 19 plus a random number which depends on the user-selected difficulty of the puzzle.
The next step is to check if the generated black fields make up a reasonable puzzle. Too large clusters of black fields or lone white fields should not occur. If one of those is found the generation of black fields is repeated.
In the next step, all remaining white fields are filled with suitable numbers. A recursive backtracking algorithm is used for finding numbers that obey the rules. The maximal recursion depth of the backtracking is limited because some puzzles took too long to be completed with numbers. For those cases, it is faster to restart the generation process.
Afterward, black fields with known numbers are generated. Therefore all black fields are checked for numbers that can be inserted without violating the game rules. Up to a maximum number of black fields with known numbers suitable numbers are inserted into the grid.
The next step is to remove numbers from white fields. The number of cells which have to be completed by the user depends on the number of black fields and the selected difficulty of the puzzle. Maximum 50 numbers are removed. After each removed number possible solutions of the puzzle are counted via another backtracking algorithm. If there is more than one solution the game would be non-unique. In this case, the game generation is restarted.
After the puzzle was generated it is first encoded as a binary string. The first 8 bits contain the encoding version number. The subsequent 6 ⋅ 81 = 486 bits encode the whole game grid with its 81 cells. Each cell is represented by 6 bits. The first two bits contain the information about the mode of the field, i.e. if it is black or white and if the number is known to the user or not. The remaining 4 bits encode the number of the cell. The whole binary string is then converted into a base64url string. In theory, each character of the string encodes one cell of the puzzle. Although it is probably not a serious problem, one could read of the solution for some cells from the base64 string which is displayed as part of the browser URL. However, the first 8 bits of the encoding version number induce a bitshift to the encoded game grid which makes the decoding harder for humans.