Coming Back to Old Problems: How I Finally Wrote a Sudoku Solving Algorithm

Ali Spittel on June 26, 2018

Quick warning, this article will be part technical, part personal story, part cultural critique. If you are just here for the code and explanatio... [Read Full]
markdown guide
 

From how you described the school you went to, I can say that the education system in Saudi Arabia is the same. We don't have serious computer or programming classes. In best cases they would teach you how to use MS Office and that's it. I started learning programming earlier in my last year of elementary school. It was all self-learning. I kept studying and implementing some simple code using PHP and MySQL. A few years later I lost interest and gradually moved away from programming.

When I went to college I chose a major that is related to computers (MIS), and I was forced to go back to programming, specially since my graduation project was to design a whole system using Java by my own. Now I'm back again and studying so intensively. I'm happy to be programming and learning more stuff about it, but I still regret that I had stopped doing so for long years, I could've been a much better programming now.

Thank you for sharing this Ali (by the way Ali is a male name in Arabic :p)

 

Sounds familiar to me. I went to school in Mumbai (Bombay), India where they had 'computers' as a subject since 5th grade. They used to take us to a computer tab filled with computers in late 90s, running software from 1980s and let us play Dragon Ball and Pacman on those monochrome monitors. The syllabus used to start with the chapter 'Introduction to Computers', every alternate year and if consisted of repetitive things like "constants and variables". They made us memorize a few QBASIC programs with no clear explanation and we were supposed to 'spit' it out during our practical exams.

The entire environment was to make students believe that computers are boring, hard and the only good use they had was to play video-games.

It took me long to realize the potential of computer programming when I picked it up during my second year of college that was supposed to be based on Electronics Engineering. I find myself lucky to even realize how fun programming can be and it all happened in class when a teacher was pretending to explain us a C program that added two numbers. Majority of my classmates flunked the subject at the end of the term, probably because of the way the subject was presented (mis-represented) to us, but I have been writing programs since that day in 2004.

Adding to that, it is till today that I mostly focus on what I can make a computer do for me rather than to learn theory that makes it all sound more complicated than it is supposed to be.

 

The entire environment was to make students believe that computers are boring, hard and the only good use they had was to play video-games.

In retrospect every school I've been to, no matter how much they focused on programming, they always lacked the overall "if a computer can do it, why shouldn't it?" attitude, and were way too much focused on building imaginary systems instead of solving actual problems.

 

Once I ran into your GitHub account and I saw the sudoku repo I didn't open it though because I don't like spoilers hahaha so I decided to make my own sudoku solver that like your first version only solve easy ones...I tested it using the Gnome sudoku from ubuntu 14.04 and It solves easy and medium level of difficultly this is the repo github.com/lmbarr/sudoku-solver

PD: I didn't know about the backtracking algorithm, now I do know thank to you.

 

I will say that computer science programs don't tend to start in a way that allows people who didn't write code earlier in life to participate, which in a few years with computer science education policy changes may be okay, but for now eliminates people who grew up in small towns, who weren't interested in coding growing up, or who went to weaker high schools.

👏 My story to a T

Small town, the computer class was "Advanced Excel" (pivot tables and maybe vlookup), most of the school was on free lunch so computers at home weren't a thing... I'm still dealling with that feeling of not knowing a lick about anything anyone is saying.

I ended up in a couple programming classes due to my math program, but overall, it was just playing around (nothing to show of it either) while unemployed after graduation that helped show my interviewers that I knew how to Google and learn on the job enough to hire me.

 

Nice job! Always rewarding to go back and solve problems that stumped in the past. You know... now that I think about it... I'm not sure I ever succeeded at writing a Sudoku solver 🤔 Perhaps it's time to fix that for me, too!

 

Another one! I wasn't given a Sudoku solver to do as part of a class (I trained in engineering), but have done one recently simply because it's really interesting. Pretty sure this one is efficient (github.com/rantydave/sudoku), took a lot longer than a couple of hours :)

 

Amazing, the sudoku part almost exactly mirrors my experience.
I first wrote it in javascript, with sets of possible numbers for every cell and human-like non-destructive transforms being applied (only answers we are sure about). There were quite a few different transforms, because I picked a modified version of Sudoku which had these additional blob sum constraints, which were interesting because they were indeed sums and not sets of the [1,9] range.
🅱udoku
For the UI, it used Vue, but really the renderer was mostly handwritten svg. It solved the lesser difficulties, but then I got bored.
Later, I stumbled upon someone quoting the backtracking algorithm as described in wikipedia. So I implemented it in Rust, with the additional constraints. The first time I wrote it, it solved them all in negligible time. I also tried it 3x4 and 4x4 boards. 4x4 gave noticeable time, and anything above 4x4 took too long to run.
Perhaps applying human-like transforms is computationally valuable at bigger board sizes to reduce the iteration space dramatically.
Maybe I'll still port those, or make the rust code an API or a WASM embed to the UI. Probably not though.

 

Thanks for sharing Ali. I think it's unfortunate that those first CS courses are often used to weed out students. I'm glad you persevered, even if you did end up dropping the CS minor!

 

here's the solution (and the explanation) by Peter Norvig, director of research at Google: norvig.com/sudoku.html

 

The are also some quite efficient, well studied solutions for this problem. For example, check this repo which uses AC3: github.com/msanpe/Sudoku-Backtrack...

 

Wow! Nice article!
Really loved reading it, ❤️
someday I'll implement this challenge as well!
But currently I don't even know how to play it!

 
 

To be clear, that was for the easy solver! Not the hard one -- that took a few hours + cleanup

 

Interesting story! Puzzles are fun.

I am not a software developer, but would like to share a simple method to use excel to solve SUDOKU.

It only uses addition and substitution, with no guessing, and only the 81 cells.

Only formulas, no macros or programs.

All puzzles, including "the world's hardest" have been solved.

Let me know if you have interest.

Thanks

code of conduct - report abuse