#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 13 05:34:58 2019
Sudoku solver.
This was converted from my older C++ sudoku solver, 
which might explain it's C-like code style.
@author: taylor@mst.edu
"""

from typing import List


# UNASSIGNED is used for empty cells in grid (a constant)
UNASSIGNED = 0


def solve_sudoku(grid: List[List[int]], indent: str = "") -> bool:
    """
    Takes a partially filled-in grid and attempts to assign values to all
    unassigned locations in such a way as to meet the requirements for Sudoku:
    non-duplication across rows, columns, and zones
    """
    row_col: List[int] = []

    # If there is no unassigned location, we are done
    # Otherwise, row and col are modified
    # (since they are passed by ref)
    if not find_unassigned_location(grid, row_col):
        # Total sucess
        return True

    row, col = row_col

    # consider digits 1 to 9
    for num in range(1, 10):
        # Does this digit produce any immediate conflicts?
        if is_safe(grid, row, col, num):
            # make tentative assignment
            grid[row][col] = num
            print(indent, "grid[", row, "]", "[", col, "] = ", num, sep="")

            # return, if success, yay!
            if solve_sudoku(grid, indent + " "):
                # like it occurs after recursive call
                return True

            # failure, un-do (backtrack) and try again
            grid[row][col] = UNASSIGNED

    print(indent, "grid[", row, "]", "[", col, "] = 1-9 all conflict!", sep="")
    # this triggers backtracking
    return False


def find_unassigned_location(grid: List[List[int]], row_col: List[int]) -> bool:
    """
    Searches the grid to find an entry that is still unassigned. If found, the
    reference parameters row, col will be end up set (by the for loop) to the
    location that is unassigned, and true is returned. If no unassigned entries
    remain, false is returned.
    """
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if grid[row][col] == UNASSIGNED:
                row_col[:] = row, col
                return True
    return False


def used_in_row(grid: List[List[int]], row: int, num: int) -> bool:
    """
    Returns a boolean which indicates whether any assigned entry in the
    specified row matches the given number.
    """
    for col in range(len(grid[0])):
        if grid[row][col] == num:
            return True
    return False


def used_in_col(grid: List[List[int]], col: int, num: int) -> bool:
    """
    Returns a boolean which indicates whether any assigned entry in the
    specified column matches the given number.
    """
    for row in range(len(grid)):
        if grid[row][col] == num:
            return True
    return False


def used_in_box(
    grid: List[List[int]], box_start_row: int, box_start_col: int, num: int
) -> bool:
    """
    Returns a boolean which indicates whether any assigned entry within the
    specified 3x3 box matches the given number.
    """
    for row in range(3):
        for col in range(3):
            if grid[row + box_start_row][col + box_start_col] == num:
                return True
    return False


def is_safe(grid: List[List[int]], row: int, col: int, num: int) -> bool:
    """
    Returns a boolean which indicates whether it will be legal to assign num to
    the given row,col location. Check if 'num' is not already placed in
    current row, current column and current 3x3 box
    """
    return (
        not used_in_row(grid, row, num)
        and not used_in_col(grid, col, num)
        and not used_in_box(grid, row - row % 3, col - col % 3, num)
    )


def print_grid(grid: List[List[int]]) -> None:
    """
    Prints the grid.
    """
    for row in grid:
        for element in row:
            print(element, " ", end="")
        print()


def main() -> None:
    # 0 for unassigned cells, as the constant at top
    grid = [
        [3, 0, 6, 5, 0, 8, 4, 0, 0],
        [5, 2, 0, 0, 0, 0, 0, 0, 0],
        [0, 8, 7, 0, 0, 0, 0, 3, 1],
        [0, 0, 3, 0, 1, 0, 0, 8, 0],
        [9, 0, 0, 8, 6, 3, 0, 0, 5],
        [0, 5, 0, 0, 9, 0, 6, 0, 0],
        [1, 3, 0, 0, 0, 0, 2, 5, 0],
        [0, 0, 0, 0, 0, 0, 0, 7, 4],
        [0, 0, 5, 2, 0, 6, 3, 0, 0],
    ]

    print("Problem is:")
    print_grid(grid)
    print("Solution is:")

    if solve_sudoku(grid):
        print_grid(grid)
    else:
        print("No solution exists")


if __name__ == "__main__":
    main()