hi everyone i have a 9x9 chess board I am given an initial position and final position of knight. can anyone plz help me to find minimum no of moves to reach final position??

my problem is regarding how to find shortest path conditioning

[Jos (10584)]

chess is played on a 8-by-8 board!

[Arslan Ahmad]

the question is about finding the shortest path and i think board size is not necessary but if you can help me with 8x8 then i can change it to my desired dimensions

Answer 1

[Arslan Ahmad]

I did it myself easy way using structured arrays with the help from another code.

function [turns] = myKnightTo(board_dim, p1, p2, max_turns)

target = [p2(1); p2(2)];

x=p1(1);y=p1(2);

moves = [x-1, y-2; x+1, y-2; x-1, y+2; x+1, y+2; x-2, y-1; x+2, y-1; x-2, y+1; x+2, y+1];

problem = struct('solver', 'intlinprog');

problem.f = ones(length(moves), 1);

problem.intcon = 1:length(moves);

problem.Aeq = moves';

problem.beq = target;

problem.lb = zeros(length(moves), 1);

problem.options = optimoptions('intlinprog', 'Display', 'off');

solution = round(intlinprog(problem));

turns=sum(solution);

end

[Walter Roberson]

This looks to me as if what it constructs is not the details of the path, but rather a count of how many of each kind of move would be used. Which I suppose is a valid interpretation of the question.

Answer 2

[Walter Roberson]

Given a grid, since you know the valid moves, if you label the nodes, you can automatically construct a table of source nodes and valid destination nodes. There are 8 different moves, so it is enough to construct 8 different sub-lists of sources and targets in parallel. Put all the sources and all the targets together into a pair of S and T lists, and G = digraph(S,T) . Now you can use shortestpath(G, source_node, target_node)

[Jan]

@Walter: Thanks, I've removed my answer, in which I confused "knights" with "kings". A problem of the language...

[Issy Cassidy]

what do you exactly mean by 'here are 8 different moves, so it is enough to construct 8 different sub-lists of sources and targets in parallel' ??? what exactly is the source list and target list? Additionally what it the significance of the parallel?

[Walter Roberson]

locs = reshape(1:81, 9, 9);

%move 1: move 1 right, 2 down: (+1,+2)
S1 = locs(1:end-1,1:end-2);
T1 = locs(2:end, 3:end);

%move 2: move 1 right, 2 up: (+1,-2)
S2 = locs(1:end-1, 3:end);
T2 = locs(2:end, 1:end-2);

Now do the same kind of thing for (+2,-1), (+2,+1), (-1,+2), (-1,-2), (-2, -1), (-2,+1), giving S1 through S8 and T1 through T8, extracting the proper subsets of locs in each case.

S = [S1(:); S2(:), S3(:), S4(:), S5(:), S6(:), S7(:), S8(:)];
T = [T1(:), T2(:), T3(:), T4(:), T5(:), T6(:), T7(:), T8(:)];

and then

G = digraph(S, T);