"""
Starter code for a Sudoku solver, adapted from UMass CS 220.

To run from the command line: python3 starter.py

This will run the unit tests at the end of the file.
"""
import unittest

class Board:
    """Board(board_dict) is a class that represents a Sudoku board, where:

    - board_dict is a dictionary from (row, col) to a list of available values.
      The rows and columns are integers in the range 0 .. 8 inclusive. Each
      available value is an integer in the range 1 .. 9 inclusive."""


    def __init__(self, board_dict):
        """board_dict should be a dictionary, as described in the definition of
        the Board class."""

        self.board_dict = board_dict


    def __str__(self):
        """Prints the board nicely, arranging board_dict like a Sudoku board."""
        rows = [ ]
        for row in range(0, 9):
            col_strs = [ ]
            for col in range(0, 9): 
                val_str = ''.join(str(x) for x in self.board_dict[(row, col)])
                # Pad with spaces for alignment.
                val_str = val_str + (' ' * (9 - len(val_str)))
                col_strs.append(val_str)
                # Horizontal bar to separate boxes
                if col == 2 or col == 5:
                    col_strs.append('|')
            rows.append(' '.join(col_strs))
            # Vertical bar to separate boxes
            if row == 2 or row == 5:
                rows.append(93 * '-')
        return '\n'.join(rows)


    def copy(self):
        """Creates a deep copy of this board. Use this method to create a copy
        of the board before modifying the available values in any cell."""
        new_dict = { }
        for (k, v) in self.board_dict.items():
            new_dict[k] = v.copy()
        return Board(new_dict)


    def value_at(self, row, col):
        """Returns the value at the cell with the given row and column (zero
        indexed). Produces None if the cell has more than one available
        value."""
        # TODO: Implement
        raise NotImplementedError("value_at")


    def place(self, row, col, value):
        """Places value at the given row and column.
        
        Eliminates value from the peers of (row, col) and recursively calls
        place on any cell that is constrained to exactly one value."""
        # TODO: Implement
        raise NotImplementedError("place")


    def next_boards(board):
        """Returns a list of boards that have one cell filled.

        Selects a cell that is maximally constrained: i.e., has a minimum
        number of available values.
        """
        # TODO: Implement
        raise NotImplementedError("next_boards")
        

    def is_solved(self):
        """Returns True if the board is fully solved, and there are no choices
        to make at any cell."""
        # TODO: Implement
        raise NotImplementedError("is_solved")
    

    def is_unsolvable(self):
        """Returns True if the board is unsolvable."""
        # TODO: Implement
        raise NotImplementedError("is_unsolvable")


def parse(sudoku_string):
    """Parses a string of 81 digits and periods for empty cells into, produce
    a Board that represents the Sudoku board."""
    # TODO: Implement
    raise NotImplementedError("parse")


def peers(row, col):
    """Returns the peers of the given row and column, as a list of tuples."""
    # TODO: Implement
    raise NotImplementedError("peers")


def solve(board):
    """Recursively solve the board."""
    raise NotImplementedError("solve")

def check_solution(board):
    """Check to see if the board represents a valid Sudoku solution."""
    raise NotImplementedError("check_solution")

class SudokuTests(unittest.TestCase):

    def test_solved_puzzle(self):
        s = "853697421914238675762145893128563947475982136396471582581724369637859214249316758"
        board = parse(s)
        assert(board.value_at(0,0)==8)
        
    def test_solve_one(self):
        s = ".53697421914238675762145893128563947475982136396471582581724369637859214249316758"
        board = parse(s)
        assert(board.value_at(0,0)==8)

    def test_solve_third(self):
        s = "85.697421914238675762145893128563947475982136396471582581724369637859214249316758"
        board = parse(s)
        assert(board.value_at(0,2)==3)

    def test_empty_puzzle(self):
        s = "."*81
        board = parse(s)
        board_dict = { }
        for i in range(9):
            for j in range(9):
                board_dict[(i, j)] = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
        assert(board.board_dict == board_dict)

    def test_easy1(self):
        s = "85....4.1......67...21....3..85....7...982...3....15..5....43...37......2.9....58"
        board = parse(s)
        solution = solve(board)
        assert(solution is not None)

    def test_medium1(self):
        s = ".1.....2..3..9..1656..7...33.7..8..........89....6......6.254..9.5..1..7..3.....2"
        board = parse(s)
        solution = solve(board)
        assert(solution is not None)

    def test_medium2(self):
        s = "2...8.3...6..7..84.3.5..2.9...1.54.8.........4.27.6...3.1..7.4.72..4..6...4.1...3"
        board = parse(s)
        solution = solve(board)
        assert(solution is not None)


if __name__ == "__main__":
    unittest.main()