import random
import sys
from time import time

def print_board(board):

    row_labels = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H','I']
    print("            ", end=' ')
    print("  1 2 3 4 5 6 7 8 9")
    for x in range(0,9):
        word=''+row_labels[x]+'|'

        for y in range(0,9):
            if(str(board[9*x+y]) == '0'):
                word+='-|'
            else:
                word += str(board[9*x+y]) + '|'
        print("            ",word)

def print_board2(board1, board2):

    row_labels = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H','I']
    print("   Input Board                   Solution Board ")
    print("-------------------           ------------------")
    print("  1 2 3 4 5 6 7 8 9             1 2 3 4 5 6 7 8 9")
    for x in range(0,9):
        word = ''+row_labels[x]+'|'
        for y in range(0,9):
            if(str(board1[9*x+y]) == '0'):
                word+='-|'
            else:
                word += str(board1[9*x+y]) + '|'
        word += "          "
        word += ''+row_labels[x]+'|'
        for z in range(0,9):
            word += str(board2[9*x+z]) + '|'
        print(word)


def is_number(s):
    try:
        float(s)
        return True
    except ValueError:
        return False


def board_check(board):

    if(len(str(board)) == 0):
        return False

    for e in board:
        if(not is_number(e)):
            print("\n    --Board is not Integer (Has ",type(board),")--")
            return False

    if(len(str(board)) < 81):
        print("\n      --Board is length,",len(str(board)) ," (< 81)--")
        return False

    return True

def board_select():
    f = open('puzzles.txt', 'r')
    total_puzzles = f.readlines()
    puzzle_number = random.randint(0,400)
    f.close()

    return puzzle_number, total_puzzles[puzzle_number]


########
#Solved#
########

#Is this board the solution?
def solved(domains, neighborhood, variables):
    for e in variables:
        for neigh in neighborhood:
            answers = list(range(1,10))
            for elem in neigh:
                if(int(domains[elem][0]) in answers):
                    answers.remove(int(domains[elem][0]))
                else:
                    return False

    return True

##############
#valid_choice#
##############

#Is this assignment valid?
def valid_choice(elem, neighbors, assignment):

    for neigh in neighbors[elem]:
        answers = list(range(1,10))
    if(int(assignment[elem][0]) != 0):
        answers.remove(int(assignment[elem][0]))
    for value in neigh:
        complete = False
    for p_val in assignment[value]:
        if(complete == False and int(p_val) !=0 and p_val in answers):
            answers.remove(int(p_val)); complete = True

    if(complete == False and int(p_val) == 0):
        complete = True

    if(complete == False):
        return False

    return True

 ##############
 #Faulty Board#
 ##############

