Solve sudokus automatically — and naturally

I sometimes do sudokus in the newspaper, and most of the time I can’t solve them, it is because I’ve messed up. So I sometimes think about how write some code to solve a sudoku methodically, to avoid these kinds of mistakes.

Writing code that solves a sudoku using brute force, or recursion, is relatively straight forward, there are some examples out there (for example this one). However, I don’t want something that solves a sudoku using steps that I couldn’t ever replicate — I want something that does steps I could do, and shows me how it does them.

So, inspired by the link above, I decided to work on a solver that does what I do when I solve them. The basic steps I use are:

  1. Filling in the empty boxes with all the numbers that a square could be
  2. If a cell has a single number in it, then that number can’t be in any other cells in the row, column or box.
  3. If a group of n cells in a row (or column or box) have just n digits between them, those n digits can’t be anywhere else in the row (or column or box)
  4. If a number is only in one row (column) of a box, it cannot be in that row (column) in any other boxes.

In fact, as I thought about it, rule 2 is just a special case of 3.

I haven’t ever seen a sudoku that I couldn’t solve with these steps. Sure, one could create a sudoku grid that couldn’t be solved with these steps, but I’d most likely find it unsatisfying (and impossible to do on paper). So, I tried to code these steps, and see how I went. (If I find any satisfying sudokus that can’t be solved using this method, then I might look at enhancing my code to handle them.)

My starting point is the raw table, eg:

Image for post
Image for post

I then have a function preparesudoku() that populates fills all the 0’s with all the possible values:

a function that works out the maximum number of digits still present, and one to print the sudoku:

Next I have a function getgroup() which gets a row or col or box from the sudoku. This function includes the location of each of the cells it has brought back:

Next I have a function for step 3 above, ie it goes through a group, and for each group of ‘size’ elements, if there are only ‘size’ different numbers between them, it deletes those numbers from every other cell in the group.

I wrap this function in a calling function cleanarrays():

Finally, I have written some code for step 4. It is pretty ugly, sorry.

So, when I want to run this on a sudoku, I run the following lines of code:

This outputs:

I’ve tried this algorithm on a few sudokus on http://websudoku.com/, even evil level ones, and it has managed to solve them all. Obviously that doesn’t guarantee it will work on every sudoku — do let me know if you find one that you think should be solveable with pure logic like this, that my algorithm isn’t able to solve.

And please don’t judge me on my python code, I mainly just wanted something to show someone, and figured other people might be interested. I have also included the code in my public github repository.

Fascinated by what makes societies and markets work, especially in sustainable energy. http://guylipman.com.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store