### 瀏覽

- 索引
- 模組 |
- SudokuStudyLib 1.0 documentation »
- Module code »

# Source code for sudoku.sudoku

    """
    .. module:: sudoku
       :platform: Unix, Windows
       :synopsis: oop's method of solving sudoku

    .. moduleauthor:: Robert J. Hwang <RobertOfTaiwan@gmail.com>
    """

    import sys
    import copy
    import itertools
    import traceback
    import time
    import os

    ACTION_SET = 's'  # action of set number
    ACTION_REDUCE = 'r'  # action of reduce number
    WRITEN_POSSIBLE_LIMITS = 3  # When a position's possible numbers <= this numer,
    # it will be assume that it's possible number has been writen down for a human,
    # 0 is same as 9 means no any limit
    ACTION_GET_INFO = True  # if want to get the info of an action,
    # those can be re-played by the info to describe the action
    SCAN_ONE_NUMBER = True  # in the methods of scanning numbers, use this to scan only one number
    SCAN_ALL_NUMBER = False  # in the methods of scanning numbers, use this to scan all numbers
    SCAN_DEF_BEGIN = 1  # in the methods of scanning number, the default begin number
    METHOD_DEF_BEGIN = 0  # the default idx of a serial methods to start
    METHOD_FILL_LAST = 0  # the idx of the method of filling the last position in a group
    METHOD_CHECK_OBVIOUS = 1  # the idx of the method of check obvious numbers
    METHOD_WRITE_POSSIBLE = 4  # the method which write down all possible numbers in the positions
    DEBUG_MODE = True  # it is in the debug mode?
    CHECK_MORE_OBVIOUS = True  # When a postion will be setting in a method, does check it for more obvious way?
    METHOD_BASIC_LEVEL = 7  # Basic methods
    METHOD_EMULATE_START = 8  # the emulate method begin idx
    METHOD_USE_TRY = True  # the default of using try method or not
    METHOD_USE_EMU = False  # the default of using emulator
    METHOD_LEVEL_LIMIT_WHENTRY = 2  # if start using try, set the level limit to use

    class Status():
        """To Store running condition

        :methodLoopIdx: int, the index of the methods loops
        :methodIdx: int, the method idx which run now
        :checkPos: Point list, set this variable, if you want to make an exception when this position has been set
        :writeDownAlready: bool, if the every un-assigned positions have been writen down their possible number?
        :emulatePossibles: int, to set the possibles when using emulate method, for both positions and numbers
        :tryStack: list of (m, x, y, idx)

        - m: Matrix object, the Matrix copy before try to set (x, y) to be the idx of possible numbers
        - x: int, the position x of trying
        - y: int, the position y of trying
        - idx: int, the index of the possible numbers, starting from 0

        :tryIdx: int, the depth index of trying
        :tryUse: bool, if using Guess method or not
        :emuUse: bool, if using emulator methods or not
        :Scope: int, the difficult level of this sudoku
        :Level: int, the level Limit, 0 means no limit
        :Original: Matrix, the init Matrix
        :Result: Matrix, the now Matrix
        :printSteop: bool, if print the steps of solving
        :nowPath: str, record now path
        """

        name = {}
        name["methodLoopIdx"] = 0
        name["methodIdx"] = 0
        name["checkPos"] = None
        name["writeDownAlready"] = False
        name["emulatePossibles"] = 2
        name["tryStack"] = []
        name["tryIdx"] = 0
        name["tryUse"] = True
        name["emuUse"] = True
        name["Scope"] = 0
        name["Level"] = 0
        name["Original"] = None
        name["Result"] = None
        name["printStep"] = False
        name["nowPath"] = os.path.abspath(os.path.dirname(__file__))

        def __init__(self):
            pass

    class SudokuError(Exception):
        """An exception when x, y can't be set or reduce to or form the number v
        t: is the type: 's' means set, 'r' means reduce"""

        def __init__(self, x, y, v, t):
            """
            :param x: int, position x, which occurs an error
            :param y: int, position y, which occurs an error
            :param v: int, the number be set or reduced that occurs an error
            :param t: char, "s" -- set, "r" -- reduce
            """
            self.x = x
            self.y = y
            self.v = v
            self.t = t

    class SudokuDone(Exception):
        """An exception When the table has been filled 81 positions"""

        def __init__(self, x, y, v):
            """
            :param x: int, last position x, when done
            :param y: int, last position y, when done
            :param v: int, the last number be set, when done
            """

            self.x = x
            self.y = y
            self.v = v

    class SudokuStop(Exception):
        """An exception When the the record number >= recLimit"""

        def __init__(self):
            pass

    class SudokuWhenPosSet(Exception):
        """An exception When the position, checkPos, has been set, and program want to setit"""

        def __init__(self, x, y, v):
            """
            :param x: int, position x, when one of the check positions has been set
            :param y: int, position y, when one of the check positions has been set
            :param v: int, the number be set
            """

            self.x = x
            self.y = y
            self.v = v

    class Point:
        """A Position in a Sudoku's table

        .. note:: We can imagine that a Point object is an house

        """

        def __init__(self, x, y):
            """This is the init of Point Object

            :param x: int, the x position of this object
            :param y: int, the y position of this object
            """
            self.x = x
            self.y = y
            self.v = 0
            self.possible = list(i for i in range(1, 10))
            self.writen = False  # does the position's possible number has been writen by man
            self.b = int(x / 3) * 3 + int(y / 3)  # the box index which this position belong to

        def __repr__(self):
            return "p({0},{1})".format(self.x + 1, self.y + 1)

        def can_see(self, p1):
            """Check this position can see p1?

            :param p1: Point, a point object
            :returns: int, the value can't be 3 or 7 it means the same pos

            return code:

            - 0: can't see p1
            - 1: can see it in x line
            - 2: can see it in y line
            - 4: can see it in the box
            """

            if self == p1:
                return -1
            rtn = 0
            if self.x == p1.x:
                rtn += 1
            if self.y == p1.y:
                rtn += 2
            if self.b == p1.b:
                rtn += 4
            return rtn

        def can_see_those(self, posList):
            """check this position can see which positions in the posList

            :param posList: list, a [(x, y),...] list
            :returns: list, [(x, y),...

            """

            rtn = []
            for x, y in posList:
                if self.x == x and self.y == y:
                    continue
                if x == self.x or y == self.y:
                    rtn.append((x, y))
            return rtn

    class GroupBase:
        """The Base Class of a Line or Box"""

        def __init__(self, idx, p):
            """The init function of a GroupBase object

            :param idx: int, the id of this object
            :param p: the point object list in this object

            """

            self.idx = idx
            self.p = p
            self.filled = 0
            self.possible = list(i for i in range(1, 10))
            self.chain = []  # store this group's chain positions

        def allow(self, v):
            """check the group can be filled the number(v)?

            :param v: int, the number to be checked

            :returns: True or False

            """

            for p1 in self.p:
                if p1.v == v:
                    return False
            return True

        def get_num_pos(self, v):
            """get the position of a group which have been filled the number(v

            :param v: int, the number to be found its position

            :returns: None or a Point object

            """

            rtn = None
            for p1 in self.p:
                if p1.v == v:
                    rtn = p1
                    break
            return rtn

        def count_num_possible(self, count=1):
            """get the un-assigned position in this group, and possible numbers only in [count] positions

            .. note:: The output format is a tuple list, the tuple has two value, one is number,
                      another is s position list

            :param count: int, how many positions are un-assigned to get

            :returns: list, [(num,[p1, p2...]),...]

            """

            rtn = []
            # count all possible number in to c and pos list, c is the times it show in the position,
            # p records which positions
            c = list(0 for x in range(9))
            pos = list([] for x in range(9))
            for p1 in self.get_all_pos(method="u"):
                for num in p1.possible:
                    c[num - 1] += 1
                    pos[num - 1].append(p1)
            # get all the times = count
            for i in range(9):
                if c[i] == count:
                    rtn.append((i + 1, pos[i]))

            return rtn

        def get_all_pos(self, diff=[], method="a", num=0, notInLineX=None, notInLineY=None, chain=None, possibles=None):
            """get position list in this group

            :param diff: list, exclude the positions in it
            :param method: char, a: all, s:has assigned, u:not assigned
            :param num: int, if method is u and set the number to 1-9, will get all possible pos which are possible to be assigned the num
            :param notInLineX: bool, exclude the x line's positions
            :param notInLineY: bool, exclude the y line's positions
            :param chain: bool, if set, check it, if it is True, just get the chain positions, or get the un-chained positions
            :param possibles: int, if method="u" and possibles!=None, it will only get the possible set's length = possibles

            :returns: list: a List of Position
            """
            rtn = []
            lGetOtherThan = len(diff) > 0
            for p1 in self.p:
                if (method == "u" and p1.v != 0) or (method == "s" and p1.v == 0):
                    continue
                if lGetOtherThan and p1 in diff:
                    continue
                if num != 0 and method == "u" and num not in p1.possible:
                    continue
                if p1.x == notInLineX or p1.y == notInLineY:
                    continue
                if chain is not None:
                    if (chain and p1 not in self.chain) or (not chain and p1 in self.chain):
                        continue
                if possibles and method == "u":
                    if len(p1.possible) != possibles:
                        continue
                rtn.append(p1)
            return rtn

    class LineX(GroupBase):
        """Line of X"""

        def __repr__(self):
            rtn = ""
            for x in self.p:
                rtn += "{0:3d}\n".format(x.v)
            return rtn

    class LineY(GroupBase):
        """Line of Y"""

        def __repr__(self):
            rtn = ""
            for x in self.p:
                rtn = rtn + "{0:3d}".format(x.v)
            return rtn

    class Box(GroupBase):
        """A 3x3 Box Object"""

        def __init__(self, idx, p):
            """
            :param idx: int, the box's id
            :param p: the Point object list of this object

            .. note:: This will replace the original GroupBase's init()

            """
            super(Box, self).__init__(idx, p)
            x = int(idx / 3)
            y = idx % 3
            # record all the box's related boxes
            self.effects = set()
            self.effectsX = set()  # x-direction's effect boxes
            self.effectsY = set()  # y-direction's effect boxes
            for i in range(3):
                for j in range(3):
                    if (i == x and j != y) or (i != x and j == y):
                        idx = i * 3 + j
                        self.effectsX.add(idx) if i == x else self.effectsY.add(idx)
                        self.effects.add(idx)
            self.groupnumber = set()  # record the box's group number

        def __repr__(self):
            rtn = ""
            for i in range(3):
                for j in range(3):
                    p1 = self.p[j * 3 + i]
                    rtn = rtn + "{0:3d}".format(p1.v)
                rtn += "\n"
            return rtn

        def get_group_number(self, num, pos=[], notInLineX=None, notInLineY=None):
            """if the unassigned num in this box which it's all possible positions have the same direction,
            we call it as a GroupNumber

            :param num: int, find this num, it is a group number in this box
            :param pos: list, the Point object list which to find a group number, if it is empty, the function will get all unassigned points to be a list
            :param notInLineX: bool, to call get_all_pos to not include x-line's unassigned point
            :param notInLineY: bool, as above, but y-line

            :return: GroupNumber, none or a GroupNumber Object
            """
            if len(pos) <= 0:
                pos = super(Box, self).get_all_pos(num=num, method="u", notInLineX=notInLineX, notInLineY=notInLineY)

            amt = len(pos)
            if amt < 2 or amt > 3:
                return None

            # check the first two position and decide the direction
            if pos[0].x == pos[1].x:
                idx = pos[0].x
                direction = "x"
            elif pos[0].y == pos[1].y:
                idx = pos[0].y
                direction = "y"
            else:
                return None

            # if there is three possible position, check it
            if amt > 2:
                if not (pos[2].x == idx if direction == "x" else pos[2].y == idx):
                    return None
            # record the number
            self.groupnumber.add(num)

            return GroupNumber(self.idx, num, pos, direction, idx)

    class GroupNumber():
        """Group Number in Box"""

        def __init__(self, b, num, p, direction, idx):
            """
            :param b: int, the Box Object Idx
            :param num: int, the number that the object presents
            :param p: Point List, the Point Object List that form this Group Number
            :param direction: char, "x" or "y" means the direction of this Group Number
            :param idx: int, the line(x or y) index
            """
            self.b = b  # box idx
            self.num = num  # 1..9
            self.p = p  # the positions' list which form a group number
            self.direction = direction  # "x": as a x-line's number, "y": as a y-line's number
            self.idx = idx  # x-line or y-line's index

        def __repr__(self):
            rtn = "GroupNumber({0}) in box({1}) formed by {2} at line-{3}({4})".format(self.num, self.b, repr(self.p),
                                                                                       self.direction, self.idx)
            return rtn

    class Number:
        """Number Object

        .. note:: You can imagine that an object of this class is equal to a country,
                  every country has its own id from 1-9.
        """

        def __init__(self, v):
            """
            :param v: int, the id of the Number, from 1 to 9
            """

            self.v = v
            self.p = list()  # record every member's position
            self.filled = 0
            self.group = []  # store the GroupNumber info

        def __repr__(self):
            return repr(self.p)

        def setit(self, p1):
            """ save assigned position in the p list

            :param p1: Point, a position that are assigned to this object
            """

            self.p.append(p1)
            self.filled += 1

        def can_see_by_group_number(self, p1):
            """Check if the position, p1, can be seen of all this number's group number

            :param p1: Point, a position

            :return: gn if can be seen by it, or None
            """
            if len(self.group) <= 0:
                return None
            for gn in self.group:
                if gn.b == p1.b:  # at the same box
                    continue
                if (gn.direction == "x" and p1.x == gn.idx) or (gn.direction == "y" and p1.y == gn.idx):
                    return gn
            return None

    class Chain:
        """A chain of two and above positions which are not in the same box but in the same line and can form a chain,
        means the possible number in this chain positions only can be filled in these positions
        """

        def __init__(self, numList, posList):
            """
            :param numList: int list, presents the numbers of this chain
            :param posList: Point list, presents the positions that form the chain
            """
            self.numList = numList
            self.posList = posList
            #self.direction = "x" if posList[0].x == posList[1].x else "y"
            #self.idx = posList[0].x if self.direction == "x" else posList[0].y

        def __repr__(self):
            return "chain({0} in Pos({1})".format(self.numList, self.posList)

    class Matrix:
        """A Table of a Sudoku"""

        def __init__(self, file=""):
            """
            :param file: file, the define file of a sudoku

            Properties:

            - rec: list of (x, y, v, t, d), the record of all the solving steps
            - filled: int, the amount of assigned points
            - done: bool, if solved or not
            - error: bool, if there is an error occurs
            - lineX: LineX list
            - lineY: LineY list
            - b: Box List
            - p: a two dimensions of list of Point
            - n: Number list
            - chain: Chain list
            """
            self.rec = []  # record all the steps,
            # element's format is (x, y, v, t, d), t="s"|"r", d="Description String"
            self.filled = 0  # record how many numbers have been assigned in this table
            self.done = False  # if solved or not
            self.error = False  # if there is an error occurs
            self.lineX = list([] for i in range(9))
            self.lineY = list([] for i in range(9))
            self.b = list([] for i in range(9))
            self.p = list(list(Point(y, x) for x in range(9)) for y in range(9))
            self.n = list([] for i in range(10))
            for i in range(9):
                self.lineX[i] = LineX(i, list(self.p[i][j] for j in range(9)))
            for i in range(9):
                self.lineY[i] = LineY(i, list(self.p[j][i] for j in range(9)))
            for i in range(3):
                for j in range(3):
                    idx = i * 3 + j
                    self.b[idx] = Box(idx, list(self.p[3 * i + x][3 * j + y] for x in range(3) for y in range(3)))
            for i in range(1, 10):  # the first, index=0 will not be used
                self.n[i] = Number(i)

            self.chain = []  # store chains in this list

            # read define
            if file != "":
                self.read(file)

        def get_all_pos(self, diff=[], method="a", num=0, chain=None, possibles=None):
            """get all positions, to call the :meth:GroupBase.get_all_pos function to get it

            :param diff: Point list, other than the postions in this list
            :param method: char, "a" -- all, "u" -- unassigned, "s" -- assigned
            :param num: int, the unassigned position which has the [num] in its possible numbers
            :param chain: bool, if set, check it, if it is True, just get the chain positions, or get the un-chained positions
            :param possibles: int, if set, only get the unassigned positions that those possible numbers are equal to it

            :return: Point list
            """
            rtn = []
            for line in self.lineX:
                rtn = rtn + line.get_all_pos(method=method, num=num, chain=chain, diff=diff, possibles=possibles)
            return rtn

        def sort_unassigned_pos_by_possibles(self, possibles=0):
            """Get unassign position's possible number list, format is [p1, p2,...]
            and Sorted By the possible numbers

            :param possibles: 0 for all, >=2, mean get only the possible numbers for it

            :return: Point list
            """
            rtn = []
            check = possibles >= 2
            for i in range(9):
                for j in range(9):
                    if self.p[i][j].v != 0:
                        continue
                    if check and len(self.p[i][j].possible) != possibles:
                        continue
                    rtn.append(self.p[i][j])
            rtn = sorted(rtn, key=lambda pos: len(pos.possible))
            return rtn

        def can_see(self, p0, method="u", num=0):
            """get the position list which can see the position, p

            :param method: char, "u": un-assigned positions, "a": all, "s": assigned positions
            :param num: if method="u", the position must have be possible to be filled the number

            :return: Point list
            """
            rtn = []
            for group in (self.lineX[p0.x].p, self.lineY[p0.y].p, self.b[p0.b].p):
                for p1 in group:
                    if p1 == p0 or p1 in rtn:
                        continue
                    if method == "u":
                        if p1.v != 0 or (num != 0 and num not in p1.possible):
                            continue
                    elif method == "s":
                        if p1.v == 0:
                            continue
                    rtn.append(p1)
            return rtn

        def setit(self, x, y, v, d="define", info=""):
            """set the position x, y to be the number v

            :param x: int, x position
            :param y: int, y position
            :param v: int, the number of this position
            :param d: str, the description of the solving
            :param info: str, the detail methods of the solving

            :return: int, >=1 if set successfully, 0 if it can't be set the number v
            """

            sets = 0
            if not self.allow(x, y, v):
                raise SudokuError(x, y, v, ACTION_SET)
                return 0

            idx = self.p[x][y].b

            # the position(x, y)'s possible set to be empty
            self.p[x][y].possible.clear()

            # the filled numbers add one
            self.filled += 1
            self.lineX[x].filled += 1
            self.lineY[y].filled += 1
            self.b[idx].filled += 1

            # reduce every group's possible number set
            self.b[idx].possible.remove(v)
            self.lineX[x].possible.remove(v)
            self.lineY[y].possible.remove(v)

            # set number in this position
            sets += 1
            self.p[x][y].v = v

            # reduce all effect's positions' possible numbers
            for p1 in self.can_see(self.p[x][y], method="u", num=v):
                rtn = self.reduce(p1.x, p1.y, v, d="set")
                if rtn >= 2:
                    sets += 1

            # record the number's position
            self.n[v].setit(self.p[x][y])

            # record this step
            if d != "define":
                self.rec.append((x, y, v, ACTION_SET, d, info))

            # check if it is done
            if self.filled == 81:
                raise SudokuDone(x, y, v)

            if DEBUG_MODE:
                # check the checkPos is set and now the position is it or not
                if Status.name["checkPos"] and (x, y) in Status.name["checkPos"]:
                    raise SudokuWhenPosSet(x, y, v)

            #if d != "define":
            #   print("set: p({0},{1})={2} by {3}({4})".format(x+1, y+1, v, d, info))

            return sets

        def print_rec(self):
            """Print all the steps of solving process"""
            i = 0
            for x, y, v, t, d, info in self.rec:
                i += 1
                print("{5:3d}-{4}: p({0},{1})={2} by {3} - {6}".format(x + 1, y + 1, v, d, t, i, info))

        def reduce(self, x, y, v, d="set", check=False, info=""):
            """reduce the position(x, y)'s possible numbers from v

            :param x: int, x position
            :param y: int, y position
            :param v: int, the possible number
            :param d: str, the description of solving
            :param check: bool, check or not
            :param info: str, the details of solving

            :return: int, as following code

            - 2: if set a number,
            - 1: if just set number
            - 0: if is not in the possible set, if check is True, it will raise an SudokuError exception
            """

            if len(self.p[x][y].possible) <= 1:
                raise SudokuError(x, y, v, ACTION_REDUCE)

            if v in self.p[x][y].possible:
                self.p[x][y].possible.remove(v)
                # record this step
                if d != "set":
                    self.rec.append((x, y, v, ACTION_REDUCE, d, info))
                return 1
            else:
                if check:
                    raise SudokuError(x, y, v, ACTION_REDUCE)
                else:
                    return 0

        def allow(self, x, y, v):
            """Checking if the position x, y, can be set the value v

            :param x: int, x position
            :param y: int, y position
            :param v: int, the number

            :return: True or False
            """

            idx = self.p[x][y].b
            if self.p[x][y].v != 0 or not self.lineX[x].allow(v) or not self.lineY[y].allow(v) or not self.b[idx].allow(v):
                return False
            else:
                return True

        def read(self, file):
            """Read Sudoku's Define from file

            :param file: file, the sudoku define file, can give it the absolute path name,
                        if only the file name, it would find file in the data path.
            """

            if not os.path.isfile(file):
                file = "data/" + file
            try:
                f = open(file, "r")
            except IOError:
                return -1

            i = 0
            for line in f:
                if len(line) > 0:
                    index = line.split(",")
                    x, y = (int(index[0]) - 1, int(index[1]) - 1)
                    v = int(index[2])
                    self.setit(x, y, v)
                    i += 1
            return i

        def __repr__(self):
            rtn = ""
            for i in range(9):
                for j in range(9):
                    rtn = rtn + "{0:3d}".format(self.p[j][i].v)
                rtn += "\n"
            return rtn

    def fill_only_one_possible(m, **kw):
        """Check every unassigned position, if it's possible numbers left one only WRITEN_POSSIBLE_LIMIT:  True, Check position's writen is True or note False, don't check.

        :param m: Matrix Object
        :param first: int, the first number of checking
        :param only: bool, just check the first number or not

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """
        sets = 0
        for line in m.p:
            for p1 in line:
                if (WRITEN_POSSIBLE_LIMITS == 0 or (WRITEN_POSSIBLE_LIMITS > 0 and p1.writen)) and p1.v == 0 and len(
                        p1.possible) == 1:
                    m.setit(p1.x, p1.y, p1.possible[0], d="Only One Possible")
                    sets += 1
        return sets, 0, METHOD_DEF_BEGIN, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

    def fill_last_position_of_group(m, **kw):
        """If the un-assigned positions in a group(line or box) are only one left

        :param m: Matrix Object

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        sets = 0
        for grouptype in (m.lineX, m.lineY, m.b):
            for grp in grouptype:
                if grp.filled == 8:
                    for p1 in grp.p:
                        if p1.v == 0:
                            m.setit(p1.x, p1.y, grp.possible[0],
                                    d="Last Position in a {0}: {1}".format(grp.__doc__, grp.idx))
                            sets += 1
                            break
        return sets, 0, METHOD_DEF_BEGIN, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

    def fill_last_position_by_setting(m, sets):
        """When setting a number, may cause 1-3 groups left only one possible position
        check if a group have only position left, just set it.

        :param m: Matrix Object
        :param sets: int, how many last sets want to be checked

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        recIdx = len(m.rec) - 1
        idx = 1
        rtn = 0
        v = 1
        # process every sets from the end of records
        while idx <= sets:
            while True:
                r = m.rec[recIdx]
                if r[3] != "s":
                    recIdx -= 1
                else:
                    break
            x = r[0]
            y = r[1]

            for group in (m.lineX[x], m.lineY[y], m.b[m.p[x][y].b]):
                if len(group.possible) != 1:
                    continue
                for p1 in group.p:
                    if p1.v == 0:
                        v = group.possible[0]
                        m.setit(p1.x, p1.y, v, d="Last Position By Setting")
                        rtn += 1

            idx += 1  # next settings

        return rtn, 0, METHOD_CHECK_OBVIOUS, v, SCAN_ALL_NUMBER

    def set_obvious_method_for_pos(m, method1, p1, v):
        """Check is there an more obvious method for the position, p1 than method1
        Obvious methods include fillLastPositionOfGroup=0 and checkObviousNumber=1

        :param m: Matrix object
        :param method1: int, method index
        :param p1: Point, the postion to be checked
        :param v: int, the number to be assigned

        :return: True: set, False: not set
        """

        if method1 > METHOD_FILL_LAST:
            # check p1 is an last postion in a group or not
            if m.lineX[p1.x].filled == 8 or m.lineY[p1.y].filled == 8 or m.b[p1.b].filled == 8:
                m.setit(p1.x, p1.y, v, d="Change To Be Last Position!")
                return True
        if method1 > METHOD_CHECK_OBVIOUS:
            info = ""
            # check p1 can get in an obvious way, like METHOD_CHECK_OBVIOUS
            for p2 in m.b[p1.b].get_all_pos(method="u", num=v, diff=[(p1.x, p1.y)]):
                if m.lineX[p2.x].allow(v):
                    return False
                else:
                    if ACTION_GET_INFO:
                        info = info + repr(p2) + ", lineX(" + repr(m.lineX[p2.x].get_num_pos(v)) + ")\n"
                if m.lineY[p2.y].allow(v):
                    return False
                else:
                    if ACTION_GET_INFO:
                        info = info + repr(p2) + ", lineY(" + repr(m.lineY[p2.y].get_num_pos(v)) + ")\n"
            # after checking every possible poses in a box other than the position, p1,
            # that not allowing for the number, v, so p1 must be v
            m.setit(p1.x, p1.y, v, d="checkObviousNumber", info=info)
            return True

        return False

    def check_obvious_number(m, first=1, only=False):
        """Check every number which has been assigned and its effect's boxes' does not have assigned that number

        :param m: Matrix object
        :param first: the first number to be checked
        :param only: False, check all numbers, True, check the first number only

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        sets = 0
        end = 9 if not only else 1  # if check the first number
        for i in range(end):
            num = first + i
            num = num if num < 10 else num - 9
            checked = set()  # save the checked box
            for p1 in m.n[num].p:
                for b in m.b[p1.b].effects:
                    #print("check number {0} of pos({1},{2})!".format(num, p1.x, p1.y))
                    possible = []
                    info = ""  # record how to descide to set
                    if b in checked:
                        continue
                    else:
                        checked.add(b)
                    if num not in m.b[b].possible:
                        continue
                    for p2 in m.b[b].p:
                        if p2.v != 0 or p2.can_see(p1) > 0:
                            continue;
                        if not m.lineX[p2.x].allow(num):
                            if ACTION_GET_INFO:
                                info = info + repr(p2) + ", lineX(" + repr(m.lineX[p2.x].get_num_pos(num)) + ")\n"
                            continue
                        if not m.lineY[p2.y].allow(num):
                            if ACTION_GET_INFO:
                                info = info + repr(p2) + ", lineY(" + repr(m.lineX[p2.x].get_num_pos(num)) + ")\n"
                            continue
                        #print(num, p2, p2.possible)
                        possible.append(p2)
                    if len(possible) == 1:
                        sets += 1
                        flag_set_more_obvious = False
                        if CHECK_MORE_OBVIOUS:
                            flag_set_more_obvious = set_obvious_method_for_pos(m, METHOD_CHECK_OBVIOUS, possible[0], num)
                        if not flag_set_more_obvious:
                            m.setit(possible[0].x, possible[0].y, num, d="checkObviousNumber", info=info)
                        # call self to solve the same number completely
                        r = check_obvious_number(m, first=num, only=SCAN_ALL_NUMBER)
                        sets += r[0]
                        return sets, r[1], r[2], r[3], r[4]
        return sets, 0, METHOD_CHECK_OBVIOUS, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

    def update_group_number(m, num):
        """Update the group number, num, in a box, and store those group number in m.n.group list

        :param m: Matrix object
        :param num: the number to be updated

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        sets = 0
        actions = 0
        info = ""
        #m.n[num].group.clear() # empty first
        for i in range(9):  # check every box
            if num not in m.b[i].possible or num in m.b[i].groupnumber:
                continue
            pos = m.b[i].get_all_pos(num=num, method='u')
            # if the possible position, just set it and return
            if len(pos) == 1:
                #print(m.b[i], pos, num)
                if ACTION_GET_INFO:
                    pass

                SetInMoreObvious = False
                if CHECK_MORE_OBVIOUS:
                    SetInMoreObvious = set_obvious_method_for_pos(m, 3, pos[0], num)
                if not SetInMoreObvious:
                    m.setit(pos[0].x, pos[0].y, num, d="UpdateGroupNumber", info=info)
                return 1, 0, METHOD_CHECK_OBVIOUS, num, SCAN_ONE_NUMBER

            gn = m.b[i].get_group_number(num, pos=pos)
            if gn is not None:
                m.n[num].group.append(gn)
                actions += 1
        if actions > 0:
            sets, k, start, first, only = update_indirect_group_number(m, num)
            actions = actions + k
        else:
            start = METHOD_DEF_BEGIN
            first = SCAN_DEF_BEGIN
            only = SCAN_ALL_NUMBER

        return sets, actions, start, first, only

    def update_indirect_group_number(m, num, amt=0, start=METHOD_DEF_BEGIN, first=SCAN_DEF_BEGIN, only=SCAN_ALL_NUMBER):
        """Update in-direct Group Number, formed by the assigned number and Group Number already known,
        a recursive function

        :param m: Matrix object
        :param num: int, the number to be checked
        :param amt: int, the amount of Group Number found
        :param start: int, the method idx which will be called when it return back to another method
        :param first: int, the pointed number to be checked firstly when it return back to another method
        :param only: bool, just check the first number or not when it return back to another method

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        info = ""
        for gn in m.n[num].group:
            effects = m.b[gn.b].effectsX if gn.direction == "x" else m.b[gn.b].effectsY
            #print(amt, effectBoxes, gn)
            for idx in effects:  # check every effect box, does the possible position for the num can form a group
                # number or not
                # check if the num is existed in the box, or already as a groupnumber
                if num not in m.b[idx].possible or num in m.b[idx].groupnumber:
                    continue
                if gn.direction == "x":
                    pos = m.b[idx].get_all_pos(num=num, method='u', notInLineX=gn.idx)
                else:
                    pos = m.b[idx].get_all_pos(num=num, method='u', notInLineY=gn.idx)
                if len(pos) == 1:
                    if ACTION_GET_INFO:
                        pass

                    flag = False
                    if CHECK_MORE_OBVIOUS:
                        flag = set_obvious_method_for_pos(m, 4, pos[0], num)
                    if not flag:
                        m.setit(pos[0].x, pos[0].y, num, d="UpdateInDirectGroupNumber", info=info)

                    return 1, amt, METHOD_CHECK_OBVIOUS, num, SCAN_ONE_NUMBER

                gn0 = m.b[idx].get_group_number(num, pos=pos)
                if gn0 is not None:
                    m.n[num].group.append(gn0)
                    amt += 1
                    # call self again to get all possible InDirect GroupNumber
                    return update_indirect_group_number(m, num, amt=amt)
        return 0, amt, start, first, only

    def check_inobvious_number(m, first=1, only=False):
        """Check every number which has been assigned and known as group-number and its effect's boxes' does not have assigned that number"

        :param m: Matrix object
        :param first: the first number to be checked
        :param only: bool, False -- check all numbers, True -- check the first number only

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        sets = 0
        actions = 0
        end = 9 if not only else 1  # if check the first number
        for i in range(end):
            num = first + i
            num = num if num < 10 else num - 9
            checked = set()  # save the checked box
            sets, actions, start, first, only = update_group_number(m, num)
            if sets > 0:
                return sets, actions, start, first, only
            # check every box
            for bi in range(9):
                if num not in m.b[bi].possible:
                    continue
                pos = []
                info = ""
                for p1 in m.b[bi].get_all_pos(num=num, method="u"):
                    gn = m.n[num].can_see_by_group_number(p1)
                    if gn is not None:
                        if ACTION_GET_INFO:
                            info = info + repr(gn) + "\n"
                        continue
                    else:
                        pos.append(p1)
                if len(pos) == 1:

                    flag = False
                    if CHECK_MORE_OBVIOUS:
                        flag = set_obvious_method_for_pos(m, 5, pos[0], num)
                    if not flag:
                        m.setit(pos[0].x, pos[0].y, num, d="checkInObviousNumber", info=info)

                    return 1, actions, METHOD_CHECK_OBVIOUS, num, SCAN_ALL_NUMBER

        return sets, actions, METHOD_DEF_BEGIN, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

    def check_line_last_possible_for_number(m, **kw):
        """Check every line that only have one position for un-assigned number

        :param m: Matrix object

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        sets = 0

        for groupType in (m.lineX, m.lineY):
            for line in groupType:
                if line.filled >= 8:
                    continue
                for c in line.count_num_possible(count=1):
                    p1 = c[1][0]
                    info = ""
                    if ACTION_GET_INFO:
                        pass
                    m.setit(p1.x, p1.y, c[0], d="checkLineLastPossibleForNumber", info=info)
                    sets += 1
                    # if get one, just return, let other methods to process others
                    return sets, 0, METHOD_DEF_BEGIN, c[0], SCAN_ONE_NUMBER

        return sets, 0, METHOD_DEF_BEGIN, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

    def write_down_possible(m, **kw):
        """Write down the possible numbers in every un-assigned position
        if WRITEN_POSSIBLE_LIMITS has set to 1..9, it will only write down the
        possibles which <= that limits

        :param m: Matrix object

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        Status.name["writeDownAlready"] = True
        for line in m.p:
            for p1 in line:
                if p1.v != 0 or p1.writen:
                    continue
                # if set writen limits and the possible numbers great it, just pretend it can not be seen for the user
                if 0 < WRITEN_POSSIBLE_LIMITS < len(p1.possible):
                    continue
                p1.writen = True
                if len(p1.possible) == 1:
                    v = p1.possible[0]
                    m.setit(p1.x, p1.y, v, d="writeDownPossible")
                    return 1, 0, METHOD_CHECK_OBVIOUS, v, SCAN_ALL_NUMBER

        return 0, 0, METHOD_DEF_BEGIN, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

    def reduce_by_group_number(m, first=1, only=False):
        """Reduce the possible number in a posiition by GroupNumber

        :param m: Matrix object

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """
        sets = 0
        actions = 0
        end = 9 if not only else 1  # if check the first number
        for i in range(9):
            num = first + i
            num = num if num < 10 else num - 9
            for gn in m.n[num].group:
                for bi in m.b[gn.b].effectsX if gn.direction == "x" else m.b[gn.b].effectsY:
                    for p1 in m.b[bi].get_all_pos(method="u", num=num):
                        if p1.x == gn.idx if gn.direction == "x" else p1.y == gn.idx:
                            rtn = m.reduce(p1.x, p1.y, num, d="reduceByGroupNumber")
                            actions += 1
        return sets, actions, METHOD_DEF_BEGIN, num, SCAN_ONE_NUMBER

    def get_chains(m, group, pos, numbers):
        """ get the possible positions(pos) numbers chain

        :param m: Matrix object
        :param group: lineX or lineY or Box object
        :param pos: Point list of a group
        :param numbers: int, the amount of the numbers to form a chain

        :return: Chain list
        """
        amt = 0
        q = []
        for p1 in pos:
            if len(p1.possible) <= numbers:
                q.append(p1)
        # if qualified positions is less than numbers, just return
        if len(q) < numbers:
            return []

        rtn = []
        for c in itertools.combinations(q, numbers):
            s = set()
            for p1 in c:
                s = s | set(p1.possible)
            if len(s) == numbers:
                chain = Chain(list(s), c)
                rtn.append(chain)
                m.chain.append(chain)
                for p1 in c:
                    group.chain.append(p1)
                amt += 1

        return rtn

    def update_chain(m, **kw):
        """Update the chain of line
        return: >=0 means the chain number's amount in the matrix, m

        :param m: Matrix object

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        sets = 0
        reduces = 0
        info = ""

        for groupType in (m.lineX, m.lineY, m.b):
            for g in groupType:
                pos = g.get_all_pos(method="u", chain=False)
                k = len(pos)
                if k == 0:
                    continue
                elif k == 1:
                    #print(g, g.idx, pos, k, pos[0].possible)
                    m.setit(pos[0].x, pos[0].y, pos[0].possible[0], d="updateChain")
                    return 1, 0, METHOD_CHECK_OBVIOUS, pos[0].possible[0], SCAN_ALL_NUMBER
                else:
                    maxChainNumbers = min(k, WRITEN_POSSIBLE_LIMITS) if WRITEN_POSSIBLE_LIMITS != 0 else k
                    for i in range(1, maxChainNumbers):
                        chains = get_chains(m, g, pos, i + 1)
                        if len(chains) == 0:
                            continue
                        # reduce by chain and return
                        for chain in chains:
                            for p1 in g.get_all_pos(method="u", diff=chain.posList):
                                for v in chain.numList:
                                    if v in p1.possible:
                                        m.reduce(p1.x, p1.y, v, d="updateChain", info=repr(chain))
                                        reduces += 1
                        if reduces > 0:
                            return 0, reduces, METHOD_CHECK_OBVIOUS, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

        return sets, reduces, METHOD_DEF_BEGIN, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

    def reduce_by_two_possible_in_one_position(m, **kw):
        """when a position(p1) has two possible numbers only, we can assume if the position is one number(first)
        then try to emulate to set the position with the other number(second),
        then see the first number will be filled in a position(p2) which the position can see it
        if so, we can reduce all these positions which can see p1 and p2 at the same time from the first number

        :param m: Matrix object

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        reduces = 0
        sets = 0
        for p1 in m.get_all_pos(method="u", possibles=2):
            for i in range(2):
                if i == 0:
                    first, second = p1.possible
                else:
                    second, first = p1.possible
                pos = m.can_see(p1, method="u", num=first)
                if len(pos) <= 1:
                    continue
                else:
                    targets = [(p.x, p.y) for p in pos]
                rtn, m1, idx = emulator(m, p1.x, p1.y, second, targets=targets, checkval=first)
                if rtn == 2:
                    m.setit(p1.x, p1.y, second, d="Emulate it and solve the sudoku!")
                    return 1, 0, METHOD_CHECK_OBVIOUS, second, SCAN_ALL_NUMBER
                elif rtn == 1:
                    p0 = m.p[targets[idx][0]][targets[idx][1]]
                    for x, y in p0.can_see_those(targets):
                        if first in m.p[x][y].possible:
                            #print("{4} and {5} reduce ({0},{1})'s possilbe={2} from {3}".format(x+1, y+1, m.p[x][y].possible, first, p1, p0))
                            r = m.reduce(x, y, first,
                                         d="reduceByTwoPossibleInOnePostion{0}, first={1}, second={2} with postion:{3}".format(
                                             (p1.x, p1.y), first, second, p0))
                            if r == 1:
                                reduces += 1
                            elif r == 2:
                                sets += 1
                    if sets > 0 or reduces > 0:
                        return sets, reduces, METHOD_CHECK_OBVIOUS, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER
                elif rtn == -1:
                    m.setit(p1.x, p1.y, first, d="Emulate it and it causes error, so the number must be another!")
                    return 1, 0, METHOD_CHECK_OBVIOUS, first, SCAN_ALL_NUMBER
                else:
                    continue

        return sets, reduces, METHOD_DEF_BEGIN, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

    def reduce_by_emulate_possible_in_one_position(m, **kw):
        """when a position(p1) has 2 or more possible numbers, we can emulate every possible number and get its result:

        - if it causes an error, we can reduce that number,
        - if it can solve the sudoku, we can set this number,
        - if all possible number can's get condition 1 or 2, we can compare their rec, if they have the same records, we can do it.

        :param m: Matrix object

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        emus = Status.name["emulatePossibles"]

        if Status.name["printStep"]:
            print("reduceByEmulatePossibleInOnePositions: {0}".format(emus))
        reduces = 0
        sets = 0
        emu = []  # record the emulate method, [(p1,v),....]
        result = []  # save the emulate result of matrix for every possible number
        for p1 in m.get_all_pos(method="u", possibles=emus):
            for num in p1.possible:
                emu.append((p1, num))
                rtn, m1, idx = emulator(m, p1.x, p1.y, num)
                if rtn == 2:
                    m.setit(p1.x, p1.y, num, d="Emulate it and solve the sudoku!")
                    return 1, 0, METHOD_CHECK_OBVIOUS, num, SCAN_ALL_NUMBER
                elif rtn == -1:
                    m.reduce(p1.x, p1.y, num, d="Emulate it and it causes error, so the number can be reduce!")
                    return 0, 1, METHOD_CHECK_OBVIOUS, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER
                else:
                    result.append(m1)
                    continue

        if len(result) == emus:
            sets, reduces = compare_result(m, emu, result)

        return sets, reduces, METHOD_DEF_BEGIN, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

    def reduce_by_emulate_possible_number_in_group(m, **kw):
        """when a group(lineX, lineY, Box) has 2 or more position have the same possible number,
        we can emulate every position to set the number and get its result:

        - if it causes an error, we can reduce the position's possible number from that number,
        - if it can solve the sudoku, we can set this number in the position,
        - if all possible position can's get condition 1 or 2, we can compare their rec, if they have the same records, we can do it.

        :param m: Matrix object

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        emus = Status.name["emulatePossibles"]

        if Status.name["printStep"]:
            print("reduceByEmulatePossibleNumberInGroup: {0}".format(emus))
        reduces = 0
        sets = 0
        emu = []  # record the emulate method, [(p1,v),....]
        result = []  # save the emulate result of matrix for every possible number
        for groupType in (m.lineX, m.lineY, m.b):
            for idx in range(9):
                for num, pos in groupType[idx].count_num_possible(count=emus):
                    for p1 in pos:
                        emu.append((p1, num))
                        rtn, m1, idx = emulator(m, p1.x, p1.y, num)
                        if rtn == 2:
                            m.setit(p1.x, p1.y, num, d="Emulate it and solve the sudoku!")
                            return 1, 0, METHOD_CHECK_OBVIOUS, num, SCAN_ALL_NUMBER
                        elif rtn == -1:
                            m.reduce(p1.x, p1.y, num, d="Emulate it and it causes error, so the number can be reduce!")
                            return 0, 1, METHOD_CHECK_OBVIOUS, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER
                        else:
                            result.append(m1)
                            continue
                if len(result) == emus:
                    s, r = compare_result(m, emu, result)
                    sets += s
                    reduces += r

        return sets, reduces, METHOD_DEF_BEGIN, SCAN_DEF_BEGIN, SCAN_ALL_NUMBER

    def compare_result(m, emu, result):
        """compare the result list, to check if there are same result in every step after the last record of original m.rec
        if same for all emulate result, it means that it must be true, so can do by it

        :param m: Matrix object
        :param emu: a two dimension list, [[Point, Assigned Number],...]
        :param result: Matrix list, the list of Matrix object of emulating results

        :return: tuple, (sets, reduces), sets: the amount of setting, reduces: the amount of reducing
        """

        emus = Status.name["emulatePossibles"]

        sets = 0
        reduces = 0
        recIdx = len(m.rec)
        results = len(result)
        m1 = result[0]  # use the first result to compare with others
        i = 0
        for r1 in m1.rec[recIdx:]:
            i += 1  # step idx of m1
            info = "The #{0} step of the {1} emulate as {2} is same with follows:".format(i, emu[0][0], emu[0][1])
            same = 0
            resultIdx = 0
            for m2 in result[1:]:
                resultIdx += 1
                idx = 0  # step idx of others
                for r2 in m2.rec[recIdx:]:
                    idx += 1
                    if (r1[0], r1[1], r1[2], r1[3]) == (r2[0], r2[1], r2[2], r2[3]):
                        if ACTION_GET_INFO:
                            info = info + "\nThe #{0} step of the {1} emulate as {2}".format(idx, emu[resultIdx][0],
                                                                                             emu[resultIdx][1])
                        same += 1
                        break
            if same == results - 1:
                if r1.t == "s":
                    sets += 1
                    m.setit(r1[0], r1[1], r1[2], d="compareResult for {0} emulate!".format(results), info=info)
                else:
                    reduces += 1
                    m.reduce(r1[0], r1[1], r1[2], d="compareResult for {0} emulate!".format(results), info=info)
        return sets, reduces

    def emulator(m, x, y, v, targets=[], checkval=0):
        """emulate the x, y to be set v, then start to use some basic methods to try to solve
        it will stop when and return:

        - 1: one of the targets have been set the checkval
        - 2: isDone
        - -1: error is True
        - 0: all basic methods have been tested, and can't solve

        and the result matrix

        :param m: Matrix object
        :param x: int, the start x position
        :param y: int, the start y position
        :param v: int, the number to be emulated be in the (x, y) position
        :param targets: Point list, tho target list to be checked
        :param checkval: int, when the targets be set, it will check whether the checkval has been assigned in those

        :return: tuple, (rtn, matrix, idx)

        - rtn:
            * 1: one of the targets have been set the checkval
            * 2: isDone
            * -1: error is True
            * 0: all basic methods have been tested, and can't solve
        - matrix: Matrix, the reulst of emulating
        - idx: int, if the rtn == 1, this will indicate the index of the target that has been assigned the number, checkval
        """

        check_pos_save = Status.name["checkPos"]
        m1 = copy.deepcopy(m)

        if len(targets) > 0:
            check_target = True
            Status.name["checkPos"] = targets
        else:
            check_target = False

        method_loop_idx = 0
        allmethods = reg_method()
        start = METHOD_CHECK_OBVIOUS  # start from for the first time
        num = 1
        only = False
        rtn = 0
        idx = 0  # the index of the targets, which = checkval
        emulate_first = True

        while True:
            actions = 0
            method_loop_idx += 1
            try:

                if emulate_first:
                    #print(m1.p[2][2].possible)
                    #print("Emulator Start in P({0},{1})={2}!".format(x, y, v))
                    m1.setit(x, y, v, d="Emulator Start!")
                    emulate_first = False

                for method in allmethods[start:METHOD_BASIC_LEVEL]:
                    # every method have 5 return values:
                    # sets: how many positions have been set
                    # reduces: how many numbers have been reduced
                    # start: which method will start to be used, default is 1
                    # num: which number will be the first number to be procossed, for methods that look over all numbers
                    # only: for methods which look over all numbers to process one only, which is the num
                    sets, reduces, start, num, only = method.run(m1, first=num, only=only)
                    #print("Emulate#{0}-{2}: {1}, sets={3}, reduces={4}".format(methodLoopIdx, method.name, methodIdx, sets, reduces))
                    if sets > 0:
                        rtn = fill_last_position_by_setting(m1, sets)
                        if rtn[0] > 0:
                            start = rtn[2]
                            first = rtn[3]
                            only = rtn[4]
                            #print("Emulate#{0}-last: {1}, sets={3}, reduces={4}".format(methodLoopIdx, "LastPosition", methodIdx, rtn, reduces))
                            sets = sets + rtn[0]
                    if (sets > 0 or reduces > 0) and Status.name["writeDownAlready"]:
                        rtn = fill_only_one_possible(m1)
                        if rtn[0] > 0:
                            sets = rtn[0]
                            start = rtn[2]
                            first = rtn[3]
                            only = rtn[4]
                            #print("Emulate#{0}-only: {1}, sets={3}, reduces={4}".format(methodLoopIdx, "LastPossible", methodIdx, rtn, reduces))
                    if sets > 0 or reduces > 0:
                        actions = actions + sets + reduces
                        break
            except SudokuDone as err:
                if Status.name["printStep"]:
                    print("It is done by the last position({0},{1}) to set to be {2}!".format(err.x, err.y, err.v))
                rtn = 2
                break
            except SudokuWhenPosSet as err:
                #print("It is stopped by the position({0}) be set! method={1}".format(checkPos, methodIdx))
                if err.v == checkval:
                    idx = targets.index((err.x, err.y))
                    rtn = 1
                    break
                else:
                    continue
            except SudokuError as err:
                rtn = -1
                if Status.name["printStep"]:
                    print("It is impossible for {0}, {1} to set/reduce {2}! ({3})".format(err.x, err.y, err.v, err.t))
                #traceback.print_exc()
                break
            except:  # unexpected error
                if Status.name["printStep"]:
                    print("Unexpected error:", sys.exc_info()[0])
                traceback.print_exc()
                break

            if actions <= 0:
                break

        #restore
        Status.name["checkPos"] = check_pos_save
        #print(checkPos)
        return rtn, m1, idx

    def try_error(m=None, file="", depth=0):
        """Try Error Method, only fill the first possible position

        .. note: This is an recursive function

        :param m: Matrix object, if it is None, you should give it the sudoku define file
        :param file: file, the sudoku define file
        :param depth: int, count the call depth of this function

        :return: bool, True if the sudoku has been solved
        """

        if file != "":
            m = Matrix(file=file)

        possibles = m.sort_unassigned_pos_by_possibles()
        done = False
        depth += 1

        m1 = copy.deepcopy(m)

        p1 = possibles[0]

        k = len(p1.possible)
        if k <= 0:
            #print("try#{0}: {1} has empty possible!".format(depth, p1))
            return False
        elif k == 1:
            #print("try#{0}: {1} has only one possible!, set it to {2}".format(depth, p1, p1.possible[0]))
            try:
                m1.setit(p1.x, p1.y, p1.possible[0], d="try")
                flag = try_error(m1, depth=depth)
                if flag:
                    return True
                else:
                    return False
            except SudokuDone:
                print(m1)
                return True
            except SudokuError:
                return False
        else:
            flag = False
            m2 = copy.deepcopy(m1)
            for v in p1.possible:
                try:
                    if m1.allow(p1.x, p1.y, v):
                        #print("try#{0}: {1} try set it to be {2} of {3}".format(depth, p1, v, p1.possible))
                        m1.setit(p1.x, p1.y, v, d="try")
                        flag = try_error(m1, depth=depth)
                        if flag:
                            return True
                        else:
                            m1 = copy.deepcopy(m2)
                            continue
                    else:
                        #print("try#{0}: {1} is impossible to be set to be {2}".format(depth, p1, v))
                        continue
                except SudokuDone as err:
                    print(m1)
                    done = True
                    return True
                except SudokuError as err:
                    m1 = copy.deepcopy(m2)
                    continue
            if not flag:
                #print("try#{2}: {0} is not impossible to set any for {1}".format(p1, p1.possible, depth))
                # restore it and continue
                # m1 = copy.deepcopy(m)
                return False
            else:
                #print(p1, p1.v, p1.possible)
                return True

    def guess(m, idx=0, **kw):
        """Guess every possible number in a position by from the min possibles of positions

        :param m: Matrix object
        :param idx: int, 0 means the new guess, others mean the idx of the possible number of a position

        :return: tuple, (sets, reduces, method index, first, only), as following

        - sets: int, the amount of set a number
        - reduces: int, the amount of reduce a number
        - mothod index: int, method Index to restart using
        - first: int, the first number to scan for the methods need this information
        - only: bool, if only check the first number or not
        """

        # if start using tryMethod, set the level to the METHOD_LEVEL_LIMIT_WHENTRY
        Status.name["Level"] = METHOD_LEVEL_LIMIT_WHENTRY

        Status.name["Scope"] += 5  # it is easy as the method of write down possible
        if idx == 0:  # Add New Try
            Status.name["tryIdx"] += 1
            possibles = m.sort_unassigned_pos_by_possibles()  # get all unassigned position and sorted by the possibles number
            m1 = copy.deepcopy(m)
            p1 = possibles[0]  # the first un-assigned postion
            x = p1.x
            y = p1.y
            Status.name["tryStack"].append([m1, x, y, 0])
            if Status.name["printStep"]:
                print("Try Add: {0},{1} to set {2} of {3}".format(x, y, p1.possible[0], p1.possible))
        else:
            i = Status.name["tryIdx"] - 1
            Status.name["tryStack"][i][3] = idx
            x = Status.name["tryStack"][i][1]
            y = Status.name["tryStack"][i][2]
            if Status.name["printStep"]:
                print(
                    "Try Idx={3}: {0},{1} to set {2} of {4}".format(x, y, m.p[x][y].possible[idx], idx, m.p[x][y].possible))

        v = m.p[x][y].possible[idx]
        m.setit(x, y, v, d="try")
        return 1, 0, METHOD_CHECK_OBVIOUS, v, SCAN_ALL_NUMBER

    class SolveMethod():
        """Method Object"""
        lastNumber = 1

        def __init__(self, fun, idx, name="", level=0, obvious=True):
            """
            :param fun: function, the function name defined in Python
            :param idx: int, the sequence of executing solving
            :param name: str, the description of this function
            :param level: int, the difficult level
            :param obvious: bool, is it a obvious method for a human
            """
            self.fun = fun
            self.idx = idx
            self.name = name if name != "" else fun.__name__
            self.des = fun.__doc__
            self.level = level  # the difficult level for human, can be set 0-9
            self.obvious = obvious

        def run(self, m, *args, **ks):
            """ To execute a method to solve a sudoku

            :param m: Matrix object
            :param ks: first(int), only(bool)

            :return: tuple, (sets, reduces, method index, first, only), as following

            - sets: int, the amount of set a number
            - reduces: int, the amount of reduce a number
            - mothod index: int, method Index to restart using
            - first: int, the first number to scan for the methods need this information
            - only: bool, if only check the first number or not
            """

            return self.fun(m, *args, **ks)

    def reg_method():
        """register all method as an object and save them into a list to return

        :return: SolveMethod list
        """

        methods = list()
        #methods.append(SolveMethod(fillOnlyOnePossible, 0, level=0))
        methods.append(SolveMethod(fill_last_position_of_group, 1, level=1))
        methods.append(SolveMethod(check_obvious_number, 2, level=1))
        methods.append(SolveMethod(check_line_last_possible_for_number, 3, level=2))
        methods.append(SolveMethod(check_inobvious_number, 4, level=3))
        methods.append(SolveMethod(reduce_by_group_number, 5, level=5))
        methods.append(SolveMethod(write_down_possible, 6, level=5))
        methods.append(SolveMethod(update_chain, 7, level=10))
        methods.append(SolveMethod(reduce_by_two_possible_in_one_position, 8, level=15))
        if Status.name["emuUse"]:
            methods.append(SolveMethod(reduce_by_emulate_possible_in_one_position, 9, level=20))
            methods.append(SolveMethod(reduce_by_emulate_possible_number_in_group, 10, level=20))
        if Status.name["tryUse"]:
            methods.append(SolveMethod(guess, 11, level=0))
        return methods

    def solve(file, loop_limit=0, rec_limit=0, check=None, level_limit=0, emu_limits=2, use_try=METHOD_USE_TRY,
              use_emu=METHOD_USE_EMU, print_step=False):
        """Solve a sudoku which define in a file!

        :param loop_limit: int, the limit for the method loops, 0: no limits
        :param rec_limit: int, for debug, when the records >= recLimit, it will stop, 0: no limits
        :param check: int, for debug, to set the a (x,y) list to check, it will stop when these positions have been set
        :param level_limit: int, limit the methods using, 0: no limit, >0: just using the methods which lever < level_limit
        :param emu_limits: imt, if using emulator method, this tells the emulator just emulate in emu_limits possible numbers or positions
        :param use_try: bool, using guess method or not
        :param use_emu: bool, using emulator methods or not
        :param print_step: bool, printing the solving steps of not

        :except SudokuDone: when a method can solve the sudoku
        :except SudokuError: when a step will break the rules of sudoku game

        :return: Matrix object

        """

        Status.name["checkPos"] = check
        begin = time.time()
        m = Matrix(file=file)
        Status.name["Original"] = copy.deepcopy(m)
        Status.name["Result"] = m
        start = METHOD_CHECK_OBVIOUS  # start from for the first time
        num = 1
        only = False
        max_method = 0
        Status.name["tryUse"] = use_try
        Status.name["emuUse"] = use_emu
        allmethods = reg_method()
        Status.name["Level"] = level_limit
        Status.name["printStep"] = print_step
        Status.name["Level"] = 0

        while True:
            actions = 0
            Status.name["methodLoopIdx"] += 1
            try:
                for method in allmethods[start:]:
                    if 0 < Status.name["Level"] < method.level:
                        continue
                    Status.name["methodIdx"] = method.idx
                    # every method have 5 return values:
                    # sets: how many positions have been set
                    # reduces: how many numbers have been reduced
                    # start: which method will start to be used, default is 1
                    # num: which number will be the first number to be processed, for methods that look over all numbers
                    # only: for methods which look over all numbers to process one only, which is the num
                    sets, reduces, start, num, only = method.run(m, first=num, only=only)
                    Status.name["Scope"] += method.level
                    max_method = max(max_method, method.idx)
                    if Status.name["printStep"]:
                        print("Try#{0}-{2}: {1}, sets={3}, reduces={4}".format(Status.name["methodLoopIdx"], method.name,
                                                                               Status.name["methodIdx"], sets, reduces))
                    if sets > 0:
                        rtn = fill_last_position_by_setting(m, sets)
                        if rtn[0] > 0:
                            start, first, only = rtn[2:]
                            if Status.name["printStep"]:
                                print(
                                    "Try#{0}-last: {1}, sets={3}, reduces={4}".format(Status.name["methodLoopIdx"],
                                                                                      "LastPosition",
                                                                                      Status.name["methodIdx"],
                                                                                      rtn, reduces))
                            sets = sets + rtn[0]
                    if (sets > 0 or reduces > 0) and Status.name["writeDownAlready"]:
                        rtn = fill_only_one_possible(m)
                        if rtn[0] > 0:
                            sets = rtn[0]
                            start, first, only = rtn[2:]
                            if Status.name["printStep"]:
                                print(
                                    "Try#{0}-only: {1}, sets={3}, reduces={4}".format(Status.name["methodLoopIdx"],
                                                                                      "LastPossible",
                                                                                      Status.name["methodIdx"],
                                                                                      rtn, reduces))
                    if DEBUG_MODE:
                        if 0 < rec_limit <= len(m.rec):
                            raise SudokuStop()
                    if sets > 0 or reduces > 0:
                        Status.name[
                            "emulatePossibles"] = 2  # if any thing work, the emulatePossible set to the begin number
                        actions = actions + sets + reduces
                        break
            except SudokuDone as err:
                if Status.name["printStep"]:
                    print("It is done by the last position({0},{1}) to set to be {2}!".format(err.x, err.y, err.v))
                break
            except SudokuStop:
                print("It is stop by the limit of recLimit set to {0}:".format(rec_limit))
                m.print_rec()
                break
            except SudokuWhenPosSet:
                print("It is stopped by the position({0}) be set! method={1}".format(Status.name["checkPos"],
                                                                                     Status.name["methodIdx"]))
                traceback.print_exc()
                break
            except SudokuError as err:
                if Status.name["tryUse"] and Status.name["tryIdx"] > 0:
                    flag = False
                    while Status.name["tryIdx"] > 0:
                        m1, x, y, idx = Status.name["tryStack"][Status.name["tryIdx"] - 1]
                        idx += 1
                        if len(m1.p[x][y].possible) > idx:
                            m = copy.deepcopy(m1)
                            sets, reduces, start, num, only = guess(m, idx=idx)
                            flag = True
                            break
                        else:
                            Status.name["tryIdx"] -= 1
                            Status.name["tryStack"].pop(-1)
                    if flag:
                        continue
                if Status.name["printStep"]:
                    print("It is impossible for {0}, {1} to set/reduce {2}! ({3})".format(err.x, err.y, err.v, err.t))
                    traceback.print_exc()
                break
            except KeyboardInterrupt:
                traceback.print_exc()
                break

            if DEBUG_MODE:
                # for testing
                if Status.name["methodLoopIdx"] == loop_limit:
                    break

            if actions <= 0:
                if Status.name["emulatePossibles"] < emu_limits:
                    Status.name["Scope"] += 1000
                    Status.name["emulatePossibles"] += 1
                    if Status.name["printStep"]:
                        print("Try emulate numbers = {0}".format(Status.name["emulatePossibles"]))
                    start = METHOD_EMULATE_START
                    continue
                else:
                    break

        print("The Original: ")
        print(Status.name["Original"])
        print("The Result:")
        print(Status.name["Result"])
        if m.filled < 81:
            print("Can't solve it, still need {0} more effort, it takes {1}!".format(81 - m.filled, time.time() - begin))
        else:
            print(
                "Done! good job, it takes {0}! Level={1}, Methods Used={2}".format(time.time() - begin,
                                                                                   Status.name["Scope"], max_method))
        return m

### 瀏覽

- 索引
- 模組 |
- SudokuStudyLib 1.0 documentation »
- Module code »