스도쿠 푸는 프로그램 입니다.
글쓴이: 임창진 / 작성시간: 금, 2006/02/03 - 9:22오전
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{4,4,5,' '} ,['54']=newCell{5,4,5,' '} ,['64']=newCell{6,4,5,' '} ,['74']=newCell{7,4,6,'5'} ,['84']=newCell{8,4,6,' '} ,['94']=newCell{9,4,6,' '} , ['15']=newCell{1,5,4,' '} ,['25']=newCell{2,5,4,' '} ,['35']=newCell{3,5,4,' '} ,['45']=newCell{4,5,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
Forums:
요즘 스도쿠에 빠져서 삽니다. 책도하나 사서 계속 풀고 있지요.. :)
요즘 스도쿠에 빠져서 삽니다. 책도하나 사서 계속 풀고 있지요.. :)
내용과는 관계없이 반가와서 답글을 올려봅니다.
---
http://coolengineer.com
조선일보 스도쿠
조선일보 스도쿠 깨 볼까요?
Real programmers /* don't */ comment their code.
If it was hard to write, it should be /* hard to */ read.
Re: 스도쿠 푸는 프로그램 입니다.
간단히 하기위해서 재귀를 이용해서 짜봤읍니다.C로 코딩할려고 했는데
간단히 하기위해서 재귀를 이용해서 짜봤읍니다.
C로 코딩할려고 했는데 오랫동안 안쓰다가 다시 하려고 하니
안되는군요. 그래서 익숙한 Ada로...
효율성은 무시하고 ^^; . 그냥가능한 모든값을 대입해서 찾는 방식입니다.
그렇지만 그렇게 느리지는 않네요.
몇개를 테스트해봤는데 전부 거의 1초안에 답을 출력하는군요.
pc방인데 환경이 별로라서 대충해서 올려봅니다. 꼭 버그가 있을것
같은 기분이...
다른 스도쿠가 있는지는 모르겠지만 인터넷에서 찾아보니 전부
9x9의 형식이네요 그래서 이것도 마찬가지입니다.
이거 로그인이 안되어 있네요 쩝.....혹시 위의 코드를 테스트 해보
이거 로그인이 안되어 있네요 쩝.....
혹시 위의 코드를 테스트 해보시려거든 ada컴파일러를 설치하시고
gnatmake sudoku 하시면 됩니다. 알아서 컴파일합니다.
입력은 그냥 한줄 9개의 문자를 공백없이 9번 입력하시면 됩니다.
300900200 Enter.
다음줄 입력...
요런식으로 ...
약간 수정합니다.위의 Ada코드에서 Is_Valid 함수의 주석에 N
약간 수정합니다.
위의 Ada코드에서 Is_Valid 함수의 주석에 Num이 속한 9x9의 제일위의 인덱스가 아니라 3x3입니다.
그리고 Solve_Sudoku함수에서 for 루프문에 '0' 이아니라
'1'부터 시작입니다. 물론 상관이 없지만.....
댓글 달기