Velocity Reviews > Brute force sudoku cracker

# Brute force sudoku cracker

Antoon Pardon
Guest
Posts: n/a

 09-22-2005
Op 2005-09-21, Tom Anderson schreef <(E-Mail Removed)>:
> On Mon, 19 Sep 2005, Antoon Pardon wrote:
>
>> Op 2005-09-17, Tom Anderson schreef <(E-Mail Removed)>:
>>> On Fri, 16 Sep 2005, Bas wrote:
>>>
>>>> -any ideas how to easily incorporate advanced solving strategies?
>>>> solve(problem1) and solve(problem2) give solutions, but
>>>> solve(problem3) gets stuck...
>>>
>>> the only way to solve arbitrary sudoku problems is to guess.

>>
>> That is strange, in al the puzzles that I have solved untill now, I
>> never needed to guess, unless the puzzle had multiple solutions, which
>> personnally I find inferior.

>
> Well, if we are to believe Lance Fortnow, a fairly expert comptational
> complexionist, that's probably not generally true:
>
> http://weblog.fortnow.com/2005/08/sudoku-revisited.html
>
> It's this bit:
>
> "Since we don't believe that NP has fast probabilistic algorithms, we
> expect that there are no efficient procedures to completing a generalized
> Sudoku grid"
>
> That makes me think that there probably isn't a non-backtracking method,
> since that would almost certainly be polynomial-time.
>
> The thing is, the puzzles you encounter in the wild have been designed to
> be solved by humans, using non-backtracking methods; they're much easier
> to solve than the general class of Sudoku.

Well I stand corrected. Thanks for the information.

--
Antoon Pardon

Dennis Lee Bieber
Guest
Posts: n/a

 09-23-2005
On 22 Sep 2005 12:57:58 GMT, Antoon Pardon <(E-Mail Removed)>
declaimed the following in comp.lang.python:

> Op 2005-09-21, Tom Anderson schreef <(E-Mail Removed)>:

> > The thing is, the puzzles you encounter in the wild have been designed to
> > be solved by humans, using non-backtracking methods; they're much easier
> > to solve than the general class of Sudoku.

>
> Well I stand corrected. Thanks for the information.

I wouldn't be too sure... I have a book of the deadly puzzles... The
last third is full of puzzles that come up with multiple candidate
paths, that have sometimes required me to backtrack parts at least twice
(I typically give up when I get these cycles with split points -- since
I do the puzzles in fountain pen).
--
> ================================================== ============ <
> http://www.velocityreviews.com/forums/(E-Mail Removed) | Wulfraed Dennis Lee Bieber KD6MOG <
> (E-Mail Removed) | Bestiaria Support Staff <
> ================================================== ============ <
> Overflow Page: <http://wlfraed.home.netcom.com/> <