API tools faq
paste
Advertisement
CaptainSpaceCat

Sudoku Diagnostics

CaptainSpaceCat
Jun 22nd, 2016
150
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Lua 11.81 KB | None | 0 0
raw download clone embed print report
  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.                 write(board[y][x])
  110.                 if x == 3 or x == 6 then
  111.                     term.setTextColor(colors.white)
  112.                     write("|")
  113.                 end
  114.             end
  115.             term.setTextColor(colors.white)
  116.             write("|")
  117.         end
  118.         term.setCursorPos(1, 1)
  119.         write("-------------")
  120.         term.setCursorPos(1, 5)
  121.         write("|---+---+---|")
  122.         term.setCursorPos(1, 9)
  123.         write("|---+---+---|")
  124.         term.setCursorPos(1, 13)
  125.         write("-------------")
  126.         term.setCursorPos(1, 14)
  127.     end
  128.     if debug then
  129.         if str then
  130.             term.clearLine()
  131.             write(str)
  132.         end
  133.         os.pullEvent()
  134.     end
  135.     chrono = chrono + 1
  136.     if chrono >= 100 then
  137.         sleep(.005)
  138.         chrono = 0
  139.     end
  140. end
  141.  
  142. ----------------------------------------------GENERATION
  143. function initializeBoard(board)
  144.     for y = 1, 9 do
  145.         board[y] = {}
  146.         for x = 1, 9 do
  147.             board[y][x] = {1, 1, 1, 1, 1, 1, 1, 1, 1}
  148.         end
  149.     end
  150. end
  151.  
  152. function generatePuzzle(board)
  153.     local scanRef = {}
  154.     --log("-=-=-=-=-=-=-=-Starting Generation Algorithm-=-=-=-=-=-=-=-")
  155.     for n = 1, 9 do
  156.         --log("Filling in " .. n .. " --------------")
  157.         scanRef = {{1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1}}
  158.         for q = 1, 9 do
  159.             --log("Quadrant " .. q .. "...")
  160.             scanRef, changed = scanPatterns(board, q, n, scanRef)
  161.             --if debug and changed then
  162.             local logString = ""
  163.             for i = 1, 2 do
  164.                 for n = 1, 9 do
  165.                     logString = logString .. scanRef[i][n] .. ", "
  166.                 end
  167.                 logString = logString:sub(1, -3)
  168.                 logString = logString .. "\n"
  169.             end
  170.                 printBoard(board, n, "ScanRef:\n" .. logString)
  171.             --end
  172.             if scanRef[2][q] == 1 then
  173.                 local cells = getAvailableCells(board, q, n)
  174.                 local c = cells[math.random(1, #cells)]
  175.                 isolateNumber(board, c[1], c[2], n, " -=-random-=-")
  176.                 scanRef[2][q] = 0
  177.             end
  178.             --printBoard(board, n, "Reverting cycle...")
  179.             --log("Quadrant " .. q .. " isolated>>")
  180.         end
  181.     end
  182.     --finalizeBoard(board)
  183. end
  184.  
  185. function isolateNumber(board, x, y, num, comment)
  186.     comment = comment or ""
  187.     local logTab = {}
  188.     if debug then
  189.         table.insert(logTab, {x, y, 1})
  190.         for i = 1, 9 do
  191.             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
  192.             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
  193.             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
  194.                 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]})
  195.             else
  196.                 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]})
  197.             end
  198.         end
  199.     end
  200.     for i = 1, 9 do
  201.         if not tonumber(board[i][x]) then board[i][x][num] = 0 end--whole row
  202.         if not tonumber(board[y][i]) then board[y][i][num] = 0 end--whole column
  203.         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
  204.             board[(math.ceil(y/3)-1)*3+math.ceil(i/3)][(math.ceil(x/3)-1)*3+(i-1)%3+1][num] = 0
  205.         end
  206.         --log("-->" .. (math.ceil(y/3)-1)*3+(i-1)%3+1 .. ":" .. (math.ceil(x/3)-1)*3+(i-1)%3+1)
  207.                              --whole box (holy crap! what a line of code!)
  208.     end
  209.     --for i = 1, 9 do
  210.     --  board[y][x][i] = 0
  211.     --end
  212.     board[y][x] = num
  213.     printBoard(board, num, "Isolated: " .. x .. ":" .. y .. comment, _, _, logTab)
  214. end
  215.  
  216. function scanPatterns(board, qStart, num, refTab)
  217.     local flag = true
  218.     local altered = false
  219.     while flag do
  220.         flag = false
  221.         for i = qStart, 9 do
  222.             local cells = getAvailableCells(board, i, num)
  223.             if #cells < 1 then
  224.                 --convertBoard(board)
  225.                 if not diagnostics then
  226.                     printBoard(board, num, _, true)
  227.                 end
  228.                 error("ERROR: No avilable places for number " .. num .. " in quadrant " .. i .. " ("..num..":"..i..")")
  229.             elseif #cells == 1 and refTab[2][i] == 1 then
  230.                 isolateNumber(board, cells[1][1], cells[1][2], num)
  231.                 refTab[2][i] = 0
  232.                 flag = true
  233.                 altered = true
  234.                 break;
  235.             elseif #cells > 1 and #cells <= 3 and refTab[1][i] == 1 then
  236.                 local detected, rays = detectLine(cells)
  237.                 if detected then
  238.                     refTab[1][i] = 0
  239.                     flag = true
  240.                     altered = true
  241.                     for _, v in ipairs(rays) do
  242.                         --log("Row?: " .. tostring(v[1]) .. " Slice:" .. v[2] .. "  | Q" .. i)
  243.                         eliminateLine(board, v[1], v[2], i, num)
  244.                     end
  245.                     break;
  246.                 end
  247.             end
  248.         end
  249.     end
  250.     return refTab, altered
  251. end
  252.  
  253. function detectLine(cells)
  254.     local xList = {}
  255.     local yList = {}
  256.     for i, v in ipairs(cells) do
  257.         table.insert(xList, v[1])
  258.         table.insert(yList, v[2])
  259.     end
  260.     local rays = {}
  261.     table.sort(xList)
  262.     table.sort(yList)
  263.     if xList[1] == xList[#xList] then
  264.         table.insert(rays, {false, xList[1]})
  265.     end
  266.     if yList[1] == yList[#yList] then
  267.         table.insert(rays, {true, yList[1]})
  268.     end
  269.     return #rays > 0, rays
  270. end
  271.  
  272. function eliminateLine(board, row, slice, homeQuadrant, num) --num: the current number
  273.     --int[][][]board: the board, boolean row: whether it is a row or a column
  274.     --int slice: row/col being altered, homeQuadrant: unnaffected quadrant
  275.     local logTab = {}
  276.     if row then
  277.         for i = 1, 9 do
  278.             if not tonumber(board[slice][i]) then                                                           -- or board[slice][i]
  279.                 table.insert(logTab, {i, slice, math.ceil(i/3) ~= (homeQuadrant-1)%3 + 1, board[slice][i][num]})
  280.                 if math.ceil(i/3) ~= (homeQuadrant-1)%3 + 1 then
  281.                     board[slice][i][num] = 0
  282.                 end
  283.             else
  284.                 table.insert(logTab, {i, slice, math.ceil(i/3) ~= (homeQuadrant-1)%3 + 1, 0, board[slice][i]})
  285.             end
  286.         end
  287.     else
  288.         for i = 1, 9 do
  289.             if not tonumber(board[i][slice]) then
  290.                 table.insert(logTab, {slice, i, math.ceil(i/3) ~= math.ceil(homeQuadrant/3), board[i][slice][num]})
  291.                 if math.ceil(i/3) ~= math.ceil(homeQuadrant/3) then
  292.                     board[i][slice][num] = 0
  293.                 end
  294.             else
  295.                 table.insert(logTab, {slice, i, math.ceil(i/3) ~= math.ceil(homeQuadrant/3), 0, board[i][slice]})
  296.             end
  297.         end
  298.     end
  299.     printBoard(board, num, "Line Eliminated: Q" .. homeQuadrant .. ", " .. tostring(row) .. ", " .. slice, _, logTab)
  300. end
  301.  
  302. function getAvailableCells(board, quadrant, num)
  303.     local result = {}
  304.     for y = (math.ceil(quadrant/3)-1)*3 + 1, (math.ceil(quadrant/3)-1)*3 + 3 do
  305.         for x = ((quadrant-1)%3)*3 + 1, ((quadrant-1)%3)*3 + 3 do
  306.             if board[y][x] == num or (not tonumber(board[y][x]) and board[y][x][num] == 1) then
  307.                 table.insert(result, {x, y})
  308.             end
  309.         end
  310.     end
  311.     return result
  312. end
  313.  
  314. ----------------------------------------------SOLUTION
  315.  
  316. ----------------------------------------------ENGINE
  317. local tArgs = {...}
  318. term.setBackgroundColor(colors.black)
  319. term.setTextColor(colors.white)
  320. term.clear()
  321.  
  322. local seed = math.random(1, 100000)
  323. math.randomseed(seed)
  324. log(seed)
  325.  
  326. if #tArgs == 0 then
  327.     term.setCursorPos(1, 1)
  328.     print("Usage: ".. shell.getRunningProgram() .." gen <view>")
  329.     print("adding <view> will show the process")
  330.     print("algorithm works about 40% of the time\n")
  331.     print("Usage: ".. shell.getRunningProgram() .." solve [puzzleFile] <view>")
  332.     print("input the sudoku puzzle file into puzzleFile")
  333.     print("adding <view> will show the process")
  334.     print("coming soon...\n")
  335.     print("Usage: ".. shell.getRunningProgram() .." test [g or s]")
  336.     print("Analyzes the current algorithm and compiles results")
  337.     print("g for generation, s for solution (WIP)")
  338. else
  339.     if tArgs[1] == "generate" or tArgs[1] == "gen" or tArgs[1] == "g" then
  340.         if tArgs[2] == "view" then debug = true end
  341.         local board = {}
  342.         initializeBoard(board)
  343.         generatePuzzle(board)
  344.         printBoard(board)
  345.     elseif tArgs[1] == "solve" or tArgs[1] == "s" then
  346.         if tArgs[3] == "view" then debug = true end
  347.     elseif tArgs[1] == "test" then
  348.         diagnostics = true
  349.         local board = {}
  350.         if tArgs[2] == "g" then
  351.             local s = 0
  352.             local f = 0
  353.             local errors = {}
  354.             for i = 1, 9 do
  355.                 errors[i] = 0
  356.             end
  357.             while f < 100 do
  358.                 initializeBoard(board)
  359.                 ok, err = pcall(generatePuzzle, board)
  360.                 if not ok then
  361.                     errors[tonumber(err:sub(#err-3, -4))] = errors[tonumber(err:sub(#err-3, -4))] + 1
  362.                     f = f + 1
  363.                     term.setCursorPos(1, h-1)
  364.                     term.setBackgroundColor(colors.black)
  365.                     term.clearLine()
  366.                     write("Generating errors...")
  367.                     term.setCursorPos(w-#tostring(f), h-1)
  368.                     write(f .. "%")
  369.                     term.setBackgroundColor(colors.red)
  370.                     term.setCursorPos(1, h)
  371.                     write(string.rep(" ", math.floor((f/100)*w)))
  372.                 else
  373.                     s = s + 1
  374.                 end
  375.             end
  376.             --printBoard(board)
  377.             term.setBackgroundColor(colors.black)
  378.             term.clear()
  379.             term.setCursorPos(1, 1)
  380.             print("Results:")
  381.             print("1  2  3  4  5  6  7  8  9")
  382.             print("-------------------------")
  383.             for i, v in ipairs(errors) do
  384.                 term.setCursorPos(3*(i-1) + 1, 4)
  385.                 write(v)
  386.             end
  387.             print("\n")
  388.             print("Puzzles generated: " .. s+f)
  389.             print("Success rate: " .. string.sub(tostring(s/(s+f)*100), 1, 5) .. "%")
  390.         elseif tArgs[2] == "s" then
  391.            
  392.         end
  393.     end
  394. end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!