Solving Sudoku using Python and Prolog

Two weeks ago, I add came up with an interesting algorithm for solving Hidato which basically involves decomposing the board the grid (can be square, hexagonal or any other shape), into classes of pieces and then arranging them (maybe I’ll write a detailed post on it in the future). So while pondering whether it would be interesting enough to go forward and actually implementing the algorithm compared to the work it would require, I started thinking what will be the simplest way to solve such puzzles, as opposed to efficient.

At first I’ve looked at general purpose constraint solvers, and decided to tackle Sudoku instead as it’s a bit simple to define in terms of constraints. I considered several libraries but in the end I’ve settled on plainly using Prolog. I chose Prolog because as a logic programming language, constraints are its bread and butter. I although kind of liked it as I haven’t done anything in Prolog for quite a few years.

Describing Sudoku in terms of constraints is extremely simple. You need to state that every cell is in a given range and that all rows, columns and sub-grid contain different integers. As mangling with lists in prolog isn’t fun, I’ve wrote a python program that outputs all the prolog statements with hardcoded references to the variables which build-up the board. It’s ugly but dead simple. The script gets the dimensions of the sub-grid.

import sys

VAR_TEMPLATE = "G%02d%02d"

def puzzle_declaration(x,y):
    lines = []
    for i in range(x*y):
        vars = map(lambda j: VAR_TEMPLATE % (i,j), range(x*y))
        lines.append('[' + ', '.join(vars)+ ']')

    print "puzzle("
    print '  ' + ',\n  '.join(lines)
    print "):-"

def constraints_range(x,y):
    vars = [VAR_TEMPLATE % (i,j) for i in range(x*y) for j in range(x*y)]
    print "\tVars = [" + ', '.join(vars) + "],"
    print "\tVars ins 1..%d," % (x*y)

def constraints_diff(x,y):
    # rows
    rows = []
    for i in range(x*y):
        row = [VAR_TEMPLATE % (i,j) for j in range(x*y)]
        rows.append("all_different([" + ', '.join(row) + "])")

    columns = []
    for j in range(x*y):
        column = [VAR_TEMPLATE % (i,j) for i in range(x*y)]
        columns.append("all_different([" + ', '.join(column) + "])")

    rects = []
    for i in range(x):
        for j in range(y):
            rect = [VAR_TEMPLATE % (k+y*i,l+x*j) for k in range(y) for l in range(x)]
            rects.append("all_different([" + ', '.join(rect) + "])")
        
    print '\t' + ',\n\t'.join(rows) + ","
    print '\t' + ',\n\t'.join(columns) + ","
    print '\t' + ',\n\t'.join(rects) + "."

def generate_puzzle(x,y):
    puzzle_declaration(x,y)
    constraints_range(x,y)
    constraints_diff(x,y)


if __name__=="__main__":
    x = int(sys.argv[1])
    y = int(sys.argv[2])
    generate_puzzle(x,y)

For example running the script with 3 3 as arguments generates a regular 9×9 Sudoku solver.

:- use_module(library(clpfd)).

