News for hackers. Stuff that matters.
Re:Solving Every Sudoku Puzzle (2006) by mxz3000 on Wednesday September 04, 2019 @04:13PM (#20880954)
Hmm it's weird. I tried my solver on it and it tells me that it can't find a solution (in 13 seconds). My solver is pretty well tested (on some very difficult sudokus as well). Maybe this guy's solver is bugged?
Re:Solving Every Sudoku Puzzle (2006) by lostcolony on Thursday September 05, 2019 @04:16PM (#20890288)
Yeah; the one I implemented used a different algorithm, and would have noted that there was no solution.

I basically just kept a "possibility space" for each empty cell (containing a list of all possible values it could be), started with the one with the smallest size > 0, tried a value as 'true', removed that possible value from all related cells (same row, column, 3x3), recursed. If an empty cell had a possibility space of 0, it would pop back off the stack, removing that prior 'possibility' and resume from there. If I ever got back to an empty stack, there was no solution.

I threw a few dozen puzzles at it, trying to pull ones that were hard both for humans and, ostensibly, for machines, but I never saw it take more than a couple seconds, and that in the most degenerate "had to try every possible permutation" cases. Hence why I really wish I'd kept the code to throw that one at.

Re:Solving Every Sudoku Puzzle (2006) by war1025 on Thursday September 05, 2019 @10:09PM (#20892429)
That doesn't seem any different than the algorithm my solver uses. From what a sibling poster commented, it looks like the thing that causes the trouble is that the square that makes it unsolvable basically lets you solve it down to just that square in many different ways, which then just ends up with you enumerating an absolutely enormous state space because the solvers don't have enough tricks built in to recognize it as an unsolvable board from the start.
Re:Solving Every Sudoku Puzzle (2006) by lostcolony on Monday September 09, 2019 @11:11AM (#20918898)
Right; I am saying it's different than the original post's because it -could- handle unsolvable boards (maybe I misread; it sounded like that was an unhandled case in it).

I knew that there could be degenerate cases like that that would cause it to take O(n!) time, but the ones that I ran into still didn't take -that- long, which was what surprised me.

Re:Solving Every Sudoku Puzzle (2006) by war1025 on Wednesday September 04, 2019 @05:07PM (#20881418)
I guess you should be able to verify pretty easily that the solution he posted is valid, right? But I guess he didn't actually post the solution his code came up with, so who knows...
Re:Solving Every Sudoku Puzzle (2006) by knorrke on Wednesday September 04, 2019 @07:05PM (#20882262)
Well the text says it doesn't have a solution, so...
Re:Solving Every Sudoku Puzzle (2006) by war1025 on Wednesday September 04, 2019 @07:57PM (#20882591)
Hadn't noticed that. I assumed when he said it to 1400 seconds then it did come up with a solution. Makes me feel less bad then :)
Re:Solving Every Sudoku Puzzle (2006) by mxz3000 on Thursday September 05, 2019 @02:26AM (#20884320)
Oh that explains everything. That's what I get for being too lazy and not reading the fine print I feel happy now at the fact that my solver is about 2 orders of magnitude faster than his!
Re:Solving Every Sudoku Puzzle (2006) by barbegal on Wednesday September 04, 2019 @05:18PM (#20881531)
It's trivial to know that it has more than one possible solution since less than 8 of the possible numbers are on the initial board meaning any valid solution that is found has a mirrored solution with all of one number swapped for all of another number.
Re:Solving Every Sudoku Puzzle (2006) by mxz3000 on Wednesday September 04, 2019 @05:59PM (#20881842)
Sure. My solver is designed to return the first solution it finds (it doesn't check for solution uniqueness, just that there is one). However currently my solver is saying that it can't find _any_ solution at all.
Re:Solving Every Sudoku Puzzle (2006) by war1025 on Wednesday September 04, 2019 @05:32PM (#20881642)
Theoretically a board with multiple solutions should be easier to find a solution for though, right?
Re:Solving Every Sudoku Puzzle (2006) by whataboutist on Wednesday September 04, 2019 @06:44PM (#20882122)
Theoretically a board with multiple solutions isn't a sudoku.