Sample Sudoku Generator v1.0

--[[ Sample Sudoku generator code v1.0 . Made by Orwell. ]]--

local Attempts = {}
Attempts.__index = Attempts

--[[ Creates an instance of Attempts.
  Attemps will keep track of attempted numbers for each square and
  supplies random numbers for them on each call to getNextNumber. ]]--
function Attempts.create()
  math.randomseed(os.time()*1000)  -- set the time in milliseconds as seed for the RNG
  local attempts = {}
  setmetatable(attempts, Attempts)
  return attempts
end

--[[ Resets the array of attempted number for the square at given index. ]]--
function Attempts.clear(self, index)
  self[index] = {}
end

--[[ Returns an unattempted random number for the square at given index.
  It will return nil when all numbers have been tried. ]]--
function Attempts.getNextNumber(self, index)
  if not self[index] then  -- initialize the array at this index if it doesn't exist yet
    self[index] = {}
  end

  if self:isExhausted(index) then  -- return nil if there is no number left
    return
  end

  local nextNumber
  repeat
    nextNumber = math.random(1,9)
  until not self[index][nextNumber]  -- grab random numbers until we get an unused one

  self[index][nextNumber] = true  -- set the number to used
  return nextNumber
end

--[[ Returns true if all numbers have been tried for the square at given index. ]]--
function Attempts.isExhausted(self, index)
  return #self[index] == 9  -- if all keys from 1 to 9 have 'true' as value, the 'length' of it will be 9
end

local Sudoku = {}
Sudoku.__index = Sudoku

--[[ Sets the square at x,y to value. ]]--
function Sudoku.setSquare(sudoku, x, y, value)
  sudoku[x][y] = value
end

--[[ Sets the square at x,y to nil. ]]--
function Sudoku.resetSquare(sudoku, x, y)
  sudoku[x][y] = nil
end

--[[ Returns true if this square contains given value. ]]--
function Sudoku.checkSquare(sudoku, x, y, value)
  return sudoku[x][y] and sudoku[x][y] == value
end

--[[ Returns true if this column contains given value. ]]--
function Sudoku.checkColumn(sudoku, x, value)
  local occupied = false
  for y=1,9 do
    occupied = occupied or sudoku:checkSquare(x, y, value)
  end
  return occupied
end

--[[ Return true if this row contains given value. ]]--
function Sudoku.checkRow(sudoku, y, value)
  local occupied = false
  for x=1,9 do
    occupied = occupied or sudoku:checkSquare(x, y, value)
  end
  return occupied
end

--[[ Returns true if this region contains given value. ]]--
function Sudoku.checkRegion(sudoku, x, y, value)
  local occupied = false
  local X = math.floor((x-1)/3)*3
  local Y = math.floor((y-1)/3)*3
  for i = X+1,X+3 do
    for j = Y+1,Y+3 do
      occupied = occupied or sudoku:checkSquare(i, j, value)
    end
  end
  return occupied
end

--[[ Returns true if the spot at x,y can have specified value. ]]--
function Sudoku.isValid(sudoku, x, y, value)
  return not ( sudoku:checkColumn(x, value) or sudoku:checkRow(y, value) or sudoku:checkRegion(x, y, value) )
end

--[[ Creates a Sudoku object; it's basically a table of tables with the Sudoku metatable set. ]]--
function Sudoku.generateBlank()
  local sudoku = {}
  setmetatable(sudoku, Sudoku)
  for i = 1,9 do
    sudoku[i]={}
  end
  return sudoku
end

--[[ Set text color if possible. ]]--
local function setColor(color)
  if term.isColor and term.isColor() then
    term.setTextColor(color)
  end
end

--[[ Prints the sudoku to the screen in a typical table-style. ]]--
function Sudoku.print(sudoku)
  setColor(colors.white)
  write("+-----+-----+-----+\n")
  setColor(colors.red)
  for y=1,9 do
    setColor(colors.white)
    write("|")
    setColor(colors.red)
    for x=1,9 do
      local num = sudoku[x][y]
      write(num and string.format("%d",num) or " ")
      setColor(colors.white)
      write(x%3==0 and "|" or " ")
      setColor(colors.red)
    end
    write("\n")
    if y%3==0 then
      setColor(colors.white)
      write("+-----+-----+-----+\n")
      setColor(colors.red)
    end
  end
  setColor(colors.white)
end

--[[ Generates a random valid sudoku. ]]--
function Sudoku.generate()
  local sudoku = Sudoku.generateBlank()  -- generate an empty sudoku matrix

  local attempts = Attempts.create()  -- generate a new instance of Attempts

  local sleepCount = 0
  local index = 1  -- the index of the square we are at during calculations
  while index <= 81 do  -- repeat until we reached the last square
    local x = (index-1)%9+1  -- calculate x out of the index
    local y = math.floor((index-1)/9)+1  -- calculate y out of the index
    local nextNumber = attempts:getNextNumber(index)  -- get the next random number for current index
    if not nextNumber then  -- if there is no next number, then backtrack!
      attempts:clear(index)  -- reset the attempted numbers for current index
      sudoku:resetSquare(x,y)  -- reset the square we temporarily set
      index = index-1  -- go back one square
    elseif sudoku:isValid(x, y, nextNumber) then  -- else, if this is a valid number for the square at index, set it
      sudoku:setSquare(x, y, nextNumber)
      index = index+1  -- proceed to the next square
    end  -- if there were numbers left and this wasn't a valid number, we will stay at the same index and try a new number on the next iteration
    sleepCount = sleepCount+1
    if sleepCount%10000==0 then  -- yield once every 10000 calculations
      sleep(0)
    end
  end
  return sudoku
end

--[[ Only usefull if this file is being used as API. The Sudoku metatable
  isn't public. ]]--
function generateSudoku()
  return Sudoku.generate()
end

local sudoku = Sudoku.generate()
sudoku:print()