7 ms·
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
by mxz3000 7y ago
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?
- deleted 7y ago[deleted]
- war1025 7y agoI 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...
- barbegal 7y agoIt'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.
- war1025 7y agoTheoretically a board with multiple solutions should be easier to find a solution for though, right?
- whataboutist 7y agoTheoretically a board with multiple solutions isn't a sudoku.
- mxz3000 7y agoSure. 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.
- knorrke 7y agoWell the text says it doesn't have a solution, so...
- war1025 7y agoHadn'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 :)
- mxz3000 7y agoOh 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!
- deleted 7y ago[deleted]
- lostcolony 7y agoYeah; 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.
- war1025 7y agoThat 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.
- lostcolony 7y agoRight; 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.