Byron Peebles ◊ Blog

A small Sudoku solver in Python

About six years ago, I decided to write a simple Sudoku solver in Python and then try to get it as small as possible. I recently looked at it again, and after shaving off a few bytes, wanted to share. (GitHub repo if you want to just read that: bpeebles/sudoku.py.)

While I was still drafting this, I learned that the "father" of Sudoku, Maki Kaji (NYT), passed away.

First off, here’s the oldest minified version I have, at 396 bytes:

sudoku_min.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import sys
R=0,1,2
def v(b):x=filter('0'.__ne__,b);return len(x)==len(set(x))
def S(b,n):
 if'0'!=b[n]:return S(b,n+1)
 b=list(b)
 for t in'123456789':
  b[n]=t
  for j in range(9):t=v(b[9*j:9*j+9])and v(b[j::9])and t
  for x in R:
   for y in R:u=x*3+y*27;t=v(b[u:u+3]+b[u+9:u+12]+b[u+18:u+21])and t
  if t:
   if'0'not in b:return b
   t=S(b,n+1)
  if t:return t
print''.join(S(sys.argv[1],0))
Note
 It reads the board from the first command line argument, with full rows one after each other in a single string, 0 means 'empty', which is a fairly standard way to share Sudoku boards. It also prints the first solved Sudoku board to stdout if it has a solution, otherwise nothing. To see more boards, they can be found pretty easily via searches. A couple of places I’ve used: SudokuWiki.org: Sudoku Solver or Rosetta Code: Sudoku.

It’s a fairly simple recursive solver. It starts by given the starting board and when it finds a space that is empty (0), it populates it with 1, if that is a valid board, print and exit. If not, move to the next space and do that same process again. If it runs out of spots to try, it goes back up one level and then tries 2 in the most recent spot and descends back down. Boards exist that make this go quite deep in stack depth and take quite long to solve.

When returning to this, I first just tried to run it.

$ python3.8 sudoku.py 123456789456789123789123456000000000000000000000000000000000000000000000000000000
  File "sudoku.py", line 16
    print''.join(S(sys.argv[1],0))
         ^
SyntaxError: invalid syntax

well, I guess I need to upgrade to Python 3 since it’s a new decade, so I made the changes below:

  • filter now returns an iterator, so convert it to a list so len works.

  • print is now just a built-in and not a statement so add `()`s.

-def v(b):x=filter('0'.__ne__,b);return len(x)==len(set(x))
+def v(b):x=list(filter('0'.__ne__,b));return len(x)==len(set(x))
-print''.join(S(sys.argv[1],0))
+print(''.join(S(sys.argv[1],0)))

And it works:

$ python3.8 sudoku.py 123456789456789123789123456000000000000000000000000000000000000000000000000000000
123456789456789123789123456214365897365897214897214365531642978642978531978531642

Making it smaller

While reading a bit about this, I saw some examples used exit to finish and I looked it up and it’s a kind of odd built-in in Python I hadn’t really know about that exits with the provided exit code, which I knew. But, if you provide it with a string, it sets the exit code to 1 and prints the string to stderr, which seems like a good compromise.

So I did:

-  if t:return t
-print(''.join(S(sys.argv[1],0)))
+  exit(''.join(t))
+S(sys.argv[1],0)

which gets us down to 391 bytes. I then realized that the if blocks around probably can be shorter as a boolean-statement since Python does their boolean operators using short-circuit evaluation and returns the "final" value evaluated instead of a boolean:

-  if t:
-   if'0'not in b:return b
-   t=S(b,n+1)
-  exit(''.join(t))
+  t=t and('0'not in b and exit(''.join(b))or S(b,n+1))

at 379 bytes, smaller for sure.

The final statement reads kind of like:
If there are no '0's in b, print the board and exit, otherwise let t be equal to S(b,n+1) (the "next" board).

I decided to try using a if-else expression to see how long that ends up being and got to this:

-  t=t and('0'not in b and exit(''.join(b))or S(b,n+1))
+  t=t and(S(b,n+1)if'0'in b else exit(''.join(b)))

which gets the size down to 375 bytes.

More information

You can see an annotated version of my original attempt or the current annotated version.

My implementation only prints out the first solution it finds, some prints out all of them, which is nice. It’s not particularly the fastest. Like this board takes over a minute with PyPy (which is faster than CPython in my tests for this) on my i9-9880H CPU @ 2.30GHz:

850002400720000009004000000000107002305000900040000000000080070017000000000036040

A classic, early-ish solver and fairly well-known and document is by Peter Norvig Solving Every Sudoku Puzzle. (I haven’t ever read the whole thing since I had wanted to write my solver mostly, not entirely, from my known sense of the rules and a priori knowledge of solving problems like this.) The smallest Python Sudoku solver I’ve run across is 169 bytes at ShortestSudokuSolver. But, I’m still fairly happy with my implementation such as it is.

Current version

You can see the current version in my GitHub repo bpeebles/sudoku.py. Here it is as of the last update of this post:

sudoku_min.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import sys
R=0,1,2
def v(b):x=list(filter('0'.__ne__,b));return len(x)==len(set(x))
def S(b,n):
 if'0'!=b[n]:return S(b,n+1)
 b=list(b)
 for t in'123456789':
  b[n]=t
  for j in range(9):t=v(b[9*j:9*j+9])and v(b[j::9])and t
  for x in R:
   for y in R:u=x*3+y*27;t=v(b[u:u+3]+b[u+9:u+12]+b[u+18:u+21])and t
  t=t and(S(b,n+1)if'0'in b else exit(''.join(b)))
S(sys.argv[1],0)

Feel free to suggest improvements. Or, perhaps better, let it inspire you to write your own and let me know about it!

❦