回溯算法解决数独

sudoko = {
    {8, 0, 0, 0, 0, 0, 0, 0, 0},  
    {0, 0, 3, 6, 0, 0, 0, 0, 0},  
    {0, 7, 0, 0, 9, 0, 2, 0, 0},  
    {0, 5, 0, 0, 0, 7, 0, 0, 0},  
    {0, 0, 0, 0, 4, 5, 7, 0, 0},  
    {0, 0, 0, 1, 0, 0, 0, 3, 0},  
    {0, 0, 1, 0, 0, 0, 0, 6, 8},  
    {0, 0, 8, 5, 0, 0, 0, 1, 0},  
    {0, 9, 0, 0, 0, 0, 4, 0, 0}
};  

function check(row,  line,number,matrix)
    --判断该行该列是否有重复数字  
    for  i = 1 ,9 do 
        if matrix[row][i] == number or  matrix[i][line] == number then
            return false
        end
    end
    --判断小九宫格是否有重复 
    local tempRow = math.ceil (row / 3)  - 1

    local  tempLine =math.ceil (line/ 3) - 1
    for  i = 1,3 do 
        for j = 1,3 do 
            if (matrix[tempRow * 3 + i][tempLine * 3 + j] == number) then

                return false
            end
        end
    end
    return  true
end

function printArray(matrix)
    for k,v in ipairs(matrix) do
        print(table.concat(v,","))
    end
end

function backTrace(i,j,matrix)
    --结尾
    if  i == 9 and  j  == 10   then
        printArray(matrix)
        return 
    end 
    --到达列尾
    if  j == 10   then
        j = 1
        i = i +1    
    end
    if  (matrix[i][j] == 0) then
        for  k = 1 ,9 do 
            if check(i, j, k,matrix) then
                matrix[i][j] = k
                backTrace(i, j + 1,matrix)
                --回溯还原
                  matrix[i][j] = 0; 
            end 
        end

    else 
        --下个位置
        backTrace(i, j + 1,matrix);  
    end
end 

backTrace(1,1,sudoko)

--优化版本
sudoko = {}
--初始化
sudoko.matrix = {
    {8, 0, 0, 0, 0, 0, 0, 0, 0},  
    {0, 0, 3, 6, 0, 0, 0, 0, 0},  
    {0, 7, 0, 0, 9, 0, 2, 0, 0},  
    {0, 5, 0, 0, 0, 7, 0, 0, 0},  
    {0, 0, 0, 0, 4, 5, 7, 0, 0},  
    {0, 0, 0, 1, 0, 0, 0, 3, 0},  
    {0, 0, 1, 0, 0, 0, 0, 6, 8},  
    {0, 0, 8, 5, 0, 0, 0, 1, 0},  
    {0, 9, 0, 0, 0, 0, 4, 0, 0}
};  
sudoko.count = 0

function sudoko:check(row,  line,number)
    local  matrix = self.matrix
    --判断该行该列是否有重复数字  
    for  i = 1 ,9 do 
        if matrix[row][i] == number or  matrix[i][line] == number then
            return false
        end
    end
    --判断小九宫格是否有重复 
    local tempRow = math.ceil (row / 3)  - 1
    local  tempLine =math.ceil (line/ 3) - 1
    for  i = 1,3 do 
        for j = 1,3 do 
            if (matrix[tempRow * 3 + i][tempLine * 3 + j] == number) then
                return false
            end
        end
    end
    return  true
end

function sudoko:printArray()
    local  matrix = self.matrix
    for k,v in ipairs(matrix) do
        print(table.concat(v,","))
    end
    print("统计backTrace调用次数:" .. self.count)
end

function sudoko:backTrace(i,j)
    local  matrix = self.matrix
    --统计函数调用次数
    self.count = self.count + 1
    --结尾
    if  i >= 9 and  j  >= 10   then
        self:printArray()
        return true
    end 
    --到达列尾
    if  j == 10   then
        i = i +1    
        j = 1 
    end
    if  (matrix[i][j] == 0) then
        for  k = 1 ,9 do 
            if self:check(i, j, k) then
                matrix[i][j] = k
                if self:backTrace(i, j + 1)    then
                    return  true 
                end
                --回溯还原
                matrix[i][j] = 0; 
            end 
        end
    else 
        --下个位置
        return self:backTrace(i, j + 1);  
    end
end 


sudoko:backTrace(1,1)

优化之后backTrace函数调用次数72097次,之前3031697次
参考
http://blog.csdn.net/tianyaleixiaowu/article/details/50912924