I wrote one in C# a while ago:
http://isaksky.wordpress.com/2010/10/30/objected-oriented-so...
Sudoku Solving
11–20 of 55 posts
Re: Sudoku Solving
#12He could have used Mechanical Turk to solve them. ;) Growing up, we had a favorite game. That is until my sister solved it in that going first you could always win. It wasn't as fun after that.
http://xkcd.com/832/
I like that one.
Ours was a different game: Mühle. Also Mill or Nine Men's Morris.
I just discovered that Ralph Gasser solved it in 1996 using retrograde analysis and an 18-ply alpha- beta search. [1] Becoming "the first non-trivial game to be solved that does not seem to benefit from knowledge-based methods."
Re: Sudoku Solving
#13Re: Sudoku Solving
#14Earlier quoted context omitted.
I'm curious... what would be the 'proper' technique?
solving without trial and error at all.
That strikes me as extremely unlikely.
I think the complexity class of Sudoko is NP-Complete (a quick google confirms it's not exactly NP but very close: http://11011110.livejournal.com/23221.html?thread=19381 -- complexity is the same as solving SAT problems which have only one unique solution)
Re: Sudoku Solving
#15Can someone explain the Ben Laurie quote? I know what Sudoku is, and I know what a DOS attack is. I don't see the connection between the two.
Sudoku has a human using their mind to solve things which don't need to be solved. A denial of service attack leaves a computer trying to handle things which don't need to be handled. So they have something trying to deal with things that don't need to be dealt with.
Thank you.
Re: Sudoku Solving
#16Earlier quoted context omitted.
I'm curious... what would be the 'proper' technique?
solving without trial and error at all.
If you do the constraint propagation right, the number of trials and errors will be very small (and it will be only one trial and no errors for the easy ones).
I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like. (apart from pathologic solutions like querying a database of all valid 9x9 sudoku combinations).
Re: Sudoku Solving
#17Earlier quoted context omitted.
solving without trial and error at all.
That strikes me as extremely unlikely . I think the complexity class of Sudoko is NP-Complete (a quick google confirms it's not exactly NP but very close: http://11011110.livejournal.com/23221.html?thread=19381 -- complexity is the same as solving SAT problems which have only one unique solution)
I usually solve them by hand without guess and check, though occasionally, you get down to where there are pairs of values where you have no choice but to try one and see what works (or maybe I just need to figure out more constraints to use).
Re: Sudoku Solving
#18Earlier quoted context omitted.
solving without trial and error at all.
That strikes me as extremely unlikely . I think the complexity class of Sudoko is NP-Complete (a quick google confirms it's not exactly NP but very close: http://11011110.livejournal.com/23221.html?thread=19381 -- complexity is the same as solving SAT problems which have only one unique solution)
Sudoku are designed so that there is always a correct move that does not require guesswork.
Re: Sudoku Solving
#19Earlier quoted context omitted.
solving without trial and error at all.
If you do the constraint propagation right, the number of trials and errors will be very small (and it will be only one trial and no errors for the easy ones). I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like. (apart from pathologic solutions like querying a database of all valid 9x9 sudoku combinations).
If you get down to trial and error at all, your best odds are 50/50. If it's easy enough to guarantee the right guess, it's not a guess.
Re: Sudoku Solving
#20Earlier quoted context omitted.
solving without trial and error at all.
That strikes me as extremely unlikely . I think the complexity class of Sudoko is NP-Complete (a quick google confirms it's not exactly NP but very close: http://11011110.livejournal.com/23221.html?thread=19381 -- complexity is the same as solving SAT problems which have only one unique solution)
[deleted]