3D SUDOKU Puzzle with 81 Connected Cubes

Year: 2013 Authors: Hans Kuiper; Walt van Ballegooijen

Core claim

Connected 81-cube Sudoku sculptures in a 9×9×9 space do exist, and the authors found many more solutions through symmetry-based search and minimal swaps.

Topics

3D Sudoku sculptures, connected solutions, search algorithms, minimal art, solution families

Domains

Sudoku, Latin squares, graph connectivity, symmetry operations, minimal art, sculpture, 3D printing, Rhino modeling

Methods

trial and error, random swapping, minimal swaps, rotation and mirroring, 3D printing

Media

cubes, nylon plastic, framed cube, Rhino

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture

3D SUDOKU Puzzle with 81 Connected Cubes

Hans Kuiper

Rietdekkershoek 21

3981 TN Bunnik

The Netherlands

E-mail: hans.kuiper@net.hcc.nl

Web: http://web.inter.nl.net/hcc/Hans.Kuiper/

Walt van Ballegooijen

Parallelweg 18

4261 GA Wijk en Aalborg

The Netherlands

E-mail: waltvanb@xs4all.nl

Abstract

In this paper we describe how we developed minimal art based Sudoku-sculptures with 81 connected cubes. We proved that connected solutions actually exist by finding a first example. After some more successes we tried to improve our algorithms and found much more solutions. Here we describe our search, some results and conclusions, and we try (not completely successful) to estimate how many solutions could exist.

Can our object exist?

In 2008 Hans Kuiper presented a paper “SUDOKU Puzzle Generates a Minimal Art Sculpture” at the Bridges Conference in Leeuwarden [1]. A flat Sudoku puzzle becomes a 3D sculpture by replacing every single cell by a cube in a layer corresponding the number in the cell. So the cell with number 1 is a cube in the bottom layer and a cell with number 9 is a cube in the top layer and the other numbers are in between.

Figure 1: 64 connected cubes in a $8\times 8\times 8$ space

Figure 2: three ways how cubes can be connected on edges or corners

Hans described how he developed a sculpture of 64 connected cubes in $8\times 8\times 8$ space (figure 1). He did not manage to create a sculpture of 81 cubes in a $9\times 9\times 9$ space. Until 2012. In Towson Hans shared his problem with Walt van Ballegooijen and several other participants of the Bridges Conference 2012. Can your object exist, someone asked. Hans could not answer that question. Until then we never saw a Sudoku puzzle with 81 connected cubes. “Connected” means that every cube in the object in layer L is connected on an edge or at a corner (figure 2) with at least one other neighboring cube in layer L-1, layer L or layer L+1 (for L=1 and L=9 this rule slightly differs), and that all cubes are connected this way in one single group. Differently stated: they form a connected graph. Walt was absolutely enthralled by the problem. He answered the question by developing the first connected solution. Our object can exist!

Kuiper and Van Ballegooijen

Trial and error

A Sudoku is a special kind of Latin Square, and for its terminology we refer to [3]. We confine ourselves to standard 9x9 Sudoku puzzles, like the (not connected) example shown in figure 3. The reader can quite easily check the connectedness of any solved Sudoku puzzle by hand and pencil. Try it! It will almost certainly be not connected.

Figure 3: Analysis of a not connected Sudoku with 11 groups.

From left to right: Grid, Connectivity graph, showing connected groups and 3D projection

Walt and Hans independently developed all kinds of algorithms. Hans’ algorithm counts the number of cells of a solved Sudoku which are connected to the cell the middle. Then it randomly swaps some data, according to the “Sudoku preserving symmetries” (see figure 4 and ref. [4]). At first a swap was only accepted if the number of connections did not decrease. Later it appeared that accepting a small decrease was a much more fruitful strategy. The algorithm continuously swaps until it reaches 81 connected cells. Walt’s algorithms created random Sudoku’s, and selected those with only a small number of connected groups. Then it explored all minimal swaps (see later), searching for fewer groups, until their number is 1. It took a runtime of several hours to catch a solution. But finally we found one (figure 5) and soon more!

Figure 4: From figure 3 to figure 5 in three “Sudoku preserving symmetry” swaps

Figure 5: Analysis of Walt’s first connected solution

3D SUDOKU Puzzle with 81 Connected Cubes

Families, minimal swaps, islands and numbers

We found that solutions come in “families” of 16 members, which can be derived from each other by rotation and/or mirroring (schematically shown in figure 6). For administrative purposes we identified these families by the lowest of these 16 81-digit number codes (reading a Sudoku row by row). What the lowest and highest possible values are remains a open question, but in the solutions we found, they are 123456789486297153579381624847529361965138472312674598231865947754912836698743215 and 432198756951367482876452931695834217124975368783216549349781625268549173517623894.

Figure 6: Each solution is member of a family of 16 essentially the same [according 2] solutions

When in a Sodomu two cells of a block are swapped, some but not necessarily all other cells containing the same values are also forced to swap. A “minimal swap” only changes as little as possible of these 18 cells. This can be 2 to 7 pairs, or all 9 pairs. Trying out all minimal swaps on a connected solution quickly exploded the number of solutions we found. Figure 7 shows that a path from one solution to three others can be derived by minimal swaps only. We say that these solutions are all on the same “island” (in a sea of not-connected Sodomu’s). Sometimes an island has 1 solution, and sometimes more than 1000, in which case we stopped the search for more solutions on that island. At a certain point we found 132 islands with in total 52.754 families (of 16 connected solutions) on them.

Figure: 7: Minimal swaps in 2, 3 or 4 blocks that generate other connected solutions

From that time we realized that our seemingly rare solutions must be enormous in number. It has been proven [2] that there are about $6,7\mathrm{E}+21$ different Sudoku-puzzles. Only a small fraction of them is connected. We were not able to make a good and sound statistical analyses, but our educated guess is that not more than 1 on every million Sudoku’s (it might be much less!) is fully connected. That corresponds to an upper limit of about $6,7\mathrm{E}+15$ different fully connected Sudoku-puzzles (see figure 8). We don’t dare to give a guess for the lower limit. We only know for sure that it is (much) more than the $52.754\times 16=844.064$ different solutions that we have found.

Kuiper and Van Ballegooijen

Figure 8: Total numbers of Latin Squares, Sudoku’s and (estimated upper limit of) 3D-connected Sudoku’s, their numbers of essentially different ones, and some comparisons

As a tangible proof of existence we made some 3D prints. In Rhino we designed dice like cubes for each of the nine levels, with the numbers on top being 10 minus the numbers on the bottom. We placed 81 of them in a framed cube, that was added for reasons of strength and stability (figure 9). The first 3 solutions we have found have been printed this way in nylon plastic (figure 10), each model is about $10\times 10\times 10$ cm.

Figure 9: The design of the 3D prints: one of 81 parts and a complete model with frame

Figure 10: The 3D prints of 3 different solutions

References

[1] Hans Kuiper, SUDOKU Puzzle Generates a Minimal Art Sculpture, Bridges Leeuwarden Proceedings 2008 [2] http://www.afjarvis staff.shef.ac.uk/sudoku/ [3] http://en.wikipedia.org/wiki/List_of_Sudoku_terms_and_jargon [4] http://en.wikipedia.org/wiki/Mathematics_of_Sudoku