Generating Calcudoku Puzzles

Calcudoku is a number puzzle game similar to sudoku. An example 6x6 puzzle is shown below

The square must be filled in such that each row and column contain the numbers 1 through 6. The numbers in each group must satisfy the operation listed. For example, the 12+ group must contain 3 numbers that add to 12. The solution for this puzzle is shown below

Generating Puzzles

Creating the Square

Calcudoku puzzles can be generated in reverse order, i.e., starting with the solution and creating groups that satisfy the generated solution. The first step is filling each row and column such that they all contain the numbers 1 through N. This type of square is called a Latin Square, and there do exist fast algorithms to uniformly randomly sample from all possible latin squares. Here is an example of a latin square

Here we use a relatively simple algorithm, we loop through every square on the board and find all possible values that square can be, based upon the other numbers in it’s row/column. Then we pick a random number from the possible values. For example, consider the partially completed square

1	3	4	2
2	4	x

The square labelled ‘x’ can take on the values 1, or 3, and is chosen randomly from these two numbers.

Partitioning the Square

Now that we have a solution, we need to generate groups that specify the solution. We do this by creating a size 1 partition, one for every square, and repeatedly merge them together until some criteria is met. The procedure goes like this

1. Randomly choose the base partition to merge with. Probabilities for this choice are weighted by the partition size, with smaller partitions given higher priority to merge.
2. Choose a partition from the base partitions neighors to merge with, once again probabilities are weighted by the resulting merged partition size.
3. If the average size of all the partitions is greater than some specified value stop, else go back to 1.

Choosing Operations

Once the partitions are generated we have to choose which operation to assign to the partition. Say we have a partition with the numbers (5, 4, 1). The valid operations we could assign are:

• Multiplication, 5x4x1 = 20
• Addition, 5+4+1 = 10
• Subtraction, 5-4-1 = 0 For every partition we find the valid operations that can be assigned, and then randomly choose one. The random choice is weighted by prior values for each operation, as well as the current number of the operation to keep the numbers close to uniform.

Large Puzzles

The way the algorithm is set up it is easy to add new operations such as exclusive or, and generate very large puzzles

Code

A Python package which implements the above ideas can be found on my Github.