--[[

    File: knightstour.lua

    Copyright (C) 2000-2008 Christopher Moore (christopher.e.moore@gmail.com)
	  
    This software is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.
  
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
  
    You should have received a copy of the GNU General Public License along
    with this program; if not, write the Free Software Foundation, Inc., 51
    Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

--]]


--[[
Knights Tour Solver

lua knightstour.lua

if you want to run this on a certain range of board sizes
	lua -e 'bsMin=$n bsMax=$m' knightstour.lua

]]
-------------------------------- Util --------------------------------

function castnumber(b)
	return tonumber(b) or 0
end

function union(ta,tb)
	for k,v in pairs(tb) do ta[k] = v end
	return ta
end

function class(classname, init)
	local classObj = {}
	if init then union(classObj, init) end
	
	classObj.instMetaTable = { __index = classObj }
	_G[classname] = classObj		-- register it in the global namespace
	
	classObj.class = classObj
	classObj.classname = classname
	classObj.new = function(self, ...)
		local inst = {}
		setmetatable(inst, self.instMetaTable)
		if inst.ctor then
			inst:ctor(...)
		end
		return inst
	end
end

-------------------------------- Table --------------------------------

function table:contains(test)
	for k,v in pairs(self) do
		if v == test then return true end
	end
	return false
end

TableMeta = { __index = table }
function Table(...)
	local t = {...}
	setmetatable(t, TableMeta)		-- depends on the table package being imported
	return t
end

-------------------------------- Edge --------------------------------

class('Edge')

function Edge:ctor(m,n)
	self.n = Table(m,n)
end

-- returns true if the edges match, order-independant
function Edge:matches(e)
	if e.n[2] == self.n[2] and e.n[1] == self.n[1] then return true end
	if e.n[2] == self.n[1] and e.n[1] == self.n[2] then return true end
	return false
end

function Edge:adjacent(n)
	if n == self.n[1] then return self.n[2] end
	if n == self.n[2] then return self.n[1] end
	print('UT OH, Edge:adjacent got a non-possessed node: '..n.i..','..n.j)
end

-------------------------------- Node --------------------------------

class('Node')

function Node:ctor(i,j)
	-- of all associated edges
	self.edges = Table()
	
	-- keep track of initial position
	self.i = i
	self.j = j
	
	-- keep track of the number of traversed neighbors
	self.degree = 0
	
	-- and keep track of what order we are in the tour
	self.order = 0
end


-------------------------------- Board --------------------------------

class('Board')

-- usage: Board:new(n,m)
--grid is indexed by [n][m]
function Board:ctor(...)
	local args = {...}
	if not args[1] then n = 5 else n = args[1] end
	if not args[2] then m = n else m = args[2] end
	
	-- nodes
	self.grid = Table()
	self.nodes = Table()
	for i=1,n do
		self.grid:insert(Table())
		for j=1,m do
			local n = Node:new(i,j)
			self.grid[i]:insert(n)
			self.nodes:insert(n)
		end
	end
	
	-- edges
	self.edges = Table()
	
	local offsets
	offsets = {
		{-1,-2},
		{-1,2},
		{1,-2},
		{1,2},
		{-2,-1},
		{-2,1},
		{2,-1},
		{2,1}
	}
	
	for i=1,n do
		for j=1,m do
			for k,v in ipairs(offsets) do
				self:addEdgeByIndices(i,j,i+v[1],j+v[2])
			end
		end
	end
end

-- safe accessor of nodes by indices through the grid
function Board:getNode(i,j)
	local t = self.grid[i]
	if not t then return nil end
	return t[j]
end

-- quick accessor for adding edges by indicies
function Board:addEdgeByIndices(i1,j1,i2,j2)
	return self:addEdge( self:getNode(i1,j1), self:getNode(i2,j2) )
end

-- edgeExists(edge) to teest for edge equality
-- edgeExists(node1,node2) to do so for nodes
function Board:edgeExists(...)
	local args = {...}
	local e = args[1]
	if #args == 2 then e = Edge:new(args[1], args[2]) end
	
	for i,v in ipairs(self.edges) do
		-- if we find a match then bail out
		if v:matches(e) then 
			return true
		end
	end
	return false
end

function Board:addEdge(m,n)
	if not m or not n then return end
	local e = Edge:new(m,n)
	-- add it uniquely ...
	if self:edgeExists(e) then return end
	-- add to edge list
	self.edges:insert(e)
	-- add to each vertex's list
	m.edges:insert(e)
	n.edges:insert(e)
end


