sudoku.lua

game = {
	{0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 0}
}
x = 5
y = 5
LOOPS = 0

if arg then
	for _,s in pairs(arg) do
		if #s == 81 and tonumber(s) then
			s = arg[1]
			for n=1,81 do
				local num,i,inn = n/9,0,tonumber(s:sub(n,n))
				if inn ~= 0 then
				if math.floor(num) == math.ceil(num) then
					i = num-1
				else
					i = math.floor(num)
				end
				--print((n-i*9)..","..(i+1)..": "..inn)
				game[i+1][n-i*9] = inn
			end end
			AUTOSOLVE = true
		end
		if s:lower() == "ro" then
			ONLYRESULT = true
		end
		if s:lower() == "json" then
			require"json"
			JSON = true
		end
	end
end

function table.has(t, v)
	for k,value in pairs(t) do
		if value == v then
			return true
		end
	end
end
function table.deepcopy(t)
	local lot = {}
	local function _copy(t)
		if type(t) ~= "table" then
			return t
		elseif lot[t] then
			return lot[t]
		end
		local nt = {}
		lot[t] = nt
		for k,v in pairs(t) do
			nt[_copy(k)] = _copy(v)
		end
		return setmetatable(nt, _copy(getmetatable(t)))
	end
	return _copy(t)
end

function boxes()
	return {
		{game[1][1], game[1][2], game[1][3],
		 game[2][1], game[2][2], game[2][3],
		 game[3][1], game[3][2], game[3][3],
		 originx = 0, originy = 0},
		{game[1][4], game[1][5], game[1][6],
		 game[2][4], game[2][5], game[2][6],
		 game[3][4], game[3][5], game[3][6],
		 originx = 3, originy = 0},
		{game[1][7], game[1][8], game[1][9],
		 game[2][7], game[2][8], game[2][9],
		 game[3][7], game[3][8], game[3][9],
		 originx = 6, originy = 0},
		{game[4][1], game[4][2], game[4][3],
		 game[5][1], game[5][2], game[5][3],
		 game[6][1], game[6][2], game[6][3],
		 originx = 0, originy = 3},
		{game[4][4], game[4][5], game[4][6],
		 game[5][4], game[5][5], game[5][6],
		 game[6][4], game[6][5], game[6][6],
		 originx = 3, originy = 3},
		{game[4][7], game[4][8], game[4][9],
		 game[5][7], game[5][8], game[5][9],
		 game[6][7], game[6][8], game[6][9],
		 originx = 6, originy = 3},
		{game[7][1], game[7][2], game[7][3],
		 game[8][1], game[8][2], game[8][3],
		 game[9][1], game[9][2], game[9][3],
		 originx = 0, originy = 6},
		{game[7][4], game[7][5], game[7][6],
		 game[8][4], game[8][5], game[8][6],
		 game[9][4], game[9][5], game[9][6],
		 originx = 3, originy = 6},
		{game[7][7], game[7][8], game[7][9],
		 game[8][7], game[8][8], game[8][9],
		 game[9][7], game[9][8], game[9][9],
		 originx = 6, originy = 6}
	}
end
function box(fx, fy)
	if fx < 4 then
		if fy < 4 then
			return 1
		elseif fy > 3 and fy < 7 then
			return 4
		elseif fy > 6 then
			return 7
		end
	elseif fx > 3 and fx < 7 then
		if fy < 4 then
			return 2
		elseif fy > 3 and fy < 7 then
			return 5
		elseif fy > 6 then
			return 8
		end
	elseif fx > 6 then
		if fy < 4 then
			return 3
		elseif fy > 3 and fy < 7 then
			return 6
		elseif fy > 6 then
			return 9
		end
	end
end
function printgame(new, force)
	if JSON and SOLVING then return end
	if ONLYRESULT and not force then return end
	if not JSON then print"" end
	local ret = {}
	if not JSON then
	for fy,v in ipairs(game) do
		for fx,i in ipairs(v) do
			local pada,padb = " "," "
			if not AUTOSOLVE and not hlz and not SOLVING and fy == y and fx == x then
				pada,padb = "[","]"
			end
			if SOLVING and i == 0 then
				pada,padb = "[","]"
			end
			if new and new[fx..","..fy] == true then
				pada,padb = ">","<"
			end
			io.write(pada..i..padb)
		end
		io.write"\n\n"
	end end
	if JSON and SOLVED then
	for fy,v in ipairs(game) do
		for fx,i in ipairs(v) do
			ret[#ret+1] = i
		end
	end end
	if JSON then
		ret.solved = SOLVED or false
		print(json.encode(ret))
	end
end
function cleargame()
	game = {
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0}
	}
end

function boxhas(n, b)
	for fy,v in ipairs(game) do
		for fx,i in ipairs(v) do
			if box(fx, fy) == b then
				if n == i then
					return true
				end
			end
		end
	end
	return false
end
function linexhas(n, l)
	for fy,v in ipairs(game) do
		for fx,i in ipairs(v) do
			if fx == l then
				if n == i then
					return true
				end
			end
		end
	end
	return false
end
function lineyhas(n, l)
	for fy,v in ipairs(game) do
		if fy == l then
			for fx,i in ipairs(v) do
				if n == i then
					return true
				end
			end
		end
	end
	return false
