KUBEGENERATOR: README

This web page generates solvable Sudokubes using one of two algorithms.

A Sudokube is a Rubik’s cube-like puzzle. It is a 4x4x4 cube. Each cubie face (squares) is labeled with one of 0, 1, 2, …, F. In order to be solved, the cube must be in a state such that each face has a single occurrence of each label and also that on each orbit around the cube, each label occur once. This is analogous to a Sudoku puzzle as seen in many modern newspapers, which is a 9x9 grid where each row and column must have one each of the digits from 0-9 and each column or row must also have one of each digit. To illustrate, here is a solved cube:

You can see that the two lines of squares in italics and bold are in a solved state.

The creation of a solvable Sudokube is a non-trivial task. In fact, it is analogous to solving a Sudoku problem, but harder since there are 96 squares to label rather than 81 as in a regular Sudoku. Two similar but markedly different approaches were implemented to solve this problem.

Both algorithms rely on the same core idea. The cube has six faces, designated front, back, up, down, left and right (F, B, U, D, L, R). The program begins by assigning face F an arbitrary labeling as follows:

It then generates safe-sets for all the other squares on the cube. The safe-set of a square is the set of labels that can be applies to that square. For example, if we looked at the square at (0, 0) on face R, it can no longer have labels 0, 1, 2 or 3 because it is adjacent to row 1 of face F. Thus, its safe-set is 4-F.

Depending on how many random faces KubeGenerator is asked to generate, the program will assign a deterministic labeling to one or all of the faces on the cube. It is, however, impossible to ask for only one face of the cube to be random, because as soon as the labeling of the five other faces is determined, there is only one possible labeling for the sixth. This is reflected in the output of KubeGenerator by the blue labeling of face F. While it is unlikely that the labels on face F actually were the last sixteen left to be done, it is designated as a pseudo-random face to make it clear that once the labeling of five faces is generated, the labeling of the last one is completely deterministic as only one possibility remains.

At this point, the two algorithms differ. We now have between 32 (2 x 16) and 80 (5 x 16) unlabeled squares (depending on how many faces remain to be labeled). Each of these squares has a safe set whose size can range from zero to sixteen.

Algorithm 1 performs a bucket sort on the safe-sets indexed by their size, which we know is in the range 0-16. It will then check if any sets of size 0 exist. If they do, then we have reached a dead end in the labeling: there is an unlabeled square for which no valid label remains. At this point, the program throws away all the work it has done to date and starts over.

If no empty sets exist, it will take the smallest bucket that does have squares in it, then randomly select a square among those with the smallest safe-sets, and then randomly select a label from that square’s safe-set and apply it to that square. The square that has been labeled is moved into a bucket for labeled squares. It then updates the safe-sets of all squares on the cube affected by the labeling and continues. Eventually, we have either labeled the entire cube or an empty safe-set occurs and we restart as described above.

This algorithm is designed to favor smaller safe-sets because if a larger safe-set is chosen and a label from it is applied, it is more likely to destroy the smaller sets and cause dead ends.

Algorithm 2 differs from the first only in the selection of which square to label next. Rather than sort the squares by safe-set in buckets 0-16, it will simply place the squares into three buckets: empty safe-set, singleton safe-set and non-empty safe-set, as well as the labeled square bucket. If an empty safe-set is found, then as above we have reached a dead end and start over. When algorithm 2 selects a square to label, it will check if any singleton sets occur; squares with only one valid label. If such a square exists, algorithm 2 will favor it over any other. If more than one such square exists, one is randomly picked. If no singleton set occurs, then a square is randomly chosen from the non-empty safe-set bucket and a randomly chosen label applied. Algorithm 2 continues to try until it labels the cube.

A more “pure” version of algorithm 2 without the singleton set bucket was attempted, but ultimately didn’t work because it ran into too many dead ends and took too long to label cubes.

In terms of performance, algorithm 1 is altogether much faster than algorithm 2. Both algorithms were run 1,000 times and their average runtime and average number of failures were compared:

Algorithm 1:

• Average runtime (s): 1.2340311017
• Average number of failures: 11

Algorithm 2:

• Average runtime (s): 64.0133712273
• Average number of failures: 2148

This means you shouldn’t be surprised if your browser seems to hang you ask KubeGenerator to generate five random faces with algorithm 2. It just takes a long time! Runtimes do fall drastically when fewer random faces are asked for, especially for algorithm 2.

Further Scrambling:

Algorithms 1 and 2 both generate solved cubes. To create actual solvable problems, two further scrambling techniques are used at the user’s option.

First, a certain number of random rotations may be specified. This will apply however many rotations the user asks for to the cube. These are rotations that could be performed on a real cube, so scrambling it in this fashion preserves the solvability of the Sudokube. This is also how the solution given on the result page is generated, and why it is far from an ideal one.

Second, a substitution may be applied. When this option is selected, KubeGenerator randomly generates a bijective function on [0, 15] -> [0, 15] and then uses it to scramble the cube by substituting the labels. Since the labels are arbitrary so long as there are sixteen of them and they are distinct, this too preserves the solvability of the cube, but makes it harder to spot patterns such as the obvious 0, 1, 2… labeling on face F.