Solving Sudoku using Python and Prolog

Two weeks ago, I came up with an interesting algorithm for solving Hidato, which basically involves decomposing the board grid (which 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 implement the algorithm, compared to the work it would require, I started thinking about what would be the simplest way to solve such puzzles, as opposed to the most efficient way.

At first I looked at general-purpose constraint solvers and decided to tackle Sudoku instead, as it’s a bit simpler to define in terms of constraints. I considered several libraries, but in the end I settled on simply using Prolog. I chose Prolog because, as a logic programming language, constraints are its bread and butter. I also 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-grids contain different integers. Since mangling with lists in Prolog isn’t fun, I wrote a Python program that outputs all the Prolog statements with hardcoded references to the variables that 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' + ',nt'.join(rows) + ","
    print 't' + ',nt'.join(columns) + ","
    print 't' + ',nt'.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 it is easy: just pass integers instead of the variables. Another nice thing is that if there isn’t a unique solution, it will output which cells have definite values 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 perform 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.