-- print the board
function Board:tostring(showDegrees)
	local str = ''
	local maxnum = math.floor(math.log10(#self.nodes))+1
	local newline = ''
	for i=1,#self.grid do
		str = str .. newline .. '['
		newline = '\n'
		if showDegrees then
			-- print the values
			for j=1,#self.grid[i] do
				local m = string.format('  %'..maxnum..'d', self.grid[i][j].degree)
				str = str .. m
			end
			str = str .. '\t|'
		end
		-- print the values
		for j=1,#self.grid[i] do
			local m = string.format('  %'..maxnum..'d', self.grid[i][j].order)
			str = str .. m
		end
		str = str .. ']'
	end
	return str
end

--heuristic
-- degree of a square = # of squares reachable by it (not already traversed)
-- each time you add a square to the tour you gotta decrease all its neighbor's degrees

function Board:solve(i,j, printAsYouGo)

	-- prep for a solve ... init the degrees and nodes
	-- you know if you put this in an structure adjacent to the board 
	-- then we could multithread this solver ...
	
	--	calculate the degree of all the nodes
	for i,n in ipairs(self.nodes) do
		n.degree = 0
		n.order = 0
	end
	for i,e in ipairs(self.edges) do
		for j,n in ipairs(e.n) do
			n.degree = n.degree + 1
		end
	end

	if printAsYouGo then
		print(self:tostring(true))
		print('')
	end
	
	function recursiveDive(self,tour)
		--prep the last element on the list
		local n = tour.list[#tour.list]
		n.order = #tour.list
		n.degree = 0			-- prevent future lookup
		
		-- then try to find a next one
		-- decrease the degree of all its neighbors
		-- and recursive solve for the max of all its neighbors
		local minValue = #self.nodes+1
		local minNode = nil
		for i,e in ipairs(n.edges) do
			local m = e:adjacent(n)
			if m.degree ~= 0 then
				m.degree = m.degree - 1
				-- only consider the node if it has at least one degree
				if minValue > m.degree then
					minValue = m.degree
					minNode = m
				end
			end
		end
		
		if printAsYouGo then
			print(self:tostring(true))
			print('')
		end

		-- no min found - the tour is over
		if not minNode then return end
		
		if minNode.order ~= 0 then
			print('Danger Will Robinson - you tried to add a node that already has an order!')
			return
		end
		if tour.list:contains(minNode) then
			print('Danger Will Robinson - you tried to add a node already in the tour!')
			return
		end
		
		-- add the new one to the list
		tour.list:insert(minNode)
		
		-- recursive call on the min node
		recursiveDive(self,tour)
	end
	
	local tour = Tour:new()

	-- add node i,j to some sort of list
	local n = self:getNode(i,j)
	if not n then 
		print('looks like we were asked to add a node to the tour which doesnt exist ... ')
		return tour
	end

	tour.list:insert(n)
	recursiveDive(self, tour)
	return tour
end

-------------------------------- Tour --------------------------------

class('Tour')

function Tour:ctor()
	self.list = Table()
end

Tour.instMetaTable.__concat = function(a,b)
	local str = ''
	for i,v in ipairs({a,b}) do
		if v.class == Tour then
			str = str .. '['
			local coma = ''
			for i,n in ipairs(v.list) do
				str = str .. coma .. '{'..n.i..','..n.j..'}'
				coma = ', '
			end
			str = str .. ']'
		else
			str = str .. tostring(v)
		end
	end
	return str
end

-------------------------------- Main --------------------------------

if bsMin == nil then bsMin = 3 end
if bsMax == nil then bsMax = 5 end

for bs = bsMin,bsMax do
	print('testing boards sized '..bs..'x'..bs)
	board = Board:new(bs,bs)

	local moveHist = Table()
	local moves = Board:new(bs,bs)
	
	local closedCount = 0
	local closedBoard = Board:new(bs,bs)

	for i = 1,bs do
		for j = 1,bs do
			local tour = board:solve(i,j)

--			print(board:tostring(true))
--			if #tour.list ~= #board.nodes then print('failed to find a full tour') end
--			print(''..tour)
			
			local n = #tour.list
			moveHist[n] = castnumber(moveHist[n]) + 1
			
			moves:getNode(i,j).order = n

			if #tour.list == #board.nodes and
				board:edgeExists(tour.list[1], tour.list[#tour.list])
			then
				closedCount = closedCount + 1
				closedBoard:getNode(i,j).order = 1
			end
		end
	end

	-- no good way in lua to sort keys ... php wins
	for i,v in pairs(moveHist) do
		print('we found '..v..' tours of length '..i)
	end

	print('here\'s our tour size for each starting location:')
	print(moves:tostring())
	
	print('we found '..closedCount..' closed tours')
	print('here\'s a graph of whether the tours were closed (1) or not (0):')
	print(closedBoard:tostring())
end