-- Task: обойти конём доску, посещённые ранее клетки и клетки с дырами не доступны local F = far.Flags local board="8x8" -- 8x8 по умолчанию --local holes={{4,4},{4,3}} --local holes={{1,4}} -- список координат дыр holes = holes or {} local x0,y0,ret0 = 1,1,true -- старт с 1-го этажа, возврат в точку старта local bx,by = (far.InputBox(nil,"Task","Enter d d (default "..board.."):",nil,nil,nil,nil,F.FIB_NONE) or board):match("(%d)[x, ](%d)") bx,by = tonumber(bx),tonumber(by) local ttime=far.FarClock() local t,t1 = {},{} -- дерево возможных переходов local initt=function() for x=1,bx do t[x]={} end for _,v in pairs(holes) do t[v[1]][v[2]]={0,0} end end -- карта с установленными дырами initt() local d={{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2}} -- варианты ходов --local d={{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}} -- варианты ходов local st=function(x,y) -- определение свободных переходов с текущей клетки local t0={} for i=1,#d do local x2,y2 = x+d[i][1],y+d[i][2] if x2>=1 and x2<=bx and y2>=1 and y2<=by and not t[x2][y2] then table.insert(t0,d[i]) end end table.insert(t1,t0) end local chk=function(x,y) for i=1,#d do if x+d[i][1]==x0 and y+d[i][2]==y0 then return true end end return false end local x,y = x0,y0 -- текущая клетка local count,ret = 1,ret0 -- cчётчик итераций while true do local stnext=function() t[x][y]={x+t1[#t1][#t1[#t1]][1],y+t1[#t1][#t1[#t1]][2]} x,y = t[x][y][1],t[x][y][2] count=count+1 end local stprev=function() t[x][y]=nil x,y = x-t1[#t1][#t1[#t1]][1],y-t1[#t1][#t1[#t1]][2] count=count+1 end st(x,y) if #t1[#t1]>0 then stnext() else if #t1==(bx*by-#holes) and (not ret or chk(x,y)) then break else repeat table.remove(t1) if #t1==0 then break end stprev() table.remove(t1[#t1]) until #t1[#t1]>0 if #t1==0 then if ret then ret,x,y = false,x0,y0 initt() else break end else stnext() end end end end local wl,s = 0,"Board: "..bx.."x"..by.."\nHoles: " for i=1,#holes do s=s..holes[i][1]..holes[i][2].."," end s=string.sub(s,1,-2).."\nSteps: "..#t1.."\n\nSolution: "..(ret==ret0 and "found" or "not found").."\nWay: "..x0..y0 local x2,y2 = x0,y0 for i=1,#t1-1 do x2,y2 = x2+t1[i][#t1[i]][1],y2+t1[i][#t1[i]][2] s=s.." "..x2..y2 end ttime = math.floor((far.FarClock()-ttime)/1000)/1000 far.Message(s.."\nIterations: "..count.."\nTime: "..ttime.." s","Task: Chess Knight") |