sudoku


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Sudoku solver implementation
-- Uses Backtracking and recursion
-- See : http://en.wikipedia.org/wiki/Sudoku

-- Checks if num exists on a row
local function rowHasNotNum(sudoku, row, num)
  for column = 1,9 do
    if sudoku[row][column] == num then
      return false
    end
  end
  return true
end

-- Checks if num exists on a column
local function columnHasNotNum(sudoku, column, num)
  for row = 1,9 do
    if sudoku[row][column] == num then return false end
  end
  return true
end

-- Given a (row, column) location on the sudoku grid
-- identifies the corresponding 3x3 box and checks if
-- num exists in this box
local function boxHasNotNum(sudoku, row, column, num)
  row = math.floor((row - 1) / 3) * 3 + 1
  column = math.floor((column - 1) / 3) * 3 + 1
  for rwOffset = 0, 2 do
    for clOffset = 0, 2 do
      if sudoku[row + rwOffset][column + clOffset] == num then
        return false
      end
    end
  end
  return true
end

-- Checks if num can be assigned to sudoku[row][column]
-- without breaking sudoku rules.
local function isLegit(sudoku, row, column, num)
  return rowHasNotNum(sudoku, row, num)
    and columnHasNotNum(sudoku, column, num)
    and boxHasNotNum(sudoku, row, column, num)
end


-- Checks if the actual problem is solved.
-- If not, returns false, plus the location on the
-- first unassigned cell found.
local function isSolved(sudoku)
  for row = 1, 9 do
    for column = 1, 9 do
      if sudoku[row][column] == 0 then
        return false, row, column
      end
    end
  end
  return true
end

-- Sudoku solving via backtracking and recursion
-- sudoku  : a 2-dimensional grid of numbers (0-9)
--           0 matches unknown values to be found.
-- returns : true, if a solution was found,
--           false otherwise.
local function solve(sudoku)
  local solved, row, column = isSolved(sudoku)
  if solved then return true end
  for num = 1, 9 do
    if isLegit(sudoku, row, column, num) then
      sudoku[row][column] = num
      if solve(sudoku) then return true end
      sudoku[row][column] = 0
    end
  end
  return false
end

return solve



-- Tests for sudoku.lua
local sudoku_solve = require 'sudoku'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

-- Checks if t1 and t2 arrays are the same
local function same(t1, t2)
  if #t1 ~= #t2 then return false end
  for r, row in ipairs(t1) do
    for v, value in ipairs(row) do
      if t2[r][v] ~= value then return false end
    end
  end
  return true
end

run('An easy problem', function()
  local problem = {
    {3, 0, 6, 5, 0, 8, 4, 0, 0},
    {5, 2, 0, 0, 0, 0, 0, 0, 0},
    {0, 8, 7, 0, 0, 0, 0, 3, 1},
    {0, 0, 3, 0, 1, 0, 0, 8, 0},
    {9, 0, 0, 8, 6, 3, 0, 0, 5},
    {0, 5, 0, 0, 9, 0, 6, 0, 0},
    {1, 3, 0, 0, 0, 0, 2, 5, 0},
    {0, 0, 0, 0, 0, 0, 0, 7, 4},
    {0, 0, 5, 2, 0, 6, 3, 0, 0},
  }

  local solution = {
    {3, 1, 6, 5, 7, 8, 4, 9, 2},
    {5, 2, 9, 1, 3, 4, 7, 6, 8},
    {4, 8, 7, 6, 2, 9, 5, 3, 1},
    {2, 6, 3, 4, 1, 5, 9, 8, 7},
    {9, 7, 4, 8, 6, 3, 1, 2, 5},
    {8, 5, 1, 7, 9, 2, 6, 4, 3},
    {1, 3, 8, 9, 4, 7, 2, 5, 6},
    {6, 9, 2, 3, 5, 1, 8, 7, 4},
    {7, 4, 5, 2, 8, 6, 3, 1, 9},
  }
  sudoku_solve(problem)
  assert(same(problem, solution))
end)

run('A harder problem', function()
  local problem = {
    {9, 0, 0, 1, 0, 0, 0, 0, 5},
    {0, 0, 5, 0, 9, 0, 2, 0, 1},
    {8, 0, 0, 0, 4, 0, 0, 0, 0},
    {0, 0, 0, 0, 8, 0, 0, 0, 0},
    {0, 0, 0, 7, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 2, 6, 0, 0, 9},
    {2, 0, 0, 3, 0, 0, 0, 0, 6},
    {0, 0, 0, 2, 0, 0, 9, 0, 0},
    {0, 0, 1, 9, 0, 4, 5, 7, 0},
  }

  local solution = {
    {9, 3, 4, 1, 7, 2, 6, 8, 5},
    {7, 6, 5, 8, 9, 3, 2, 4, 1},
    {8, 1, 2, 6, 4, 5, 3, 9, 7},
    {4, 2, 9, 5, 8, 1, 7, 6, 3},
    {6, 5, 8, 7, 3, 9, 1, 2, 4},
    {1, 7, 3, 4, 2, 6, 8, 5, 9},
    {2, 9, 7, 3, 5, 8, 4, 1, 6},
    {5, 4, 6, 2, 1, 7, 9, 3, 8},
    {3, 8, 1, 9, 6, 4, 5, 7, 2},
  }
  sudoku_solve(problem)
  assert(same(problem, solution))
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))