数独小解

浅浅的花香味﹌ 2022-04-08 08:41 282阅读 0赞

> 本文简述了一种关于数独游戏的程序解法

数独游戏相信大家都有所耳闻,规则上非常简明:

> 在 9 x 9 的数格中(由 9 个 3 x 3 的九宫格组成)会预先给定不少于(>=)17个数字,你需要在满足以下条件的情况下补完其余数格中的数字:
> 
> 1.  每一行的数字不重复
> 2.  每一列的数字不重复
> 3.  每个 3 x 3 九宫格中的数字不重复

这里有个示例:

![图片来自维基百科][2018120711524031.png]

使用程序求解数独的一种简单方法便是穷举(搜索),较粗糙的一种方式就是枚举 9 x 9 数格中所有的数字组合(为每个数格指定 1 ~ 9 之间的某个数字),只是这种搜索方式的解空间较大,实际运用中需要进行剪枝,剪枝的思路其实也很朴素,依据数独中相关数字不可重复的3条规则即可:

**按照空白数格顺序进行深度优先搜索,对于每个空白数格生成候选数字列表(即满足规则下可能填入该空白数格的数字列表),然后依次填入可能的候选数字,并在下一个空白数格处继续进行相同的深度优先搜索,如果成功则找到答案,否则返回失败.**

(*可以使用启发式算法优化,譬如按候选数字列表最短的空白数格顺序进行搜索(实际测试中因为工程原因其实比顺序搜索方法更慢)*)

下面是使用 Lua 实现的示例程序:

function get_sudoku_row_and_col(data)
        local row = #data
        local col = data[1] and #data[1] or 0
        return row, col
    end
    
    function print_sudoku(data)
        local row, col = get_sudoku_row_and_col(data)
        for i = 1, row do
            local str_buffer = {}
            for j = 1, col do
                table.insert(str_buffer, data[i][j])
            end
            print(table.concat(str_buffer, ", "))
        end
        print()
    end
    
    function check_sudoku_row(data, row_index)
        local row, col = get_sudoku_row_and_col(data)
        local sum = 1
        for i = 1, col do
            sum = sum | (1 << (data[row_index][i]))
        end
        return sum == 0x3FF
    end
    
    function check_sudoku_col(data, col_index)
        local row, col = get_sudoku_row_and_col(data)
        local sum = 1
        for i = 1, row do
            sum = sum | (1 << (data[i][col_index]))
        end
        return sum == 0x3FF
    end
    
    function check_sudoku_square(data, row_index, col_index)
        local row, col = get_sudoku_row_and_col(data)
        local sum = 1
        for i = row_index, row_index + 2 do
            for j = col_index, col_index + 2 do
                sum = sum | (1 << (data[i][j]))
            end
        end
        return sum == 0x3FF
    end
    
    function check_sudoku(data)
        local row, col = get_sudoku_row_and_col(data)
        
        -- check row
        for i = 1, row do
            if not check_sudoku_row(data, i) then
                return false
            end
        end
        
        -- check col
        for i = 1, col do
            if not check_sudoku_col(data, i) then
                return false
            end
        end
        
        -- check square
        for i = 1, row // 3 do
            local row_index = (i - 1) * 3 + 1
            for j = 1, col // 3 do
                local col_inex = (j - 1) * 3 + 1
                if not check_sudoku_square(data, row_index, col_inex) then
                    return false
                end
            end
        end
        
        return true
    end
    
    function apply_sudoku(data, delta)
        local row, col = delta.row, delta.col
        if data[row] and data[row][col] then
            data[row][col] = delta.val
        end
    end
    
    function revert_sudoku(data, delta)
        local row, col = delta.row, delta.col
        if data[row] and data[row][col] then
            data[row][col] = 0
        end
    end
    
    function get_pending_list(data, row, col)
        if data[row] and data[row][col] then
            if data[row][col] == 0 then
                -- only empty pos has pending list
                local pending_list = { true, true, true, true, true, true, true, true, true }
                
                local data_row, data_col = get_sudoku_row_and_col(data)
                
                -- check row
                for i = 1, data_col do
                    pending_list[data[row][i]] = false
                end
                
                -- check col
                for i = 1, data_row do
                    pending_list[data[i][col]] = false
                end
                
                -- check square
                local square_row = (row - 1) // 3 * 3 + 1 -- or math.ceil(row / 3) * 3 - 2
                local square_col = (col - 1) // 3 * 3 + 1 -- or math.ceil(col / 3) * 3 - 2
                for i = square_row, square_row + 2 do
                    for j = square_col, square_col + 2 do
                        pending_list[data[i][j]] = false
                    end
                end
                
                -- gen pending list number
                local pending_list_num = {}
                for i = 1, #pending_list do
                    if pending_list[i] then
                        table.insert(pending_list_num, i)
                    end
                end
                
                return pending_list_num
            end
        end
    end
    
    function get_next_search_pos(data, row, col)
        -- now we just search in order
        local data_row, data_col = get_sudoku_row_and_col(data)
        
        -- top right part
        for j = col, data_col do
            if data[row][j] == 0 then
                return row, j
            end
        end
        
        -- rest part
        for i = row + 1, data_row do
            for j = 1, data_col do
                if data[i][j] == 0 then
                    return i, j
                end
            end
        end
    end
    
    function search_sudoku_recur(data, row, col)
        row, col = get_next_search_pos(data, row, col)
        if row and col then
            local pending_list = get_pending_list(data, row, col)
            if pending_list and #pending_list > 0 then
                for i = 1, #pending_list do
                    apply_sudoku(data, { row = row, col = col, val = pending_list[i] })
                    local val = search_sudoku_recur(data, row, col)
                    if val then
                        return true
                    else
                        revert_sudoku(data, { row = row, col = col, val = pending_list[i] })
                    end
                end
                
                -- all pending list is not valid
                return false
            else
                -- no valid pending list
                return false
            end
        else
            -- all data filled
            if check_sudoku(data) then
                -- valid data
                return true
            else
                -- invalid data
                return false
            end
        end
    end
    
    function search_sudoku(data)
        return search_sudoku_recur(data, 1, 1)
    end

示例程序并不简短,但是理解起来并不困难,要点如下:

*  数独的数格表示使用了"二维数组"
 *  函数 check\_sudoku 用以检查数格中的数字是否满足数独条件
 *  函数 search\_sudoku 实现了上述的深度优先搜索方法

下图是号称世界上迄今难度最大的数独游戏,有兴趣的朋友可以试下:

![迄今最难数独][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rrb2tvZjE_size_16_color_FFFFFF_t_70]

#### 参考资料 ####

1.  [数独的维基百科][Link 1]
2.  [<算法的乐趣>][Link 2]
3.  [世上最难数独][Link 3]

[2018120711524031.png]: /images/20220407/a91e9fa558ee4b54ad31be9bebaa3ceb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rrb2tvZjE_size_16_color_FFFFFF_t_70]: /images/20220407/88284bf53be3415da6d6124b32d16c20.png
[Link 1]: https://zh.wikipedia.org/wiki/%E6%95%B8%E7%8D%A8
[Link 2]: https://book.douban.com/subject/26351257/
[Link 3]: https://baike.baidu.com/item/%E4%B8%96%E7%95%8C%E6%9C%80%E9%9A%BE%E6%95%B0%E7%8B%AC/13848819