-- Task: обойти конём доску, посещённые ранее клетки и клетки с дырами недоступны local ffi = require("ffi") local C = ffi.C ffi.cdef[[ typedef uint8_t t1[9]; ]] local F = far.Flags local board="6x6" -- 8x8 по умолчанию local holes -- список координат дыр --holes={{4,4},{4,3}} --holes={{3,1}} holes = holes or {} local ret0 = 0 -- =0 без обязательного возврата в точку старта, =1 с возвратом --local ret0 = false -- возврат в точку старта local nm="zc" local answer = far.InputBox(nil,"Task "..nm,"Enter bx by x0 y0 ret (ex.: "..board..", start 1 1, ret 1: 6 6 1 1 1):",nil,nil,nil,nil,F.FIB_NONE) or "" local ttime=far.FarClock() local bx,by,x0,y0,ret0 = string.match(answer,"(%d+)[x, ](%d+)[, ](%d+)[, ](%d+)[, ]([01])") if not bx then ret0,bx,by,x0,y0 = 0,string.match(answer,"(%d+)[x, ](%d+)[, ](%d+)[, ](%d+)") if not bx then ret0,x0,y0,bx,by,ret = 0,1,1,string.match(answer,"(%d+)[x, ](%d+)") if not bx then bx,by = 6,6 end end end bx,by,x0,y0,ret0 = tonumber(bx),tonumber(by),tonumber(x0),tonumber(y0),tonumber(ret0)==1 local full=bx*by-#holes -- количество клеток для ходов -- {dx,dy} - вектор хода --local dx=ffi.new("int8_t[8]",{-1,-2,-2,-1, 1, 2, 2, 1}) --local dy=ffi.new("int8_t[8]",{ 2, 1,-1,-2,-2,-1, 1, 2}) local dx=ffi.new("int8_t[8]",{-1,-1, 2,-2, 1, 1,-2, 2}) local dy=ffi.new("int8_t[8]",{ 2,-2, 1, 1,-2, 2,-1,-1}) -- создаём чистую доску, свободная клетка -1, клетка занятая вектором хода 0-7, дырой 8 local function array(st,...) st=st..string.rep('[$]',#{...}) local array_ct = ffi.typeof(st,...) return array_ct({{ -1 }}) end local t00=array('int8_t' ,bx,by) -- слой векторов с дырами local t01=array('int16_t',bx,by) -- слой нумерации ходов for _,v in ipairs(holes) do t00[v[1]-1][v[2]-1]=8 end -- расставляем дыры 0 based local t1=ffi.new("t1[?]",full) -- дерево оставшихся возможных векторов ходов bx,by,x0,y0,full = bx-1,by-1,x0-1,y0-1,full-1 -- align from 1 to 0 based local t1s,t1v,x,y -- номер текущего хода, последний (текущий) вектор, координаты текущего поля local function initt() -- инициализация t1s,t1v,x,y = -1,0,x0,y0 end initt() local cx=ffi.new("int8_t[8]",{-1}) local cy=ffi.new("int8_t[8]",{-1}) local ta=ffi.new("int8_t[8]",{-1}) local ti=ffi.new("int8_t[8]",{-1}) local function around(x,y) local tl=-1 for i=7,0,-1 do local x2,y2 = x+dx[i],y+dy[i] if x2>=0 and x2<=bx and y2>=0 and y2<=by and t00[x2][y2]<0 then tl=tl+1 local a,v = 0,i<4 and i+4 or i-4 -- противоположный вектор for j=7,0,-1 do if i==v then goto continue end -- исключаем клетку с которой пришли local x3,y3 = x2+dx[j],y2+dy[j] if x3>=0 and x3<=bx and y3>=0 and y3<=by and t00[x3][y3]<0 then a=a+1 end ::continue:: end ta[tl],ti[tl] = a,i end end -- сортируем по убыванию, обеспечивая приоритет обхода клеток с наименьшим количеством входов local l=tl-1 if l>=0 then for j=l,0,-1 do local b=true for i=l,0,-1 do local i1=i+1 if ta[i]<ta[i1] then b,ta[i],ti[i],ta[i1],ti[i1] = false,ta[i1],ti[i1],ta[i],ti[i] end end if b then break end end end return tl end -- массив клеток на расстоянии 1 хода от старта local cl=around(x,y) for i=cl,0,-1 do cx[i],cy[i] = x+dx[ti[i]],y+dy[ti[i]] end if ret0 then t00[cx[0]][cy[0]]=9 -- исключаем клетку финиша из маршрутов full=full-1 -- учитываем недоступность клетки финиша end --local function chk() for i=cl,0,-1 do if x==cx[i] and y==cy[i] then return true end end return false end -- проверка возврата к старту local turn,fw = 0,1 local function chk() for i=7,0,-1 do if x+dx[i]==cx[0] and y+dy[i]==cy[0] then t00[cx[0]][cy[0]]=-1 t01[x][y]=t1s t1[t1s][0],t1[t1s][1] = 1,i t1s,fw,turn,full = t1s+1,fw+1,turn+1,full+1 -- последний ход t01[cx[0]][cy[0]]=t1s return true end end return false end -- проверка возврата к старту local rb,ret,sub = 0,ret0 -- счётчик итераций while true do ::NOD0:: -- проверяем доступность клеток вокруг t1s,turn = t1s+1,turn+1 t1v=around(x,y)+1 ffi.copy(t1[t1s]+1,ti,t1v) t1[t1s][0]=t1v -- последний вектор хода ::NOD1:: if t1v>0 then local v=t1[t1s][t1v] t00[x][y],t01[x][y] = v,t1s x,y = x+dx[v],y+dy[v] fw=fw+1 else -- варианты ходов с текущей клетки отсутствуют if t1s==full and (not ret or chk()) then if not ret then t01[x][y]=t1s end break end -- последняя клетка? ::NOD3:: repeat -- откат t1s=t1s-1 -- удаляем последний неудачный ход if t1s<0 then if ret then ret=false initt() goto NOD0 else goto NOD2 end end -- испробованы все пути, решение не найдено t1v=t1[t1s][0] -- восстанавливаем индекс последнего вектора t00[x][y],t01[x][y] = -1,-1 local v=t1[t1s][t1v] x,y = x-dx[v],y-dy[v] rb=rb+1 -- возвращаемся на ход назад t1v=t1v-1 t1[t1s][0]=t1v -- откат на предыдущий вектор хода until t1v>0 if t1s==0 then t00[cx[0]][cy[0]]=-1 local v=t1[t1s][t1v+1] cx[0],cy[0] = x0+dx[v],y0+dy[v] t00[cx[0]][cy[0]]=9 end local v=t1[t1s][t1v] t00[x][y],t01[x][y] = v,t1s x,y = x+dx[v],y+dy[v] fw=fw+1 end end ::NOD2:: bx,by,x0,y0,full = bx+1,by+1,x0+1,y0+1,full+1 -- align from 0 to 1 local s = "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: "..(t1s+1).."\nClosed path: "..tostring(ret0).."\n\nSolution: "..(ret==ret0 and "found" or "not found").."\n\nWay: "..x0..y0 local fbx="%0"..#tostring(bx).."d" local fby="%0"..#tostring(by).."d" local x2,y2 = x0,y0 for i=0,t1s-1 do x2,y2 = x2+dx[t1[i][t1[i][0]]],y2+dy[t1[i][t1[i][0]]] s=s.." "..string.format(fbx,x2)..string.format(fby,y2) end s=s.."\n\n" local bb=bx*by local sf=#tostring(full) for y=by,1,-1 do for x=1,bx do local dd=t01[x-1][y-1]+1 s=s..string.format(bb==dd and "*%"..sf.."d*" or " %"..sf.."d ",dd) end s=s.."\n" end ttime = math.floor((far.FarClock()-ttime)/1000)/1000 s=s.."\n\nIterations: "..(fw+rb).."\n Turnover: "..turn.."\n Forward: "..fw.."\n Rollback: "..rb.."\n\nTime: "..ttime.." s" title="Task "..nm..": Chess Knight" far.Message(s,title) --local h=io.open([[Z:\temp\1.txt]],"wb") h:write(title.."\n\n"..s) h:close() |