清空筛选条件
清空筛选条件

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??

1 次查看（过去 30 天）
Arslan Ahmad
Arslan Ahmad 2018-2-14
评论： Walter Roberson 2018-2-19
my problem is regarding how to find shortest path conditioning

请先登录，再回答此问题。

采纳的回答

Arslan Ahmad
Arslan Ahmad 2018-2-19
编辑：Walter Roberson 2018-2-19
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
  1 个评论
Walter Roberson
Walter Roberson 2018-2-19
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.

请先登录，再进行评论。

更多回答（1 个）

Walter Roberson
Walter Roberson 2018-2-15
编辑：Walter Roberson 2018-2-15
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)
  3 个评论
显示 1更早的评论
Issy Cassidy
Issy Cassidy 2018-2-15
编辑：Issy Cassidy 2018-2-15
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
Walter Roberson 2018-2-15
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);

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Board games 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by