puzzle(
  [G0000, G0001, G0002, G0003, G0004, G0005, G0006, G0007, G0008],
  [G0100, G0101, G0102, G0103, G0104, G0105, G0106, G0107, G0108],
  [G0200, G0201, G0202, G0203, G0204, G0205, G0206, G0207, G0208],
  [G0300, G0301, G0302, G0303, G0304, G0305, G0306, G0307, G0308],
  [G0400, G0401, G0402, G0403, G0404, G0405, G0406, G0407, G0408],
  [G0500, G0501, G0502, G0503, G0504, G0505, G0506, G0507, G0508],
  [G0600, G0601, G0602, G0603, G0604, G0605, G0606, G0607, G0608],
  [G0700, G0701, G0702, G0703, G0704, G0705, G0706, G0707, G0708],
  [G0800, G0801, G0802, G0803, G0804, G0805, G0806, G0807, G0808]
):-
	Vars = [G0000, G0001, G0002, G0003, G0004, G0005, G0006, G0007, G0008, G0100, G0101, G0102, G0103, G0104, G0105, G0106, G0107, G0108, G0200, G0201, G0202, G0203, G0204, G0205, G0206, G0207, G0208, G0300, G0301, G0302, G0303, G0304, G0305, G0306, G0307, G0308, G0400, G0401, G0402, G0403, G0404, G0405, G0406, G0407, G0408, G0500, G0501, G0502, G0503, G0504, G0505, G0506, G0507, G0508, G0600, G0601, G0602, G0603, G0604, G0605, G0606, G0607, G0608, G0700, G0701, G0702, G0703, G0704, G0705, G0706, G0707, G0708, G0800, G0801, G0802, G0803, G0804, G0805, G0806, G0807, G0808],
	Vars ins 1..9,
	all_different([G0000, G0001, G0002, G0003, G0004, G0005, G0006, G0007, G0008]),
	all_different([G0100, G0101, G0102, G0103, G0104, G0105, G0106, G0107, G0108]),
	all_different([G0200, G0201, G0202, G0203, G0204, G0205, G0206, G0207, G0208]),
	all_different([G0300, G0301, G0302, G0303, G0304, G0305, G0306, G0307, G0308]),
	all_different([G0400, G0401, G0402, G0403, G0404, G0405, G0406, G0407, G0408]),
	all_different([G0500, G0501, G0502, G0503, G0504, G0505, G0506, G0507, G0508]),
	all_different([G0600, G0601, G0602, G0603, G0604, G0605, G0606, G0607, G0608]),
	all_different([G0700, G0701, G0702, G0703, G0704, G0705, G0706, G0707, G0708]),
	all_different([G0800, G0801, G0802, G0803, G0804, G0805, G0806, G0807, G0808]),
	all_different([G0000, G0100, G0200, G0300, G0400, G0500, G0600, G0700, G0800]),
	all_different([G0001, G0101, G0201, G0301, G0401, G0501, G0601, G0701, G0801]),
	all_different([G0002, G0102, G0202, G0302, G0402, G0502, G0602, G0702, G0802]),
	all_different([G0003, G0103, G0203, G0303, G0403, G0503, G0603, G0703, G0803]),
	all_different([G0004, G0104, G0204, G0304, G0404, G0504, G0604, G0704, G0804]),
	all_different([G0005, G0105, G0205, G0305, G0405, G0505, G0605, G0705, G0805]),
	all_different([G0006, G0106, G0206, G0306, G0406, G0506, G0606, G0706, G0806]),
	all_different([G0007, G0107, G0207, G0307, G0407, G0507, G0607, G0707, G0807]),
	all_different([G0008, G0108, G0208, G0308, G0408, G0508, G0608, G0708, G0808]),
	all_different([G0000, G0001, G0002, G0100, G0101, G0102, G0200, G0201, G0202]),
	all_different([G0003, G0004, G0005, G0103, G0104, G0105, G0203, G0204, G0205]),
	all_different([G0006, G0007, G0008, G0106, G0107, G0108, G0206, G0207, G0208]),
	all_different([G0300, G0301, G0302, G0400, G0401, G0402, G0500, G0501, G0502]),
	all_different([G0303, G0304, G0305, G0403, G0404, G0405, G0503, G0504, G0505]),
	all_different([G0306, G0307, G0308, G0406, G0407, G0408, G0506, G0507, G0508]),
	all_different([G0600, G0601, G0602, G0700, G0701, G0702, G0800, G0801, G0802]),
	all_different([G0603, G0604, G0605, G0703, G0704, G0705, G0803, G0804, G0805]),
	all_different([G0606, G0607, G0608, G0706, G0707, G0708, G0806, G0807, G0808]).

Again, not so pretty, but it’s python-generated hence simple as hell. Now solving is easily by passing integers instead of the variables. You can see below a prolog solution that demos solving a Sudoku. Another nice thing, is that if there isn’t a unique solution, it will be output say which cells have definite value, and output the constraints that hold for the rest of the cells.

I’ve tested it with both regular size Sudokus and mini-size (6×6), and it seems to preform pretty fast.

?- puzzle(
  [G0000, G0001,     1,     3, G0004, G0005, G0006, G0007,     8],
  [G0100, G0101,     7,     5,     6, G0105, G0106,     4, G0108],
  [G0200,     3, G0202, G0203,     7,     8,     6, G0207, G0208],
  [G0300, G0301,     4,     2, G0304, G0305, G0306, G0307,     6],
  [G0400,     9, G0402, G0403, G0404, G0405, G0406,     5, G0408],
  [    1, G0501, G0502, G0503, G0504,     5,     9, G0507, G0508],
  [G0600, G0601, G0602,     1,     2, G0605, G0606,     6, G0608],
  [G0700,     1, G0702, G0703,     3,     7,     5, G0707, G0708],
  [G0800, G0801, G0802, G0803, G0804,     9,     3, G0807, G0808]
).

G0000 = 5,
G0001 = 6,
G0004 = 4,
G0005 = 2,
G0006 = 7,
G0007 = G0100, G0100 = 9,
G0101 = 8,
G0105 = 1,
G0106 = 2,
G0108 = 3,
G0200 = 4,
G0202 = 2,
G0203 = 9,
G0207 = 1,
G0208 = 5,
G0300 = 7,
G0301 = 5,
G0304 = 9,
G0305 = 3,
G0306 = 1,
G0307 = G0400, G0400 = 8,
G0402 = 3,
G0403 = 7,
G0404 = 1,
G0405 = 6,
G0406 = 4,
G0408 = G0501, G0501 = 2,
G0502 = 6,
G0503 = 4,
G0504 = 8,
G0507 = 3,
G0508 = 7,
G0600 = 3,
G0601 = 7,
G0602 = 5,
G0605 = 4,
G0606 = 8,
G0608 = 9,
G0700 = 6,
G0702 = 9,
G0703 = 8,
G0707 = 2,
G0708 = 4,
G0800 = 2,
G0801 = 4,
G0802 = 8,
G0803 = 6,
G0804 = 5,
G0807 = 7,
G0808 = 1.