The New Sudoku Players' Forum

[dudzcom]

hi,

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 programatic discoveries about some fundamental rules for Sudoku computation. "Three Generalized Logical Reductions for Solving Sudoku"

The reduction principles, along with my term paper are available on my website, www.dudziak.com/sudoku.php.

I might stop back and check out this thread every now and then, but if you have real interest in discussing the work I've done, please contact me via the forums at dudziak.com.

[gsf]

Reduction 4 (Heuristic Search):
Individually test branches of the search tree using rudimentary search methods and determine if any candidates for cells are invalid due to certain chain reactions within the grid when values are placed. Complexity: O((total remaining candidates)2). Nearly all Sudoku can be solved using the first three approaches. The HS approach is a last-ditch effort to try and work out a solution to a stubborn problem.

This generalized rule covers the popular rules:
Coloring, Remote Pairs, XY-Chains, Forcing Chains, Nishio, XY/XYZ-Wing, Aligned Pairs, Single Chains, Y-Wing Chains

a closer read of the forums will reveal clear distinctions between heuristic/brute-force/backtrack/placement-guess
search and the property/structure based techniques like coloring etc.

you need another reduction category:

Code: Select all

reduction 4: the other well known methods I didn't implement
reduction 5: "insert your adjective here" search


[dudzcom]

hi gsf,

i appreciate that you feel i left out the distinction between the "Reduction 4" rules. you may have a point that these are differnet conceptual approaches for problem reduction, however in any efficient code implementation (which is seldom identical to conceptual approches), they all reduce to the same basic search algorithm.

the truth is, that the complex logic involved in the "reduction 4" techniques is simply not necessary. our little human brains need to see patterns to logic our way through things, when in truth, detecting those patterns requires more computation than simply brute-forcing your way through the problem.

when it comes to algorithm design, efficiency is king. all of the "Reduction 4" rules are most efficiently implemented as a simple search. Actually adhearing to the 'letter' of the rule, and writing the algorithm to perform the rule as it is stated for human consumption is suicidal if you want your program to run fast.

thanks again for your reply,
-will

[gsf]

you may have a point that these are differnet conceptual approaches for problem reduction, however in any efficient code implementation (which is seldom identical to conceptual approches), they all reduce to the same basic search algorithm.

when it comes to algorithm design, efficiency is king. all of the "Reduction 4" rules are most efficiently implemented as a simple heuristic search.

you are lumping all algorithm design goals together
attempting to code the fastest computer solver will guide the design in a different direction
than a solver intended to mimic human techniques
both nonetheless may be coded for efficiency consistent with the goals

also, if efficiency is your goal then why not just have reduction-1==singles and reduction-2==search?
what is your reduction-1-4 solutions/sec/Ghz for the top1465?

[dudzcom]

also, if efficiency is your goal then why not just have reduction-1==singles and reduction-2==search?

thats a concept that was toyed around with, however it turns out to be much more computationally intensive than using 1,2, & 3 together, and 4 if we get stuck.

reductions 2&3 are both very valuable because they do not require much computation time (about the same as Reduction 1), and do indeed reduce the problem size whereas "reduction 4" techniques rarely are needed.

attempting to code the fastest computer solver will guide the design in a different direction
than a solver intended to mimic human techniques
both nonetheless may be coded for efficiency consistent with the goals

no argument here. perhaps i should restate the goals/conslusions on the webpage - suggestions appreciated.

[gsf]

also, if efficiency is your goal then why not just have reduction-1==singles and reduction-2==search?

thats a concept that was toyed around with, however it turns out to be much more computationally intensive than using 1,2, & 3 together, and 4 if we get stuck.

that may depend on how the search is coded
forward checking or constraint propagation may change the number of
techniques required for good average performance

reductions 2&3 are both very valuable because they do not require much computation time (about the same as Reduction 1), and do indeed reduce the problem size whereas "reduction 4" techniques rarely are needed.

see if the top1465 adjusts this claim

[dudzcom]

will do.