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

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

邪惡的小案子

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