4 ms·

I left my solver running for 28 minutes and it never found a solution to that puzzle. Guess whatever corner case it's hitting in his program is the same as my p

I left my solver running for 28 minutes and it never found a solution to that puzzle. Guess whatever corner case it's hitting in his program is the same as my program runs into.

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 ago
  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...
- barbegal 7y ago
  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.
  - war1025 7y ago
    Theoretically a board with multiple solutions should be easier to find a solution for though, right?
    - whataboutist 7y ago
      Theoretically a board with multiple solutions isn't a sudoku.
  - mxz3000 7y ago
    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.
- knorrke 7y ago
  Well the text says it doesn't have a solution, so...
  - war1025 7y ago
    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 :)
    - mxz3000 7y ago
      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!
- deleted 7y ago
  [deleted]
- lostcolony 7y ago
  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.
  - war1025 7y ago
    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.
    - lostcolony 7y ago
      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.
53x15 7y ago
It's easy to see why this puzzle has no solution. Looking at columns 4-6 we see that none of the digits 1,5,6 can occur in cells G4,H4,I4 or G6,H6,I6. So some permutation of these digits occupies G5,H5,I5 and all digits other than 1,5,6 can be eliminated from these cells. But we also see that all the digits 1,5,6 have already been placed in row G, leaving no candidates for G5. It's also easy to see why this presents a problem for the Norvig solver (and many solvers like it). If you squint at the algorithm you'll see that it behaves like DPLL (https://en.wikipedia.org/wiki/DPLL_algorithm https://en.wikipedia.org/wiki/DPLL_algorithm) given a CNF encoding of the Sudoku exactly-one constraints. In this scheme constraint propagation only occurs via unit resolution. i.e., when a positive clause is reduced to a single literal because the domain of a cell is reduced to a single digit or a unit/group is reduced to having a single place for a given digit. In Sudoku land these are known as naked and hidden singles. Unfortunately, the conclusion that none of 2,4,7,8,9 can occupy G5 arises from the interaction of multiple non-unit clauses. It is simply not reachable by unit resolution. As a result, the conflict won't be discovered until the algorithm actually attempts to assign G5, and, since there are many cells that initially have fewer possibilities than G5, this is not likely to happen early in the search. Some of the faster solvers can handle this by adding checks for "locked candidates", or by representing the logic in a way that's equisatisfiable, but that makes these inferences available to unit resolution. In such cases this puzzle is recognized as unsatisfiable in microseconds.

I left my solver running for 28 minutes and it never found a solution to that puzzle. Guess whatever corner case it's hitting in his program is the same as my program runs into.

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 ago
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...
barbegal 7y ago
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.
- war1025 7y ago
  Theoretically a board with multiple solutions should be easier to find a solution for though, right?
  - whataboutist 7y ago
    Theoretically a board with multiple solutions isn't a sudoku.
- mxz3000 7y ago
  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.
knorrke 7y ago
Well the text says it doesn't have a solution, so...
- war1025 7y ago
  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 :)
  - mxz3000 7y ago
    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!
deleted 7y ago
[deleted]
lostcolony 7y ago
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.
- war1025 7y ago
  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.
  - lostcolony 7y ago
    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.

53x15 7y ago

It's easy to see why this puzzle has no solution. Looking at columns 4-6 we see that none of the digits 1,5,6 can occur in cells G4,H4,I4 or G6,H6,I6. So some permutation of these digits occupies G5,H5,I5 and all digits other than 1,5,6 can be eliminated from these cells. But we also see that all the digits 1,5,6 have already been placed in row G, leaving no candidates for G5. It's also easy to see why this presents a problem for the Norvig solver (and many solvers like it). If you squint at the algorithm you'll see that it behaves like DPLL (https://en.wikipedia.org/wiki/DPLL_algorithm https://en.wikipedia.org/wiki/DPLL_algorithm) given a CNF encoding of the Sudoku exactly-one constraints. In this scheme constraint propagation only occurs via unit resolution. i.e., when a positive clause is reduced to a single literal because the domain of a cell is reduced to a single digit or a unit/group is reduced to having a single place for a given digit. In Sudoku land these are known as naked and hidden singles. Unfortunately, the conclusion that none of 2,4,7,8,9 can occupy G5 arises from the interaction of multiple non-unit clauses. It is simply not reachable by unit resolution. As a result, the conflict won't be discovered until the algorithm actually attempts to assign G5, and, since there are many cells that initially have fewer possibilities than G5, this is not likely to happen early in the search. Some of the faster solvers can handle this by adding checks for "locked candidates", or by representing the logic in a way that's equisatisfiable, but that makes these inferences available to unit resolution. In such cases this puzzle is recognized as unsatisfiable in microseconds.