Python Sudoku Solver - Computerphile

Fun comes in many forms - playing puzzles, or writing programs that solve the puzzles for you. Professor Thorsten Altenkirch on a recursive Sudoku solver.


This video was filmed and edited by Sean Riley.

[dickjohnson]

It must ba a joy having him as teacher, he is so chill and methodical.

[spacemangmail]

Once you understand recursion you can understand recursion

[MatheusLeston]

1:38 wow he was able to say "recursion" without even moving his mouth, that's the real trick

[garethevans]

It's more fun to write a solver/ generator than it is to do the puzzles by hand

[jordanolson]

I really like Thorsten, he seems like a good guy.

[ThePolaroidPicture]

Does he have his own YouTube channel? I really enjoy the way he talks about problems. Makes them seem much easier than they really are.

[etienneschramm]

The Dancing Links algorithm, by Knuth, is one of the most beautiful algos I have ever seen. It works by abstracting away from the sudoku itself, and translating all the constraints into a matrix form, on witch you can apply a backtracking algorithm, in order to find a subset of lines with exactly one non-zero value in each column. The advantage is that it treats all constraints as equal.

You should absolutely do a video on solving Sudoku with Dancing Links. Moreover, you can show that by generalizing a problem, you can use exactly the same algorithm for Sudoku, Pentominos, Soma cube and many others.

[ylyassun]

The time when Targaryens not using Dragons anymore, They are using Python..

[songzh]

Dear Thorsten, I was your student and enjoy this video. As a Chinese, I want to tell that the later game is called Huarongdao. (华容道), The story is about a general of a kingdom escaping from a losing battle. I have some fun when I was a child with it.

[johantitulaer]

I was actually contemplating on making a sudoku solver myself as practice or not, but then seeing how it's done is just way too fun.

[edhofiko]

For those who wanted to learn more about this. The problem of solving sudoku can be generalized to a problem called Constraint Satisfaction Problem (CSP), CSP includes things from puzzle solving to real world problem like planning and scheduling.

[zuixyqw]

I remember i made my own sudoku solver in my late teens. I don't remember much but i remember part of it would track POSSIBLE numbers for each square. This video brought back a bit of my memory when i saw "possible" in the code.

[kchannel]

As someone who's learning Python I'm excited to try this project. I've learned to build my first LogisticRegression model, so I'm excited to to continue making progress.

[tomw]

This is really a clever little algorith for the problem. It's a bit too simple for my taste because it only prints out the solution while the solve() recursion is still running. After solve() is completed, the grid is in the state from the beginning again and the solution is lost. I slightly modified it by adding a returnvalue to solve() and some evaluation to keep the final result in the variable grid[ ][ ]. A while back I began programming a sudoku solver that should replicate the exact way I solve a sudoku on paper. It's still not finished because it struggles with the extra hard Sudokus. I like these Computerphile videos.

[DiegoPerezTenessa]

Great teacher, fun and entertaining for super tough concepts. Such an elegant solution too.

[NomenNescio]

At one time I wanted to learn java, so I wrote a sudoku solver in Java, with a gui to input the puzzle.

The principles of solving were basically the same as the python version, but Thorstens version were more elegantly written.

[avi]

He has so much more enthusiasm for computer science than 90% of my professors in the department. Lol.

[TonyBestOfficial]

You can use the built-in pprint function (from pprint import pprint) to pretty print data

[igorperfeitovivo]

I’ve tried to code it myself using my own logic on solving sudokus. It is far more complicated and frustrating to code, and this is where the beauty of his method resides.

[okawashingo]

I would like to watch your follow-up video about Knuth’s algorithm x and dancing links, considering a sudoku solver as a constraint satisfaction problem :)