스도쿠 푸는 프로그램 입니다.

lua 5.02 로 작성한 스도쿠 푸는 프로그램 입니다.
못푸는 문제도 있을수 있습니다.
따로 문제를 입력하는 방법은 없고 소스코드를 수정해서 입력해야 합니다.

44라인부터가 스도쿠의 문제를 표현한 부분입니다. 문제지의 빈칸은 space 번호가 있는칸은 해당번호를 넣으시면 됩니다.

local function newgetn(tbl)
    local n = 9
    local nilN = 0

    for i = 1,9 do
        if not tbl[i] then nilN = nilN + 1 end
    end

    return n - nilN
end


local function isEmpty(self)
    if self.dispNum ==  ' ' then
        return true
    else
        return false
    end
end

local function toString(self)
    return string.format("(%s,%s)=>[%s]",self.garo,self.sero,self.dispNum)
end

newCell = function(cellData)
    local tbl = {}
    local nomi = {'1','2','3','4','5','6','7','8','9'}

    tbl.sero = cellData[2]
    tbl.garo = cellData[1]
    tbl.blocknum = cellData[3]
    tbl.dispNum = cellData[4]
    tbl.isEmpty = isEmpty
    tbl.toString = toString

    tbl.nomi = nil
    if cellData[4] == ' ' then
        tbl.nomi = nomi
    end

    return tbl
end

board = {
    ['11']=newCell{1,1,1,' '} ,['21']=newCell{2,1,1,' '} ,['31']=newCell{3,1,1,'4'} ,['41']=newCell{4,1,2,' '} ,['51']=newCell{5,1,2,'5'} ,['61']=newCell{6,1,2,' '} ,['71']=newCell{7,1,3,' '} ,['81']=newCell{8,1,3,'6'} ,['91']=newCell{9,1,3,' '} ,
    ['12']=newCell{1,2,1,' '} ,['22']=newCell{2,2,1,'6'} ,['32']=newCell{3,2,1,' '} ,['42']=newCell{4,2,2,'1'} ,['52']=newCell{5,2,2,' '} ,['62']=newCell{6,2,2,' '} ,['72']=newCell{7,2,3,'8'} ,['82']=newCell{8,2,3,' '} ,['92']=newCell{9,2,3,'9'} ,
    ['13']=newCell{1,3,1,'3'} ,['23']=newCell{2,3,1,' '} ,['33']=newCell{3,3,1,' '} ,['43']=newCell{4,3,2,' '} ,['53']=newCell{5,3,2,' '} ,['63']=newCell{6,3,2,'7'} ,['73']=newCell{7,3,3,' '} ,['83']=newCell{8,3,3,' '} ,['93']=newCell{9,3,3,' '} ,
    ['14']=newCell{1,4,4,' '} ,['24']=newCell{2,4,4,'8'} ,['34']=newCell{3,4,4,' '} ,['44']=newCell{1,9,' ',' '} ,['54']=newCell{' ',' ',' ',' '} ,['64']=newCell{' ',' ',' ',' '} ,['74']=newCell{' ',' ',' ',' '} ,['84']=newCell{' ',' ',2,' '} ,['94']=newCell{' ',' ',8,' '} ,
    ['15']=newCell{' ',' ',2,' '} ,['25']=newCell{' ',' ',1,' '} ,['35']=newCell{4,' ',' ',' '} ,['45']=newCell{' ',' ',5,'4'} ,['55']=newCell{5,5,5,' '} ,['65']=newCell{6,5,5,'3'} ,['75']=newCell{7,5,6,' '} ,['85']=newCell{8,5,6,' '} ,['95']=newCell{9,5,6,' '} ,
    ['16']=newCell{1,6,4,' '} ,['26']=newCell{2,6,4,' '} ,['36']=newCell{3,6,4,'6'} ,['46']=newCell{4,6,5,' '} ,['56']=newCell{5,6,5,' '} ,['66']=newCell{6,6,5,' '} ,['76']=newCell{7,6,6,' '} ,['86']=newCell{8,6,6,'7'} ,['96']=newCell{9,6,6,' '} ,
    ['17']=newCell{1,7,7,' '} ,['27']=newCell{2,7,7,' '} ,['37']=newCell{3,7,7,' '} ,['47']=newCell{4,7,8,'2'} ,['57']=newCell{5,7,8,' '} ,['67']=newCell{6,7,8,' '} ,['77']=newCell{7,7,9,' '} ,['87']=newCell{8,7,9,' '} ,['97']=newCell{9,7,9,'6'} ,
    ['18']=newCell{1,8,7,'1'} ,['28']=newCell{2,8,7,' '} ,['38']=newCell{3,8,7,'5'} ,['48']=newCell{4,8,8,' '} ,['58']=newCell{5,8,8,' '} ,['68']=newCell{6,8,8,'4'} ,['78']=newCell{7,8,9,' '} ,['88']=newCell{8,8,9,'3'} ,['98']=newCell{9,8,9,' '} ,
    ['19']=newCell{1,9,7,' '} ,['29']=newCell{2,9,7,'2'} ,['39']=newCell{3,9,7,' '} ,['49']=newCell{4,9,8,' '} ,['59']=newCell{5,9,8,'7'} ,['69']=newCell{6,9,8,' '} ,['79']=newCell{7,9,9,'1'} ,['89']=newCell{8,9,9,' '} ,['99']=newCell{9,9,9,' '} ,

    emptyCell=81
}


