Sudoku Puzzle Solver

Question

I have written a program to solve Sudoku puzzles as a (fun?) way to learn Python. It solves puzzles as a human would, using reasoning algorithms rather than brute force/backtracking, as I thought it would a more interesting challenge that way.

I really looking for any feedback on how to reduce indentation, lines of code, or increase efficiency. I'm sure the functions that I've repeated for columns/rows/subgrids can be merged into one, but I just can't think of an elegant way. Any general feedback would be more than welcome too, please lay into the code as much as possible. I'm a 2nd year computing (CS but lite) student if that makes any difference but probably not.

I appreciate this involves domain specific knowledge i.e. how to solve Sudoku puzzles. I created all the algorithms using only the following resource and all of the techniques contained in the program are described here for anyone interested.

import itertools

# TERMINOLOGY
# grid:         The main 9x9 grid of the puzzle.
# sub-grid:     A 3x3 sub-grid within the main grid.
# square:       A single square within the grid.
# row:          A whole row of squares within the main grid.
# column:       A whole column of squares within the main grid.
# sub-row:      A row of three squares in a sub-grid.
# sub-column:   A column of three squares in a sub-grid.
# candidate:    A possible solution for a square.
# solved:       A square is solved when the correct value is filled.
#
# For in-depth descriptions of the various sudoku solving techniques 
# used in this program, visit:
# http://www.paulspages.co.uk/sudoku/howtosolve/index.htm
# This is the sole resource used to generate the techniques
# found in this program.


# Holds puzzle itself as 2d list. Blank squares represented as 0.
# Individual square access: main_grid[x][y]
main_grid = [[] for x in range(0, 9)]

# Holds all possible candidates for each square as a 2d list of sets.
# Individual square set access: candidates_grid[x][y]
candidates_grid = [[set() for y in range(0, 9)] for x in range(0, 9)]

# Holds all solved values in an individual row/col/sub-grid
col_set = [set() for x in range(0, 9)]  # Access: col_set[x]
row_set = [set() for x in range(0, 9)]  # Access: row_set[y]
sub_grid_set = [[set() for y in range(0, 3)] for x in range(0, 3)]

# Misc sets used for solving techniques/optimisation
full_set = set({1, 2, 3, 4, 5, 6, 7, 8, 9})
coordinates_set = set({0, 1, 2, 3, 4, 5, 6, 7, 8})


# Populates main_grid, candidates_grid, row/col/block sets from data file
def init():
    puzzle = open('../puzzles/extreme2.txt', 'r')
    for y in range(0, 9):
        next_line = puzzle.readline()
        for x in range(0, 9):
            main_grid[x].append(int(next_line[x]))
            if next_line[x] != '0':
                col_set[x].add(int(next_line[x]))
                row_set[y].add(int(next_line[x]))
                sub_grid_set[int(x / 3)][int(y / 3)].add(int(next_line[x]))

    for y in range(0, 9):
        for x in range(0, 9):
            if main_grid[x][y] == 0:
                candidatesSet = set.union(row_set[y], col_set[x],
                                          sub_grid_set[int(x / 3)][int(y / 3)])
                candidates_grid[x][y] = full_set.difference(candidatesSet)


def iter_over_subgrids(func, *args):
    for sub_grid_y in range(0, 3):
        for sub_grid_x in range(0, 3):
            func(sub_grid_x, sub_grid_y, *args)


def iter_over_line(func, *args):
    for square in range(0, 9):
        func(square, *args)


def print_main_grid():
    for y in range(0, 9):
        for x in range(0, 9):
            print(main_grid[x][y], end="")
            if x % 3 == 2:
                print(" ", end="")
        print("")


def print_candidates_grid():
    for y in range(0, 9):
        for x in range(0, 9):
            print(candidates_grid[x][y], " ", end="")
        print("")


def is_solved():
    for y in range(0, 9):
        if len(row_set[y]) != 9:
            return 0
    return 1


