I got stuck on the Sudoku Solver project. My code seems to work, it solves all the string in the puzzle-string.js file and reports as invalid some puzzles I fed it. But when I try to feed it the invalid string that the FCC tester uses: 9.9..5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
it seems to get suck after a while.
It runs until cell B8 and then the backtracking algorithm just stops to call back itself and I don’t understand why.
Here is my code for reference: code
Did anybody have the same problem?
Hi sanity, thank you for your reply.
I expect it to continue to substitute numbers until 9 and then going back a step and repeat. It should keep on substituting and going back and forth until it reaches the first empty cell again and discovers that none of the value is fine. At that point, it should return the object {error: "The puzzle cannot be solved"}.
What it really does, is substituting until 4 and then just stops.
I’m getting some mixed results on fork of your code, with tests turned on no error appears. While without tests there’s error about exceeding stack size due to recursion.
Did you consider to check, before trying to solve, whether the initial input puzzle is actually possible?
The initial puzzle has 2 nine’s in the first row, so it is not possible to solve. I expect the solver to give me back the object {error: "The puzzle cannot be solved"}.
It gives me back the correct results with other invalid puzzles, so I was wondering why it does not work with that particular one.
If it gives you exceeding stack size, I probably have to get back on the recursion controls, because it means they could be made more efficiently.
Thank you again for your time!
Yeah, double 9 makes it obvious it can’t be solved. However solver doesn’t leverage that with check if already placed numbers in puzzle makes sense, but proceeds to try to solve it.
Ok, I found an article about backtracking and it talks about the idea behind the sudoku solver.
The algorithm works under the assumption that the given puzzle respects the sudoku rules (no repetition in columns, regions, and rows). I only relied on the “Backtracking” section of the Wikipedia article about Sudoku solving algorithms, so I did not make that assumption.
Once I implemented the additional level of validation, I was able to pass the test.
Thanks again!