Advertisement
CaptainSpaceCat

Sudoku Diagnostics

Jun 22nd, 2016
165
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Lua 11.81 KB | None | 0 0
  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