# Writes solution to main_grid, updates sets and tables.
def pencil_in(solution, x, y, func):
    sub_grid_x = int(x / 3)
    sub_grid_y = int(y / 3)
    main_grid[x][y] = solution
    row_set[y].add(solution)
    col_set[x].add(solution)
    sub_grid_set[sub_grid_x][sub_grid_y].add(solution)
    candidates_grid[x][y].clear()

    for sg_y in range(sub_grid_y * 3, sub_grid_y * 3 + 3):
        for sg_x in range(sub_grid_x * 3, sub_grid_x * 3 + 3):
            candidates_grid[sg_x][sg_y].discard(solution)
    for i in range(0, 9):
        candidates_grid[x][i].discard(solution)
        candidates_grid[i][y].discard(solution)


# Solves squares that have only one candidate.
def single_candidate_square(y):
    for x in range(0, 9):
        if len(candidates_grid[x][y]) == 1:
            pencil_in(candidates_grid[x][y].pop(), x, y,
                      single_candidate_square)


# Solves squares where candidate appears only once in a row.
def single_sq_candidate_row(y):
    for candidate in full_set.difference(row_set[y]):  # Skip solved values
        count = 0
        prev_x = 0
        for x in range(0, 9):
            if candidate in candidates_grid[x][y]:
                count += 1
                prev_x = x
        if count == 1:
            pencil_in(candidate, prev_x, y, single_sq_candidate_row)


# As single_sq_candidate_row, for columns.
def single_sq_candidate_col(x):
    for candidate in full_set.difference(col_set[x]):  # Skip solved values
        count = 0
        prev_y = 0
        for y in range(0, 9):
            if candidate in candidates_grid[x][y]:
                count += 1
                prev_y = y
        if count == 1:
            pencil_in(candidate, x, prev_y, single_sq_candidate_col)


# As single_sq_candidate_row, for subgrids.
def single_sq_candidate_subgrid(sub_grid_x, sub_grid_y):
    for candidate in full_set.difference(sub_grid_set[sub_grid_x][sub_grid_y]):
        count = 0
        prev_coords = [0, 0]
        for y in range(sub_grid_y * 3, sub_grid_y * 3 + 3):
            for x in range(sub_grid_x * 3, sub_grid_x * 3 + 3):
                if candidate in candidates_grid[x][y]:
                    count += 1
                    prev_coords[0] = x
                    prev_coords[1] = y
        if count == 1:
            pencil_in(candidate, prev_coords[0], prev_coords[1],
                      single_sq_candidate_subgrid)


# Finds candidates in block that lie only on one subrow,
# removes candidates from rest of row.
def number_claiming_row(sub_grid_x, sub_grid_y):
    # Get set of all candidates each subrow
    subrow_sets = [set(), set(), set()]
    for y in range(sub_grid_y * 3, sub_grid_y * 3 + 3):
        for x in range(sub_grid_x * 3, sub_grid_x * 3 + 3):
            subrow_sets[y % 3] = subrow_sets[y % 3].union(candidates_grid[x][y])

    # Get candidates which only appear in one subrow
    claimed = [subrow_sets[0].difference(subrow_sets[1], subrow_sets[2])]
    claimed.append(subrow_sets[1].difference(subrow_sets[0], subrow_sets[2]))
    claimed.append(subrow_sets[2].difference(subrow_sets[0], subrow_sets[1]))

    # Remove candidates from other subrows in parent row
    for sub_row in range(0, 3):
        for claimant in set(claimed[sub_row]):
            for x in range(0, 9):
                if int(x / 3) != sub_grid_x:
                    candidates_grid[x][sub_grid_y * 3 + sub_row].discard(claimant)


