Sudoku solver in lua

This is traditional backtracking: Try all possibilities, but give up the moment it is obviously wrong.

The board is in literals inside the program.

But a bad choice to have it as an array of strings, since strings are immutable. So I made the bchange-function to construct a new string, with a new value in one the characters. It is inefficient, but it works.

Note that in lua, you have to write local to make local variables. The variables c1 and r1 in tryit has to be local — otherwise it won't work.

Arrays mostly start in 1 in lua, so that's what we do.

sudoku1.lua

board = { '29..4.8..',
          '....9.2.1',
          '...7...3.',
          '...6..72.',
          '4.1...6.8',
          '.52..4...',
          '.6...7...',
          '7.5.6....',
          '..9.8..76'
        }

function b(x,y)
  return string.sub(board[x],y,y)
end

function bchange(x,y,val)
  board[x] = string.sub(board[x],1,y-1) .. val .. 
             string.sub(board[x],y+1,9)
end

function okrow(r,val)
  for i=1,9 do
    if b(r,i) == val then
      return false;
    end
  end
  return true
end

function okcol(c,val)
  for i=1,9 do
    if b(i,c) == val then
      return false
    end
  end
  return true
end

corner = {1,1,1,4,4,4,7,7,7}   -- created only once
function oksquare(r,c,val)
  local top = corner[r]
  local left = corner[c]
  for i=left,left+2 do
    for j=top,top+2 do
      if b(j,i) == val then
        return false
      end
    end
  end
  return true
end

function printboard()
    for x=1,9 do
      for y=1,9 do
        io.write(b(x,y))
        if y % 3 == 0 then
          io.write(" ")
        end
      end
      io.write("\n")
      if x % 3 == 0 then
        io.write('\n')
      end
   end
 end

function tryit(r,c)
  local c1 = 0
  local r1 = 0
  if r>=10 then
      print('Solution')
      printboard();
  else
    if c==9 then
       c1 = 1
       r1 = r+1
    else
       c1 = c+1
       r1= r
    end
    if b(r,c)=='.' then

      for _,val in pairs({'1','2','3','4','5','6','7','8','9'}) do
        if okrow(r,val) and
          okcol(c,val) and
          oksquare(r,c,val) then
            bchange(r,c,val)
            tryit(r1,c1)
            bchange(r,c,'.')
        end
      end
    else
      tryit(r1,c1)
    end
  end
end

printboard()

tryit(1,1)

sudoku2.lua

But as I said: bchange is not pretty. I'd like to keep the array of strings, but convert it to a 2-dimensional array of byte. Bytes are mutable. This is done in the function convert. A 2-dimensional array must be adressed with double brackets: b[x][y].

board = { '29..4.8..',
          '....9.2.1',
          '...7...3.',
          '...6..72.',
          '4.1...6.8',
          '.52..4...',
          '.6...7...',
          '7.5.6....',
          '..9.8..76'
        }

b = { }

function convert()
  for x=1,9 do
    b[x] = {}
    for y=1,9 do
      b[x][y] = string.sub(board[x],y,y)
    end
  end
end

convert()

function okrow(r,val)
  for i=1,9 do
    if b[r][i] == val then
      return false;
    end
  end
  return true
end

function okcol(c,val)
  for i=1,9 do
    if b[i][c] == val then
      return false
    end
  end
  return true
end

corner = {1,1,1,4,4,4,7,7,7}   -- created once
function oksquare(r,c,val)
  local top = corner[r]
  local left = corner[c]
  for i=left,left+2 do
    for j=top,top+2 do
      if b[j][i] == val then
        return false
      end
    end
  end
  return true
end

function printboard()
    for x=1,9 do
      for y=1,9 do
        io.write(b[x][y])
        if y % 3 == 0 then
          io.write(" ")
        end
      end
      io.write("\n")
      if x % 3 == 0 then
        io.write('\n')
      end
   end
 end

function tryit(r,c)
  local c1 = 0
  local r1 = 0
  if r>=10 then
      print('Solution')
      printboard();
  else
    if c==9 then
       c1 = 1
       r1 = r+1
    else
       c1 = c+1
       r1= r
    end
    if b[r][c]=='.' then
      for _,val in pairs({'1','2','3','4','5','6','7','8','9'}) do
        if okrow(r,val) and
          okcol(c,val) and
          oksquare(r,c,val) then
            b[r][c]=val
            tryit(r1,c1)
            b[r][c]='.'
          end
      end
    else
      tryit(r1,c1)
    end
  end
end

printboard()

tryit(1,1)

Speed?

So is this faster? Yes it is.

Times for sudoku1.lua:

real    0m0.040s
user    0m0.036s
sys     0m0.004s

Times for sudoku2.lua:

real    0m0.012s
user    0m0.010s
sys     0m0.002s