About a month ago, when I saw couple of people I know (who shall remain nameless) solving sudoku, I thought to myself “I can probably code a sudoku solver before they can finish this”. I didn’t have a computer there and then, but I saw how long it took them (about an hour or so), and I when I came home, I took up the challenge.

The language of choice was Python – since I wasn’t going at it by “brute force,” and instead I was going to use simple deduction methods, I was sure this wouldn’t consist a problem. Also, I thought I might as well solve it for an n by n sudoku (we usually solve for 3×3).

#### Neighborhoods, Adjacency and Potentials

A simple concept I’ll be using is neighborhood. Any single row, single column, or a n by n sub-square is defined as a *neighborhood*. A spot (x,y) is said to be *adjacent* to another spot (x’,y’) if they are both included in some neighborhood. For any spot (x,y) we have *potentials* – a value v will be in (x,y)’s potentials if no adjacent spot to (x,y) has the value v. Intuitively, these are the values that can potentially be in (x,y).

**Step 0 – Just Modeling**

First thing I did was model the environment – with spots, potentials, and neighborhood calculation.

**Step 1 – Strikeouts **

Next thing was placing a set_value(x, y, value) function to the model. The only “extra” I added, was that once you set a value in a spot (x,y), it goes to all neighborhoods of (x,y) and strikes out the value from the potentials. This makes very obvious sense, in sudoku you can’t have one value twice in the same neighborhood. With this in hand, the sudoku solver could already solve the easy sudoku, in 0 time.

**Step 2 – Existence**

Before we used a simple rule of thumb “one neighborhood cannot have two spots with the same value”. Since the size of each neighborhood is n^{2}, and there are n^{2} possible values, it necessarily asserts a second rule – “each neighborhood will have each value once”.

So we can define an “existence-check”: for each neighborhood N, and each value v, check how many spots in N have v in their potentials. If it’s only one, then voila – that spot will be awarded with that value. Applying the existence checks repeatedly, our sudoku solver could already solve the medium and hard sudokus, also in 0 time.

**Step 3 – Guessing**

Having the sudoku solver beating the hard sudokus, I was feeling rather confident – so I downloaded a “very hard” one, and fed it to the solver. The results were surprising – no success! Looking at the printout of the solver’s “status,” I realized what was the problem – a point arrived in which neither the strikouts or existence checks helped. In fact, there were spots with two potential numbers, and a guess needed to be done. Notice that this will happen in manual solving too – you’ll need to pencil in guesses at some point (for very hard sudokus).

There was nothing that could be done – so I implemented a backtracking method that takes guesses with the smallest branches (try to eliminate as much as possible, and once arrived to a spot with two potentials, take a guess). Notice that practically, the depth of this backtracking couldn’t be more than two or three – since it would take insanely amount of time for the manual solver. However, having the privileges of a machine, I left it unlimited.

The result was a success – I could now solve *any* sudoku in 0 time.

The code can be found here. Overall, it took a bit more than my wager (I think it totaled at about two hours), but it still was fun. Once I was done, I snooped around the internet and saw that there are many sites that do it, and they discuss “methods” and so forth.

I am still writing this here because I think there’s something nice about my solution – it uses only two trivial rules, and manages to solve the hardest sudoku, in 0 time, in a slow environment like python. It is my hope it’ll be helpful to somebody to spite sudoku-players.

## Leave a Reply