Udacity AI Project1: Solving Sudoku

什麼是數獨？

9x9棋盤上，每個3x3方塊，把1~9不重複填入，但是對9x9棋盤而言，每個row或是column也不能遊戲會是先幫玩家填入幾個，當作是constraint：

Board representation

在課程中，教材內容把9x9 board encode成string 'A1' ... 'I9'，以下三種組合(unit)是可能需要在解題過程中考慮的：

對一個方格(box)來說，跟他同row, 同column, 同3x3 block的其他方格（稱為peers)都是必須要檢查的項目，因為遊戲規則所致，所以對上圖紅色box來說，他總共有20個peers，這對任意box都是一樣的數目。

可以用字串來encode目前board填入數字的狀況，例如以下：

左圖右上到下，由左至右可以encode成：
..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..

右圖全部填入數字後，就可以把 . 符號換成填入的數字：
483921657967345821251876493548132976729564138136798245372689514814253769695417382

由於我們要依據某個box的名稱(例如'A1'或是'D7')快速找到某個box，可以用dictionary來implement lookup table。每個空格box值要填入'123456789'，因為我們待會要用消去法來消去重複的數字。

所以box dictionary在初始化的時候會變成以下形式：

{
    'A1': '123456789',
    'A2': '123456789',
    'A3': '3',
    'A4': '123456789'
    'A5': '2',
    ...
    'I9': '123456789'
}




思考邏輯

1. 消去法(elimination)：對任意一個box來說，先去除掉所有peers中不可能的值，例如以下圖示：

我們上面的範例，如果對每一個空格box依序執行對default value '123456789' 進行elimination，可以得出空格box的各種可能值（不是最optimal form，可能需要進行多次才能得到optimal form）：

def eliminate(values):
    solved_values = [box for box in values.keys() if len(values[box]) == 1]
    for box in solved_values:
        digit = values[box]
        for peer in peers[box]:
            values[peer] = values[peer].replace(digit,'')
    return values

2. 唯一可能
消去可能的選項後，如果出現唯一可能者，代表我們solve了某一個box的值，例如以下紅色unit:

有四個空格都有兩個以上的可能性，但是數字1只出現在右上角的空格！所以1只能填入右上角的box，solved!

對整個棋盤上所有的units（rows, cols, 3x3 blocks)去執行這樣的唯一可能檢查，不過這邊implementation要注意容易出錯，總之就是要exhaustively check:

def only_choice(values):
     for unit in unitlist:
        for number in '123456789':
            occurrences = [box for box in unit if number in values[box]]
            if (len(occurrences) == 1):
                values[occurrences[0]] = number

    return values

Constraint Propagation

以上的思考邏輯是用constraint來縮減search space（我們還沒開始search），這兩個步驟可以重複做（稱為propagation)，直到search space不能再被縮減為止，此時可能會找到solution，也可能不會，要檢查goal_state是否達到，以及是否再也不能having progress:

對這個specific board instance來說，constraint propagation是可以找到solution，但是對其他的board instance就不一定了，就要進入search階段。

下面的implementation為什麼要return false? 單純的constraint propagation不應該會抵達錯誤的state，意即某個box的值最後是填空的。但是下面這個reduce_puzzle是之後要當作search前處理的，所以當search選了某個child state去嘗試（也就是越俎代庖做了錯誤的only_choice)，的確有可能造成錯誤的state，就跟我們人力在玩Sudoku一樣，選了一個可能，最後發現填不下去了。

def reduce_puzzle(values):
    stalled = False    while not stalled:
        solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])
        values = eliminate(values)
        values = only_choice(values)
        solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
        stalled = solved_values_before == solved_values_after
        if len([box for box in values.keys() if len(values[box]) == 0]):
            return False    return values

Search

如果一個比較複雜的board instance，無法用constraint propagation來找到solution，我們就可以進行search，例如DFS/BFS/AStar ... 。

initial state會是constrain propagation reduce之後的結果，這樣先大量減少我們的search space。root node可以選目前含有最少可能數字的box。

def search(values):
    values = reduce_puzzle(values)
    if values is False:
        return False
    if all(len(values[s]) == 1 for s in boxes):
        return values
    n,s = min((len(values[s]), s) for s in boxes if len(values[s]) > 1)
    for value in values[s]:
        new_sudoku = values.copy()
        new_sudoku[s] = value
        attempt = search(new_sudoku)
        if attempt:
            return attempt

Naked Twins 技巧

這算是only_choice的升級版，能有效縮減search space。我們在DFS search中要隨意選一個目前unsolved box value 長度最少者，當然最小值會是2，然後進行elimination和one_choice。

眾多value = 2的box candidates中，任意選擇一個就會長出至少一個錯誤的subtree，而且每次search只能100%確定這個box。，但是如果同時看兩個一樣value = 2且有相同value的boxes呢？（在同一個unit中）：

把這種box pair當作candidate的話，每ㄧ次search可以同時確定兩個boxes，因為如果某個child state return False，則明顯正確的答案就是另一個child state，當然在elimination步驟也能受惠：

Diagonal Sudoku變形

這就是Udacity AIND第一個作業啦，在課堂給的skeleton code上面，修改成更困難的Sudoku變形，也就是對角線的數字也要符合1~9不重複出現的constraint:

Sample code

到這邊下載: https://bitbucket.org/wang_sonny/aind_sudoku