Solving Sudoku with Python

Probably not the most exciting thing for the common people, but I love to solve Sudokus. And after going through a few books, I asked how I would solve them using a python script.

First, I had to learn Python. Approaching the language is really easy, but I suspect that mastering it is a different story. Anyways, after a few hours of practice, I was able to run a few things.

Now solving the sudokus. I basically took a number of different grids and started looking not at the resolution, but at the process behind the resolution. I found I use four techniques.

1. Pruning - that's the basic: if a value is known, remove that from the possibilities for each cell on the same row, column and square.
2. Only occurence finding - in a line, it may occur that a single cell contains a given digit. For example, if in a line you need a 2, a 4 and a 5, and the first cell allows [2,4], the second [2,4,5] and the third [2,4], 5 goes into the second. 
3. Values in a row (or column) - in a square, it may happen that 1 or more values are on a single row (resp. column), which means that that or these values can be removed from the same line (resp. column) on the square-line (resp. square column).
4. Pair pruning - if two cells contain a pair of values that appear only in these two cells plus additional values that also appear on other cells, the other values can be removed. 

So far, I was able to solve all the grids I could lay my hands on. If you have a grid (okay, let's specify a grid that can be solved!) that defeats my script, feel free to send it.

How to use it?

There is nothing fancy: it's a CLI script (as of now). Download the two files from my repository, and in the same folder, type at the prompt "python", then:

import sudoku as s
A=['...1...6.', '5.9.....7', '.....3..5', '...58.7..', '13..7..54', '..7.42...', '6..8.....', '9.....6.2', '.8...9...']
s.solvesudoku(A)

solvesudoku() takes a list containing 9 strings each of 9 characters. Each non digit or null digit character is treated as an unknown cell in the grid.

It will solve the following grid:

+-------+-------+-------+
|       | 1     |   6   |
| 5   9 |       |     7 |
|       |     3 |     5 |
+-------+-------+-------+
|       | 5 8   | 7     |
| 1 3   |   7   |   5 4 |
|     7 |   4 2 |       |
+-------+-------+-------+
| 6     | 8     |       |
| 9     |       | 6   2 |
|   8   |     9 |       |
+-------+-------+-------+

And it will return the solution:

+-------+-------+-------+
| 3 2 4 | 1 5 7 | 9 6 8 |
| 5 1 9 | 2 6 8 | 3 4 7 |
| 7 6 8 | 4 9 3 | 2 1 5 |
+-------+-------+-------+
| 4 9 6 | 5 8 1 | 7 2 3 |
| 1 3 2 | 9 7 6 | 8 5 4 |
| 8 5 7 | 3 4 2 | 1 9 6 |
+-------+-------+-------+
| 6 7 1 | 8 2 4 | 5 3 9 |
| 9 4 3 | 7 1 5 | 6 8 2 |
| 2 8 5 | 6 3 9 | 4 7 1 |
+-------+-------+-------+

The function solvesudoku() returns True if the grid has been solved and False otherwise: cannot solve, not enough lines or characters and so forth.

Have fun!