grid = {}

function printGrid()
    local function putc(c) io.stdout:write(c) end
    for i=1,9 do
        putc('[')
        putc(grid[i][1] or ' ')
        for j=2,9 do
            putc(',')
            putc(grid[i][j] or ' ')
        end
        putc(']')
        putc('\n')
    end
end

function getPosibilities(x,y)
    local num, pos = 9, {true,true,true,true,true,true,true,true,true}

    local function chk(i,j)
        local t = grid[i][j]
        if t and pos[t] then num, pos[t] = num-1 end
        return num==0
    end

    for z=1,9 do
        if chk(x,z) or chk(z,y) then return num,pos end
    end

    local gx = math.ceil(x/3)*3-2
    local gy = math.ceil(y/3)*3-2
    for i=gx,gx+2 do
        for j=gy,gy+2 do
            if chk(i,j) then return num,pos end
        end
    end

    return num,pos
end

function findPossibilities1()
    local n,p,x,y = 10
    for i=1,9 do
        for j=1,9 do
            if nil==grid[i][j] then
                local num,pos = getPosibilities(i, j)
                if num==0 then return num,pos,i,j
                elseif num<n then n,p,x,y = num,pos,i,j end
            end
        end
    end
    return n,p,x,y
end

function findPossibilities2()
    local n,p,x,y = 10
    for i=1,9 do
        for j=1,9 do
            if nil==grid[i][j] then
                local num,pos = getPosibilities(i, j)
                if num==0 then return num,pos,i,j
                else return num,pos,i,j end
            end
        end
    end
    return n,p,x,y
end

function findPossibilities3()
    local h  = {0,0,0,0,0,0,0,0,0}
    local v  = {0,0,0,0,0,0,0,0,0}
    local g  = {0,0,0,0,0,0,0,0,0}

    for i=1,9 do for j=1,9 do if grid[i][j] then
        local k = 3*math.ceil(i/3)+math.ceil(j/3)-3
        h[i],v[j],g[k] = h[i]+1,v[j]+1,g[k]+1
    end end end

    local n,x,y = -1
    for i=1,9 do
        for j=1,9 do if grid[i][j]==nil then
            local num = h[i] + v[j] + g[3*math.ceil(i/3)+math.ceil(j/3)-3]
            if num>n then n,x,y = num,i,j end
        end end
    end
    if n>=0 then
        local num,pos = getPosibilities(x,y)
        return num,pos,x,y
    else
        return 10
    end
end


local depth,max = 0,0
function recurse()
    depth = depth + 1; if depth>max then max=depth end
    local n,p,x,y = findPossibilities()
    if n<10 then
        for v in pairs(p) do
            grid[x][y] = v
            if recurse() then depth=depth-1; return true end
        end
        grid[x][y] = nil
        depth=depth-1
        return false
    else
        print('solution:')
        printGrid()
        depth=depth-1
        return true
    end
end

grilles = {
    {
        "000000001",
        "210000904",
        "403500600",
        "900204500",
        "002705800",
        "001608003",
        "004007309",
        "709000068",
        "100000000"
    },{
        "060230000",
        "008004000",
        "305008047",
        "002000001",
        "500060009",
        "900000700",
        "740900506",
        "000400900",
        "000083070"
    },{
        "003850090",
        "000000100",
        "600000027",
        "000100900",
        "060507080",
        "008003000",
        "150000003",
        "002000000",
        "090085400"
    },{
        "075006800",
        "000000003",
        "300510600",
        "020000000",
        "054801290",
        "000000050",
        "002059006",
        "700000000",
        "003100980"
    },{
        "605000040",
        "000002076",
        "000700300",
        "000620080",
        "087050620",
        "000084000",
        "001005000",
        "520800000",
        "060000905"
    },{
        "000360100",
        "000080000",
        "941502000",
        "050008007",
        "060020090",
        "800900050",
        "000106978",
        "000040000",
        "008097000"
    },{
        "970000000",
        "305002940",
        "000095000",
        "000200005",
        "004080200",
        "500009000",
        "000670000",
        "082900703",
        "000000081"
    },{
        "000003009",
        "048006072",
        "100000400",
        "709430000",
        "000020000",
        "000067201",
        "002000007",
        "930700610",
        "400600000"
    },{
        "000100003",
        "000005800",
        "010007694",
        "000058000",
        "054902380",
        "000710000",
        "678300020",
        "003500000",
        "900001000"
    },{
        "000000608",
        "569300000",
        "007600000",
        "100000500",
        "080975020",
        "050000004",
        "000007200",
        "000004753",
        "903000000"
    },{
        "080000103",
        "709000824",
        "005000007",
        "020809000",
        "000401000",
        "000206080",
        "200000500",
        "451000302",
        "807000060"
    },{
        "006007590",
        "000000020",
        "000063100",
        "095870002",
        "000040000",
        "100035960",
        "007380000",
        "040000000",
        "059700600"
    },{
        "003009060",
        "708000409",
        "500000200",
        "001200000",
        "000805000",
        "000006100",
        "005000004",
        "804000307",
        "020500900"
    },{
        "000780000",
        "070000200",
        "010500497",
        "800012500",
        "500000006",
        "006350004",
        "432005060",
        "001000050",
        "000039000"
    },{
        "500007000",
        "000008703",
        "370010002",
        "200000500",
        "005362400",
        "001000008",
        "600090045",
        "104500000",
        "000200009"
    },{
        "000050600",
        "103000700",
        "450300000",
        "020005060",
        "049020180",
        "030100090",
        "000008016",
        "005000903",
        "006030000"
    },{ -- seulement 17 indices ==> dur !
        "000000010",
        "000002003",
        "000400000",
        "000000500",
        "401600000",
        "007100000",
        "050000200",
        "000080040",
        "030910000"
    }
}

findPossibilities = findPossibilities1

start = os.clock()
for no,g in ipairs(grilles) do
     for i=1,9 do grid[i] = {} end

    for i,s in ipairs(g) do
        for j=1,9 do
            local n = tonumber(s:sub(j,j))
            if n>0 then grid[i][j] = n end
        end
    end
    print('input:', no)
    printGrid()
    max = 0
    local start = os.clock()
    if not recurse() then print('no solution!') end
    print('depth:', max)
    print('time:', os.clock()-start,'sec')
    print()
end
print('total time:', os.clock() - start,'sec')