end

function solvegame()
	lastzeroes = 0
	SOLVING = true
	while true do
		LOOPS = LOOPS + 1
		local zeroes = 0
		local newin = {}
		for fy,v in ipairs(game) do
			for fx,i in ipairs(v) do
				if i == 0 then
					local matches = {}
					for n=1,9 do
						if not boxhas(n, box(fx,fy)) and not
							   linexhas(n, fx) and not
							   lineyhas(n, fy) then
						    table.insert(matches, n)
						end
					end
					if #matches == 1 then
						newin[fx..","..fy] = true
						--print(fx..","..fy..": "..matches[1])
						game[fy][fx] = matches[1]
					else
						zeroes = zeroes + 1
					end
				end
			end
		end
		for b=1,9 do
			if table.has(boxes()[b], 0) then
				t = boxes()[b]
				local boxmatches = {{},{},{},{},{},{},{},{},{}}
				for k,v in ipairs(t) do if v == 0 then
					local x,y = t.originx,t.originy
					if k < 4 then
						x = x + k
						y = y + 1
					elseif k > 3 and k < 7 then
						x = x + (k - 3)
						y = y + 2
					elseif k > 6 then
						x = x + (k - 6)
						y = y + 3
					end
					for n=1,9 do
						if not boxhas(n, box(x,y)) and not
							   linexhas(n, x) and not
							   lineyhas(n, y) then
							boxmatches[n][#boxmatches[n] + 1] = {x,y}
						end
					end
				end end
				for n,t in ipairs(boxmatches) do
					if #t == 1 then
						newin[x..","..y] = true
						local x,y = t[1][1],t[1][2]
						--print(x..","..y..": "..n)
						game[y][x] = n
						zeroes = zeroes - 1
					end
				end
			end
		end
		if lastzeroes == zeroes then
			break
		end
		printgame(newin)
		--[[if zeroes ~= 0 then
			print(zeroes.." to go")
		end--]]
		lastzeroes = zeroes
		if zeroes == 0 then
			SOLVED = true
			break
		end
	end
	SOLVING = false
end
function guessgame()
	local savedgame,guessloops,savedloops = game,0,LOOPS
	math.randomseed(os.time())
	local rmatch = {}
	for fy,r in ipairs(game) do
		for fx,i in ipairs(r) do
			if i == 0 then
				local matches = {}
				for n=1,9 do
					if not boxhas(n, box(fx,fy)) and not
						   linexhas(n, fx) and not
						   lineyhas(n, fy) then
					    --print(fx..","..fy.." could be "..n)
						table.insert(rmatch, {fy, fx, n})
					end
				end
			end
		end
	end
	repeat
		guessloops = guessloops + 1
		if not rmatch[guessloops] then break end
		game = table.deepcopy(savedgame)
		local g = rmatch[guessloops]
		game[g[1]][g[2]] = g[3]
		if not (ONLYRESULT or JSON) then print("Trying to solve if "..g[2]..","..g[1].." would be "..g[3]) end
		solvegame()
	until SOLVED
	if not JSON then print("Took "..guessloops.." guess loops, "..((SOLVED and "solved!") or "could not solve.")) end
end

if AUTOSOLVE and not JSON then print("Original: ") end
SOLVING = true
printgame(nil, true)
SOLVING = false

if AUTOSOLVE then
	solvegame()
	if not SOLVED then
		guessgame()
	end
	if not SOLVED then
		SOLVING = false
		if JSON then
			printgame(nil, true)
		else
			print("Can't find the solution.")
		end
	else
		printgame(nil, true)
		if not JSON then print("Solved in "..LOOPS.." loops total.") end
		os.exit()
	end
	if ONLYRESULT or JSON then
		os.exit()
	end
end
function help()
	print("Specify a number to put that number in the currently selected coordinate.")
	print("Commands: up (u), down (d), left (l), right (r), exit/quit (q), solve (s), guess (g), print/show (p), clear (c), help (h)")
end
help()
printgame()
while true do
	io.write"> "
	local act = string.lower(io.stdin:read"*l" or "")
	if act == "up" or act == "u" then
		y = math.max(1, y - 1)
		printgame()
	elseif act == "left" or act == "l" then
		x = math.max(1, x - 1)
		printgame()
	elseif act == "right" or act == "r" then 
		x = math.min(9, x + 1)
		printgame()
	elseif act == "down" or act == "d" then
		y = math.min(9, y + 1)
		printgame()
	elseif act == "exit" or act == "quit" or act == "q" then
		os.exit()
	elseif #act == 1 and tonumber(act) then
		SOLVED = false
		game[y][x] = tonumber(act)
		printgame()
	elseif act == "solve" or act == "s" then
		solvegame()
		if not SOLVED then
			print("can't find the solution.")
		else
			print("Solved in "..LOOPS.." loops.")
		end
		printgame()
	elseif act == "print" or act == "show" or act == "p" then
		printgame()
	elseif act == "clear" or act == "c" then
		SOLVED = false
		cleargame()
		printgame()
	elseif act == "help" or act == "h" then
		help()
	elseif act == "guess" or act == "g" then
		guessgame()
		printgame()
		print("Solved in "..LOOPS.." loops total.")
	else
		print("Unknown command '"..act.."'")
	end
end