2008年6月25日 星期三

sudoku solver partII

Sudoku Solver 比賽順利結束了,這個比賽相當看重速度,所以在加速和結構上做了相當大的取捨,也對於 python 這個語言的特性有一些更深入的了解。(這是小弟的第二支 python 程式)
和大家分享一下小弟的加速過程…

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等等…
不過…我個人覺得以一個小比賽來說…可以了… ^_^;

2008年6月19日 星期四

Sudoku solver

在公司內辦了一場 Python Sudoku solver 比賽
下星期二才會正式跑 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

2008年6月14日 星期六

邪惡的小案子

提升大家宅度的邪惡計畫:
http://code.google.com/p/comic-reader/