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) 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)

### Required Modules

• (none specified)