-----------------------------
-- Levak ©2011 --------------
-- http://levak.free.fr/ ----
-- levak92@gmail.com --------
-----------------------------

------ Deep Table Copy
function table.copy(t)
	local u = { }
	for k, v in pairs(t) do
		if type(v) ~= "table" then
			u[k] = v
		else
			print("Sub-Table detected : "..k.." "..tostring(v)..":"..type(v))
			u[k] = table.copy(v)
		end
	end
	--print("Table copied")
	return setmetatable(u, getmetatable(t))
end

------ Table contains test
function table.contains(table, element)
	for _, value in pairs(table) do
		if value == element then
			return true
		end
	end
	return false
end

------ Table Merge
function table.merge(t, x)
	for i = 1, #x do
		t[#t+1] = x[i]
	end
	return t
end

------ Explode function (from http://www.wellho.net/resources/ex.php4?item=u108/split)
function string:explode(delimiter)
  local result = { }
  local from  = 1
  local delim_from, delim_to = string.find( self, delimiter, from  )
  while delim_from do
    table.insert( result, string.sub( self, from , delim_from-1 ) )
    from  = delim_to + 1
    delim_from, delim_to = string.find( self, delimiter, from  )
  end
  table.insert( result, string.sub( self, from  ) )
  return result
end

-- Time format

function PaintTimer(gc)
	local width, height = 6*normal, 3*normal
	local x, y = platform.window:width() - width - normal, 2*normal
	local minutes = math.floor(timeSpan / 60)
	local seconds = timeSpan % 60
	local str = tostring(minutes)..":"
	if seconds <= 9 then str = str.."0" end
	str = str..tostring(seconds)
	gc:setPen("medium", "smooth")
	gc:setFont("sansserif", "b", fnormal)
	gc:drawRect(x, y, width, height)
	gc:drawString(str, x+gc:getStringWidth(str)/2, y+gc:getStringHeight(str)/2, "top")
end

-- Sudoku Engine 

function PaintGrid(gc, HL)
	gc:setPen("thin", "smooth")
	for j = 1, 9 do
		for Case = (j - 1) * 9 + 1, j * 9 do
			if win or (not paused) then
				if Case == HL then
					gc:setPen("thick", "smooth")
					if OriginalGrid[selectedCase.X + (selectedCase.Y - 1) * 9] ~= 0 then
						gc:setColorRGB(128, 128, 128)
					end				
					gc:drawRect(x + (GetColumn(Case)-1) * iter,
									y + (GetLine(Case)-1) * iter,
									iter, iter)
					gc:setPen("thin", "smooth")
					gc:setColorRGB(0, 0, 0)
				end
				if OriginalGrid[Case] ~= 0 then
					gc:setFont("sansserif", "b", fnormal)
				else
					gc:setFont("sansserif", "r", fnormal)
				end
				if DisplayGrid[Case] ~= 0 then
					gc:drawString(tostring(DisplayGrid[Case]),
													 x + (GetColumn(Case)-1) * iter + iter / 2,
													 y + (GetLine(Case)-1) * iter + iter / 2,
													"middle")
				end
			end
		end
		if (j - 1) % 3 == 0 then
			gc:setPen("medium", "smooth")
		else
			gc:setPen("thin", "smooth")
		end
		gc:drawLine(x + (j - 1) * iter, y, x + (j - 1) * iter, y + dim * 2)
		gc:drawLine(x, y + (j - 1) * iter, x + dim * 2, y + (j - 1) * iter)
	end
	gc:setPen("medium", "smooth")
	gc:drawLine(x + 9 * iter, y, x + 9 * iter, y + dim * 2)
	gc:drawLine(x, y + 9 * iter, x + dim * 2, y + 9 * iter)
end

function GetLine(Case)
	return math.floor((Case - 1) / 9) + 1
end

function GetColumn(Case)
	return (Case - 1) % 9 + 1
end

function GetSquare(Case)
	return math.floor((GetLine(Case)-1)/3) * 3 * 9 + math.floor((GetColumn(Case)-1)/3) * 3 + 1
end

-- Sudoku Sovler

SudokuSolver = {}
SudokuSolver.__index = SudokuSolver

function SudokuSolver.new(newGrid)
	local sudoku = {}
	setmetatable(sudoku, SudokuSolver)
	sudoku.Grid = newGrid
	return sudoku
end

function SudokuSolver:isHLineValidWithCase(Case, Value)
	for i = (GetLine(Case) - 1) * 9 + 1, GetLine(Case) * 9 do 
		if Case ~= i and Value == self.Grid[i] then
			return false
		end
	end
	return true
end

function SudokuSolver:isVLineValidWithCase(Case, Value)
	for j = GetColumn(Case), GetColumn(Case) + 72, 9 do 
		if Case ~= j and Value == self.Grid[j] then
			return false
		end
	end
	return true
end

function SudokuSolver:isSquareValidWithCase(Case, Value)
	for j = 0, 2 do
		for i = 0, 2 do
			local c = GetSquare(Case) + i + j * 9
			if Case ~= c and Value == self.Grid[c] then
				return false
			end
		end
	end
	return true
end

function SudokuSolver:GetValidValues(Case)
	local list = {}
	for i = 1, 9 do
		if 	 self:isHLineValidWithCase(Case, i)
			and self:isVLineValidWithCase(Case, i)
			and self:isSquareValidWithCase(Case, i) then
				table.insert(list, i)
		end
	end
	return list
end

function SudokuSolver:isValid(ZeroMatters)
	for Case = 1, 81 do
		if ZeroMatters and self.Grid[Case] == 0 then
			return false
		end
		if self.Grid[Case] ~= 0 then
			if 	not self:isHLineValidWithCase(Case, self.Grid[Case])
				or not self:isVLineValidWithCase(Case, self.Grid[Case])
				or not self:isSquareValidWithCase(Case, self.Grid[Case]) then
					return false
			end
		end
	end
	return true
end

function SudokuSolver:SolveSingletons()
	local isThereAnySingleton
	local minPossibilitiesCase
	local minPossibilitiesCount
	
	repeat
		isThereAnySingleton = true
		minPossibilitiesCase = 0
		minPossibilitiesCount = 9
		for Case = 1, 81 do
			if self.Grid[Case] == 0 then
				validValues = self:GetValidValues(Case)				
				local count = #validValues
				if count == 1 then
					self.Grid[Case] = validValues[1];
					isThereAnySingleton = false
				elseif count > 1 then
					if minPossibilitiesCount > count then
						minPossibilitiesCount = count
						minPossibilitiesCase = Case
					end
				end
			end
		end		
	until (isThereAnySingleton)
	return minPossibilitiesCase
end

function SudokuSolver:Solve()
	local nextCase = self:SolveSingletons()
	if nextCase > 0 then
		print(tostring(nextCase))
		local validValues = self:GetValidValues(nextCase)
		for i,value in ipairs(validValues) do
			local newGrid = self.Grid --table.copy(self.Grid)
			newGrid[nextCase] = value
			local newSudokuSolver = SudokuSolver.new(table.copy(newGrid))
			newSudokuSolver:Solve()
			if newSudokuSolver:isValid(true) then
				self.Grid = newSudokuSolver.Grid
				break
			end
		end
	end
end

function SudokuSolver:GiveRandomValue(Case)
	local validValues = self:GetValidValues(Case)
	local newCase = validValues[math.random(1, #validValues)]
	self.Grid[Case] = newCase
end

function SudokuSolver:PickUp()
	for Case = 1, 81, 10 do
		self:GiveRandomValue(Case)
	end
	for Case = 73, 9, -8 do
		self:GiveRandomValue(Case)
	end
	for Case = 2, 8 do
		self:GiveRandomValue(Case)
	end
	for Case = 74, 80 do
		self:GiveRandomValue(Case)
	end
end

function SudokuSolver:Generate()
	if not pcall(function() return self:PickUp() end) then
		self:Generate()
	end
	self:Solve()
end

-- Save & Load

function loadGame(name)
	print(name)
	SolutionGrid = var.recall(name..".SolutionGrid")
	OriginalGrid = var.recall(name..".OriginalGrid")
	print(OriginalGrid)
	for _, var in pairs(OriginalGrid) do
		print(tostring(var))
	end
	PlayGrid = var.recall(name..".PlayGrid")
	timeSpan = var.recall(name..".timeSpan")
	GridSeed = var.recall(name..".GridSeed")
	--annotation = var.recall("game.annotation")
	DisplayGrid = PlayGrid
	pause = false
	win = false
	oldTimer = timer.getMilliSecCounter()
	timer.start(1)
	platform.window:invalidate()
end

function saveGame(name)
	var.store(name..".SolutionGrid", SolutionGrid)
	var.store(name..".OriginalGrid", OriginalGrid)
	var.store(name..".PlayGrid", PlayGrid)
	var.store(name..".timeSpan", timeSpan)
	var.store(name..".GridSeed", GridSeed)
	--var.store("game.annotation", annotation)
	platform.window:invalidate()
end