randomfox (randomfox) wrote,
randomfox
randomfox

Sudoku puzzle solver in Lua


#!lua

--[[
Sudoku solver.
Last updated: December 5, 2005

This is a puzzle where you have to fill all the blank spaces with digits
from 1 to 9 such that no row, column, or 3x3 block of cells have any
digits repeated.

Supply the puzzle via standard input or via a file whose file name is
given as the first command line argument. Example input:

    8xx 69x xx2
    91x xxx xxx
    5xx xx8 xx7

    xxx 2x9 xx6
    xxx 8xx xx3
    2xx 3x4 xxx

    3xx 78x xx9
    xxx xxx xx5
    4xx x5x x28
]]

function readboard()
    local board = {}
    local lineno = 0
    for line in io.lines() do
	line = string.gsub(line, "%s+", "")
	if string.len(line) > 0 then
	    if string.len(line) < 9 then
		error("line " .. lineno .. " '" .. line .. "' is too short.")
	    end
	    local row = {}
	    for i = 1,9 do
		row[i] = tonumber(string.sub(line, i, i)) or 0
	    end
	    lineno = lineno + 1
	    board[lineno] = row
	end
    end
    if lineno < 9 then
	error("not enough rows. only " .. lineno .. " found.")
    end
    return board
end

function printboard(board)
    for i = 1,9 do
	print(table.concat(board[i], " "))
    end
end

function getpossible(board, row, col)
    local used = {}
    for i = 1,9 do
	used[board[row][i]] = true
	used[board[i][col]] = true
    end

    local blockrow = row - math.mod(row - 1, 3);
    local blockcol = col - math.mod(col - 1, 3);
    for i = blockrow, blockrow + 2 do
	for j = blockcol, blockcol + 2 do
	    used[board[i][j]] = true
	end
    end

    local i = 0
    return function()
	while i < 9 do
	    i = i + 1
	    if not used[i] then return i end
	end
    end
end

function tryboard(board, row, col)
    local nodecount = 0

    local function tryboard2(board, row, col)
	if row > 9 or col > 9 then
	    print "Success"
	    printboard(board)
	    print(nodecount .. " nodes examined")
	    return true
	end

	nodecount = nodecount + 1

	local nextrow = row
	local nextcol = col + 1
	if nextcol > 9 then
	    nextrow = row + 1
	    nextcol = 1
	end

	if board[row][col] ~= 0 then
	    return tryboard2(board, nextrow, nextcol)
	end

	for cell in getpossible(board, row, col) do
	    board[row][col] = cell
	    if tryboard2(board, nextrow, nextcol) then
		return true
	    end
	end
	board[row][col] = 0
    end

    tryboard2(board, row, col)
end

if arg[1] then
    io.input(arg[1])
end
tryboard(readboard(), 1, 1)

Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments