"""
This code implements a Constraint Satisfaction Problem (CSP) algorithm to resolve Sudokus. 
Written using Python 3.7.

When excuting it, it reads each of the strings passed on from <input_string> = "sudokus_start.txt", as a string and converts it to a numpy array (dtype = object) to pass it onto the method 'AI_solver' which will in turn call in the AC3 method first and then combined with Backtrack search and Forward Check if AC3 alone is not successful.

Algorithm returns a file called 'output.txt', containing various lines of text, each representing the finished Sudoku board and the algorithm name used (AC3 or BTS) which solved the Sudoku board. Note this version will append each new solved puzzle to the 'outputs.txt' file instead of rewriting the file. Refer to the function write_txt() and in the code below change 'a' for 'w' for rewriting instead of appending. 
    with open(filepath, 'a') as out:
        out.write(var + '\n')
    
Example of output.txt:

148697523372548961956321478567983214419276385823154796691432857735819642284765139 BTS
435269781682571493197834562826195347374682915951743628519326874248957136763418259 BTS
956138742237954816481672953594867321128593674763421598879246135312785469645319287 BTS
794582136268931745315476982689715324432869571157243869821657493943128657576394218 BTS
249186573735942186168375429512697348976834251483251967694723815327518694851469732 BTS

"""

# builtin modules
import os
import psutil
import requests
import sys
import math
import copy
import types

# 3rd party modules
import pandas as pd
import csv
import numpy as np
from itertools import chain

class Queue:
   # class queue brought here to ensure code run in Vocareum on python 3.4. Queue implements a first-in-first-out (FIFO) queuing policy.
   # https://docs.python.org/2/tutorial/datastructures.html
   def __init__(self, initial):
      self.items = initial

   def contains(self, item):
      return item in self.items

   def empty(self):
      return len(self.items) == 0

   def push(self, item):
      self.items.insert(0,item)

   def pop(self):
      return self.items.pop()

   def size(self):
      return len(self.items)


# Set up x_keys and y_keys as global variables to use them accross all functions

global x_keys, y_keys

x_keys = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
y_keys = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
 

# Functions to setup the Sudoku board and the CSP main settings

def get_boards(filename:str = 'sudokus_start.txt'):

    input_path = os.path.join(os.getcwd(), 'data', filename)
    boards = pd.read_csv(input_path, sep=" ", header=None)

    boards = boards.values

    return boards

def setup_board(board:str):
    
    values = dict() # empty dict to assign the starting board
    index = 0
    for y in range(0, 9):
        for x in range(0, 9):
            n = board[0][index]
            if (n == "0"):
                val = np.arange(1,10)
            else:
                val = [int(n)]
            values[y_keys[y] + x_keys[x]] = val
            index += 1
    
    arcs = dict()
    for y in range(0, 9):
        for x in range(0, 9):
            key = y_keys[y] + x_keys[x]
            arcs[key] = get_neighbor_arcs(x, y)

    return values, arcs

def view_board(values:dict):
    title_row = " |  SUDOKU BOARD  | \n"
    top_row = " "
    for val in x_keys:
        top_row += " " + val
    top_row += "\n"
    
    result = title_row
    result += top_row
    result += " +-----+-----+-----+\n"

    for y in range(0, 9):
        result += y_keys[y] + "|"
        for x in range(0, 9):
            domain = values[y_keys[y] + x_keys[x]]
            if (len(domain) == 1):
                val = domain[0]
            else:
                val = 0

            result += str(val)
            if (x == 2 or x == 5 or x == 8):
                result += "|"
            else:
                result += " "
        if (y == 2 or y == 5 or y == 8):
            result += "\n +-----+-----+-----+\n"
        else:
            result += "\n"

    return print(result)


def get_neighbors(arcs:dict, Xi:int):
    result = []
    for (x,y) in arcs[Xi]:
        result.append(y)
    return result

