Your solve() function looks a little problematic to me.
First, just as a matter of clarity -- you are returning an int variable "solutions" which seems like its suggesting the number of solutions found, but this isnt quite right is it.. You really just want to return a bool of true if a solution was found, or false if not. The recursive calls must eventually end in a true or a false, which gets propagated back up to be returned. You never want to find more than 1 solution, and your algorithm explicitly stops searching once it finds one solution. Having it look like its adding up solution counts makes it harder to understand. This makes lines like 40 particularly confusing since you really should be saying "return false" -- there is no way to get there with a solutions>0.
And now looking more into the loop, the idea is to recursively fill in one value, and then call solve on the new grid with the filled in value, each recursive call filling in one additional square of the grid.
(you are doing some optimization on what ORDER you try to fill in squares based on looking at ones with least options first -- maybe document the reasoning and approach more; that's not important).
So the idea of this recursion is that it should return FALSE if you ever call solve() with a grid where there is a hole (blank square) that CANNOT be filled in. That false will return to the caller who will continue looping checking for a different value to put into the square before it recursively checks for another solution. That looks right to me.
And then you need it to return TRUE when it has SOLVED the grid COMPLETELY.
But looking at the code, i see what MIGHT be a problem.
Your last lines of solve say "
# if we got this far then we've solved it! solutions += 1 return solutions
"
But let's look how we can get down there.
One way is if there are no more holes -- that's what we want. When there are no holes, return TRUE, we found a solution.
But also i think you can get there if your PRELIMINARY sorting operations identifying possibilities creates a situation where some illegal spot has no good options. this should NOT be returning a true case(!)
I think the better solution would be to set some flag line at line 14: flagFoundHole = true;
then somewhere before line 18 you could just say
If (!flagFoundHole) {
// no holes found, so this represents a solution!
return true;
}
Recent Posts
