CaptainSpaceCat

SudokuGen V2

Jun 13th, 2016
85
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ----------------------------------------------MISC FUNCS
  2. if fs.exists("console") then
  3.     shell.run("delete console")
  4. end
  5.  
  6.  
  7. local debug = false
  8. local h = fs.open("console","a")
  9. function log(t)
  10.     if debug then
  11.   if type(t) == "table" then
  12.     for i,v in pairs(t) do
  13.       h.write("i = ")
  14.       h.write(i)
  15.       h.write(" v = ")
  16.       h.write(v)
  17.       h.write("\n")
  18.     end
  19.    
  20.   else
  21.     h.write(t)
  22.     h.write("\n")
  23.   end
  24.   h.flush()
  25.   end
  26. end
  27.  
  28. function logBoard(board, currentPos, futurePos)
  29. if debug then
  30.     for y = 1, 9 do
  31.     term.setCursorPos(1, y + math.ceil(y/3) - 1)
  32.         for x = 1, 9 do
  33.             if tonumber(board[y][x]) then
  34.                 term.setTextColor(colors.red)
  35.                 write(board[y][x])
  36.             else
  37.                 term.setTextColor(colors.white)
  38.                 write("0")
  39.             end
  40.             if x == 3 or x == 6 then
  41.                 write(" ")
  42.             end
  43.         end
  44.     end
  45.     if currentPos then
  46.         term.setTextColor(colors.orange)
  47.         term.setCursorPos(currentPos[1] + math.floor((currentPos[1]-1)/3), currentPos[2] + math.floor((currentPos[2]-1)/3))
  48.         term.write(board[currentPos[2]][currentPos[1]])
  49.     end
  50.     if futurePos then
  51.         term.setTextColor(colors.lime)
  52.         term.setCursorPos(futurePos[1] + math.floor((futurePos[1]-1)/3), currentPos[2] + math.floor((futurePos[2]-1)/3))
  53.         term.write("*")
  54.         os.pullEvent("mouse_click")
  55.     end
  56.     print("")
  57.     sleep(.1)
  58. end
  59. end
  60.  
  61. function printBoard(board)
  62.     for y = 1, 9 do
  63.     term.setCursorPos(1, y + math.ceil(y/3) - 1)
  64.         for x = 1, 9 do
  65.             if tonumber(board[y][x]) then
  66.                 term.setTextColor(colors.red)
  67.                 write(board[y][x])
  68.             else
  69.                 term.setTextColor(colors.white)
  70.                 write("0")
  71.             end
  72.             if x == 3 or x == 6 then
  73.                 write(" ")
  74.             end
  75.         end
  76.     end
  77.     print("")
  78. end
  79.  
  80. ----------------------------------------------GENERATION
  81. function initializeBoard(board)
  82.     for y = 1, 9 do
  83.         board[y] = {}
  84.     end
  85. end
  86.  
  87. function generatePuzzle(board)
  88.     for i = 1, 9 do               --x                             --y
  89.         log("-=-=-=-=-=-=-=-=-=-=-=-=-=-=-" .. i)
  90.         local refTab = {{{1, 2, 3}, {1, 2, 3}, {1, 2, 3}}, {{1, 2, 3}, {1, 2, 3}, {1, 2, 3}}}
  91.         for y = 1, 3 do
  92.             for x = 1, 3 do
  93.                 local availableCells = getAvailableCells(x, y, refTab, board)
  94.                 local yOff = 0
  95.                 local xOff = 0
  96.                 for loop = 1, 4 do
  97.                     if #availableCells == 0 and loop%2 == 1 then
  98.                         log("No possible cells... reshuffling Y...")
  99.                         for recurY = y-1-yOff, 1, -1 do
  100.                             local iPosLocal, iPosGlobal = iLocate(i, x, recurY, board)
  101.                             local options = {}
  102.                             for n = 1 + (x-1)*3, 3 + (x-1)*3 do
  103.                                 if not board[iPosGlobal[2]][n] and refTab[1][x][n - (x-1)*3] ~= 0 then   --(recurY-1)*3 +
  104.                                     table.insert(options, {n, iPosGlobal[2]})
  105.                                 end
  106.                             end
  107.                             if #options > 0 then
  108.                                 local choice = options[math.random(1, #options)]
  109.                                 logBoard(board, iPosGlobal, choice)
  110.                                    
  111.                                 board[iPosGlobal[2]][iPosGlobal[1]] = nil
  112.                                 board[choice[2]][choice[1]] = i
  113.                                     log("Moving " .. iPosGlobal[1] .. ":" .. iPosGlobal[2] .. " to " .. choice[1] .. ":" .. choice[2])
  114.                                 refTab[1][math.ceil(choice[1]/3)][iPosLocal[1]] = 1
  115.                                 refTab[1][math.ceil(choice[1]/3)][(choice[1]-1)%3+1] = 0
  116.                                 yOff = yOff + 1
  117.                                 break;
  118.                             end
  119.                         end
  120.                     elseif #availableCells == 0 and loop%2 == 0 then
  121.                         log("No possible cells... reshuffling X...")
  122.                         for recurX = x-1-xOff, 1, -1 do
  123.                             local iPosLocal, iPosGlobal = iLocate(i, recurX, y, board)
  124.                             local options = {}
  125.                             for n = 1 + (y-1)*3, 3 + (y-1)*3 do
  126.                                 if not board[n][iPosGlobal[1]] and refTab[2][y][n - (y-1)*3] ~= 0 then   --(recurY-1)*3 +
  127.                                     table.insert(options, {iPosGlobal[1], n})  ---not sure
  128.                                 end
  129.                             end
  130.                             if #options > 0 then
  131.                                 local choice = options[math.random(1, #options)]
  132.                                 logBoard(board, iPosGlobal, choice)
  133.                                    
  134.                                 board[iPosGlobal[2]][iPosGlobal[1]] = nil
  135.                                 board[choice[2]][choice[1]] = i
  136.                                     log("Moving " .. iPosGlobal[1] .. ":" .. iPosGlobal[2] .. " to " .. choice[1] .. ":" .. choice[2])
  137.                                 refTab[2][math.ceil(choice[2]/3)][iPosLocal[2]] = 1
  138.                                 refTab[2][math.ceil(choice[2]/3)][(choice[2]-1)%3+1] = 0
  139.                                 xOff = xOff + 1
  140.                                 break;
  141.                             end
  142.                         end
  143.                     end
  144.                 end
  145.                 if #availableCells == 0 then
  146.                     availableCells = getAvailableCells(x, y, refTab, board)
  147.                     printBoard(board)
  148.                 end
  149.                 log(x .. "|" .. y .. "============ " .. #availableCells)
  150.                 for i, v in pairs (availableCells) do
  151.                     log(v[1] .. ":" .. v[2])
  152.                 end
  153.                 chosenCell = availableCells[math.random(1, #availableCells)]
  154.                 log(chosenCell[1] .. "," .. chosenCell[2] .. "\n")
  155.                 board[chosenCell[2] + (y-1)*3][chosenCell[1] + (x-1)*3] = i
  156.                 refTab[1][x][chosenCell[1]] = 0
  157.                 refTab[2][y][chosenCell[2]] = 0
  158.                     logBoard(board)
  159.             end
  160.         end
  161.     end
  162. end
  163.  
  164. function getAvailableCells(quadrantX, quadrantY, refTab, board)
  165.     local result = {}
  166.     for y, _ in pairs (refTab[2][quadrantY]) do
  167.         for x, _ in pairs (refTab[1][quadrantX]) do
  168.             if refTab[2][quadrantY][y] ~= 0 and refTab[1][quadrantX][x] ~= 0 and not board[y + (quadrantY-1)*3][x + (quadrantX-1)*3] then
  169.                 table.insert(result, {x, y})
  170.             end
  171.         end
  172.     end
  173.     return result
  174. end
  175.  
  176. function iLocate(i, quadrantX, quadrantY, board)
  177.     for y =  1, 3 do
  178.         for x = 1, 3 do
  179.             if board[y + (quadrantY-1)*3][x + (quadrantX-1)*3] == i then
  180.                 return {x, y}, {x + (quadrantX-1)*3, y + (quadrantY-1)*3}
  181.             end
  182.         end
  183.     end
  184.     printBoard(board)
  185.     error("iLocate Failed")
  186. end
  187. ----------------------------------------------SOLUTION
  188.  
  189. ----------------------------------------------ENGINE
  190. local tArgs = {...}
  191. term.setBackgroundColor(colors.black)
  192. term.setTextColor(colors.white)
  193. term.clear()
  194.  
  195. if tArgs[1] == "generate" or tArgs[1] == "gen" then
  196.     local board = {}
  197.     initializeBoard(board)
  198.     local ok = pcall(generatePuzzle(board))
  199.     local c = 1
  200.     while not ok do
  201.         initializeBoard(board)
  202.         --printBoard(board)
  203.         ok = pcall(generatePuzzle(board))
  204.         sleep(.1)
  205.         if c % 100 == 0 then
  206.             print(c)
  207.             sleep(.1)
  208.         end
  209.         c = c + 1
  210.     end
  211.     printBoard(board)
  212. elseif tArgs[1] == "solve" then
  213.    
  214. end
RAW Paste Data Copied