import numpy as np
from queue import Queue, LifoQueue
import time
import copy


class Recoder():
    point = None  # 进行猜测的点
    point_index = 0  # 猜测候选列表使用的值的索引
    value = None  # 回溯记录的值


class Sudo():
    def __init__(self, data):
        # 数据初始化(二维的object数组)
        self.value = np.array([[0] * 9] * 9, dtype=object)
        self.new_points = Queue()  # 先进先出的新解坐标
        self.recoder = LifoQueue()  # 先进后出的回溯器
        self.guess_times = 0  # 猜测次数

        # 九宫格的基准列表
        self.base_points = [[0, 0], [0, 3], [0, 6], [3, 0], [3, 3], [3, 6], [6, 0], [6, 3], [6, 6]]

        # 整理数据
        data = np.array(data).reshape(9, -1)
        for r in range(0, 9):
            for c in range(0, 9):
                if data[r, c]:
                    self.value[r, c] = data[r, c]
                    # 新点添加到列表中，以便遍历
                    self.new_points.put((r, c))
                else:
                    self.value[r, c] = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    # 剔除数字
    def _cut_num(self, point):
        r, c = point
        val = self.value[r, c]

        # 行
        for i, item in enumerate(self.value[r]):
            if isinstance(item, list):
                if item.count(val):
                    item.remove(val)

                    # 判断移除后，是否剩下一个元素
                    if len(item) == 1:
                        self.new_points.put((r, i))
                        self.value[r, i] = item[0]

        # 列
        for i, item in enumerate(self.value[:, c]):
            if isinstance(item, list):
                if item.count(val):
                    item.remove(val)

                    # 判断移除后，是否剩下一个元素
                    if len(item) == 1:
                        self.new_points.put((i, c))
                        self.value[i, c] = item[0]

        # 所在九宫格(3x3的数组)
        b_r, b_c = [x // 3 * 3 for x in point]  # 九宫格基准点
        for m_r, row in enumerate(self.value[b_r:b_r + 3, b_c:b_c + 3]):
            for m_c, item in enumerate(row):
                if isinstance(item, list):
                    if item.count(val):
                        item.remove(val)

                        # 判断移除后，是否剩下一个元素
                        if len(item) == 1:
                            r = b_r + m_r
                            c = b_c + m_c
                            self.new_points.put((r, c))
                            self.value[r, c] = item[0]

    # 同一行、列或九宫格中1~9可能性只有一个的情况
    def _check_one_possbile(self):
        # 同一行只有一个数字的情况
        for r in range(0, 9):
            values = [x for x in self.value[r] if isinstance(x, list)]

            for c, item in enumerate(self.value[r]):
                if isinstance(item, list):
                    for value in item:
                        if sum([x.count(value) for x in values]) == 1:
                            self.value[r, c] = value
                            self.new_points.put((r, c))
                            return True

        # 同一列只有一个数字的情况
        for c in range(0, 9):
            values = [x for x in self.value[:, c] if isinstance(x, list)]

            for r, item in enumerate(self.value[:, c]):
                if isinstance(item, list):
                    for value in item:
                        if sum([x.count(value) for x in values]) == 1:
                            self.value[r, c] = value
                            self.new_points.put((r, c))
                            return True

        # 九宫格内的单元格只有一个数字的情况
        for r, c in self.base_points:
            values = [x for x in self.value[r:r + 3, c:c + 3].reshape(1, -1)[0] if isinstance(x, list)]

            for m_r, row in enumerate(self.value[r:r + 3, c:c + 3]):
                for m_c, item in enumerate(row):
                    if isinstance(item, list):
                        for value in item:
                            if sum([x.count(value) for x in values]) == 1:
                                self.value[r + m_r, c + m_c] = value
                                self.new_points.put((r + m_r, c + m_c))
                                return True

    # 同一个九宫格内数字在同一行或同一列处理
    def _check_same_num(self):
        for b_r, b_c in self.base_points:
            block = self.value[b_r:b_r + 3, b_c:b_c + 3]

            # 判断数字1~9在该九宫格的分布情况
            data = block.reshape(1, -1)[0]
            for i in range(1, 10):
                result = [0 if not isinstance(x[1], list) else x[0] + 1 if x[1].count(i) else 0 for x in
                          enumerate(data)]
                result = [x for x in result if x > 0]
                r_count = len(result)

                if r_count in [2, 3]:
                    # 2或3个元素才有可能同一行或同一列
                    rows = [(x - 1) // 3 for x in result]
                    cols = [(x - 1) % 3 for x in result]

                    if len(set(rows)) == 1:
                        # 同一行，去掉其他行的数字
                        result = [b_c + (x - 1) % 3 for x in result]
                        row = b_r + rows[0]

                        for col in range(0, 9):
                            if not col in result:
                                item = self.value[row, col]
                                if isinstance(item, list):
                                    if item.count(i):
                                        item.remove(i)

                                        # 判断移除后，是否剩下一个元素
                                        if len(item) == 1:
                                            self.new_points.put((row, col))
                                            self.value[row, col] = item[0]
                                            return True

                    elif len(set(cols)) == 1:
                        # 同一列
                        result = [b_r + (x - 1) // 3 for x in result]
                        col = b_c + cols[0]

                        for row in range(0, 9):
                            if not row in result:
                                item = self.value[row, col]
                                if isinstance(item, list):
                                    if item.count(i):
                                        item.remove(i)

                                        # 判断移除后，是否剩下一个元素
                                        if len(item) == 1:
                                            self.new_points.put((row, col))
                                            self.value[row, col] = item[0]
                                            return True

    # 排除法解题
    def solve_sudo(self):
        is_run_same = True
        is_run_one = True

        while is_run_same:
            while is_run_one:
                # 剔除数字
                while not self.new_points.empty():
                    point = self.new_points.get()  # 先进先出
                    self._cut_num(point)

                # 检查单个数字的情况
                is_run_one = self._check_one_possbile()

            # 检查同行或列的情况
            is_run_same = self._check_same_num()
            is_run_one = True

    # 得到有多少个确定的数字
    def get_num_count(self):
        return sum([1 if not isinstance(x, list) else 0 for x in self.value.reshape(1, -1)[0]])

    # 评分，找到最佳的猜测坐标
    def get_best_point(self):
        best_score = 0
        best_point = (0, 0)

        for r, row in enumerate(self.value):
            for c, item in enumerate(row):
                point_score = self._get_point_score((r, c))
                if best_score < point_score:
                    best_score = point_score
                    best_point = (r, c)
        return best_point

    # 计算某坐标的评分
    def _get_point_score(self, point):
        # 评分标准 (10-候选个数) + 同行确定数字个数 + 同列确实数字个数
        r, c = point
        item = self.value[r, c]

        if isinstance(item, list):
            score = 10 - len(item)
            score += sum([1 if isinstance(x, int) else 0 for x in self.value[r]])
            score += sum([1 if isinstance(x, int) else 0 for x in self.value[:, c]])
            return score
        else:
            return 0

    # 检查有没错误
    def check_value(self):
        # 行
        for row in self.value:
            nums = []
            lists = []
            for item in row:
                (lists if isinstance(item, list) else nums).append(item)
            if len(set(nums)) != len(nums):
                return False  # 数字要不重复
            if len([x for x in lists if len(x) == 0]):
                return False  # 候选列表不能为空集

        # 列
        for c in range(0, 9):
            nums = []
            lists = []
            col = self.value[:, c]

            for item in col:
                (lists if isinstance(item, list) else nums).append(item)
            if len(set(nums)) != len(nums):
                return False  # 数字要不重复
            if len([x for x in lists if len(x) == 0]):
                return False  # 候选列表不能为空集

        # 九宫格
        for b_r, b_c in self.base_points:
            nums = []
            lists = []
            block = self.value[b_r:b_r + 3, b_c:b_c + 3].reshape(1, -1)[0]

            for item in block:
                (lists if isinstance(item, list) else nums).append(item)
            if len(set(nums)) != len(nums):
                return False  # 数字要不重复
            if len([x for x in lists if len(x) == 0]):
                return False  # 候选列表不能为空集
        return True

    # 猜测记录
    def recode_guess(self, point, index=0):
        # 记录
        recoder = Recoder()
        recoder.point = point
        recoder.point_index = index
        recoder.value = copy.deepcopy(self.value)
        self.recoder.put(recoder)
        self.guess_times += 1  # 记录猜测次数

        # 新一轮的排除处理
        item = self.value[point]
        self.value[point] = item[index]
        self.new_points.put(point)
        self.solve_sudo()

    # 回溯，需要先进后出
    def reback(self):
        while True:
            if self.recoder.empty():
                raise Exception('sudo is wrong')
            else:
                recoder = self.recoder.get()
                point = recoder.point
                index = recoder.point_index + 1
                item = recoder.value[point]

                # 判断索引是否超出范围。若超出，则再回溯一次
                if index < len(item):
                    break

        self.value = recoder.value
        self.recode_guess(point, index)

    # 解题
    def calc(self):
        # 第一次解题
        self.solve_sudo()

        # 检查有没错误的，有错误的则回溯；没错误却未解开题目，则再猜测
        while True:
            if self.check_value():
                if self.get_num_count() == 81:
                    break
                else:
                    # 获取最佳猜测点
                    point = self.get_best_point()

                    # 记录并处理
                    self.recode_guess(point)
            else:
                # 出错，则回溯，尝试下一个猜测
                self.reback()
        return self.value


if __name__ == '__main__':
    data = [[0, 0, 6, 1, 0, 0, 4, 0, 0],
            [0, 5, 0, 0, 3, 0, 0, 0, 8],
            [0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 8, 0, 7, 0, 4, 0, 0, 0],
            [0, 2, 0, 0, 0, 0, 0, 5, 3],
            [0, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 0, 4, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 2, 0, 0, 3, 0],
            [0, 0, 7, 0, 0, 0, 0, 0, 0]]

    t1 = time.time()
    sudo = Sudo(data)
    result = sudo.calc()
    t2 = time.time()

    print(result)
    print("耗时：%.3fs" % (t2 - t1))