# As number_claiming_row, but for columns
def number_claiming_col(sub_grid_x, sub_grid_y):
    # Get set of all candidates each subcolumn
    subcol_sets = [set(), set(), set()]
    for x in range(sub_grid_x * 3, sub_grid_x * 3 + 3):
        for y in range(sub_grid_y * 3, sub_grid_y * 3 + 3):
            subcol_sets[x % 3] = subcol_sets[x % 3].union(candidates_grid[x][y])

    # Get candidates which only appear in one subcolumn
    claimed = [subcol_sets[0].difference(subcol_sets[1], subcol_sets[2])]
    claimed.append(subcol_sets[1].difference(subcol_sets[0], subcol_sets[2]))
    claimed.append(subcol_sets[2].difference(subcol_sets[0], subcol_sets[1]))

    # Remove candidates from other subcolumns in parent column
    for sub_col in range(0, 3):
        for claimant in set(claimed[sub_col]):
            for y in range(0, 9):
                if int(y / 3) != sub_grid_y:
                    candidates_grid[sub_grid_x * 3 + sub_col][y].discard(claimant)


# Finds sets of n squares in a row where:
# - No squares contain more than n candidates each.
# - The cardinality of the set of all the candidates in squares is n.
# All candidates in that set can be assumed to lie in those squares,
# so the set of candidates can be removed from all other squares in
# that row. Sudoku solvers may already know disjoint subsets as "pairs"
# or "triples".
#
# Basic example: three squares in a row contain the candidate sets
# {2,4}, {2,7} and {4,7} respectively. All three squares contain no
# more than three candidates, and the set of all candidates is {2,4,7},
# which has a cardinality of three. It can then be assumed that those
# squares MUST contain 2, 4 and 7 and nothing else. Any squares outside
# those three in the row can then have the candidates 2, 4 and 7 removed.
def disjoint_subsets_row(y, n):
    sets = []
    # Get all candidate sets in row with cardinality no greater than n
    for x in range(0, 9):
        if 1 < len(candidates_grid[x][y]) <= n:
            sets.append(candidates_grid[x][y])

    # For all disjoint subsets found, remove candidates from other squares
    for d in get_disjoint_subsets(sets, n):
        for x in range(0, 9):
            if not candidates_grid[x][y].issubset(d):
                candidates_grid[x][y] = candidates_grid[x][y].difference(d)


# As disjoint_subsets_row, for columns
def disjoint_subsets_col(x, n):
    sets = []
    # Get all candidate sets in row with cardinality no greater than n
    for y in range(0, 9):
        if 1 < len(candidates_grid[x][y]) <= n:
            sets.append(candidates_grid[x][y])

    # For all disjoint subsets found, remove candidates from other squares
    for d in get_disjoint_subsets(sets, n):
        for y in range(0, 9):
            if not candidates_grid[x][y].issubset(d):
                candidates_grid[x][y] = candidates_grid[x][y].difference(d)


# As disjoint_subsets_row, for sub-grids.
def disjoint_subsets_subgrid(sub_grid_x, sub_grid_y, n):
    sets = []
    # Get all candidate sets in row with cardinality no greater than n
    for y in range(sub_grid_y * 3, sub_grid_y * 3 + 3):
        for x in range(sub_grid_x * 3, sub_grid_x * 3 + 3):
            if 1 < len(candidates_grid[x][y]) <= n:
                sets.append(candidates_grid[x][y])

    # For all disjoint subsets found, remove candidates from other squares
    for d in get_disjoint_subsets(sets, n):
        for y in range(sub_grid_y * 3, sub_grid_y * 3 + 3):
            for x in range(sub_grid_x * 3, sub_grid_x * 3 + 3):
                if not candidates_grid[x][y].issubset(d):
                    candidates_grid[x][y] = candidates_grid[x][y].difference(d)


def get_disjoint_subsets(sets, n):
    disjoint_subsets = set()
    # For each combination of n sets in sets
    for combination in itertools.combinations(sets, n):
        superset = set()
        # For each individual set in combination
        for c in combination:
            superset = superset.union(c)
        if len(superset) == n:
            # Cardinality of candidate superset in combination is n, is djss.
            disjoint_subsets.add(frozenset(superset))
    return disjoint_subsets


