Welcome, guest | Sign In | My Account | Store | Cart

A simple brute-force Sudoku solver written in functional-programming style. This code is not aimed for speed, the goal is to write a clear, compact and (hopefully) pedagogical functional solution.

Python, 55 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import re
import sys

def copy_board(board, sets):
    """Return a copy of board setting new squares from 'sets' dictionary."""
    return [[sets.get((r, c), board[r][c]) for c in range(9)] for r in range(9)]
            
def get_alternatives_for_square(board, nrow, ncolumn):
    """Return sequence of valid digits for square (nrow, ncolumn) in board."""
    def _box(idx, size=3):
        """Return indexes to cover a box (3x3 sub-matrix of a board)."""
        start = (idx // size) * size
        return range(start, start + size)
    nums_in_box = [board[r][c] for r in _box(nrow) for c in _box(ncolumn)]
    nums_in_row = [board[nrow][c] for c in range(9)]
    nums_in_column = [board[r][ncolumn] for r in range(9)]
    nums = nums_in_box + nums_in_row + nums_in_column
    return sorted(set(range(1, 9+1)) - set(nums)) 

def get_more_constrained_square(board):
    """Get the square in board with more constrains (less alternatives)."""
    ranges = ((x, y) for x in range(9) for y in range(9))
    constrains = [(len(get_alternatives_for_square(board, r, c)), (r, c)) 
        for (r, c) in ranges if not board[r][c]]
    if constrains:
        return min(constrains)[1]
     
def solve(board):
    """Return a solved Sudoku board (None if no solution was found)."""
    pos = get_more_constrained_square(board)
    if not pos:
        return board # all squares are filled, so this board is the solution
    nrow, ncolumn = pos
    for test_digit in get_alternatives_for_square(board, nrow, ncolumn):
        test_board = copy_board(board, {(nrow, ncolumn): test_digit})
        solved_board = solve(test_board)
        if solved_board:
            return solved_board

def lines2board(lines):
    """Parse a text board stripping spaces and setting 0's for empty squares."""
    spaces = re.compile("\s+")
    return [[(int(c) if c in "123456789" else 0) for c in spaces.sub("", line)]
            for line in lines if line.strip()]

def main(args):
    """Solve a Sudoku board read from a text file."""
    from pprint import pprint
    path, = args
    board = lines2board(open(path))
    pprint(board)
    pprint(solve(board))
    
if __name__ == '__main__':
    sys.exit(main(sys.argv[1:]))

To test the code create a text file containing the grid. Example (mysudoku.txt):

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

- - -  5 - 9  - - -
1 - -  3 4 8  - - 9
- - -  7 - 1  - - -

- - 5  9 - -  3 - -
3 - -  - - 6  1 - -
7 6 -  - - -  - - 8

And then run:

$ python sudoku.py mysudoku.txt

Using a list to represent a Sudoku board is the most obvious option, but we could also have represented it as a dictionary of pairs (position, digit). Check here a possible solution using a dictionary as board.


Functional programming (FP) is an extremely powerful paradigm. Although Python is not a functional language (Haskell, OCaml, Scheme or Erlang are -more or less- pure FP languages), we can take advantage of some of its features (first-class functions, list comprehensions, the itertools module) to write nice functional constructions.

Here are some links on how to use Functional Programming with Python:

Created by Arnau Sanchez on Mon, 12 Apr 2010 (MIT)
Python recipes (4591)
Arnau Sanchez's recipes (4)

Required Modules

  • (none specified)

Other Information and Tasks