Solved world's hardest sudoku with python

· 3 min read

Sudoku

Last week I posted how I can solve a zebra puzzle with the python-constraint library.

Is it possible to solve World’s hardest sudoku with this library? Sudoku is one of the most popular puzzle games of all time. The goal of Sudoku is to fill a 9×9 grid with numbers so that each row, column and 3×3 section contain all of the digits between 1 and 9.

World’s hardest sudoku puzzle can be found on this page.

Let’s solve it!

First I defined the board itself, some usefull variables and a neat function to print the board on the terminal.

from constraint import *
ROWS = 'abcdefghi'
COLS = '123456789'
DIGITS = range(1, 10)

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

def pretty_string(var_to_value):
    board = ''
    for rownum, row in enumerate(ROWS):
        for colnum, col in enumerate(COLS):
            board += str(var_to_value[row+col])
            board += " "
            if colnum % 3 == 2 and (colnum <8):
                board += '| '
        board += '\n'
        if rownum % 3 == 2 and (rownum < 8):
            board += '- - - + - - - + - - -\n'
    return board

Then I create some usefull variables. I can later use it to iterate over them. I create a list of all rows, all columns and all 3 by 3 squares that are present on a sudoku board.

VARS = [row + col for row in ROWS for col in COLS]
ROWGROUPS = [[row + col for col in COLS] for row in ROWS]
COLGROUPS = [[row + col for row in ROWS] for col in COLS]
SQUAREGROUPS = [
    [ROWS[3 * rowgroup + k] + COLS[3 * colgroup + j]
     for j in range(3) for k in range(3)]
    for colgroup in range(3) for rowgroup in range(3)
]

How I solve this? Here is the function. First add all the variables. This are all the cells. Each cell can contains values from 1 to 9. That is in the first for loop.

The second loop adds the hints we get from the board itself. If a value is filled in (not value 0), then that value is a constraint of our puzzle.

Loop now through all columns, all rows and all squares. Here the values should all be different. (from 1 to 9) Therefore the AllDifferentConstraint is used. This constraint enforces that the values for all given variables are different.

def solve(board):
    problem = Problem()

    for coord in [row + col for row in ROWS for col in COLS]:
      problem.addVariables([coord], DIGITS)

    for a,x in enumerate(ROWS):
      for b,y in enumerate(COLS):
        if board[a][b] != 0:
          problem.addConstraint(InSetConstraint([board[a][b]]), [x + y])

    for vargroups in [ROWGROUPS, COLGROUPS, SQUAREGROUPS]:
        for vargroup in vargroups:
            problem.addConstraint(AllDifferentConstraint(), vargroup)
    return problem.getSolutions()


solution = solve(board)
if (len(solution) > 0):
  print(pretty_string(solution[0]))
else:
  print("no solution found")

After running the code, I see the following solution:

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

And this is a correct solution. The library python-constraint is a library that can solve several problems if you can define rules and constraints.

References