# Runs through solving techniques until puzzle solved or no possible solution.
def solve():
    for x in range(0, 100):
        iter_over_line(single_candidate_square)
        iter_over_line(single_sq_candidate_row)
        iter_over_line(single_sq_candidate_col)
        iter_over_subgrids(single_sq_candidate_subgrid)
        iter_over_subgrids(number_claiming_row)
        iter_over_subgrids(number_claiming_col)
        for n in range(2, 5):
            iter_over_line(disjoint_subsets_row, n)
            iter_over_line(disjoint_subsets_col, n)
            iter_over_subgrids(disjoint_subsets_subgrid, n)
        if is_solved() == 1:
            print_main_grid()
            break

init()
solve()

Puzzles are solved in the text file in the format:

400700900  
000004000  
070280006  
500000010  
301060408  
020000009  
900036020  
000800000  
004001003  

Example of a Sudoku game:

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

The above is an "extreme" level puzzle.

Answer 1

Working with file handles

Don't do this:

puzzle = open('../puzzles/extreme2.txt', 'r')

Use with instead:

with open('../puzzles/extreme2.txt') as puzzle:
    # ...

In your version you forget to close the file handle. That's a bad practice. When using with, the file handle is automatically closed.

Use booleans

Instead of returning 0 for failure and 1 for success:

def is_solved():
    for y in range(0, 9):
        if len(row_set[y]) != 9:
            return 0
    return 1

Use booleans:

def is_solved():
    for y in range(0, 9):
        if len(row_set[y]) != 9:
            return False
    return True

Usability

It would be nice if the puzzle file was a command line argument, not the hardcoded path ../puzzles/extreme2.txt.

Documentation

It's nice that you included explanation about the terminology. But it would be better to use proper doc strings.

Simplifications

You can replace this:

full_set = set({1, 2, 3, 4, 5, 6, 7, 8, 9})

With a set literal:

full_set = {1, 2, 3, 4, 5, 6, 7, 8, 9}

---

You can write range(9) instead of range(0, 9)

---

Instead of int(x / 3), it's better to use x // 3

Answer 2

You can make it much tighter by using list comprehensions. The function below will perform all of the puzzle checks and return all possible moves for a particular row and column given a particular puzzle, although I used characters instead of ints (you can transform by switching that part to m+1 for m in range(9)).

def puzzle_moves(row,col,puzzle):
    same_row = {puzzle[row][c] for c in range(9)}
    same_col = {puzzle[r][col] for r in range(9)}
    # box row/col refer to the row/col of the box that row/col is in
    box_row = 3*(row/3)
    box_col = 3*(col/3)
    same_box = {puzzle[box_row+r][box_col+c] for r in range(3) for c in range(3)}
    return {m for m in '123456789'
        if m not in same_row
        and m not in same_col
        and m not in same_box}

My solution can solve large numbers of 'extreme' puzzles in seconds, and I think it's pretty easy to read (YMMV!).