--~ count empty cell and print empty cell count
function board:calcEmpty()
    self.emptyCell = 0
    for sero = 1,9 do
    for garo = 1,9 do
        if self[sero..garo]:isEmpty()  then
            self.emptyCell = self.emptyCell + 1
        end
    end
    end
    print('emptyCell Count : ' .. self.emptyCell)
end



--~ garo(vertical line index) sero(horizontal line index) start from 1
--~ print nominees that can be placed at garo,sero location
function board:printNomi(garo,sero)
    print('can be placed ---------------------------------')

    if not self[garo..sero]:isEmpty() then
        print( self[garo..sero].dispNum .. ' is already founded!!!')
        return
    end

    local tc = self[garo..sero]
    for i = 1,9 do
        io.write((tc.nomi[i] or type(tc.nomi[i])) ..',')
    end
    print()
end

-- print all founded number and  not yet founded cell(space) of current board
function board:print()
    for sero=1,9 do
        for garo=1,9 do
            io.write( board[garo..sero].dispNum .. ',' )
        end
        print()
    end
end

--~ guess which number can be placed this garo,sero location
function board:guess(garo,sero)
    local tmpCell = self[garo..sero]
    local blockNum = tmpCell.blocknum

    if not tmpCell:isEmpty() then return end

    tmpCell.nomi = board:rmVertDup(garo,tmpCell.nomi)
    tmpCell.nomi = board:rmHoriDup(sero,tmpCell.nomi)
    tmpCell.nomi = board:rmBlockDup(blockNum,tmpCell.nomi)

    if newgetn(tmpCell.nomi) == 1 then
        io.write(tmpCell.garo ,',',tmpCell.sero ,'=******************=>')
        for i = 1,9 do
            if tmpCell.nomi[i] then
                tmpCell.dispNum = tmpCell.nomi[i]
                io.write(tmpCell.nomi[i] .. ' found \n')
            end
        end
    else
        for i=1,9 do
            if tmpCell.nomi[i] then
                local v = tmpCell.nomi[i]
                if not board:canBeOtherPlace(tmpCell,v) then
                    print('can\'t be ::::::::::::::::: ' .. v)
                    tmpCell.dispNum = v
                    break;
                end
            end
        end
    end
end

function table.containsv(tbl,v)
    for i = 1,9 do
        if tbl[i] == v then
            return true
        end
    end

    return false
end



