Advertisement
CaptainSpaceCat

SudokuGen Alpha

Jun 21st, 2016
129
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 = true
  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. local chrono = 0
  62. function printBoard(board, num, str)
  63.     if debug and num then
  64.         for y = 1, 9 do
  65.             term.setCursorPos(1, y + math.ceil(y/3) - 1)
  66.             for x = 1, 9 do
  67.                 if board[y][x][num] == 1 then
  68.                     term.setTextColor(colors.red)
  69.                     write(num)
  70.                 else
  71.                     term.setTextColor(colors.white)
  72.                     write("0")
  73.                 end
  74.                 if x == 3 or x == 6 then
  75.                     write(" ")
  76.                 end
  77.             end
  78.         end
  79.         print("")
  80.     elseif not num then
  81.         for y = 1, 9 do
  82.             term.setCursorPos(1, y + math.ceil(y/3) - 1)
  83.             for x = 1, 9 do
  84.                 local c = 0
  85.                 for n = 1, 9 do
  86.                     if board[y][x][i] == 1 then
  87.                         if c ~= 0 then
  88.                             c = 0
  89.                             break;
  90.                         end
  91.                         c = i
  92.                     end
  93.                 end
  94.                 if c ~= 0 then
  95.                     term.setTextColor(colors.red)
  96.                     write(c)
  97.                 else
  98.                     term.setTextColor(colors.white)
  99.                     write("0")
  100.                 end
  101.                 if x == 3 or x == 6 then
  102.                     write(" ")
  103.                 end
  104.             end
  105.         end
  106.         print("")
  107.     end
  108.     if debug then
  109.         if str then
  110.             write(str)
  111.             print("                                      ")
  112.         end
  113.         os.pullEvent()
  114.     end
  115.     chrono = chrono + 1
  116.     if chrono >= 100 then
  117.         sleep(.005)
  118.         chrono = 0
  119.     end
  120. end
  121.  
  122. ----------------------------------------------GENERATION
  123. function initializeBoard(board)
  124.     for y = 1, 9 do
  125.         board[y] = {}
  126.         for x = 1, 9 do
  127.             board[y][x] = {1, 1, 1, 1, 1, 1, 1, 1, 1}
  128.         end
  129.     end
  130. end
  131.  
  132. function generatePuzzle(board)
  133.     log("-=-=-=-=-=-=-=-Starting Generation Algorithm-=-=-=-=-=-=-=-")
  134.     for n = 1, 9 do
  135.         log("Filling in " .. n .. " --------------")
  136.         local scanRef = {{1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1}}
  137.         for q = 1, 9 do
  138.             log("Quadrant " .. q .. "...")
  139.             scanRef = scanPatterns(board, n, scanRef)
  140.             printBoard(board, n, "Scanned")
  141.             local cells = getAvailableCells(board, q, n)
  142.             local c = cells[math.random(1, #cells)]
  143.             isolateNumber(board, c[1], c[2], n)
  144.             printBoard(board, n, "Isolated: " .. c[1] .. ":" .. c[2])
  145.             log("Quadrant " .. q .. " isolated>>")
  146.         end
  147.     end
  148.     finalizeBoard(board)
  149. end
  150.  
  151. function isolateNumber(board, x, y, num)
  152.     for i = 1, 9 do
  153.         board[i][x][num] = 0 --whole row
  154.         board[y][i][num] = 0 --whole column
  155.         board[(math.ceil(y/3)-1)*3+math.ceil(i/3)][(math.ceil(x/3)-1)*3+(i-1)%3+1][num] = 0
  156.         --log("-->" .. (math.ceil(y/3)-1)*3+(i-1)%3+1 .. ":" .. (math.ceil(x/3)-1)*3+(i-1)%3+1)
  157.                              --whole box (holy crap! what a line of code!)
  158.     end
  159.     for i = 1, 9 do
  160.         board[y][x][i] = 0
  161.     end
  162.     board[y][x][num] = 1
  163. end
  164.  
  165. function scanPatterns(board, num, refTab)
  166.     local flag = true
  167.     while flag do
  168.         flag = false
  169.         for i = 1, 9 do
  170.             local cells = getAvailableCells(board, i, num)
  171.             if #cells < 1 then
  172.                 --convertBoard(board)
  173.                 printBoard(board)
  174.                 error("ERROR: No avilable places for number " .. num .. " in quadrant " .. i)
  175.             elseif #cells == 1 and refTab[2][i] == 1 then
  176.                 isolateNumber(board, cells[1][1], cells[1][2], num)
  177.                 refTab[2][i] = 0
  178.                 flag = true
  179.                 break;
  180.             elseif #cells > 1 and #cells <= 3 and refTab[1][i] == 1 then
  181.                
  182.                     local rays = detectLine(cells)
  183.                     for _, v in ipairs(rays) do
  184.                         log("Row?: " .. tostring(v[1]) .. " Slice:" .. v[2] .. "  | Q" .. i)
  185.                         eliminateLine(board, v[1], v[2], i, num)
  186.                     end
  187.                 refTab[1][i] = 0
  188.                 flag = true
  189.                 break;
  190.             end
  191.         end
  192.     end
  193.     return refTab
  194. end
  195.  
  196. function getAvailableNum(board, quadrant, num)
  197.     local cells = {}
  198.     for i = 1, 3 do
  199.         for j = 1, 3 do
  200.             if board[(math.ceil(quadrant/3)-1)*3 + i][(quadrant-1)%3 + j][num] == 1 then
  201.                 table.insert(cells, {(quadrant-1)%3 + j, (math.ceil(quadrant/3)-1)*3 + i})
  202.             end
  203.         end
  204.     end
  205.     return cells
  206. end
  207.  
  208. function detectLine(cells)
  209.     local xList = {}
  210.     local yList = {}
  211.     for i, v in ipairs(cells) do
  212.         table.insert(xList, v[1])
  213.         table.insert(yList, v[2])
  214.     end
  215.     local rays = {}
  216.     table.sort(xList)
  217.     table.sort(yList)
  218.     if xList[1] == xList[#xList] then
  219.         table.insert(rays, {false, xList[1]})
  220.     end
  221.     if yList[1] == yList[#yList] then
  222.         table.insert(rays, {true, yList[1]})
  223.     end
  224.     return rays
  225. end
  226.  
  227. function eliminateLine(board, row, slice, homeQuadrant, num) --num: the current number
  228.     --int[][][]board: the board, boolean row: whether it is a row or a column
  229.     --int slice: row/col being altered, homeQuadrant: unnaffected quadrant
  230.     if row then
  231.         for i = 1, 9 do
  232.             if math.ceil(i/3) ~= (homeQuadrant-1)%3 + 1 then
  233.                 board[slice][i][num] = 0
  234.             end
  235.         end
  236.     else
  237.         for i = 1, 9 do
  238.             if math.ceil(i/3) ~= math.ceil(homeQuadrant/3) then
  239.                 board[i][slice][num] = 0
  240.             end
  241.         end
  242.     end
  243.     printBoard(board, num, "Line Eliminated: Q" .. homeQuadrant .. ", " .. tostring(row) .. ", " .. slice)
  244. end
  245.  
  246. function convertBoard(board)
  247.     for y = 1, 9 do
  248.         for x = 1, 9 do
  249.             local num = 0
  250.             for i = 1, 9 do
  251.                 if board[y][x][i] == 1 then
  252.                     if num ~= 0 then
  253.                         --error("ERROR: Multiple answers at " .. x .. ":" .. y)
  254.                         board[y][x] = 0
  255.                         break;
  256.                     else
  257.                         num = i
  258.                     end
  259.                 end
  260.             end
  261.             if num == 0 then
  262.                 --error("ERROR: No answers at " .. x .. ":" .. y)
  263.                 board[y][x] = {}
  264.             else
  265.                 board[y][x] = num
  266.             end
  267.         end
  268.     end
  269. end
  270.  
  271. function finalizeBoard(board)
  272.     for y = 1, 9 do
  273.         for x = 1, 9 do
  274.             local num = 0
  275.             for i = 1, 9 do
  276.                 if board[y][x][i] == 1 then
  277.                     if num ~= 0 then
  278.                         error("ERROR: Multiple answers at " .. x .. ":" .. y)
  279.                     end
  280.                     num = i
  281.                 end
  282.             end
  283.             if num == 0 then
  284.                 error("ERROR: No answers at " .. x .. ":" .. y)
  285.             end
  286.             board[y][x] = num
  287.         end
  288.     end
  289. end
  290.  
  291. function getAvailableCells(board, quadrant, num)
  292.     local result = {}
  293.     for y = (math.ceil(quadrant/3)-1)*3 + 1, (math.ceil(quadrant/3)-1)*3 + 3 do
  294.         for x = ((quadrant-1)%3)*3 + 1, ((quadrant-1)%3)*3 + 3 do
  295.             if board[y][x][num] == 1 then
  296.                 table.insert(result, {x, y})
  297.             end
  298.         end
  299.     end
  300.     return result
  301. end
  302.  
  303. function iLocate(i, quadrantX, quadrantY, board)
  304.     for y =  1, 3 do
  305.         for x = 1, 3 do
  306.             if board[y + (quadrantY-1)*3][x + (quadrantX-1)*3] == i then
  307.                 return {x, y}, {x + (quadrantX-1)*3, y + (quadrantY-1)*3}
  308.             end
  309.         end
  310.     end
  311.     printBoard(board)
  312.     error("iLocate Failed")
  313. end
  314. ----------------------------------------------SOLUTION
  315.  
  316. ----------------------------------------------ENGINE
  317. local tArgs = {...}
  318. term.setBackgroundColor(colors.black)
  319. term.setTextColor(colors.white)
  320. term.clear()
  321.  
  322. if tArgs[1] == "generate" or tArgs[1] == "gen" then
  323.     local board = {}
  324.     initializeBoard(board)
  325.     generatePuzzle(board)
  326.     printBoard(board)
  327. elseif tArgs[1] == "solve" then
  328.    
  329. end
Advertisement
RAW Paste Data Copied
Advertisement