Untitled

#!/usr/bin/env python
# coding:utf-8

"""
Each sudoku board is represented as a dictionary with string keys and
int values.
e.g. my_board['A1'] = 8
"""
import sys
import time

ROW = "ABCDEFGHI"
COL = "123456789"


def print_board(board):
    """Helper function to print board in a square."""
    print("-----------------")
    for r in ROW:
        row = ''
        for c in COL:
            row += (str(board[r + c]) + " ")
        print(row)


def board_to_string(board):
    """Helper function to convert board dictionary to string for writing."""
    ordered_vals = []
    for r in ROW:
        for c in COL:
            ordered_vals.append(str(board[r + c]))
    return ''.join(ordered_vals)


def backtracking(board):
    """Takes a board and returns solved board."""
    r, c = get_mrv(board)
    if r is None:
        return board

    for val in range(1, 10):
        if valid(board, val, r, c):
            if not forward_checking(board, val, r, c):
                continue
            board[ROW[r] + COL[c]] = val
            solved_board = backtracking(board)
            if solved_board:
                return solved_board
            board[ROW[r] + COL[c]] = 0

    return None


def get_mrv(board):
    mrv = 9
    r, c = None, None

    for i in range(9):
        for j in range(9):
            if board[ROW[i] + COL[j]] == 0:
                rv_count = get_rv_count(board, i, j)
                if rv_count < mrv:
                    mrv = rv_count
                    r, c = i, j

    return r, c


def get_rv_count(board, r, c):
    rv_count = 0

    for val in range(1, 10):
        if valid(board, val, r, c):
            rv_count += 1

    return rv_count


def valid(board, val, r, c):
    # check column constraints
    for i in range(9):
        if board[ROW[i] + COL[c]] == val:
            return False

    # check row constraints
    for j in range(9):
        if board[ROW[r] + COL[j]] == val:
            return False

    # check box constraints
    box_row = r // 3
    box_col = c // 3
    for i in range(3):
        for j in range(3):
            if board[ROW[box_row * 3 + i] + COL[box_col * 3 + j]] == val:
                return False

    return True


def forward_checking(board, val, r, c):
    board[ROW[r] + COL[c]] = val
    for i in range(9):
        for j in range(9):
            if board[ROW[i] + COL[j]] == 0 and get_rv_count(board, i, j) == 0:
                board[ROW[r] + COL[c]] = 0
                return False
    board[ROW[r] + COL[c]] = 0

    return True


if __name__ == '__main__':
    start_time = time.time()
    if len(sys.argv) > 1:

        # Running sudoku solver with one board $python3 sudoku.py <input_string>.
        print(sys.argv[1])
        # Parse boards to dict representation, scanning board L to R, Up to Down
        board = {ROW[r] + COL[c]: int(sys.argv[1][9 * r + c])
                 for r in range(9) for c in range(9)}

        solved_board = backtracking(board)

        # Write board to file
        out_filename = 'output.txt'
        outfile = open(out_filename, "w")
        outfile.write(board_to_string(solved_board))
        outfile.write('\n')

    else:
        # Running sudoku solver for boards in sudokus_start.txt $python3 sudoku.py

        #  Read boards from source.
        src_filename = 'sudokus_start.txt'
        try:
            srcfile = open(src_filename, "r")
            sudoku_list = srcfile.read()
        except:
            print("Error reading the sudoku file %s" % src_filename)
            exit()

        # Setup output file
        out_filename = 'output.txt'
        outfile = open(out_filename, "w")

        # Solve each board using backtracking
        for line in sudoku_list.split("\n"):

            if len(line) < 9:
                continue

            # Parse boards to dict representation, scanning board L to R, Up to Down
            board = {ROW[r] + COL[c]: int(line[9 * r + c])
                     for r in range(9) for c in range(9)}

            # Print starting board. TODO: Comment this out when timing runs.
            print_board(board)

            # Solve with backtracking
            solved_board = backtracking(board)

            # Print solved board. TODO: Comment this out when timing runs.
            print_board(solved_board)

            # Write board to file
            outfile.write(board_to_string(solved_board))
            outfile.write('\n')

        print("Finishing all boards in file.")
    end_time = time.time()
    print("Program completed in %.3f second(s)" % (end_time - start_time))