While the Node.js and testing portion of this project was rather straight forward, I have to say writing a sudoku solving algorithm tied me up for days. I was curious to hear from others if they were able to write an original algorithm, or if they had to google a workable solution (not copying code, just researching the method).
I like to solve Sudoku, so had an idea of what to look for in a solution, basically checking for slots that have just 1 workable value. That solved all the sample puzzles provided, but if I grabbed a hard puzzle online, it would only get half way through. I added algorithms to isolate possible positions in individual rows/columns/regions, that got through a few more, but not a lot. Proceeded with checking for double value spots, which resulted in embedded for-loops over 6 levels deep, a bunch of multidimensional array comparisons, and a headache. Still it couldn’t solve hard puzzles that the sample solution could.
Finally I caved and researched general methods, and what exactly a backtracking algorithm is. I kept my original code, but added a section I entitled ‘logic has failed, time for brute force’ that picks up where the others left off, and now it solves any puzzle I can throw at it.
Anybody else run into this issue with this project? Anybody come up with a non-backtracking solution?
I also found that the sample solution couldn’t solve hard to expert level puzzles begging the question how far were we expected to take this. Does anyone know what method the sample solution used?
I think the puzzles you were asked to solve were enough.
There is the idea of “gold plating” - building it better than it needs to be. If someone comes and asks you to write a function to return the if the current year is a leap year, you do that. You don’t build them a function that will also work for the Julian calendar and convert from other calendar systems and accept years written in other number bases, etc.
In the instructions you were told to:
- See the
puzzle-strings.js file in
/controllers for some sample puzzles your application should solve
That should tell you what you need to know. Build the simplest app that can reliably do that. That is the MVP (minimum viable product).
But on solving this in a broader sense, for a challenge like this, there are different issues:
solve the algorithm
understand the problem
device a method
be able to express that method in logical steps
code the solution
Is it reasonable to expect someone to become an expert in sudoku to solve this? On a basic level of a few holes, sure. It should be able to solve missing singles. What about naked pairs and x-wings? If I had to write a function to calculate gas pressure, am I expected to derive Boyle’s Gas Law on my own? Or can I look that up? I think it is a spectrum - there are algorithm challenges where you should be expected to figure out the algorithm completely, like doing a puzzle. And then I think there are others where it is unreasonable to expect someone to reinvent the wheel.
And remember that this is in the quality assurance section, not an algorithm section. In that context, I think doing some research makes sense.
Thanks for the response. I do believe it said you needed to solve more than just the sample puzzles, and said we needed to come up with the logic, which suggested they didn’t want a lot of googling to determine the answer…
The `solve` function should handle solving any given valid puzzle string, not just the test inputs and solutions. You are expected to write out the logic to solve this.
…but seemed a pretty complicated problem to solve once you get into the trenches of it… until someone whispers ‘backtracking’ in your ear, lol.
Backtracking to me seems a silly solution, just throwing the kitchen sink at it until something sticks :). My Sudoku-Solver file ended up being 462 lines of code, only 60 lines of which were the backtracking algorithm, lol.
Definitely glad for the experience. Its rare to find a problem where recursion isn’t overkill, so was a fun algorithm to write. Do you know if there is a non-backtrack solution? I haven’t gone through the freecodecamp walkthrough of this problem yet as I still have to write the testing section and final refinements before submitting, but maybe they go over the algorithm there.
I mean, we’d have to build program in the logical methodologies that humans use to solve. Like, look singles in rows, columns, and nonets. Maybe you come up with a way to do Snyder notation. You figure out a way to look for x-wings, etc. You keep looping those until you pass through without any changes. That would be programming it to solve it like a human. You’d have to learn all of the advanced Sudoku techniques and code them into your algorithm. Without that, I imagine you’re just left with testing exhaustively, and you’re going to want to optimize that with backtracking.
Yep, thats what the first 400 lines of mine does, got as far as building arrays of all possible values and comparing those for possible eliminations, but that code was so messy I assumed I was doing it wrong.
I noticed when looking for guidance that previously for this project you were also expected to build the user interface as well…Current project all the UI stuff is already in place. Wonder when/why they changed that.
Yeah, that’s the tricky part about algorithms. Sometimes it takes some work to find the “sexy” solution.
I had to read the Wiki on Sudoku algorithms but I wrote the code myself. I would have never been albe to come up with that backtrack algorithm on my own lol
This is one of the most memorable challenges. I checked my post regarding it and it looks like in few days ill have a one year anniversary since I completed it. I recall i was very proud of it, as I managed to write the logic, altho this took great effort and lot of struggle. It is important to note, key factor to be able to code it, is actually having experience in sudoku solving, otherwise I dont think thats very likely to be completed on your own. I also recall, initially my code could only solve simple sudokus and then i improved it with more extensive algorithm, which made it possible to solve all puzzles i found on my fathers newspapers.