[EDIT: I guess it's not as clear as I thought!]:

To understand this, look at the return statement: We want to return any possible 'moves' that are not in the same row, same column, or in the same box. All the lines before the return statement are defining what it means to be in the same row/col/box.

Let's start with same_row as an example:

same_row = {puzzle[row][c] for c in range(9)}

We pass in the puzzle, row and column, we want to know which moves are in this current row of the puzzle. So for example, say puzzle is a Sudoku puzzle that looks like this:

If we pass in row 0 and col 0, we expect for same row to get back everything in the 0th (first) row: {2, 7, 8, 9}

To try it for yourself with the puzzle you posted, open a python prompt and type in puzzle_str=""", then paste your puzzle, followed by """ again:

>>>puzzle_str = """400700900...etc..."""

You can then construct the puzzle as a list-of-lists:

puzzle = [[c for c in line.strip()] for line in puzzle_str.strip().split('\n')]

That line is splitting the puzzle string by newline characters (after removing any extras at the end or beginning), and then returning each character.

Then you can call the above function by passing in the puzzle with any row, col and the above puzzle. You can also try each line of code, so let's look at same_row again:

row = 0
col = 0
{puzzle[row][c] for c in range(9)}  # same_row, from above function

So this returns {'0', '4', '7', '9'}, the distinct characters that are in the first row of your puzzle. same_col follows the same logic.

Getting the same_box is trickier. To understand this part, think of the puzzle as having 3 'box rows' and 3 'box columns', which define the 9 boxes. To get the box rows/cols, you take the row/col that was passed in, and divide it by 3, which (since it's an int) will truncate it. To see this in action, look at this:

[i/3 for i in range(9)]
[0, 0, 0, 1, 1, 1, 2, 2, 2]

Once you've determined box_row and box_col, the same_box expression is just the same logic as same_row and same_col. The for r in range(3) for c in range(3) is giving you all the combinations for a 3x3 box.

I've rambled enough...please let me know if there is another specific part I can explain?

[EDIT #2] Ok, here's another version that's still pretty concise, but runs a little faster (about 10% faster). This time it's an OO design, which isn't my typical go-to, but hey, at least it's pretty!

import copy

possible_moves = set([m for m in '123456789'])

class Sudoku(object):
    def __init__(self, puzzle_str):
        self.rows = [set() for r in range(9)]
        self.cols = [set() for c in range(9)]
        self.boxes = [[set() for bc in range(3)] for br in range(3)]
        self.grid = [[c for c in line.strip()] for line in puzzle_str.strip().split('\n')]
        for r, row in enumerate(self.grid):
            for c, m in enumerate(row):
                self.move(r, c, m)

    def move(self, r, c, m):
        self.rows[r].add(m)
        self.cols[c].add(m)
        self.boxes[int(r/3)][int(c/3)].add(m)
        self.grid[r][c] = m

    def moves(self, r, c):
        return possible_moves - self.rows[r] - self.cols[c] - self.boxes[int(r/3)][int(c/3)]

    def __str__(self):
        return '\n'.join(['.'.join([c for c in line]) for line in self.grid])

worst_best_move = ((10),(),())

def solve_sudoku(puzzle):
    best_move = worst_best_move
    found_move = True
    finished = True

    while found_move:
        finished = True
        found_move = False
        best_move = worst_best_move
        for r in range(0,9):
            for c in range(0,9):
                if puzzle.grid[r][c]=='0':
                    possible_moves = puzzle.moves(r,c)
                    num_moves = len(possible_moves)
                    if num_moves==0:
                        return None
                    if num_moves==1:
                        found_move=True
                        puzzle.move(r, c, possible_moves.pop())
                    else:
                        finished = False
                        if num_moves < best_move[0]:
                            best_move =(num_moves,(r,c), possible_moves)
    if finished:
        return puzzle

    target = best_move[1]
    for move in best_move[2]:
        guess_puzzle = copy.deepcopy(puzzle)
        guess_puzzle.move(target[0], target[1], move)
        result = solve_sudoku(guess_puzzle)
        if result is not None:
            return result
    return None

def run_sudoku_test():
    puzzle_str = """
400700900
000004000
070280006
500000010
301060408
020000009
900036020
000800000
004001003"""
    puzzle = Sudoku(puzzle_str)
    #print(str(puzzle))
    result = solve_sudoku(puzzle)
    if result is None:
        print 'Failed to solve %s'%puzzle_num
    else:
        pass#print_sudoku_puzzle(result)


if __name__=='__main__':
    import timeit
    print(timeit.timeit('run_sudoku_test()',setup='from __main__ import run_sudoku_test',number=50))