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 = -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 = [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"