和大家分享一下小弟的加速過程…
1. 第一步當然是先寫 Test Framework
Filename: testcase.py
#!/usr/bin/python
import sys
import tick_solver
if sys.argv.__len__() >= 2 and sys.argv[1] :
name = sys.argv[1]
else:
name = "case_01.txt"
bb = tick_solver.Board()
bb.file_read(name)
def TC_Board_group_get(bb):
if bb.group_get(0, 0) == 0 and \
bb.group_get(2, 2) == 0 and \
bb.group_get(2, 3) == 1 and \
bb.group_get(8, 8) == 8 and \
bb.group_get(5, 7) == 5 and \
bb.group_get(6, 7) == 8 and \
bb.group_get(3, 10) == -1 and \
bb.group_get(3, 0) == 3:
print "group_get passed!!"
else:
print "group_get failed!!"
def TC_Board_data_print(bb):
bb.data_print()
bb.pretty_print()
def TC_Board_group_print(bb):
for i in range(0,9):
print "Rows["+str(i)+ "]=" + str(bb.Rows[i].left)
print "Columns["+str(i)+ "]=" + str(bb.Columns[i].left)
print "Groups["+str(i)+ "]=" + str(bb.Groups[i].left)
def TC_Board_possible_value_get(bb):
for x in range(0,9):
for y in range(0,9):
print "("+str(x)+","+str(y)+") = "+str(bb.possible_value_get(x,y))
def TC_Board_puzzle_solving(bb):
bb.puzzle_solving()
bb.pretty_print()
import cProfile
def _TC_Board_profileing():
BB.run(LALA)
def TC_Board_profileing():
cProfile.run('BB.run(LALA)')
LALA = bb.data[:]
TC_Board_group_get(bb)
TC_Board_data_print(bb)
TC_Board_group_print(bb)
TC_Board_possible_value_get(bb)
bb.pretty_print()
BB = tick_solver.Board()
TC_Board_profileing()
BB.pretty_print()
再開始實做… （小弟習慣先寫 test case 再來寫實做，testcase 會和程式一同成長）
2. 決定演算法
從google 上找出sudoku 的rule
a. 每個 raw 的九個數字都不同
b. 每個 column 的九個數字都不同
c. 每個 group 的九個數字都不同
依這三條 rule 找出 candidates , 再從candidate 最少的 cell 猜起。
trace 的路徑是走迷宮的方式。
3. 開出 functions 實作每個 function , 先不管速度，先正確了再說
Filename: tick_solver.py
ROWS=9
COLUMNS=9
TOTAL_ELEMENTS=81
class Group:
def __init__(self):
self.left = range(1, COLUMNS+1)
def set(self, x):
if self.left.__contains__(x):
self.left.remove(x)
return True
return False
def unset(self, x):
if not self.left.__contains__(x):
self.left.append(x)
return True
return False
def candidate(self):
return self.left
class Cmd_Node:
def __init__(self, x, y, v, Data):
self.x = x
self.y = y
self.v = v
self.D = []
self.tried = []
for d in Data:
if d != v:
self.D.append(d)
self.tried.append(v)
def retry(self):
v=self.D.pop()
self.tried.append(v)
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)+ " Tried="+str(self.tried)
class Board:
def __init__(self, name="case_01.txt"):
self.num_rest=TOTAL_ELEMENTS
self.trace = []
self.DATA = []
self.data = []
self.Rows = []
self.Columns = []
self.Groups = []
self.name = name
for i in range(0, ROWS):
self.Rows.append(Group())
self.Columns.append(Group())
self.Groups.append(Group())
for i in range(0, ROWS):
self.data.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
self.DATA.append([[], [], [], [], [], [], [], [], []])
if not self.file_read(self.name):
print "Warning: Bad sudoku!!"
# index from 0 - 8
def value_set(self, x, y, v):
if (v==0):
return True
if self.Columns[y].candidate().__contains__(v) and \
self.Rows[x].candidate().__contains__(v) and \
self.Groups[self.group_get(x,y)].candidate().__contains__(v):
self.data[x][y] = v
self.Columns[y].set(v)
self.Rows[x].set(v)
self.Groups[self.group_get(x,y)].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[self.group_get(x,y)].unset(v)
self.num_rest = self.num_rest + 1;
for x in range(0,9):
for y in range(0,9):
self.DATA[x][y] = self.possible_value_get(x,y)
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):
if not self.value_set(x,y,int(f.read(2))):
print "Bad sudoku!!"
return False
return True
def possible_value_get(self, x, y):
if (self.data[x][y] != 0):
return
ans = [];
Group = self.Groups[self.group_get(x, y)].candidate()
Row = self.Rows[x].candidate()
Column= self.Columns[y].candidate()
for i in Group:
if i in Row and i in Column:
ans.append(i);
return ans;
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):
pos = self.possible_value_get(x,y)
self.DATA[x][y] = pos
if pos == None:
continue
if len(pos) == 1:
v = pos[0]
self.value_set(x,y,v)
self.trace.append(Cmd_Node(x,y,v, pos))
if pos.__len__() < min:
min_x = x
min_y = y
min = pos.__len__()
if min == 1:
return True
#guess has to be made
if self.DATA[min_x][min_y].__len__() > 0:
guess = self.DATA[min_x][min_y][0]
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()
if cmd.D.__len__()==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):
pos = self.possible_value_get(x,y)
self.DATA[x][y] = pos
while cmd.D.__len__() > 0:
v = cmd.retry()
if self.DATA[cmd.x][cmd.y].__contains__(v):
self.value_set(cmd.x, cmd.y, v)
self.trace.append(cmd)
continue_flag = False
break
4. run a lot of test cases to check out the bottleneck
如 case
0 7 8 1 0 0 5 0 0
0 0 6 0 0 0 0 0 0
5 0 0 0 4 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 4 8 0 0 0 0 0
0 0 0 0 0 9 2 0 3
0 0 1 0 0 2 0 0 8
9 6 3 0 0 0 0 5 0
0 0 0 4 0 0 3 0 9
以下是test case 分析出來的結果
172502 function calls in 0.651 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.651 0.651:1( )
1 0.000 0.000 0.651 0.651 testcase.py:45(_TC_Board_profileing)
1 0.000 0.000 0.002 0.002 tick_solver.py:102(file_read)
34101 0.318 0.000 0.507 0.000 tick_solver.py:111(possible_value_get)
98 0.033 0.000 0.188 0.002 tick_solver.py:123(puzzle_solving_iterate)
909 0.004 0.000 0.005 0.000 tick_solver.py:14(unset)
1 0.006 0.006 0.649 0.649 tick_solver.py:150(puzzle_solving)
53544 0.079 0.000 0.079 0.000 tick_solver.py:19(candidate)
341 0.002 0.000 0.002 0.000 tick_solver.py:23(__init__)
20 0.000 0.000 0.000 0.000 tick_solver.py:34(retry)
1 0.000 0.000 0.002 0.002 tick_solver.py:43(__init__)
442 0.007 0.000 0.017 0.000 tick_solver.py:64(value_set)
27 0.000 0.000 0.000 0.000 tick_solver.py:7(__init__)
303 0.064 0.000 0.424 0.001 tick_solver.py:78(value_unset)
1152 0.004 0.000 0.006 0.000 tick_solver.py:9(set)
18535 0.044 0.000 0.044 0.000 tick_solver.py:90(group_get)
4397 0.006 0.000 0.006 0.000 {len}
52821 0.073 0.000 0.073 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
323 0.001 0.000 0.001 0.000 {method 'pop' of 'list' objects}
81 0.000 0.000 0.000 0.000 {method 'read' of 'file' objects}
1152 0.002 0.000 0.002 0.000 {method 'remove' of 'list' objects}
1 0.000 0.000 0.000 0.000 {open}
4249 0.008 0.000 0.008 0.000 {range}
我們會發現
possible_value_get被 call 了 34101 次，花了 0.318 秒
candidate 被 call 了 53544 次…花了 0.079 秒
list 的 append 被 call 了 52821 次 花了 0.073 秒
種種的數據告訴我 possible_value_get 是最大的 bottleneck
array 的 operation 過於 大量且昂貴
而在這，我選擇的方式是…改變 Group 存數字的方式：用 binary operations
所以 Group 就變成了
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
def min_value(V):
v=1
while not V & 1:
V = V >> 1
v+=1
return v
而 possible_value_get 變成了
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
沒錯…就變成了兩個 operations
而時間從 變成 0.651
27546 function calls in 0.126 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.126 0.126:1( )
1 0.000 0.000 0.126 0.126 testcase.py:45(_TC_Board_profileing)
1 0.001 0.001 0.002 0.002 tick_solver.py:114(file_read)
7280 0.024 0.000 0.024 0.000 tick_solver.py:127(possible_value_get)
128 0.042 0.000 0.104 0.001 tick_solver.py:136(puzzle_solving_iterate)
1161 0.002 0.000 0.002 0.000 tick_solver.py:14(unset)
1 0.007 0.007 0.124 0.124 tick_solver.py:172(puzzle_solving)
1404 0.002 0.000 0.002 0.000 tick_solver.py:19(contains)
12148 0.028 0.000 0.028 0.000 tick_solver.py:29(len)
415 0.001 0.000 0.001 0.000 tick_solver.py:37(__init__)
30 0.000 0.000 0.000 0.000 tick_solver.py:44(retry)
1 0.000 0.000 0.002 0.002 tick_solver.py:56(__init__)
27 0.000 0.000 0.000 0.000 tick_solver.py:7(__init__)
526 0.007 0.000 0.013 0.000 tick_solver.py:76(value_set)
1404 0.003 0.000 0.003 0.000 tick_solver.py:9(set)
387 0.003 0.000 0.006 0.000 tick_solver.py:90(value_unset)
490 0.001 0.000 0.001 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
387 0.001 0.000 0.001 0.000 {method 'pop' of 'list' objects}
161 0.000 0.000 0.000 0.000 {method 'read' of 'file' objects}
1 0.000 0.000 0.000 0.000 {open}
1591 0.003 0.000 0.003 0.000 {range}
從快的我們會發現 bottleneck 變成了
12148 0.028 0.000 0.028 0.000 tick_solver.py:29(len)
7280 0.024 0.000 0.024 0.000 tick_solver.py:127(possible_value_get)
由於我是用 binary operation 算 len 變成一個 cost 相當高的事。而小弟覺得用查表法實在不夠好玩… 就是不肯用，所以就找出 len 的使用點，只做最必要的計算。(其實還可以用其它變數去存…這也會比較快)
而possible_value_get 其實已經很快了…可是因為被 call 的次數很多，所以太花時間 （大多在 type checking 和 stack jump） 所以就直接 inline 到被 call 的地方
如此一直找 bottleneck 的位置，不停的 "反" refactoring
最後變成
2655 function calls in 0.039 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.039 0.039:1( )
387 0.002 0.000 0.002 0.000 tick_solver.py:107(value_unset)
1 0.000 0.000 0.000 0.000 tick_solver.py:137(array_get)
1 0.031 0.031 0.038 0.038 tick_solver.py:149(puzzle_solving)
387 0.001 0.000 0.001 0.000 tick_solver.py:29(len)
415 0.001 0.000 0.001 0.000 tick_solver.py:44(__init__)
30 0.000 0.000 0.000 0.000 tick_solver.py:51(retry)
1 0.000 0.000 0.000 0.000 tick_solver.py:68(reinit)
27 0.000 0.000 0.000 0.000 tick_solver.py:7(__init__)
1 0.000 0.000 0.039 0.039 tick_solver.py:84(run)
526 0.003 0.000 0.003 0.000 tick_solver.py:92(value_set)
490 0.001 0.000 0.001 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
387 0.001 0.000 0.001 0.000 {method 'pop' of 'list' objects
又快了三倍 ^_^
然而在高興之餘卻發現到有一些 test case 會跑非常的久
tick@tock:~/work/sudoku>./testcase.py case_09.txt
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 9, 0, 0]
[0, 0, 0, 0, 6, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 9, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 5, 0]
[0, 0, 0, 0, 0, 0, 8, 0, 0]
[0, 9, 0, 0, 0, 0, 0, 3, 0]
[0, 0, 0, 7, 0, 0, 0, 0, 0]
3838777 function calls in 47.685 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 47.685 47.685:1( )
1 0.000 0.000 47.685 47.685 testcase.py:47(_TC_Board_profileing)
1 0.000 0.000 0.001 0.001 tick_solver.py:134(array_get)
1 36.462 36.462 47.684 47.684 tick_solver.py:181(puzzle_solving)
639734 1.038 0.000 1.038 0.000 tick_solver.py:29(len)
568664 1.425 0.000 1.425 0.000 tick_solver.py:37(__init__)
71141 0.297 0.000 0.297 0.000 tick_solver.py:44(retry)
1 0.000 0.000 0.000 0.000 tick_solver.py:61(reinit)
27 0.000 0.000 0.000 0.000 tick_solver.py:7(__init__)
1 0.000 0.000 47.685 47.685 tick_solver.py:77(run)
639886 3.827 0.000 3.827 0.000 tick_solver.py:85(value_set)
639734 2.801 0.000 2.801 0.000 tick_solver.py:99(value_unset)
639850 0.893 0.000 0.893 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
639734 0.942 0.000 0.942 0.000 {method 'pop' of 'list' objects}
[7, 6, 9, 1, 2, 8, 3, 4, 5]
[1, 2, 8, 3, 4, 5, 9, 6, 7]
[3, 4, 5, 9, 6, 7, 1, 2, 8]
[6, 5, 7, 2, 1, 3, 4, 8, 9]
[2, 8, 3, 5, 9, 4, 6, 7, 1]
[9, 1, 4, 8, 7, 6, 2, 5, 3]
[5, 7, 2, 4, 3, 1, 8, 9, 6]
[8, 9, 1, 6, 5, 2, 7, 3, 4]
[4, 3, 6, 7, 8, 9, 5, 1, 2]
這是因為我走迷宮時用相當簡單的 guess ，找出最小的 candidate
而很不幸，在一些迷宮中…（尤其是那些只有唯一解的）一但走錯… cost 就會走很遠，再走回來…這是我在演算法上的miss。所以就再加上了一些演算法來做相當複雜的 guess。而演算法的選擇也是很出現機率最高的來選擇… 只為 hard guess 相當的花時間…所以我只有在題目相當困難時 (最少candidate 的cell 依然有超過三個選擇時) (關鍵少數) 才去做。其它的，就交給暴力走迷宮法。
而 hard guess 也很成功的減少了 retry 的次數… ^^;
tick@tock:~/work/sudoku>./testcase.py case_09.txt
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 9, 0, 0]
[0, 0, 0, 0, 6, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 9, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 5, 0]
[0, 0, 0, 0, 0, 0, 8, 0, 0]
[0, 9, 0, 0, 0, 0, 0, 3, 0]
[0, 0, 0, 7, 0, 0, 0, 0, 0]
372 function calls in 0.028 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.028 0.028:1( )
1 0.000 0.000 0.001 0.001 tick_solver.py:137(array_get)
1 0.025 0.025 0.027 0.027 tick_solver.py:149(puzzle_solving)
71 0.000 0.000 0.000 0.000 tick_solver.py:44(__init__)
1 0.000 0.000 0.000 0.000 tick_solver.py:68(reinit)
27 0.000 0.000 0.000 0.000 tick_solver.py:7(__init__)
1 0.000 0.000 0.028 0.028 tick_solver.py:84(run)
152 0.001 0.000 0.001 0.000 tick_solver.py:92(value_set)
116 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
[8, 2, 5, 1, 7, 9, 3, 4, 6]
[4, 1, 6, 3, 2, 5, 9, 7, 8]
[9, 3, 7, 4, 6, 8, 1, 2, 5]
[7, 5, 9, 2, 1, 6, 4, 8, 3]
[3, 4, 8, 5, 9, 7, 6, 1, 2]
[1, 6, 2, 8, 4, 3, 7, 5, 9]
[5, 7, 1, 9, 3, 2, 8, 6, 4]
[2, 9, 4, 6, 8, 1, 5, 3, 7]
[6, 8, 3, 7, 5, 4, 2, 9, 1]
有些地方被 inline 掉了 :P
以下是目前的 source code, 蠻髒的，不過也蠻好玩的
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
def min_value(V):
v=1
while not V & 1:
V = V >> 1
v+=1
return v
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)
from test_module import *
class Board(TestModule):
def __init__(self):
self.reinit()
def reinit(self):
self.num_rest=TOTAL_ELEMENTS
self.trace = []
self.DATA = []
self.data = []
self.Rows = []
self.Columns = []
self.Groups = []
for i in xrange(0,9):
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.reinit()
self.array_get(array)
self.puzzle_solving()
return self.data
# index from 0 - 8
def value_set(self, x, y, v):
if (v==0):
return True
mask = (1<< (v-1))
if mask & self.Columns[y].left & self.Rows[x].left & self.Groups[(int(x/3)*3 + int(y/3))].left:
self.data[x][y] = v
mask = ~mask
self.Columns[y].left &= mask
self.Rows[x].left &= mask
self.Groups[(int(x/3)*3 + int(y/3))].left &= mask
self.num_rest = self.num_rest - 1;
return True
print "Set ("+str(x)+", "+str(y)+")="+str(v) +" Failed!!!"
return False
def value_unset(self, x, y):
v = self.data[x][y]
self.data[x][y] = 0
mask = (1 << (v-1))
self.Columns[y].left |= mask
self.Rows[x].left |= mask
self.Groups[(int(x/3)*3 + int(y/3))].left |= mask
self.num_rest = self.num_rest + 1;
def data_print(self):
print self.data
def pretty_print(self):
for i in xrange(0,9):
print self.data[i]
def file_read(self, name):
f = open(name, "r")
for x in xrange(0,9):
for y in xrange(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 xrange(0,9):
for y in xrange(0,9):
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(self):
while self.num_rest > 0:
min=10
for x in xrange(0,9):
for y in xrange(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 = 0
v = pos;
while v:
v &= v -1
lentmp += 1
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:
continue
#guess has to be made
if min > 0:
guess = 0
if min == 2:
while not (self.DATA[min_x][min_y] & 1 << guess):
guess += 1
guess += 1
else: # give a better guess here
Row = min_x % 3
R_base = min_x/3
Column = min_y % 3
C_base = min_y/3
V = self.DATA[min_x][min_y]
# remove hidden
while V:
a = V & 1
V = V >> 1
guess += 1
if not a:
continue
row_single_check = 0
column_single_check = 0
mask = (1 << (guess-1))
for i in [0, 1, 2]:
if Row != i and (self.Rows[R_base + i].left & mask):
row_single_check += 1
if Column != i and (self.Columns[C_base + i].left & mask):
column_single_check += 1
if row_single_check == 2 or column_single_check == 2: # guess first
break
#guess = self.hard_guess_find(min_x, min_y, self.DATA[min_x][min_y])
self.trace.append(Cmd_Node(min_x, min_y, guess, self.DATA[min_x][min_y]))
if self.value_set(min_x, min_y,guess):
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 xrange(0,9):
for y in xrange(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:
if lentmp==1:
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
else: # when there are more than one candidates, may be we can take long time to find out a better guess
v = self.hard_guess_find(cmd.x, cmd.y, cmd.D)
if self.DATA[cmd.x][cmd.y] & (1<< (v-1)):
cmd.D &= ~ (1<<(v-1))
self.value_set(cmd.x, cmd.y, v)
self.trace.append(cmd)
continue_flag = False
break
lentmp = len(cmd.D)
def hard_guess_find(self, x, y, V):
Row = x % 3
R_base = x/3
Column = y % 3
C_base = y/3
v = 0
# remove hidden
while V:
a = V & 1
V = V >> 1
v += 1
if not a:
continue
row_single_check = 0
column_single_check = 0
mask = (1 << (v-1))
for i in xrange(0,3):
if Row != i and (self.Rows[R_base + i].left & mask):
row_single_check += 1
if Column != i and (self.Columns[C_base + i].left & mask):
column_single_check += 1
if row_single_check == 2 or column_single_check == 2: # guess first
return v
return v
以下是跑 1000 個 test case 的分析圖 (用 octave 畫的)
可以看得出來其實大多數的 test case 都在 0.01 秒做完，而比較久的也在 0.02 秒內做完. 中位數在 0.003 秒
其實還有相當多地方可以改進… 如查表，pattern map等等…
不過…我個人覺得以一個小比賽來說…可以了… ^_^;
沒有留言:
張貼留言