# -*- coding: UTF-8 -*- ‘‘‘Created on 2017年6月9日@author: LXu4‘‘‘import copyimport timeclass Soduku(object):    def __init__(self, problem):        self.problem = problem    def resolve(self):        solutionStack = [self.problem]        tmp = self.get_solution_array(self.problem)        solutionArrayStack = [tmp]        time_t = 0        prev_x = -1        prev_y = -1        while 1:            # time_t += 1            # fetch the last solution in solution stack            next_item_cord = {}            solutionArray = []            # print ‘still ‘,len(solutionStack),‘in stack‘            solutionNow = copy.deepcopy(solutionStack[len(solutionStack) - 1])            solutionArray = solutionArrayStack[len(solutionArrayStack) - 1]            flag = self.check_if_need_to_back(solutionNow, solutionArray)            if flag is True:                # print ‘pop!‘                solutionArrayStack.pop()                solutionStack.pop()            else:                time_t += 1                # next_item_cord = self.get_first_possible_item(solutionArray,solutionNow=solutionNow)                next_item_cord = self.get_first_possible_item(solutionArray,solutionNow=solutionNow)                if next_item_cord == False:                    break                # print ‘next_item_cord:‘,next_item_cord                prev_x = next_item_cord[‘x‘]                prev_y = next_item_cord[‘y‘]                next_item_array = solutionArray[prev_x][prev_y]                next_item = next_item_array[len(next_item_array)-1]                # randint(0,len(next_item_array)-1)                solutionNow[prev_x][prev_y] = next_item                # solutionArray_tmp = get_solution_array(solutionNow)                solutionArray_tmp = copy.deepcopy(solutionArray)                solutionArray_tmp = self.get_resolution_array_new(solutionArray_tmp, prev_x, prev_y,                                                             next_item)                if next_item in solutionArray[prev_x][prev_y]:                    solutionArray[prev_x][prev_y].remove(                        next_item)                # print ‘next point is ‘,prev_x,‘,‘,prev_y                solutionStack.append(solutionNow)                solutionArrayStack.append(solutionArray_tmp)                # print solutionArrayStack                # print solutionStack        for i in range(0, 9, 1):            print solutionStack[len(solutionStack) - 1][i]        print ‘total forward:‘,time_t    def check_if_need_to_back(self,solutionNow, solutionArray):        for i in range(0, 9, 1):            for j in range(0, 9, 1):                if len(solutionArray[i][j]) == 0 and solutionNow[i][j] == 0:                    return True        return False    def get_resolution_array_new(self,solutionArray, x, y, value):        for tmp_j in range(0, 9, 1):            if value in solutionArray[x][tmp_j]:                solutionArray[x][tmp_j].remove(value)        for tmp_i in range(0, 9, 1):            if value in solutionArray[tmp_i][y]:                solutionArray[tmp_i][y].remove(value)        for tmp_i in range(x / 3 * 3, x / 3 * 3 + 3):            for tmp_j in range(y / 3 * 3, y / 3 * 3 + 3):                if value in solutionArray[tmp_i][tmp_j]:                    solutionArray[tmp_i][tmp_j].remove(value)        return solutionArray    def get_solution_array(self,problem):        tmp = []        for i in range(0, 9, 1):            tmp_line_array = []            for j in range(0, 9, 1):                # print ‘[‘+bytes(i)+‘,‘+bytes(j)+‘]: ‘+ bytes(problem[i][j])                if problem[i][j] == 0:                    # no value, get possible value array                    tmp_value = http://www.mamicode.com/[1, 2, 3, 4, 5, 6, 7, 8, 9]                    # remove the existed value in line                    for tmp_j in range(0, 9, 1):                        if problem[i][tmp_j] != 0:                            if problem[i][tmp_j] in tmp_value:                                tmp_value.remove(problem[i][tmp_j])                    # remove the existed value in column                    for tmp_i in range(0, 9, 1):                        if problem[tmp_i][j] != 0:                            if problem[tmp_i][j] in tmp_value:                                tmp_value.remove(problem[tmp_i][j])                    # remove the existed value in the rectangle                    for x in range(i / 3 * 3, i / 3 * 3 + 3):                        for y in range(j / 3 * 3, j / 3 * 3 + 3):                            if problem[x][y] != 0:                                if problem[x][y] in tmp_value:                                    tmp_value.remove(problem[x][y])                    tmp_line_array.append(tmp_value)                else:                    tmp_line_array.append([])            tmp.append(tmp_line_array)            # print tmp_line_array        # print tmp        return tmp    # get first item to be the point of tree    def get_first_possible_item(self, solution_array, solutionNow = None):        is_finished = True        shortest_item_length = 9        shortest_item_x = 0        shortest_item_y = 0        for i in range(0, 9, 1):            for j in range(0, 9, 1):                tmp_length = len(solution_array[i][j])                if tmp_length != 0:                    is_finished = False                    if solutionNow[i][j] != 0:                        tmp_length += 1                    if tmp_length < shortest_item_length:                        shortest_item_length = tmp_length                        shortest_item_x = i                        shortest_item_y = j        # print ‘shortest item is:‘,shortest_item_length,shortest_item_x,shortest_item_y        if is_finished:            return False        else:            return {‘x‘: shortest_item_x, ‘y‘: shortest_item_y}    def get_next_possible_item(self, solution_array, prev_x, prev_y, solutionNow = None):        if prev_x == -1 and prev_y == -1:            return self.get_first_possible_item(solution_array, solutionNow)        else:            is_finished = True            shortest_item_length = 9            shortest_item_x = 0            shortest_item_y = 0            for tmp_i in range(0, 9, 1):                tmp_length = len(solution_array[tmp_i][prev_y])                if tmp_length != 0:                    is_finished = False                    if solutionNow[tmp_i][prev_y] != 0:                        tmp_length += 1                    if tmp_length < shortest_item_length:                        shortest_item_length = tmp_length                        shortest_item_x = tmp_i                        shortest_item_y = prev_y                        if tmp_length == 1:                                return {‘x‘: shortest_item_x, ‘y‘: shortest_item_y}            for tmp_j in range(0, 9, 1):                tmp_length = len(solution_array[prev_x][tmp_j])                if tmp_length != 0:                    is_finished = False                    if solutionNow[prev_x][tmp_j] != 0:                        tmp_length += 1                    if tmp_length < shortest_item_length:                        shortest_item_length = tmp_length                        shortest_item_x = prev_x                        shortest_item_y = tmp_j                        if tmp_length == 1:                                return {‘x‘: shortest_item_x, ‘y‘: shortest_item_y}            for x in range(prev_x / 3 * 3, prev_x / 3 * 3 + 3):                for y in range(prev_y / 3 * 3, prev_y / 3 * 3 + 3):                    tmp_length = len(solution_array[x][y])                    if tmp_length != 0:                        is_finished = False                        if solutionNow[x][y] != 0:                            tmp_length += 1                        if tmp_length < shortest_item_length:                            shortest_item_length = tmp_length                            shortest_item_x = x                            shortest_item_y = y                            if tmp_length == 1:                                return {‘x‘: shortest_item_x, ‘y‘: shortest_item_y}            # print ‘shortest item is:‘,shortest_item_length,shortest_item_x,shortest_item_y            if is_finished:                return self.get_first_possible_item(solution_array,solutionNow)            else:                return {‘x‘: shortest_item_x, ‘y‘: shortest_item_y}problem =     [        [3,0,8,0,0,0,6,0,0],          [0,4,0,0,6,5,0,0,7],          [7,0,0,4,3,0,0,9,0],          [0,0,7,0,0,1,5,8,0],          [1,0,0,0,2,0,0,0,9],          [0,9,4,7,0,0,2,0,0],          [8,0,0,0,7,4,0,0,0],          [4,0,0,6,5,0,8,1,0],          [0,0,9,0,0,0,7,0,2]          ]f = Soduku(problem)startTime=time.time()f.resolve()endTime=time.time()print "Finished! Time consuming: " + "%.4f" % (endTime-startTime) + " Seconds"