Hey everyone, I have been following Handmade Hero somewhat silently since the beginning (though you might have seen me as XEnDash a couple of times asking questions on the stream) and i really like it so far. I have been inspired by how simple and effortless Casey makes complicated subjects look simple and elegant in code.
I don't do much coding but on/off on my free time I have been trying to make a simple sudoku solver and i am very proud of the result.
you can check or fork the repository here:
https://github.com/XEnDash/Sudoku
the entire code is in a C file less then 400 lines long. it doesn't go very far with functionality but it's meant for programmers anyway.
please tell me what you think!
I don't do much coding but on/off on my free time I have been trying to make a simple sudoku solver and i am very proud of the result.
you can check or fork the repository here:
https://github.com/XEnDash/Sudoku
the entire code is in a C file less then 400 lines long. it doesn't go very far with functionality but it's meant for programmers anyway.
please tell me what you think!
So you are filling board with all possible combinations of numbers and checking if it is valid solution?
There exists better algorithm called Dancing Links. It's very nice, easy to implement and much faster algorithm. Long time ago I have implemented in C++, but not sure if I have that code available somewhere.
Here's original paper from Donald Knuth for this algorithm: http://arxiv.org/pdf/cs/0011047v1.pdf
Here's another explanation: https://www.kth.se/social/files/5...HLaestanderMHarrysson_dkand14.pdf
Here's explanation of algorithm with C code: http://uaasoftware.com/blog/demos...als/dancing-links-solving-sudoku/
There exists better algorithm called Dancing Links. It's very nice, easy to implement and much faster algorithm. Long time ago I have implemented in C++, but not sure if I have that code available somewhere.
Here's original paper from Donald Knuth for this algorithm: http://arxiv.org/pdf/cs/0011047v1.pdf
Here's another explanation: https://www.kth.se/social/files/5...HLaestanderMHarrysson_dkand14.pdf
Here's explanation of algorithm with C code: http://uaasoftware.com/blog/demos...als/dancing-links-solving-sudoku/
I have heard about that algorithm, but decided to do the brute force method first since i don't have a lot of experience with recursive backtracking algorithms. and also because in the stream Casey says it is better to first make the simplest implementation and then optimize. like he is doing with the sorting algorithm right now.
An interesting note is that the problem of the brute force algorithm isn't speed, but memory. Since you only do comparison and no arithmetic even on old slow processors it should run well. And further optimizations can be done like shorts instead of ints and organize the data in a cache friendly manner. The problem is that since the algorithm is recursive and backtracks a lot the stack get's filled up very fast.
An interesting note is that the problem of the brute force algorithm isn't speed, but memory. Since you only do comparison and no arithmetic even on old slow processors it should run well. And further optimizations can be done like shorts instead of ints and organize the data in a cache friendly manner. The problem is that since the algorithm is recursive and backtracks a lot the stack get's filled up very fast.