5 ms·
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 e
by 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 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.