# Sudoku Solver in Python

Interestingly I'm writing this blog post through JupyterLab, as opposed to strictly through R. Reason being, RStudio and the reticulate package have a bit of development left to go before knitr, rmarkdown, and RStudio work well together (you can reference this issue that I had a problem with here.

Nevertheless, I'm still hosting this markdown document from JupyterLab to markdown and then through my own Academic Hugo webpage through RStudio… its a party really.

So, let's start. The point of this was to learn a bit more about how Python iterates and how something comparable can be handled in R. In doing so, there are some particulars that I'll touch on, but I would certainly say there is benefit of diving in yourself and writing it out. There is bound to be something you can learn by doing so.

I originally got interested in this and adapted (stole… or borrowed) most of this code from a youtube.com video from Computerphile.

The above puzzle can easily be objectified by addinging it into Python as a series of lists.

```
board = [[5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9]]
```

Although, it looks pretty worthless when printed.

```
print(board)
```

```
[[5, 3, 0, 0, 7, 0, 0, 0, 0], [6, 0, 0, 1, 9, 5, 0, 0, 0], [0, 9, 8, 0, 0, 0, 0, 6, 0], [8, 0, 0, 0, 6, 0, 0, 0, 3], [4, 0, 0, 8, 0, 3, 0, 0, 1], [7, 0, 0, 0, 2, 0, 0, 0, 6], [0, 6, 0, 0, 0, 0, 2, 8, 0], [0, 0, 0, 4, 1, 9, 0, 0, 5], [0, 0, 0, 0, 8, 0, 0, 7, 9]]
```

Thankfully, `numpy`

can translate it back into a neat matrix for our viewing pleasure.

```
import numpy as np
print(np.matrix(board))
```

```
[[5 3 0 0 7 0 0 0 0]
[6 0 0 1 9 5 0 0 0]
[0 9 8 0 0 0 0 6 0]
[8 0 0 0 6 0 0 0 3]
[4 0 0 8 0 3 0 0 1]
[7 0 0 0 2 0 0 0 6]
[0 6 0 0 0 0 2 8 0]
[0 0 0 4 1 9 0 0 5]
[0 0 0 0 8 0 0 7 9]]
```

One thing to note, as compared to other languages, Python counts the first row and column as `0`

not `1`

. This can be confusing, but you'll see my use herein of 0-9 or 1-10 to tell Python to iterate through these series. I've also tried to mention this throughout the code comments within the chunks.

```
def possible(y, x, n) :
global board # Identify 'board' as a global variable
# Check if the `n` number is at the y,i coordinate
for i in range(0,9) :
if board[y][i] == n :
return False
for i in range(0,9) :
if board[i][x] == n :
return False
x0 = (x//3)*3 #floor divisor - returns the whole number divisor
y0 = (y//3)*3
# For each cell in the given square, is x0 or y0 = n?
for i in range(0,3) :
for j in range(0,3) :
if board[y0+i][x0+j] == n :
return False
return True
```

0 through 9 is used. row (y) and then column (x)

As an example, the top left position, x = 0 and y = 0, is 5.

```
board[0][0]
```

```
5
```

Next, you'll notice the `possible`

function serves to identify values that are possible within each row, column, and 3 x 3 square.

For instance, row 3 (the forth from the top) and column 1 (second from the left) is identified by the middle left most 3 x 3 square.

```
board[3][1]
```

```
0
```

```
possible(3,1,1)
```

```
True
```

Here, a 1 is plausible.

Next, we draft a `solve`

solution to iterate through the `possible`

options.

```
def solve() :
global board
# Find a blank cell in the matrix
for y in range(9) :
for x in range(9) :
if board[y][x] == 0 :
for n in range(1,10) :
if possible(y,x,n) :
board[y][x] = n
solve() # Recursion
# If it doesnt work, we make it zero again.
board[y][x] = 0
return
# No more zeroes, so we print the final matrix out.
print(np.matrix(board))
# Sometimes there are alternative solutions...
input("Do you want more solutions??")
```

Sometimes, as it may be, with some solutions, there are more than one possible answer to the question. So running it again may produce a slightly different answer.

```
solve()
```

```
[[5 3 4 6 7 8 9 1 2]
[6 7 2 1 9 5 3 4 8]
[1 9 8 3 4 2 5 6 7]
[8 5 9 7 6 1 4 2 3]
[4 2 6 8 5 3 7 9 1]
[7 1 3 9 2 4 8 5 6]
[9 6 1 5 3 7 2 8 4]
[2 8 7 4 1 9 6 3 5]
[3 4 5 2 8 6 1 7 9]]
Do you want more solutions??
```

So, ultimately, this post has shown how to use recursion (cycling a function over and over again by calling itself) to work through a multiple outcome problem. Although interesting, use of this procedure may be limited to instances where there are multiple options, but only one or two final solutions. Interesting none-the-less.

As stated earlier, a similar solution is drafted in R here (which is coming soon!!.

Cheers!