User:George Heineman/Sujiken

A Sujiken puzzle...

The previous puzzle, solved with additional digits that each fill a blank space.

...and its solution numbers marked in red

Sujiken is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 45-cell triangular grid with digits so that each cell contains a digit and no digit is repeated in any column, row, diagonal in any direction, each of the three outlined 3x3 square sub-grids (also called "boxes" or "regions") and each of the three outlined six-cell triangular sub-grids (also called "triangular regions"). The initial partially filled-in grid contains a number of "given" digits from which the solver must logically deduce the remaining digits to uncover the unique solution. In homage to "symmetrical" Sudoku puzzles as popularized by Nikoli, the givens in a "symmetrical" Sujiken puzzle are distributed in mirror-image fashion in relation to the North-East diagonal from the lower left cell to the half-way point of the long diagonal.

Sujiken differs from other Sudoku variations because there are regions that contain fewer than nine digits, such as the triangular regions and partial rows, columns and diagonals. The first Sudoku variation to consider diagonals -- Diagonal Sudoku -- only requires the digits in the two long diagonals of a Sudoku board to be unique.

History

Sujiken first appeared in a newspaper on September 14th 2010 in the Worcester Polytechnic Institute student newspaper "The Towers"

Sujiken first appeared in magazine form in Games World of Puzzles (ISSN 1074-4355)

First newspaper article on Sujiken appeared on Sunday April 10th 2011 in the Worcester Telegram and Gazette.

Describing Sujiken Solutions

It is often helpful to label the individual cells when describing logical solutions. For this reason, the rows are labeled from 1 (the bottom-most row) to 9 (the top row) while the columns are labeled from A (the left-most column) to I (the right-most column). Additionally, the three 3x3 square regions are labeled as left square, corner square, and lower square. The three triangular regions are labeled as top triangle, middle triangle, and lower triangle. The only diagonal with 9 distinct cells is labeled the long diagonal.

Individual cells are identified by their unique column and row coordinates. Thus the lower-left cell in a Sujiken board is labeled A1 while the top-most cell is A9.

Mathematics of Sujiken

To determine the total number of valid Sujiken boards, it is possible to compute the total number of boards using two different methods supported by computer programs. The different programs compute the same total number of valid boards using different methods, which offers some evidence that the computed value is correct.

The problem is only tractable because of symmetry. Consider filling the partial rows of the corner square in a Sujiken board with the digits

1	2	3
4	5	6
7	8	9

Any completed Sujiken board with these digits can be transformed into a different Sujiken board by selecting a permutation of the nine digits. Thus the total number of valid Sujiken boards is 9! (362,880) times the number of possible boards with this pre-filled corner square.

The first program generates potential boards by observing that there are four regions that must contain nine different digits. These are the three square regions (known as the left, corner and lower squares) and the long diagonal. With the corner square already filled-in, the program tries all possible combinations of nine digits in the left square, lower square, and long diagonal. Using brute force, the program then attempts to fill in the remaining 9 cells not belonging to any of these regions.

The second program use brute force to create partial boards with completed square regions, row 1, and column A (for a total of 33 cells). For each partial board another brute force search on the remaining 12 cells discovers the available boards.

Both programs arrive at the total of 235,318 * 9! = 85,392,195,840.

It is possible to construct an unsolvable grids with 44 givens and one blank space. In the following board, for example, no valid solution exists although all 44 digits obey the rules governing Sujiken.

.
58
321
1934
47685
852769
2689143
71463592
935278416

Note: A suitable image showing this board will replace this crude representation.

It is currently not known how few givens are required to guarantee a unique solution. A number of symmetrical boards with just 9 givens have been found, though fewer may be required in non-symmetrical Sujiken boards. It is noteworthy that this ratio (9 out of 45, or 0.2) is essentially equivalent to the fewest number of givens in Sudoku (17 out of 81, or .20987654320...).