Advertisement
CaptainSpaceCat

SudokuGen V3

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