下星期二才會正式跑 benchmark ^^
今早寫了一下，加上一些 turning
就看著 code 是如何的一步一步的加速…
從開始到現在，竟然已經加速了 1000 多倍了…
可是 code 也越來越噁心…簡直就是 反refactoring
為了讓比賽更好玩… 先把 code post 出來了 ^_^
反正… just for fun :)
Filename: tick_solver.py
ROWS=9
COLUMNS=9
TOTAL_ELEMENTS=81
class Group:
def __init__(self, value=0x1ff):
self.left = value
def set(self, x):
if self.left & (1 << (x-1)):
self.left &= (~(1<< (x-1)))
return True
return False
def unset(self, x):
if not self.left & (1 << (x-1)):
self.left |= (1 << (x-1))
return True
return False
def contains(self, x):
return not not self.left & (1 << (x-1))
def len(self):
ans = 0
v = self.left;
while v:
v &= v -1
ans += 1
return ans
def len(v):
ans=0
while v:
v &= v - 1
ans += 1
return ans
class Cmd_Node:
def __init__(self, x, y, v, Data):
self.x = x
self.y = y
self.v = v
self.D = Data
self.D &= ~( 1 << (v-1) )
def retry(self):
v=0
while not self.D & (1 << v):
v+=1
self.D &= ~(1 << v);
v+=1
self.v = v;
return v;
def pretty_print(self):
print "x="+str(self.x)+" y="+str(self.y)+" v="+str(self.v)+" D="+str(self.D)
class Board():
def __init__(self):
self.num_rest=TOTAL_ELEMENTS
self.trace = []
self.DATA = []
self.data = []
self.Rows = []
self.Columns = []
self.Groups = []
for i in range(0, ROWS):
self.Rows.append(Group())
self.Columns.append(Group())
self.Groups.append(Group())
self.data.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
self.DATA.append([ 0, 0, 0, 0, 0, 0, 0, 0, 0])
def run(self, array):
self.array_get(array)
self.puzzle_solving()
# index from 0 - 8
def value_set(self, x, y, v):
if (v==0):
return True
if self.Columns[y].contains(v) and \
self.Rows[x].contains(v) and \
self.Groups[(int(x/3)*3 + int(y/3))].contains(v):
self.data[x][y] = v
self.Columns[y].set(v)
self.Rows[x].set(v)
self.Groups[(int(x/3)*3 + int(y/3))].set(v)
self.num_rest = self.num_rest - 1;
return True
return False
def value_unset(self, x, y):
v = self.data[x][y]
self.data[x][y] = 0
self.Columns[y].unset(v)
self.Rows[x].unset(v)
self.Groups[(int(x/3)*3 + int(y/3))].unset(v)
self.num_rest = self.num_rest + 1;
def group_get(self, x, y):
if (x < 0 or x > 8 or y < 0 or y > 8):
return -1
return int(x/3)*3 + int(y/3)
def data_print(self):
print self.data
def pretty_print(self):
for i in range(0,ROWS):
print self.data[i]
def file_read(self, name):
f = open(name, "r")
for x in range(0,9):
for y in range(0,9):
while True:
v = f.read(1)
if v >= '0' and v <= '9':
break;
if not self.value_set(x,y,int(v)):
print "Bad sudoku!!"
return False
return True
def array_get(self, array):
for x in [0, 1, 2, 3, 4, 5, 6, 7, 8]:
for y in [0, 1, 2, 3, 4, 5, 6, 7, 8]:
if not self.value_set(x,y,array[x][y]):
print "Bad sudoku!!"
return False
return True
def possible_value_get(self, x, y):
return self.Groups[(int(x/3)*3 + int(y/3))].left & self.Rows[x].left & self.Columns[y].left
def puzzle_solving_iterate(self):
min_x = 0
min_y = 0
min=10
for x in range(0,9):
for y in range(0,9):
if self.data[x][y]:
continue
pos = self.Groups[(int(x/3)*3 + int(y/3))].left & self.Rows[x].left & self.Columns[y].left
self.DATA[x][y] = pos
if pos == None:
continue
lentmp = len(pos)
if lentmp == 1:
v = 0
while not (pos & 1 << v):
v += 1
v += 1
self.value_set(x,y,v)
self.trace.append(Cmd_Node(x,y,v, pos))
if lentmp < min:
min_x = x
min_y = y
min = lentmp
if min == 1:
return True
#guess has to be made
if min > 0:
guess = 0
while not (self.DATA[min_x][min_y] & 1 << guess):
guess += 1
guess += 1
self.trace.append(Cmd_Node(min_x, min_y, guess, self.DATA[min_x][min_y]))
return self.value_set(min_x, min_y,guess)
return False
def puzzle_solving(self):
while self.num_rest > 0:
if self.puzzle_solving_iterate():
continue
continue_flag=True
while continue_flag:
cmd = self.trace.pop()
lentmp = len(cmd.D)
if lentmp==0:
self.value_unset(cmd.x, cmd.y)
continue
self.value_unset(cmd.x, cmd.y)
for x in range(0,9):
for y in range(0,9):
if self.data[x][y]:
continue
self.DATA[x][y] = self.Groups[(int(x/3)*3 + int(y/3))].left & self.Rows[x].left & self.Columns[y].left
while lentmp > 0:
v = cmd.retry()
if self.DATA[cmd.x][cmd.y] & (1<< (v-1)):
self.value_set(cmd.x, cmd.y, v)
self.trace.append(cmd)
continue_flag = False
break
沒有留言:
張貼留言