Random Sudoku Board

In December of 2005, a friend challenged me to write a Sudoku-maker which could make Sudoku faster than a generic Sudoku-maker he downloaded which created them at a frequency of about every 11ms (91 Sudoku/second). Not one to disappoint, I returned to him 3 days later with an algorithm which was capable of creating random Sudoku at a rate of ~4000/second (on a 1.7GHz P4 processor) :)

Having achieved the first goal I set out to accomplish, I turned my attention to creating more complex Sudoku. Generalizing the code written for the initial 9x9 creator, I am able to now create Sudoku boards up to 36x36 in a matter of seconds.

In spring of 2006, I took an Advanced Parallel Computation course required for my Masters degree. For this course, I parallelized the work of creating arbitrarily large Sudoku, and in so doing made a couple programmatic discoveries about some fundamental rules for Sudoku computation. "Three Generalized Logical Reductions for Solving Sudoku" is presented below. Also, on the bottom of the page is a link to the paper in which my work is presented.

If you like this project, or have any comments/questions/suggestions regarding this sudoku work, please feel free to send me an email - I'd be happy to hear from you.

Project started in December 2005, currently the project is suspended as of May 2006 due to lack of interest. As of now, the Sudoku maker is in version 2.1 using C++.

After doing some research & experimentation, I have come to the conclusion that using simply 3 generic rules, the vast majority of Sudoku can be solved efficiently programmatically. Many online sites list dozens of solution strategies, however the majority of the strategies are usually instances of one of the three generic approaches.

These reudctions have the greatest use for creating Sudoku. Many creation algorithms call for 'placing a number' followed by 'checking to see if the board has a unique solution', if not, then 'placing another number' etc. Using these three reducitons exclusively when 'checking to see if the board has a unique solution' can greatly speed up Sudoku cration time.


Reduction 1 (Subset Reduction):
In an N² x N² grid, for each Row/Column/Block, if there are K cells which together contain exactly K candidate values, those candidates may be removed from all other cells in that Row/Column/Block. Complexity: O(N⁴*2^{N^2}).

This generalized rule covers the popular rules:
Naked Single/Pair/Triplet/Etc., Hidden Single/Pair/Triplet/Etc., Single/Double Block Line, Single Solution, Single Cell, Disjoint Chain


Reduction 2 (Xor Reduction):
In an N² x N² grid, take any Row or Column denoted P and a Block denoted B where C = P Ç B and C > Ø. Any candidate values not represented within the set P-C can be removed from all items in the set B-C. Likewise, any values not represented within the set B-C can be removed from all items in the set P-C. Complexity: O(N⁵).

This generalized rule covers the popular rules:
Single Box, Intersection Removal, Pointing Pairs


Reduction 3 (Symbol Reduction):
In an N² x N² grid, for each possible value V, if there are K rows which together contain exactly K possible columns for the value V, then any other rows with candidates of value V in those columns can have the candidates removed. This argument can be applied to Columns as well. Complexity: O(2^N+1*(N² Choose N)). Symbol Reduction is only valid when applied directly after Subset Reduction.

This generalized rule covers the popular rules:
X-Wing, Swordfish, Jellyfish, Squirmbag, 6-Gronk, 7-Gronk, N-Fish


Rules not covered directly by reductions 1-3:
Coloring, Remote Pairs, XY-Chains, Forcing Chains, Nishio, XY/XYZ-Wing, Aligned Pairs, Single Chains, Y-Wing Chains

Presented is a paper written for an advanced parallel processing class, describing a simple implementation of Sudoku creation using the generic Message Passing Interface (MPI).

Download the paper in Adobe PDF format:
Arbitrary Size Parallel Sudoku Creation