Fun little sudoku solver that shows progress as it works

sudoku.py

#!/usr/bin/env python
import sys
import time
import curses

sudoku = """
0 0 0 0 0 0 0 0 0
0 0 8 0 0 0 0 4 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0
"""

num_calls = 0


def row_valid(board, idx, val):
    return val not in board[idx]


def col_valid(board, idx, val):
    return val not in [ row[idx] for row in board ]


def get_box(board, box_row, box_col):
    array = []
    for x in range(box_row*3, box_row*3+3):
        for y in range(box_col*3, box_col*3+3):
            array.append(board[x][y])
    return array


def box_valid(board, row, col, val):
    return val not in get_box(board, row//3, col//3)


def cell_valid(board, row, col, val):
    return row_valid(board, row, val) and \
           col_valid(board, col, val) and \
           box_valid(board, row, col, val)


def array_valid(array):
    return sorted(array) == [x for x in range(1, 10)]


def board_valid(board):
    for row in board:
        if not array_valid(row):
            return False
    for i in range(9):
        if not array_valid([ row[i] for row in board ]):
            return False
    for x in range(3):
        for y in range(3):
            if not array_valid(get_box(board, x, y)):
                return False

    return True


def print_board(board):
    for row in board:
        for item in row:
            sys.stdout.write('{} '.format(item))
        sys.stdout.write('\n')


def display_board(stdscr, board):

    for i in range(0, 9):
        for j in range(0, 9):
            val = str(board[i][j] or '.')
            stdscr.addstr(i, j*2, val)

    stdscr.addstr(i+1, 0, 'step: {}'.format(num_calls+1))
    stdscr.refresh()


def solve_cell(stdscr, board, row, col):

    display_board(stdscr, board)
    time.sleep(0.1)

    global num_calls
    num_calls += 1

    if row > 8 or col > 8:
        return True

    if col == 8:
        next_col = 0
        next_row = row + 1
    else:
        next_col = col + 1
        next_row = row

    if board[row][col] == 0:
        for attempt in range(1, 10):
            if not cell_valid(board, row, col, attempt):
                continue

            board[row][col] = attempt
            if col == 8 and row == 8:
                return True

            if solve_cell(stdscr, board, next_row, next_col):
                break

        else:
            board[row][col] = 0
            return False
    else:
        return solve_cell(stdscr, board, next_row, next_col)

    return True


def parse_board(raw, sep=' '):
    return [ [ int(x) for x in line.split(sep) ] for line in raw.split('\n') ]


def main(stdscr):

    try:
        # Hide the cursor
        curses.curs_set(0)

        if len(sys.argv) == 2:
            with open(sys.argv[1]) as ff:
                board = parse_board(ff.read().strip(), sep=',')
        else:
            board = parse_board(sudoku.strip())

        solve_cell(stdscr, board, 0, 0)

        display_board(stdscr, board)
        stdscr.addstr(9, 0, 'board valid: {}'.format(board_valid(board)))
        stdscr.addstr(10, 0, 'total steps: {}'.format(num_calls))
        stdscr.addstr(11, 0, "press 'q' to quit")

        while True:
            char = stdscr.getch()
            if char == ord('q') or char == ord('Q'):
                break
    except KeyboardInterrupt:
        return


if __name__ == '__main__':
    curses.wrapper(main)