stack test next [0 solution += python2 env
Environment: Python27
- # -*- coding: UTF-8 -*-
- '''
- Created on 2017年6月9日
- @author: LXu4
- '''
- import copy
- import time
- class 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 = -1while1:
- # time_t += 1
- # fetch the last solution in solution stacknext_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)
- ifflagis 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)
- ifnext_item_cord == False:
- break
- # print 'next_item_cord:',next_item_cordprev_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)
- ifnext_itemin 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
- foriinrange(0, 9, 1):
- printsolutionStack[len(solutionStack) - 1][i]
- print 'total forward:',time_t
- def check_if_need_to_back(self,solutionNow, solutionArray):
- foriinrange(0, 9, 1):
- forjinrange(0, 9, 1):
- iflen(solutionArray[i][j]) == 0andsolutionNow[i][j] == 0:
- return True
- return False
- def get_resolution_array_new(self,solutionArray, x, y, value):
- fortmp_jinrange(0, 9, 1):
- ifvaluein solutionArray[x][tmp_j]:
- solutionArray[x][tmp_j].remove(value)
- fortmp_iinrange(0, 9, 1):
- ifvaluein solutionArray[tmp_i][y]:
- solutionArray[tmp_i][y].remove(value)
- fortmp_iinrange(x / 3 * 3, x / 3 * 3 + 3):
- fortmp_jinrange(y / 3 * 3, y / 3 * 3 + 3):
- ifvaluein solutionArray[tmp_i][tmp_j]:
- solutionArray[tmp_i][tmp_j].remove(value)
- return solutionArray
- def get_solution_array(self,problem):
- tmp = []
- foriinrange(0, 9, 1):
- tmp_line_array = []
- forjinrange(0, 9, 1):
- # print '['+bytes(i)+','+bytes(j)+']: '+ bytes(problem[i][j])
- ifproblem[i][j] == 0:
- # no value, get possible value arraytmp_value = [1, 2, 3, 4, 5, 6, 7, 8, 9]
- # remove the existed value in line
- fortmp_jinrange(0, 9, 1):
- ifproblem[i][tmp_j] != 0:
- ifproblem[i][tmp_j]in tmp_value:
- tmp_value.remove(problem[i][tmp_j])
- # remove the existed value in column
- fortmp_iinrange(0, 9, 1):
- ifproblem[tmp_i][j] != 0:
- ifproblem[tmp_i][j]in tmp_value:
- tmp_value.remove(problem[tmp_i][j])
- # remove the existed value in the rectangle
- forxinrange(i / 3 * 3, i / 3 * 3 + 3):
- foryinrange(j / 3 * 3, j / 3 * 3 + 3):
- ifproblem[x][y] != 0:
- ifproblem[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
- defget_first_possible_item(self, solution_array, solutionNow = None):
- is_finished = True
- shortest_item_length = 9
- shortest_item_x = 0
- shortest_item_y = 0
- foriinrange(0, 9, 1):
- forjinrange(0, 9, 1):
- tmp_length = len(solution_array[i][j])
- iftmp_length != 0:
- is_finished = False
- ifsolutionNow[i][j] != 0:
- tmp_length += 1iftmp_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}
- defget_next_possible_item(self, solution_array, prev_x, prev_y, solutionNow = None):
- ifprev_x == -1andprev_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
- fortmp_iinrange(0, 9, 1):
- tmp_length = len(solution_array[tmp_i][prev_y])
- iftmp_length != 0:
- is_finished = False
- ifsolutionNow[tmp_i][prev_y] != 0:
- tmp_length += 1iftmp_length < shortest_item_length:
- shortest_item_length = tmp_length
- shortest_item_x = tmp_i
- shortest_item_y = prev_y
- iftmp_length == 1:
- return{'x': shortest_item_x,'y': shortest_item_y}
- fortmp_jinrange(0, 9, 1):
- tmp_length = len(solution_array[prev_x][tmp_j])
- iftmp_length != 0:
- is_finished = False
- ifsolutionNow[prev_x][tmp_j] != 0:
- tmp_length += 1iftmp_length < shortest_item_length:
- shortest_item_length = tmp_length
- shortest_item_x = prev_x
- shortest_item_y = tmp_j
- iftmp_length == 1:
- return{'x': shortest_item_x,'y': shortest_item_y}
- forxinrange(prev_x / 3 * 3, prev_x / 3 * 3 + 3):
- foryinrange(prev_y / 3 * 3, prev_y / 3 * 3 + 3):
- tmp_length = len(solution_array[x][y])
- iftmp_length != 0:
- is_finished = False
- ifsolutionNow[x][y] != 0:
- tmp_length += 1iftmp_length < shortest_item_length:
- shortest_item_length = tmp_length
- shortest_item_x = x
- shortest_item_y = y
- iftmp_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"
Python 解决数独
来源: http://www.bubuko.com/infodetail-2120946.html