[原]数独小解

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

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

这里有个示例:

使用程序求解数独的一种简单方法便是穷举(搜索),较粗糙的一种方式就是枚举 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 实现了上述的深度优先搜索方法

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

参考资料

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