Hello!
I have tried to start the Sudoku Solver project, and I must admit it’s no easy one.
One part is figuring out the code, which is not what I’m currently seeking help for.
Another part is the logic/math behind this API.
Can anyone, no matter if you completed the challenge or not, perhaps share some inspiration on how to solve a Sudoku from a machine’s point of view?
If I were to solve a Sudoku in real life, I feel like I make many shortcuts that I can’t likewise do with a computer, such as guess which number is represented most etc. Having a computer do this for me, my current idea is as follows:
Using a bunch of loops, everything nested within a while loop. This while loop will check if there has been any changes made since the last execution of the loop and run as long as the new state of the Sudoku is not equal to the previous state (ie. once it finishes a loop without changing anything, the API will stop. If the Sudoku is still not solved, it will return an error message).
Inside this whole while loop, all spaces will be checked. When it hits an empty space, it will do the following:
Check all numbers from 1-9 to see if they can be placed within this space. When it returns valid for a number, this number will be added to:
An array that stores all valid numbers in one spot. If only one number is possible, the given number will be inserted into the Sudoku.
An array/object that stores the amount of times the number is valid in the region, the row and the column. If it is only valid for one space within either the region, the row or the column, the number will be inserted into the Sudoku.
Is this enough? I feel like this wouldn’t solve many Sudoku’s irl, but I am not sure
I hope one of you kind people have a good idea/some knowledge that you are willing to share
I have not done this challenge so I can’t comment on that. I can only comment on what I would do if I were building one.
My first thought would be Snyder notation. That could work for most simple puzzles, taking many passes, storing the information in a parallel data structure, going through each square and checking all three possibilities (row, column, square). There are other things you can check, but I’m not sure how to check things like hidden pairs and x-wings, but I’m sure there is a way.
But Snyder notation only notes if there are two possible places. This may just be a limitation of the human mind. Perhaps you could expand it - go through and create a list of all possibles for each square, based on the three cases. Then you start checking for squares with only one possible - as they are filled in, you eliminate those possibles from that row, col, and square. I think that would get most easy and even a lot of intermediate puzzles.
I will link some resources that you may find useful and I will also link a code wars challenge for build a sudoku solver should you like to try it out:
Thank you so much @kevinSmith and @caryaharper !
Very helpful, I will take a thorough look at these and consider what could be implemented and what will make it work for me!