function board:guessBlock(pBlockNum)
    local emptyNums = board:rmBlockDup(pBlockNum,{'1','2','3','4','5','6','7','8','9'})

    table.foreach(emptyNums,function (k,v)
        local canBePlacedCells = board:getCBPC(pBlockNum,v)

        local sGaro = getSameGaro(canBePlacedCells)
        if sGaro then
            board:cantBePlaceGaro(sGaro,v,pBlockNum)
        end

        local sSero = getSameSero(canBePlacedCells)
        if sSero then
            board:cantBePlaceSero(sSero,v,pBlockNum)
        end
    end)
end



function board:cantBePlaceGaro(garo,v,pBlockNum)
    for sero=1,9 do
        -- sero axis seearch
        if self[garo..sero]:isEmpty() and self[garo..sero].blocknum ~= pBlockNum then
            local nomi = self[garo..sero].nomi
            for i = 1,9 do
                if nomi[i] == v then
                    nomi[i] = nil
                end
            end
        end
    end
end


function board:cantBePlaceSero(sero,v,pBlockNum)
    for garo=1,9 do
		-- garo axis seearch
        if self[garo..sero]:isEmpty() and self[garo..sero].blocknum ~= pBlockNum then
            local nomi = self[garo..sero].nomi
            for i = 1,9 do
                if nomi[i] == v then
                    nomi[i] = nil
                end
            end
        end
    end
end




function getSameGaro(canBePlacedCells)
    local garo = '0'

    table.foreach(canBePlacedCells,function (k,cell)
        if garo ~= '0' and cell.garo ~= garo then
            garo = nil
        else
            garo = cell.garo
        end
--~         print (garo)
    end)

    return garo
end


function getSameSero(canBePlacedCells)
    local sero = '0'

    table.foreach(canBePlacedCells,function (k,cell)
        if sero ~= '0' and cell.sero ~= sero then
            sero = nil
        else
            sero = cell.sero
        end
--~         print (garo)
    end)

    return sero
end



function board:getCBPC(pBlockNum,v)
    local cbpcTbl = {}

    for sero=1,9 do
        for garo=1,9 do
            if self[garo..sero].blocknum == pBlockNum
                    and self[garo..sero]:isEmpty()
                    and table.containsv(self[garo..sero].nomi,v)  then
                table.insert(cbpcTbl,self[garo..sero])
            end
        end
    end

    return cbpcTbl
end

function board:canBeOtherPlace(tc,v)
    local pBlockNum = tc.blocknum
    for sero=1,9 do
        for garo=1,9 do
            local tmpCell = self[garo..sero]
            if tmpCell.blocknum == pBlockNum and tmpCell:isEmpty() and tmpCell ~= tc then
                if table.containsv(tmpCell.nomi , v) then return true end
            end
        end
    end

    return false
end


function board:rmVertDup(garo,nomi)
    for sero=1,9 do
        -- sero axis seearch
        if not self[garo..sero]:isEmpty() then
            for i = 1,9 do
                if nomi[i] == self[garo..sero].dispNum then
                    nomi[i] = nil
                end
            end
        end
    end

    return nomi
end

function board:rmHoriDup(sero,nomi)
    for garo=1,9 do
        -- garo axis seearch
        if not self[garo..sero]:isEmpty() then
            for i = 1,9 do
                if nomi[i] == self[garo..sero].dispNum then
                    nomi[i] = nil
                end
            end
        end
    end

    return nomi
end

function board:rmBlockDup(pBlockNum,nomi)
    for sero=1,9 do
        for garo=1,9 do
            if self[garo..sero].blocknum == pBlockNum and not self[garo..sero]:isEmpty() then
                for i = 1,9 do
                    if nomi[i] == self[garo..sero].dispNum then
                        nomi[i] = nil
                    end
                end
            end
        end
    end

    return nomi
end

while board.emptyCell > 0 do
    for sero=1,9 do
        for garo=1,9 do
            if board[garo..sero]:isEmpty() then
                board:guess(garo,sero)
            end
        end
    end

    for block=1,9 do
        board:guessBlock(block)
    end


    board:print();
    board:calcEmpty();
end