Advertisement
CaptainSpaceCat

Sudoku 100% (pcall)

Jun 22nd, 2016
103
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. local w, h = term.getSize()
  7.  
  8. local debug = false
  9. local diagnostics = false
  10. --local handle = fs.open("console","a")
  11. function log(t)
  12. end
  13.  
  14. local chrono = 0
  15. function printBoard(board, num, str, override, lineTab, isoTab)
  16.     if (debug and num) or override then
  17.         for y = 1, 9 do
  18.             term.setCursorPos(1, y + math.ceil(y/3))
  19.             term.setBackgroundColor(colors.black)
  20.             term.setTextColor(colors.white)
  21.             write("|")
  22.             for x = 1, 9 do
  23.                 if tonumber(board[y][x]) then
  24.                     term.setTextColor(colors.lightBlue)
  25.                     write(board[y][x])
  26.                 elseif board[y][x][num] == 1 then
  27.                     term.setTextColor(colors.lime)
  28.                     write(num)
  29.                 else
  30.                     term.setTextColor(colors.lightGray)
  31.                     write("0")
  32.                 end
  33.                 if x == 3 or x == 6 then
  34.                     term.setTextColor(colors.white)
  35.                     write("|")
  36.                 end
  37.             end
  38.             term.setTextColor(colors.white)
  39.             write("|")
  40.         end
  41.         if lineTab then
  42.             for i = 1, #lineTab do
  43.                 term.setCursorPos(lineTab[i][1] + math.ceil(lineTab[i][1]/3), lineTab[i][2] + math.ceil(lineTab[i][2]/3))
  44.                 if lineTab[i][3] then
  45.                     term.setBackgroundColor(colors.red)
  46.                     if lineTab[i][4] == 1 then
  47.                         term.setTextColor(colors.black)
  48.                         write(num)
  49.                     elseif lineTab[i][5] then
  50.                         term.setTextColor(colors.white)
  51.                         write(lineTab[i][5])
  52.                     else
  53.                         term.setTextColor(colors.gray)
  54.                         write("0")
  55.                     end
  56.                 else
  57.                     term.setBackgroundColor(colors.black)
  58.                     if lineTab[i][4] == 1 then
  59.                         term.setTextColor(colors.yellow)
  60.                         write(num)
  61.                     elseif lineTab[i][5] then
  62.                         term.setTextColor(colors.lightBlue)
  63.                         write(lineTab[i][5])
  64.                     else
  65.                         term.setTextColor(colors.lightGray)
  66.                         write("0")
  67.                     end
  68.                 end
  69.             end
  70.         end
  71.         if isoTab then
  72.             for i = 2, #isoTab do
  73.                 term.setBackgroundColor(colors.orange)
  74.                 term.setCursorPos(isoTab[i][1] + math.ceil(isoTab[i][1]/3), isoTab[i][2] + math.ceil(isoTab[i][2]/3))
  75.                 if isoTab[i][3] == 1 then
  76.                     term.setTextColor(colors.black)
  77.                     write(num)
  78.                 elseif isoTab[i][4] then
  79.                     term.setTextColor(colors.white)
  80.                     write(isoTab[i][4])
  81.                 else
  82.                     term.setTextColor(colors.gray)
  83.                     write("0")
  84.                 end
  85.             end
  86.             term.setBackgroundColor(colors.green)
  87.             term.setTextColor(colors.lime)
  88.             term.setCursorPos(isoTab[1][1] + math.ceil(isoTab[1][1]/3), isoTab[1][2] + math.ceil(isoTab[1][2]/3))
  89.             write(num)
  90.         end
  91.         term.setBackgroundColor(colors.black)
  92.         term.setTextColor(colors.white)
  93.         term.setCursorPos(1, 1)
  94.         write("-------------")
  95.         term.setCursorPos(1, 5)
  96.         write("|---+---+---|")
  97.         term.setCursorPos(1, 9)
  98.         write("|---+---+---|")
  99.         term.setCursorPos(1, 13)
  100.         write("-------------")
  101.         term.setCursorPos(1, 14)
  102.     elseif not num then
  103.         for y = 1, 9 do
  104.             term.setCursorPos(1, y + math.ceil(y/3))
  105.             term.setTextColor(colors.white)
  106.             write("|")
  107.             for x = 1, 9 do
  108.                 term.setTextColor(colors.yellow)
  109.                 if tonumber(board[y][x]) then
  110.                     write(board[y][x])
  111.                 else write ("_") end
  112.                 if x == 3 or x == 6 then
  113.                     term.setTextColor(colors.white)
  114.                     write("|")
  115.                 end
  116.             end
  117.             term.setTextColor(colors.white)
  118.             write("|")
  119.         end
  120.         term.setCursorPos(1, 1)
  121.         write("-------------")
  122.         term.setCursorPos(1, 5)
  123.         write("|---+---+---|")
  124.         term.setCursorPos(1, 9)
  125.         write("|---+---+---|")
  126.         term.setCursorPos(1, 13)
  127.         write("-------------")
  128.         term.setCursorPos(1, 14)
  129.     end
  130.     if debug then
  131.         if str then
  132.             term.clearLine()
  133.             write(str)
  134.         end
  135.         os.pullEvent()
  136.     end
  137.     chrono = chrono + 1
  138.     if chrono >= 100 then
  139.         sleep(.005)
  140.         chrono = 0
  141.     end
  142. end
  143.  
  144. ----------------------------------------------GENERATION
  145. function initializeBoard(board)
  146.     for y = 1, 9 do
  147.         board[y] = {}
  148.         for x = 1, 9 do
  149.             board[y][x] = {1, 1, 1, 1, 1, 1, 1, 1, 1}
  150.         end
  151.     end
  152. end
  153.  
  154. function generatePuzzle(board)
  155.     local scanRef = {}
  156.     --log("-=-=-=-=-=-=-=-Starting Generation Algorithm-=-=-=-=-=-=-=-")
  157.     for n = 1, 9 do
  158.         --log("Filling in " .. n .. " --------------")
  159.         scanRef = {{1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1}}
  160.         for q = 1, 9 do
  161.             --log("Quadrant " .. q .. "...")
  162.             scanRef, changed = scanPatterns(board, q, n, scanRef)
  163.             --if debug and changed then
  164.             local logString = ""
  165.             for i = 1, 2 do
  166.                 for n = 1, 9 do
  167.                     logString = logString .. scanRef[i][n] .. ", "
  168.                 end
  169.                 logString = logString:sub(1, -3)
  170.                 logString = logString .. "\n"
  171.             end
  172.                 printBoard(board, n, "ScanRef:\n" .. logString)
  173.             --end
  174.             if scanRef[2][q] == 1 then
  175.                 local cells = getAvailableCells(board, q, n)
  176.                 local c = cells[math.random(1, #cells)]
  177.                 isolateNumber(board, c[1], c[2], n, " -=-random-=-")
  178.                 scanRef[2][q] = 0
  179.             end
  180.             --printBoard(board, n, "Reverting cycle...")
  181.             --log("Quadrant " .. q .. " isolated>>")
  182.         end
  183.     end
  184.     --finalizeBoard(board)
  185. end
  186.  
  187. function isolateNumber(board, x, y, num, comment)
  188.     comment = comment or ""
  189.     local logTab = {}
  190.     if debug then
  191.         table.insert(logTab, {x, y, 1})
  192.         for i = 1, 9 do
  193.             if not tonumber(board[i][x]) then table.insert(logTab, {x, i, board[i][x][num]}) else table.insert(logTab, {x, i, 0, board[i][x]}) end
  194.             if not tonumber(board[y][i]) then table.insert(logTab, {i, y, board[y][i][num]}) else table.insert(logTab, {i, y, 0, board[y][i]}) end
  195.             if not tonumber(board[(math.ceil(y/3)-1)*3+math.ceil(i/3)][(math.ceil(x/3)-1)*3+(i-1)%3+1]) then
  196.                 table.insert(logTab, {(math.ceil(x/3)-1)*3+(i-1)%3+1, (math.ceil(y/3)-1)*3+math.ceil(i/3), board[(math.ceil(y/3)-1)*3+math.ceil(i/3)][(math.ceil(x/3)-1)*3+(i-1)%3+1][num]})
  197.             else
  198.                 table.insert(logTab, {(math.ceil(x/3)-1)*3+(i-1)%3+1, (math.ceil(y/3)-1)*3+math.ceil(i/3), 0, board[(math.ceil(y/3)-1)*3+math.ceil(i/3)][(math.ceil(x/3)-1)*3+(i-1)%3+1]})
  199.             end
  200.         end
  201.     end
  202.     for i = 1, 9 do
  203.         if not tonumber(board[i][x]) then board[i][x][num] = 0 end--whole row
  204.         if not tonumber(board[y][i]) then board[y][i][num] = 0 end--whole column
  205.         if not tonumber(board[(math.ceil(y/3)-1)*3+math.ceil(i/3)][(math.ceil(x/3)-1)*3+(i-1)%3+1]) then
  206.             board[(math.ceil(y/3)-1)*3+math.ceil(i/3)][(math.ceil(x/3)-1)*3+(i-1)%3+1][num] = 0
  207.         end
  208.         --log("-->" .. (math.ceil(y/3)-1)*3+(i-1)%3+1 .. ":" .. (math.ceil(x/3)-1)*3+(i-1)%3+1)
  209.                              --whole box (holy crap! what a line of code!)
  210.     end
  211.     --for i = 1, 9 do
  212.     --  board[y][x][i] = 0
  213.     --end
  214.     board[y][x] = num
  215.     printBoard(board, num, "Isolated: " .. x .. ":" .. y .. comment, _, _, logTab)
  216. end
  217.  
  218. function scanPatterns(board, qStart, num, refTab)
  219.     local flag = true
  220.     local altered = false
  221.     while flag do
  222.         flag = false
  223.         for i = qStart, 9 do
  224.             local cells = getAvailableCells(board, i, num)
  225.             if #cells < 1 then
  226.                 --convertBoard(board)
  227.                 if not diagnostics then
  228.                     printBoard(board, num, _, true)
  229.                 end
  230.                 error("ERROR: No avilable places for number " .. num .. " in quadrant " .. i .. " ("..num..":"..i..")")
  231.             elseif #cells == 1 and refTab[2][i] == 1 then
  232.                 isolateNumber(board, cells[1][1], cells[1][2], num)
  233.                 refTab[2][i] = 0
  234.                 flag = true
  235.                 altered = true
  236.                 break;
  237.             elseif #cells > 1 and #cells <= 3 and refTab[1][i] == 1 then
  238.                 local detected, rays = detectLine(cells)
  239.                 if detected then
  240.                     refTab[1][i] = 0
  241.                     flag = true
  242.                     altered = true
  243.                     for _, v in ipairs(rays) do
  244.                         --log("Row?: " .. tostring(v[1]) .. " Slice:" .. v[2] .. "  | Q" .. i)
  245.                         eliminateLine(board, v[1], v[2], i, num)
  246.                     end
  247.                     break;
  248.                 end
  249.             end
  250.         end
  251.     end
  252.     return refTab, altered
  253. end
  254.  
  255. function detectLine(cells)
  256.     local xList = {}
  257.     local yList = {}
  258.     for i, v in ipairs(cells) do
  259.         table.insert(xList, v[1])
  260.         table.insert(yList, v[2])
  261.     end
  262.     local rays = {}
  263.     table.sort(xList)
  264.     table.sort(yList)
  265.     if xList[1] == xList[#xList] then
  266.         table.insert(rays, {false, xList[1]})
  267.     end
  268.     if yList[1] == yList[#yList] then
  269.         table.insert(rays, {true, yList[1]})
  270.     end
  271.     return #rays > 0, rays
  272. end
  273.  
  274. function eliminateLine(board, row, slice, homeQuadrant, num) --num: the current number
  275.     --int[][][]board: the board, boolean row: whether it is a row or a column
  276.     --int slice: row/col being altered, homeQuadrant: unnaffected quadrant
  277.     local logTab = {}
  278.     if row then
  279.         for i = 1, 9 do
  280.             if not tonumber(board[slice][i]) then                                                           -- or board[slice][i]
  281.                 table.insert(logTab, {i, slice, math.ceil(i/3) ~= (homeQuadrant-1)%3 + 1, board[slice][i][num]})
  282.                 if math.ceil(i/3) ~= (homeQuadrant-1)%3 + 1 then
  283.                     board[slice][i][num] = 0
  284.                 end
  285.             else
  286.                 table.insert(logTab, {i, slice, math.ceil(i/3) ~= (homeQuadrant-1)%3 + 1, 0, board[slice][i]})
  287.             end
  288.         end
  289.     else
  290.         for i = 1, 9 do
  291.             if not tonumber(board[i][slice]) then
  292.                 table.insert(logTab, {slice, i, math.ceil(i/3) ~= math.ceil(homeQuadrant/3), board[i][slice][num]})
  293.                 if math.ceil(i/3) ~= math.ceil(homeQuadrant/3) then
  294.                     board[i][slice][num] = 0
  295.                 end
  296.             else
  297.                 table.insert(logTab, {slice, i, math.ceil(i/3) ~= math.ceil(homeQuadrant/3), 0, board[i][slice]})
  298.             end
  299.         end
  300.     end
  301.     printBoard(board, num, "Line Eliminated: Q" .. homeQuadrant .. ", " .. tostring(row) .. ", " .. slice, _, logTab)
  302. end
  303.  
  304. function getAvailableCells(board, quadrant, num)
  305.     local result = {}
  306.     for y = (math.ceil(quadrant/3)-1)*3 + 1, (math.ceil(quadrant/3)-1)*3 + 3 do
  307.         for x = ((quadrant-1)%3)*3 + 1, ((quadrant-1)%3)*3 + 3 do
  308.             if board[y][x] == num or (not tonumber(board[y][x]) and board[y][x][num] == 1) then
  309.                 table.insert(result, {x, y})
  310.             end
  311.         end
  312.     end
  313.     return result
  314. end
  315.  
  316. ----------------------------------------------SOLUTION
  317.  
  318. ----------------------------------------------ENGINE
  319. local tArgs = {...}
  320. term.setBackgroundColor(colors.black)
  321. term.setTextColor(colors.white)
  322. term.clear()
  323.  
  324. local seed = math.random(1, 100000)
  325. math.randomseed(seed)
  326. log(seed)
  327.  
  328. if #tArgs == 0 then
  329.     term.setCursorPos(1, 1)
  330.     print("Usage: ".. shell.getRunningProgram() .." gen <view>")
  331.     print("adding <view> will show the process")
  332.     print("algorithm works about 40% of the time\n")
  333.     print("Usage: ".. shell.getRunningProgram() .." solve [puzzleFile] <view>")
  334.     print("input the sudoku puzzle file into puzzleFile")
  335.     print("adding <view> will show the process")
  336.     print("coming soon...\n")
  337.     print("Usage: ".. shell.getRunningProgram() .." test [g or s]")
  338.     print("Analyzes the current algorithm and compiles results")
  339.     print("g for generation, s for solution (WIP)")
  340. else
  341.     if tArgs[1] == "generate" or tArgs[1] == "gen" or tArgs[1] == "g" then
  342.         if tArgs[2] == "view" then debug = true end
  343.         local board = {}
  344.         diagnostics=true
  345.         initializeBoard(board)
  346.         if not debug then
  347.             local ok, err = pcall(generatePuzzle, board)
  348.             while not ok do
  349.                 initializeBoard(board)
  350.                 ok, err = pcall(generatePuzzle, board)
  351.                 printBoard(board)
  352.             end
  353.         else
  354.             generatePuzzle(board)
  355.             printBoard(board)
  356.         end
  357.     elseif tArgs[1] == "solve" or tArgs[1] == "s" then
  358.         if tArgs[3] == "view" then debug = true end
  359.     elseif tArgs[1] == "test" then
  360.         diagnostics = true
  361.         local board = {}
  362.         if tArgs[2] == "g" then
  363.             local s = 0
  364.             local f = 0
  365.             local errors = {}
  366.             for i = 1, 9 do
  367.                 errors[i] = 0
  368.             end
  369.             while f < 100 do
  370.                 initializeBoard(board)
  371.                 ok, err = pcall(generatePuzzle, board)
  372.                 if not ok then
  373.                     errors[tonumber(err:sub(#err-3, -4))] = errors[tonumber(err:sub(#err-3, -4))] + 1
  374.                     f = f + 1
  375.                     term.setCursorPos(1, h-1)
  376.                     term.setBackgroundColor(colors.black)
  377.                     term.clearLine()
  378.                     write("Generating errors...")
  379.                     term.setCursorPos(w-#tostring(f), h-1)
  380.                     write(f .. "%")
  381.                     term.setBackgroundColor(colors.red)
  382.                     term.setCursorPos(1, h)
  383.                     write(string.rep(" ", math.floor((f/100)*w)))
  384.                 else
  385.                     s = s + 1
  386.                 end
  387.             end
  388.             --printBoard(board)
  389.             term.setBackgroundColor(colors.black)
  390.             term.clear()
  391.             term.setCursorPos(1, 1)
  392.             print("Results:")
  393.             print("1  2  3  4  5  6  7  8  9")
  394.             print("-------------------------")
  395.             for i, v in ipairs(errors) do
  396.                 term.setCursorPos(3*(i-1) + 1, 4)
  397.                 write(v)
  398.             end
  399.             print("\n")
  400.             print("Puzzles generated: " .. s+f)
  401.             print("Success rate: " .. string.sub(tostring(s/(s+f)*100), 1, 5) .. "%")
  402.         elseif tArgs[2] == "s" then
  403.            
  404.         end
  405.     end
  406. end
Advertisement
RAW Paste Data Copied
Advertisement