def get_neighbor_arcs(Xi:int, Xj:int):
    arcs = dict()
    cell = y_keys[Xj] + x_keys[Xi]
    xoffs = (Xi // 3) * 3
    yoffs = (Xj // 3) * 3

    for x in range(0, 9):
        if (x != Xi):
            arcs[(cell, y_keys[Xj] + x_keys[x])] = 1
    for y in range(0, 9):
        if (y != Xj):
            arcs[(cell, y_keys[y] + x_keys[Xi])] = 1
    for x in range(xoffs, xoffs + 3):
        for y in range(yoffs, yoffs + 3):
            if (x != Xi or y != Xj):
                arcs[(cell, y_keys[y] + x_keys[x])] = 1
    return arcs.keys()

def get_arcs():
    result = []
    for y in range(0, 9):
        for x in range(0, 9):
            result += get_neighbor_arcs(x, y)
    return result

def revise(values:dict, Xi:int, Xj:int):
    D = list(values[Xi]) # define the domain D
    revised = False # set revised to False at the start

    for x in list(values[Xi]):
        for y in list(values[Xj]):
            if x != y:
                if x in D:
                    D.remove(x) # remove the value x from the domain
                revised = True # and set revised to True

    return revised, D

def solved(board_string:str):
    #when board is solved, no zeros will be in string 'board'
    #returns 'False' if '0' in board and 'True' otherwise to indicate puzzle is solved
    return (str('0') not in board_string) 


# Arc consistency algorithm AC-3

def AC3(values:dict, arcs:dict):
    """
    returns False if an inconsistency is found and True otherwise
    """
    q = Queue(get_arcs()) #queue all arcs in the csp
    while not q.empty():
        (Xi, Xj) = q.pop() #remove first value in queue
        bool, domain = revise(values, Xi, Xj)
        if bool:
            if (len(domain) == 0): # if domain has no values
                #print("AC3 inconsistency found!")
                return False
            for Xk in get_neighbors(arcs, Xi):
                q.push((Xk, Xi)) # add (Xk, Xi) to queue
        #print("AC3 no inconsistency found!")
    return True

# Backtracking Search algorithm

def BTS(values:dict, arcs:dict):
    """
    returns a solution or failure
    """
    unassigned = {}

    for key in values.keys():
        val = values[key]
        if 0 not in val:
            unassigned[key] = True
    
    method = 'BTS'

    #if len(unassigned) == 0:
    #    board_string = values_to_board(values)
    #    if solved(board_string):
    #        final_board = board_string 
    #        return (method, final_board)

    (method, final_board) = backtrack_search(unassigned, values, arcs)

    return (method, final_board)


def backtrack_search(unassigned:dict, values:dict, arcs:dict):

    # check if solved with local_assignment, and if so return results
    # first convert local_assignment values to a string
    if len(unassigned) == 0:
        board_string = values_to_board(values)
        if solved(board_string):
            final_board = board_string 
            method = 'BTS'
            return (method, final_board)
  
    # get the domain ('vars') of the first unassigned variable ('key')
    # get_unassigned uses minimum remaining values MRV and degree as heuristics
    (key, vars) = get_unassigned(values, unassigned)
    
    for var in vars:
        local_assignment = values.copy() 
        local_assignment[key] = [var] # add value of variable to assignment 'values'
        unassigned[key] = False # update unassigned for the key just assigned
        # if value is consistent with assignment then
        if (is_consistent(local_assignment, arcs, key, var)):
            # start solving using AC3 and note that 
            # if we have called backtrack_search it is because 
            # earlier attempts of solving the board with AC3 only did not succeed
            use_ac3 = AC3(local_assignment, arcs)
            unassigned = update_unassigned(local_assignment)
            view_board(local_assignment)
            board_string = values_to_board(local_assignment)
            if solved(board_string):
                final_board = board_string
                method = 'BTS'
                return (method, final_board)
            # if we're still consistent, we recurse (continue)
            if (is_consistent(local_assignment, arcs, key, var)):
                board_string = values_to_board(values)
                if solved(board_string):
                    final_board = board_string
                    method = 'BTS'
                    return (method, final_board)
                # if we didn't find the result, we will end up backtracking
                else:
                    #first update the unassigned dict with the most recent local_assignment dict
                    unassigned = update_unassigned(local_assignment)
                    (method, final_board) = backtrack_search(unassigned, local_assignment, arcs)
                    if method is not None and final_board:
                        return (method, final_board)  
            # now we will apply 'forward_checking' (another more powerful type of inference)
            # to reduce the domain 'vars' of the variables in values/unassigned when stepping out of this loop. 
            saved_data = forward_checking(key, var, local_assignment, unassigned, arcs)
            for next_key in saved_data.keys():
                values[next_key] = saved_data[next_key]
        else:
            local_assignment[key] = values[key]
            unassigned[key] = True

    #final_board = values_to_board(values)

    return ('BTS', None)


# Helper functions for the backtracking search algorithm

def forward_checking(key:str, value:int, values:dict, unassigned: dict, arcs:dict):
    saved_data = dict()
    saved_data[key] = copy.copy(values[key])
    unassigned[key] = False

    values[key] = [value]
    for Xk in get_neighbors(arcs, key):
        index = 0
        domain = list(values[Xk])
        copied = False
        for domain_val in domain:
            if (domain_val == value):
                if not copied:
                    saved_data[Xk] = copy.copy(domain)
                    copied = True
                domain.pop(index)
            else:
                index += 1

    return saved_data


def get_unassigned(values:dict, unassigned:dict):
    """
    Select Unassigned Variable 
    It uses minimum remaining values MRV and degree as heuristics
    returns a tuple of:
    unassigned key and a list of the possible values
    e.g. ('a1', [1, 2, 3, 4, 5, 6, 7, 8, 9])
    """
    
    values_sort = dict() # empty dictionary to store length of possible values array

    for key in values.keys():
        length = len(values[key]) # get the length of possible values array 
        values_sort[key] = (length) # add to dictionary for sorting in next step

    # sort the dictionary including lengths of possible values from small to large
    # this is to later on assign the items with the minimum number of remaining values first
    values_sorted = dict(sorted(values_sort.items(), key=lambda item: item[1], reverse=False))

    for key in values_sorted.keys():
        if unassigned[key] == True:
            length = values_sorted[key]
            if length > 1:
                vars = values[key]
                return key, vars


# update unassigned

def update_unassigned(local_assignment:dict):

    unassigned = {}

    for k in local_assignment.keys():
                val = local_assignment[k]
                if len(val) == 1:
                    unassigned[k] = False
                if len(val) > 1:
                    unassigned[k] = True

    return unassigned

# check if value for given key is arc consistent

def is_consistent(values:dict, arcs:dict, key, value:int):
    result = True

    for Xk in get_neighbors(arcs, key):
        vals = values[Xk]
        if (len(vals) == 1 and vals[0] == value):
            result = False

    return result

def clone_values(values:dict):
    cloned_values = dict()
    for key in values.keys():
        newValues = []
        for nextValue in values[key]:
            newValues.append(nextValue)
        cloned_values[key] = newValues
    return cloned_values

def values_to_board(values:dict):
    result ="" # initiate the variable which will take the resulting string
    # iterate on dict values using the global variables y_keys and x_keys
    for y in range(0, 9):
        for x in range(0, 9):
            domain = values[y_keys[y] + x_keys[x]]
            if (len(domain) == 1):
                val = domain[0]
            else:
                val = 0
            result += str(val) # append to resulting string

    return result

# Write the outputs to a txt file per the assingment requirements

def write_txt(filename_outputs:str = 'output.txt', final_str:str = None):
    # write the outputs csv file
    filepath = os.path.join(os.getcwd(),'data', filename_outputs)
    var = final_str
    with open(filepath, 'a') as out:
        out.write(var + '\n')
    return print("New Outputs file saved to: <<", filename_outputs, ">>", sep='', end='\n')

# The main function for the AI Sudoku solver. 
# We call all other functions from this one.

def AI_solver(board):
    """
    sudoku player using AC3 or BTS
    """
    values, arcs = setup_board(board)
    print("Start Board", end="\n")
    view_board(values)
    print("First try with AC3 alone...", end="\n")
    use_ac3 = AC3(values, arcs) 
    board_string = values_to_board(values)
    if solved(board_string):
        method = 'AC3'
        final_str = ' '.join([str(board_string), method])
        write_txt('output.txt', final_str)
        print("This one was solved with AC3 alone!", end="\n")
        view_board(values)
        return print(final_str)
    else:
        print("AC3 alone did not work so we try with backtrack and forward checking", end="\n")
        method, final_board = BTS(values, arcs)
        method = 'BTS'
        if solved(final_board):
            final_str = ' '.join([str(final_board), method])
            write_txt('output.txt', final_str)
            return print(final_str)


# Helper for executing this file from the terminal
def usage():
   print("python driver.py <input_string>")
   sys.exit(2)

###################################################

def main():

    #take a string as input data from sudokus_start.txt file
    #input_string = str(sys.argv[1]) 
    input_string = 'sudokus_start.txt'
    boards = get_boards(input_string)
    for board in boards:
    #board = boards[0]
        AI_solver(board)
    
if __name__ == '__main__':
    main()