def Faulty_Board(sudoku_input, neighborhood, variables):
    domains = dict()

    for index, elem in enumerate(variables):
        domains[elem] = [int(sudoku_input[index])]

    for e in variables:
        for neigh in neighborhood:
            answers = list(range(1,10))
            for elem in neigh:
                if(int(domains[elem][0]) == 0):
                     pass
                elif(int(domains[elem][0]) in answers):
                     answers.remove(int(domains[elem][0]))
                else:
                     return str(elem[0])+str(int(elem[1])+1)

    return False

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument('board')
    args = parser.parse_args()

    sudoku = Sudoku(args.board)

    if(not board_check(sudoku_input)):
        board_num, sudoku_input = board_select()

    print_board(sudoku_input)

    #Set up Variables
    variables =[]

    for letters in ['A','B','C','D','E','F','G','H','I']:
        for numbers in range(0,9):
            variables.append(str(letters) + str(numbers))

    #Set up Neighbors in the form: neighbors[Cell] = [[Box], [Row], [Column]]
    neighbors = dict()
    neighborhood = [['A0', 'A1', 'A2', 'B0', 'B1', 'B2', 'C0', 'C1', 'C2'],
    ['A3', 'A4', 'A5', 'B3', 'B4', 'B5', 'C3', 'C4', 'C5'],
    ['A6', 'A7', 'A8', 'B6', 'B7', 'B8', 'C6', 'C7', 'C8'],
    ['D0', 'D1', 'D2', 'E0', 'E1', 'E2', 'F0', 'F1', 'F2'],
    ['D3', 'D4', 'D5', 'E3', 'E4', 'E5', 'F3', 'F4', 'F5'],
    ['D6', 'D7', 'D8', 'E6', 'E7', 'E8', 'F6', 'F7', 'F8'],
    ['G0', 'G1', 'G2', 'H0', 'H1', 'H2', 'I0', 'I1', 'I2'],
    ['G3', 'G4', 'G5', 'H3', 'H4', 'H5', 'I3', 'I4', 'I5'],
    ['G6', 'G7', 'G8', 'H6', 'H7', 'H8', 'I6', 'I7', 'I8']]

    #Add Rows to Neighborhood
    for letters in ['A','B','C','D','E','F','G','H','I']:
        row = []
        for numbers in range(0,9):
            row.append(str(letters)+str(numbers))
            neighborhood.append(row)

    #Add Columns to Neighborhood
    for numbers in range(0,9):
        row = []
        for letters in ['A','B','C','D','E','F','G','H','I']:
            row.append(str(letters)+str(numbers))
            neighborhood.append(row)

    for elem in variables: neighbors[elem] = []

    for rows in neighborhood:
        for elem in rows:
            index = rows.index(elem)
            neighbors[elem].append(rows[:index] + rows[index + 1:]) #Add all elements in list form for box/row/column neighbors

    #Set up Domains
    domains = dict()
    solved_elems = 0

    for index, elem in enumerate(variables):
        if(int(sudoku_input[index]) == 0):
            domains[elem] = [1,2,3,4,5,6,7,8,9]
            solved_elems+=1
        else:
            domains[elem] = [int(sudoku_input[index])]

    ##########################
    #Initialize Queue of Arcs#
    ##########################
    arc_q = []

    for elem in variables:
        for neigh in neighbors[elem]:
            for elem2 in neigh:
                arc_q.append((elem,elem2))

    ########################
    #Backtracking Algorithm#
    ########################

    def backtracking(val, assignment, variables, neighbors, orig_domains):
        if(solved(assignment,neighborhood,variables)):
            return True

    for x in orig_domains[val]:
        assignment[val] = [x]
        if(valid_choice(val, neighbors, assignment)):
            passed = 0
            next_val = 0
            for mm in variables:
                if(passed == 1 and len(orig_domains[mm])>1):
                    next_val = mm
                    break
        if(mm == val):
            passed = 1

    if(next_val !=0):
        if(backtracking(next_val, assignment, variables, neighbors, orig_domains)):
            return True
        else:
            if(solved(assignment,neighborhood,variables)):
                return True


        assignment[val] = [0]
    return False

    ###############
    #AC3 Algorithm#
    ###############

    Solution = True
    ac3_elems = 0

    while arc_q:
        elem1, elem2 = arc_q.pop(0)

    #--------------#
    # Revised Func #
    #--------------#
    revised = False
    for elem1_sol in domains[elem1]:
        passed = False
    for elem2_sol in domains[elem2]:
        if(elem1_sol != elem2_sol):
            passed = True

        if(passed == False):
            domains[elem1].remove(elem1_sol)
            revised = True
            ac3_elems+=1

        if revised:
            if (len(domains[elem1]) == 0):
                Solution = False
            for neigh in neighbors[elem1]:
                for elem3 in neigh:
                    if(elem3 != elem2):
                        arc_q.append((elem3,elem1))

    ################################################
    #Perform Backtracking on Reduced Solution Space#
    ################################################

    selected = []
    answer_dict = dict()

    next_val = 0
    assignment = dict()

    for m in variables:
        if(len(domains[m]) == 1):
            assignment[m] = domains[m]
        else:
            assignment[m] = [0]

    for m in variables:
        if(len(domains[m])>1): next_val = m; break


    if(next_val != 0):
        backtracking(next_val, assignment, variables, neighbors, domains)
        answer_dict = assignment
    else:
        answer_dict = domains


    ########
    #Output#
    ########
    answer=''
    solution_found = True

    for index, elem in enumerate(variables):
        try:
            answer = answer + str(answer_dict[elem][0])
        except IndexError:
            solution_found = False

            if(solution_found):
                print("Solution Board")
                print("             "+"--------------------")
                print_board(answer)
            else:
                print("\nError! This board is not Solvable!!")

main()