LÖVE

Code: Select all

-------------------------------------------------------------------------
-- main.lua  (KT01 template: pgimeno)
-------------------------------------------------------------------------
--[[
concept of:
http://code.activestate.com/recipes/578382-knights-tour-using-warnsdorff-algorithm/ 
various considerations:
http://www.cs.utsa.edu/~wagner/python/knight/knight_tour.html
 ]]
 
-- possible moves
local pm = {{-2,1},{-1,2},{1,2},{2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}}

local n   = 8 	-- number rowscollons
local cbx = n	  	-- rows
local cby = n	  	-- colls

-- startfeld  -  randomized (for testing)
math.randomseed (os.time ())    -- random start
local kx =math.random(1, 8)
local ky =math.random(1, 8)

print("Startfeld kx/ky: " ..kx.."/"..ky)
-- make chessboard nn
local cb = {}      -- cb definition with zeros 
for i = 1, n do
    cb[i] = {}
    for j = 1, n do
        cb[i][j] = 0
    end
end

math.randomseed (os.time ())    -- random (coin toss)

-- schachbrett sollte im zentrum sein (wie grid layout)
local gw =320               -- grid width: 8 x 40 = 320
local n  =8                 -- no of fields
local bs =gw/n              -- feldbreite 40 (boxsize)
local count =0              -- Zaehler ( in drawLine() ) 

-- cb zeichnen (img geht auch)
function drawCB()
	for r=0, n-1 do	--row
	  for c=0, n-1 do	--col
		if (r+c)%2 == 0 then                        
			love.graphics.setColor(255,0,0)		--red
		else            
			love.graphics.setColor(255,255,255)	--white
		end 		
		love.graphics.rectangle("fill", r*bs, c*bs, bs, bs)  
	  end -- for c
	end	-- for r
end --func


function printCB()        -- show cb 
for y = 1, n do
  io.write()
    for x = 1, n do
      if cb[y][x] == 0 then
        io.write("..")
      elseif cb[y][x] <10 then
		io.write( " "..cb[y][x].."|" )
      else
         io.write( cb[y][x].."|" )
      end
    end
    print()
end
return
end

-- between inclusive
--if nx = 1 and nx = N and ny = 1 and ny = N then  -- cb border
function between(x, min, max)
    return (x>=min) and (x<=max)
end

k = 0		-- jumps-counter

function doJump()
  while(k <65) do
    cb[ky][kx] = k+1        -- counter set & save in cb
	
	local start_x = kx * bs - (bs/2)   -- make start x, y (f. line)
	local start_y = ky * bs - (bs/2) 
	
    pq = {}                 -- make priority queue 

    for i = 1, n do 	    -- row
      nx = kx + pm[i][1]; ny = ky + pm[i][2]
      if between(nx, 1, cbx) and between(ny, 1, cby) then
        if cb[ny][nx] == 0 then ctr = 0   -- lua is 1-based!
			
          for j = 1, n do	   -- col
            ex = nx + pm[j][1]; ey = ny + pm[j][2]
            if between(ex, 1, cbx) and between(ey, 1, cby) then
              if cb[ey][ex] == 0 then ctr=ctr+1 end
            end
          end
		  
          table.insert(pq, (ctr*100)+i)	-- looking for a better solution
        end
      end
    end

  --[[ Warnsdorff's algorithmus;   extended
		move to the neighbor that has min number of available neighbors
		randomization  we could take it - or not (coin toss) 
	]]
    if #pq > 0 then
      table.sort (pq)     		-- ascending (min to supreme)
      minVal = 11			    -- max loop nr
      minD   = 0			    -- min value

      for dd = 1, #pq do			 -- provisionally:
        x = table.remove(pq,1)       -- delete head-element
        p = math.floor(x / 100)      -- p wert extrahieren
        m = x % 10				     -- m (row) wert extrahieren

        if p == minVal and math.random(100) <55 then
          minVal = p
          minD   = m
        end

        if p < minVal then
            minVal = p
            minD   = m
        end
      end  --dd

      m = minD
      kx = kx + pm[m][1]
      ky = ky + pm[m][2]
	
	local end_x = kx * bs - (bs/2)   		-- make new end x, y 
	local end_y = ky * bs - (bs/2) 	
	
	--print("start: ",start_x, start_y)
	--print("end: ",end_x, end_y)
	
	love.graphics.setColor(0,0,255)			--blue
	--love.graphics.setColor(255,255,0)		--yellow
	love.graphics.line(start_x, start_y, end_x, end_y)
	sleep(0.1)
	
    else
      if k < 63 then
        --print("Fehler im Feld-Nr.: " ..k)
		print("Error in Field-No.: " ..k)
        break
      else
        --print("Erfolg.")
		print("Success.")
        break
      end
    end

    k = k+1
  end  -- while
end --func doJump()
--   end main pgm

-- **************************** main ****************************
drawCB()
doJump()
printCB()
-- **************************** end pgm *********************