Кратчайший путь коня на шахматной доске

Я готовился к предстоящему соревнованию по программированию и наткнулся на вопрос, который меня совершенно сбил с толку. Тем не менее, я чувствую, что эту концепцию я должен изучить сейчас, а не скрещивать пальцы, что она никогда не придет в голову.

В основном это фигура коня на шахматной доске. У вас есть два входа: начальное и конечное местоположение. Затем цель состоит в том, чтобы вычислить и распечатать кратчайший путь, по которому рыцарь может добраться до целевого места.

Я никогда не занимался вопросами кратчайшего пути и даже не знаю, с чего начать. Какую логику я использую для решения этой проблемы?

PS Если это имеет какое-то отношение, они хотят, чтобы вы дополняли обычные ходы коня, позволяя ему перемещаться к четырем углам квадрата, образованного (потенциально) восемью ходами, которые может сделать конь, учитывая, что центр поля находится местонахождение рыцаря.

Здесь у вас есть график, где все доступные ходы связаны (значение = 1), а недоступные ходы отключены (значение = 0), разреженная матрица будет иметь вид:

(a1,b3)=1,
(a1,c2)=1,
  .....

Кратчайший путь из двух точек на графике можно найти с помощью http://en.wikipedia.org/wiki/Dijkstra's_algorithm.

Псевдокод со страницы википедии:

function Dijkstra(Graph, source):
   for each vertex v in Graph:           // Initializations
       dist[v] := infinity               // Unknown distance function from source to v
       previous[v] := undefined          // Previous node in optimal path from source
   dist[source] := 0                     // Distance from source to source
   Q := the set of all nodes in Graph
   // All nodes in the graph are unoptimized - thus are in Q
   while Q is not empty:                 // The main loop
       u := vertex in Q with smallest dist[]
       if dist[u] = infinity:
          break                         // all remaining vertices are inaccessible from source
       remove u from Q
       for each neighbor v of u:         // where v has not yet been removed from Q.
           alt := dist[u] + dist_between(u, v) 
           if alt < dist[v]:             // Relax (u,v,a)
               dist[v] := alt
               previous[v] := u
   return dist[]

РЕДАКТИРОВАТЬ:

1. как придурок, сказал, что использование http://en.wikipedia.org/wiki/A*_algorithm может быть быстрее.
2. Самый быстрый способ - предварительно рассчитать все расстояния и сохранить их в полной матрице 8x8. ну, я бы назвал это читерством, и работает только потому, что проблема небольшая. Но иногда соревнования проверяют, насколько быстро работает ваша программа.
3. Главное, что если вы готовитесь к соревнованиям по программированию, вы должны знать общие алгоритмы, в том числе алгоритмы Дейкстры. Хорошей отправной точкой является чтение Introduction to AlgorithmsISBN 0-262-03384-4. Или вы можете попробовать википедию, http://en.wikipedia.org/wiki/List_of_algorithms

РЕДАКТИРОВАТЬ: см. Ответ Саймона , где он исправил формулу, представленную здесь.

На самом деле существует формула O (1)

Это изображение, которое я сделал, чтобы его визуализировать (квадраты, до которых может дотянуться конь на N- ^м ходу, окрашены в один цвет).

Вы можете заметить здесь закономерность?

Хотя мы можем видеть закономерность, действительно сложно найти функцию, f( x , y )которая возвращает количество ходов, необходимых для перехода от квадрата ( 0 , 0 )к квадрату.( x , y )

Но вот формула, которая работает, когда 0 <= y <= x

int f( int x , int y )
{
    int delta = x - y;

    if( y > delta )
        return 2 * ( ( y - delta ) / 3 ) + delta;
    else
        return delta - 2 * ( ( delta - y ) / 4 );
}

Примечание: этот вопрос был задан на SACO 2007, день 1,
и решения здесь.

Вот правильное решение O (1), но для случая, когда конь движется только как шахматный конь, и на бесконечной шахматной доске:

https://jsfiddle.net/graemian/5qgvr1ba/11/

Ключ к обнаружению этого - заметить закономерности, которые появляются, когда вы рисуете доску. На диаграмме ниже число в квадрате - это минимальное количество ходов, необходимых для достижения этого квадрата (вы можете использовать поиск в ширину, чтобы найти это):

Поскольку решение симметрично по осям и диагоналям, я нарисовал только случай x> = 0 и y> = x.

Нижний левый блок - это начальная позиция, а числа в блоках представляют минимальное количество ходов для достижения этих блоков.

Обратите внимание на 3 закономерности:

• Увеличивающиеся синие вертикальные группы по 4
• "Основные" красные диагонали (они идут от верхнего левого угла к нижнему правому, как обратная косая черта)
• "Вторичные" зеленые диагонали (ориентация такая же, как у красного)

(Убедитесь, что вы видите оба набора диагоналей как верхний левый и нижний правый. У них постоянное количество ходов. Диагонали нижнего левого верхнего правого угла намного сложнее.)

Вы можете вывести формулы для каждого. Желтые блоки - особые случаи. Итак, решение становится:

function getMoveCountO1(x, y) {

    var newXY = simplifyBySymmetry(x, y);

    x = newXY.x;
    y = newXY.y;

    var specialMoveCount = getSpecialCaseMoveCount(x ,y);

    if (specialMoveCount !== undefined)
        return specialMoveCount;

    else if (isVerticalCase(x, y))
        return getVerticalCaseMoveCount(x ,y);

    else if (isPrimaryDiagonalCase(x, y))
        return getPrimaryDiagonalCaseMoveCount(x ,y);

    else if (isSecondaryDiagonalCase(x, y))
        return getSecondaryDiagonalCaseMoveCount(x ,y);

}

с самыми сложными вертикальными группами:

function isVerticalCase(x, y) {

    return y >= 2 * x;

}

function getVerticalCaseMoveCount(x, y) {

    var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);

    var groupIndex = Math.floor( normalizedHeight / 4);

    var groupStartMoveCount = groupIndex * 2 + x;

    return groupStartMoveCount + getIndexInVerticalGroup(x, y);

}

function getIndexInVerticalGroup(x, y) {

    return getNormalizedHeightForVerticalGroupCase(x, y) % 4;

}

function getYOffsetForVerticalGroupCase(x) {

    return x * 2;

}

function getNormalizedHeightForVerticalGroupCase(x, y) {

    return y - getYOffsetForVerticalGroupCase(x);

}

См. Скрипку для других случаев.

Может быть, я пропустил более простые или элегантные узоры? Если так, я бы с удовольствием их увидел. В частности, я заметил некоторые диагональные узоры в синих вертикальных корпусах, но я не исследовал их. Тем не менее, это решение по-прежнему удовлетворяет ограничению O (1).

Очень интересная проблема, с которой я столкнулся недавно. После поиска некоторых решений я попытался восстановить аналитическую формулу ( O(1) time and space complexity), приведенную в решениях SACO 2007 Day 1 .

Прежде всего, я хочу поблагодарить Грэма Пайла за очень красивую визуализацию, которая помогла мне исправить формулу.

По какой-то причине (может быть, для упрощения или красоты или просто по ошибке) они перенесли minusзнак в floorоператор, в результате получилась неправильная формула floor(-a) != -floor(a) for any a.

Вот правильная аналитическая формула:

var delta = x-y;
if (y > delta) {
    return delta - 2*Math.floor((delta-y)/3);
} else {
    return delta - 2*Math.floor((delta-y)/4);
}

Формула работает для всех пар (x, y) (после применения осей и диагональной симметрии) за исключением угловых (1,0) и (2,2), которые не удовлетворяют шаблону и жестко запрограммированы в следующем фрагменте:

function distance(x,y){
     // axes symmetry 
     x = Math.abs(x);
     y = Math.abs(y);
     // diagonal symmetry 
     if (x < y) {
        t = x;x = y; y = t;
     }
     // 2 corner cases
     if(x==1 && y == 0){
        return 3;
     }
     if(x==2 && y == 2){
        return 4;
     }
    
    // main formula
    var delta = x-y;
		if(y>delta){
  		return delta - 2*Math.floor((delta-y)/3);
  	}
  	else{
  		return delta - 2*Math.floor((delta-y)/4);
  	}
}


$body = $("body");
var html = "";
for (var y = 20; y >= 0; y--){
	html += '<tr>';
	for (var x = 0; x <= 20; x++){
  	html += '<td style="width:20px; border: 1px solid #cecece" id="'+x+'_'+y+'">'+distance(x,y)+'</td>';
  }
  html += '</tr>';
}

html = '<table>'+html+'</table>';
$body.append(html);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

Примечание: jQuery используется только для иллюстрации, код см. В distanceфункции.

Да, Дейкстра и BFS дадут вам ответ, но я думаю, что шахматный контекст этой проблемы дает знания, которые могут дать решение, которое намного быстрее, чем общий алгоритм кратчайшего пути, особенно на бесконечной шахматной доске.

Для простоты опишем шахматную доску как плоскость (x, y). Цель состоит в том, чтобы найти кратчайший путь от (x0, y0) до (x1, y1), используя только возможные шаги (+ -1, + -2), (+ -2, + -1) и (+ -2 , + -2), как описано в PS вопроса

Вот новое наблюдение: нарисуйте квадрат с углами (x-4, y-4), (x-4, y + 4), (x + 4, y-4), (x + 4, y + 4) . Этот набор (назовем его S4) содержит 32 точки. Кратчайший путь от любой из этих 32 точек до (x, y) требует ровно двух ходов .

Кратчайший путь от любой из 24 точек множества S3 (определяется аналогично) до (x, y) требует как минимум двух ходов .

Следовательно, если | x1-x0 |> 4 или | y1-y0 |> 4, кратчайший путь от (x0, y0) до (x1, y1) ровно на два хода больше, чем кратчайший путь от (x0, y0) до S4. И последнюю проблему можно быстро решить с помощью простой итерации.

Пусть N = max (| x1-x0 |, | y1-y0 |). Если N> = 4, то кратчайший путь от (x0, y0) до (x1, y1) имеет ceil (N / 2) шагов.

Ответ O (1) выше [ https://stackoverflow.com/a/8778592/4288232 Мустафа Сердар Шанлы] на самом деле не работает. (Отметьте (1,1) или (3,2) или (4,4), кроме очевидных крайних случаев (1,0) или (2,2)).

Ниже представлено гораздо более уродливое решение (python), которое действительно работает (с добавленными «тестами»):

def solve(x,y):
        x = abs(x)
        y = abs(y)
        if y > x:
            temp=y
            y=x
            x=temp  
        if (x==2 and y==2):
            return 4
        if (x==1 and y==0):
            return 3

    if(y == 0 or float(y) / float(x) <= 0.5):
        xClass = x % 4
        if (xClass == 0):
            initX = x/2
        elif(xClass == 1):
            initX = 1 + (x/2)
        elif(xClass == 2):
            initX = 1 + (x/2)
        else:
            initX = 1 + ((x+1)/2)

        if (xClass > 1):
            return initX - (y%2)
        else:
            return initX + (y%2)
    else:
        diagonal = x - ((x-y)/2)
        if((x-y)%2 == 0):
            if (diagonal % 3 == 0):
                return (diagonal/3)*2
            if (diagonal % 3 == 1):
                return ((diagonal/3)*2)+2
            else:
                return ((diagonal/3)*2)+2
        else:
            return ((diagonal/3)*2)+1


def test():
    real=[
    [0,3,2,3,2,3,4,5,4,5,6,7,6,7],
    [3,2,1,2,3,4,3,4,5,6,5,6,7,8],
    [2,1,4,3,2,3,4,5,4,5,6,7,6,7],
    [3,2,3,2,3,4,3,4,5,6,5,6,7,8],
    [2,3,2,3,4,3,4,5,4,5,6,7,6,7],
    [3,4,3,4,3,4,5,4,5,6,5,6,7,8],
    [4,3,4,3,4,5,4,5,6,5,6,7,6,7],
    [5,4,5,4,5,4,5,6,5,6,7,6,7,8],
    [4,5,4,5,4,5,6,5,6,7,6,7,8,7],
    [5,6,5,6,5,6,5,6,7,6,7,8,7,8],
    [6,5,6,5,6,5,6,7,6,7,8,7,8,9],
    [7,6,7,6,7,6,7,6,7,8,7,8,9,8]]

    for x in range(12):
        for y in range(12):
            res = solve(x,y)
            if res!= real[x][y]:
                print (x, y), "failed, and returned", res, "rather than", real[x][y]
            else:
               print (x, y), "worked. Cool!"

test()

Что вам нужно сделать, так это представить возможные ходы коня в виде графика, где каждая позиция на доске является узлом, а возможные ходы в другую позицию - ребром. Алгоритм Дейкстры не нужен, потому что каждое ребро имеет одинаковый вес или расстояние (все они так же просты или коротки). Вы можете просто выполнить поиск BFS от начальной точки до конечной позиции.

Решение из первых принципов на Python

Впервые я столкнулся с этой проблемой в тесте Codility. Мне дали 30 минут на ее решение - мне потребовалось значительно больше времени, чтобы получить такой результат! Проблема заключалась в следующем: сколько ходов нужно коню, чтобы перейти от 0,0 к x, y, используя только допустимые ходы коня. x и y были более или менее неограниченными (поэтому мы не говорим здесь о простой шахматной доске 8x8).

Они хотели решение O (1). Мне нужно было решение, в котором программа явно решала проблему (т. Е. Я хотел чего-то более очевидного, чем шаблон Грэма - шаблоны имеют привычку ломаться там, где вы не смотрите), и я действительно хотел не полагаться на неоспоримая формула, как в решении Мустафы

Итак, вот мое решение, чего оно стоит. Начнем, как и другие, с того, что отметим, что решение симметрично относительно осей и диагоналей, поэтому нам нужно решать только для 0> = y> = x. Для простоты объяснения (и кода) я собираюсь обратить проблему: конь начинает с x, y и стремится к 0,0.

Предположим, мы сократили проблему до окрестности источника. Мы узнаем, что на самом деле означает «близость», со временем, а пока давайте просто запишем некоторые решения в шпаргалке (происхождение внизу слева):

2 1 4 3
3 2 1 2
0 3 2 3

Итак, учитывая x, y в сетке, мы можем просто считать количество ходов в начало координат.

Если мы начали за пределами сетки, мы должны вернуться к ней. Мы вводим «среднюю линию», которая представляет собой линию, представленную y = x / 2. Любой конь в позиции x, y на этой линии может вернуться к шпаргалке, используя серию ходов на 8 часов (то есть: (-2, -1) ходов). Если x, y лежит выше средней линии, тогда нам понадобится последовательность движений на 8 часов и 7 часов, а если она лежит ниже средней линии, нам понадобится последовательность из 8 часов и 10 часов. Часы идут. Здесь следует отметить две вещи:

• Эти последовательности доказуемо являются кратчайшими путями. (Хочешь, чтобы я это доказал, или это очевидно?)
• Нас волнует только количество таких ходов. Мы можем комбинировать ходы в любом порядке.

Итак, давайте посмотрим на движения выше средней линии. Мы утверждаем, что:

• (dx; dy) = (2,1; 1,2) (n8; n7) (матричная запись, без математического набора - вектор-столбец (dx; dy) равен квадратной матрице, умноженной на вектор-столбец (n8; n7) - количество ходов на 8 часов и количество ходов на 7 часов), и аналогично;

• (dx; dy) = (2,2; 1, -1) (n8; n10)

Я утверждаю, что dx, dy будут примерно равны (x, y), поэтому (x-dx, y-dy) будет в непосредственной близости от начала координат (независимо от того, какой окажется «близость»).

Две строки в коде, которые вычисляют эти термины, являются решением этих проблем, но они выбраны так, чтобы иметь некоторые полезные свойства:

• Формула выше средней линии перемещает (x, y) в одно из (0,0), (1,1) или (2,2).
• Формула ниже средней линии перемещает (x, y) в одно из (0,0), (1,0), (2,0) или (1,1).

(Хотите доказательства этого?) Итак, расстояние до Рыцаря будет суммой n7, n8, n10 и шпаргалки [x-dx, y-dy], и наша шпаргалка сводится к следующему:

. . 4
. 2 .
0 3 2

Но это еще не конец истории. Посмотрите на 3 в нижнем ряду. Единственные способы достичь этого:

• Мы начали там, или
• Мы переместились туда на 8 и 10 часов. Но если последний ход был на 8 часов (что ему положено, поскольку мы можем делать ходы в любом порядке), то мы должны были пройти через (3,1), расстояние до которого на самом деле равно 2 (как вы можете см. из оригинальной шпаргалки). Итак, что нам нужно сделать, так это вернуться на один ход на 8 часов, сэкономив всего два хода.

Аналогичную оптимизацию можно провести с цифрой 4 вверху справа. Помимо начала, единственный способ добраться до него - это переместиться на 8 часов от точки (4,3). Этого нет в шпаргалке, но если бы он был там, его расстояние было бы 3, потому что вместо этого мы могли бы привязать 7 часов к (3,1), что имеет расстояние только 2. Итак, мы должны отследить один Переместитесь на 8 часов, а затем перейдите на 7 часов вперед.

Итак, нам нужно добавить в шпаргалку еще одно число:

. . 4
. 2 . 2
0 3 2

(Примечание: существует множество оптимизаций обратного отслеживания из (0,1) и (0,2), но поскольку решатель никогда не приведет нас туда, нам не нужно о них беспокоиться.)

Итак, вот некоторый код Python для оценки этого:

def knightDistance (x, y):
    # normalise the coordinates
    x, y = abs(x), abs(y)
    if (x<y): x, y = y, x
    # now 0 <= y <= x

    # n8 means (-2,-1) (8 o'clock), n7 means (-1,-2) (7 o'clock), n10 means (-2,+1) (10 o'clock)
    if (x>2*y):
        # we're below the midline.  Using 8- & 10-o'clock moves
        n7, n8, n10 = 0,  (x + 2*y)//4,  (x - 2*y + 1)//4
    else:
        # we're above the midline.  Using 7- and 8-o'clock moves
        n7, n8, n10 = (2*y - x)//3, (2*x - y)//3,  0
    x -= 2*n8 + n7 + 2*n10
    y -= n8 + 2*n7 - n10
    # now 0<=x<=2, and y <= x.  Also (x,y) != (2,1)

    # Try to optimise the paths.
    if (x, y)==(1, 0): # hit the  3.  Did we need to?
        if (n8>0): # could have passed through the 2 at 3,1.  Back-up
            x, y = 3, 1; n8-=1;
    if (x, y)==(2, 2): # hit the 4.  Did we need to?
        if (n8>0): # could have passed through a 3 at 4,3.  Back-up, and take 7 o'clock to 2 at 3,1
            x, y = 3, 1; n8-=1; n7+=1

    # Almost there.  Now look up the final leg
    cheatsheet = [[0, 3, 2], [2, None, 2], [4]]
    return n7 + n8 + n10 + cheatsheet [y][x-y]

Между прочим, если вы хотите узнать реальный маршрут, этот алгоритм также обеспечивает это: это просто последовательность из n7 7-часовых ходов, за которыми следуют (или перемежаются) n8 8-часовых ходов, n10 10- o'clock движется, и любой танец продиктован шпаргалкой (которая сама по себе может быть в шпаргалке).

Теперь: как доказать, что это правда. Недостаточно просто сравнить эти результаты с таблицей правильных ответов, потому что сама задача неограниченна. Но мы можем сказать, что если расстояние коня до квадрата s равно d, то если {m} - это набор разрешенных ходов от s, расстояние коня (s + m) должно быть либо d-1, либо d + 1. для всех м. (Вам нужно доказательство этого?) Кроме того, должен быть хотя бы один такой квадрат с расстоянием d-1, если только s не является началом координат. Итак, мы можем доказать правильность, показав, что это свойство выполняется для каждого квадрата. Таким образом:

def validate (n):

    def isSquareReasonable (x, y):
        d, downhills = knightDistance (x, y), 0
        moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1,  2)]
        for dx, dy in moves:
            dd = knightDistance (x+dx,  y+dy)
            if (dd == d+1): pass
            elif (dd== d-1): downhills += 1
            else: return False;
        return (downhills>0) or (d==0)

    for x in range (0,  n+1):
        for y in range (0,  n+1):
            if not isSquareReasonable (x,  y): raise RuntimeError ("Validation failed")

В качестве альтернативы, мы можем доказать правильность любого квадрата s, пройдя путь от спуска до начала координат. Сначала проверьте s на разумность, как указано выше, затем выберите любое s + m такое, что distance (s + m) == d-1. Повторяйте, пока не дойдете до начала координат.

Howzat?

/*
This program takes two sets of cordinates on a 8*8 chessboard, representing the
starting and ending points of a knight's path.
The problem is to print the cordinates that the knight traverses in between, following
the shortest path it can take.
Normally this program is to be implemented using the Djikstra's algorithm(using graphs)
but can also be implemented using the array method.
NOTE:Between 2 points there may be more than one shortest path. This program prints
only one of them.
*/

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

int m1=0,m2=0;

/*
This array contains three columns and 37 rows:
The rows signify the possible coordinate differences.
The columns 1 and 2 contains the possible permutations of the row and column difference 
between two positions on a chess board;
The column 3 contains the minimum number of steps involved in traversing the knight's 
path with the given permutation*/

int arr[37][3]={{0,0,0},{0,1,3},{0,2,2},{0,3,3},{0,4,2},{0,5,3},{0,6,4},{0,7,5},    {1,1,2},{1,2,1},{1,3,2},{1,4,3},{1,5,4},{1,6,3},{1,7,4},{2,2,4},{2,3,3},{2,4,2},
            {2,5,3},{2,6,3},{2,7,5},{3,3,2},{3,4,3},{3,5,4},{3,6,3},{3,7,4},{4,4,4},{4,5,3},{4,6,4},{4,7,5},{5,5,4},{5,6,5},{5,7,4},{6,6,5},{6,7,5},{7,7,6}};

void printMoves(int,int,int,int,int,int);
void futrLegalMove(int,int,int,int);
main()
{
  printf("KNIGHT'S SHORTEST PATH ON A 8*8 CHESSBOARD :\n");
  printf("------------------------------------------");
  printf("\nThe chessboard may be treated as a 8*8 array here i.e. the (1,1) ");
  printf("\non chessboard is to be referred as (0,0) here and same for (8,8) ");
  printf("\nwhich is to be referred as (7,7) and likewise.\n");
  int ix,iy,fx,fy;
  printf("\nEnter the initial position of the knight :\n");
  scanf("%d%d",&ix,&iy);
  printf("\nEnter the final position to be reached :\n");
  scanf("%d%d",&fx,&fy);
  int px=ix,py=iy;
  int temp;
  int tx,ty;
  printf("\nThe Knight's shortest path is given by :\n\n");
  printf("(%d, %d)",ix,iy);
  futrLegalMove(px,py,m1,m2);
  printMoves(px,py,fx,fy,m1,m2);
   getch();
} 

/*
  This method checkSteps() checks the minimum number of steps involved from current
  position(a & b) to final position(c & d) by looking up in the array arr[][].
*/

int checkSteps(int a,int b,int c,int d)
{  
    int xdiff, ydiff;
    int i, j;
    if(c>a)
        xdiff=c-a;
    else
        xdiff=a-c;
    if(d>b)
        ydiff=d-b;
    else
        ydiff=b-d;
    for(i=0;i<37;i++)
        {
            if(((xdiff==arr[i][0])&&(ydiff==arr[i][1])) || ((xdiff==arr[i][1])&& (ydiff==arr[i] [0])))
            {
                j=arr[i][2];break;
            }
        }

        return j;
}   

/*
This method printMoves() prints all the moves involved.
*/

void printMoves(int px,int py, int fx, int fy,int a,int b)
{    
 int temp;
 int tx,ty;
 int t1,t2;
  while(!((px==fx) && (py==fy)))
  {   
      printf(" --> ");
      temp=checkSteps(px+a,py+b,fx,fy);
      tx=px+a;
      ty=py+b;
      if(!(a==2 && b==1))
      {if((checkSteps(px+2,py+1,fx,fy)<temp) && checkMove(px+2,py+1))
      {temp=checkSteps(px+2,py+1,fx,fy);
       tx=px+2;ty=py+1;}}
      if(!(a==2 && b==-1))
      {if((checkSteps(px+2,py-1,fx,fy)<temp) && checkMove(px+2,py-1))
      {temp=checkSteps(px+2,py-1,fx,fy);
       tx=px+2;ty=py-1;}}
      if(!(a==-2 && b==1))
      {if((checkSteps(px-2,py+1,fx,fy)<temp) && checkMove(px-2,py+1))
      {temp=checkSteps(px-2,py+1,fx,fy);
       tx=px-2;ty=py+1;}}
      if(!(a==-2 && b==-1))
      {if((checkSteps(px-2,py-1,fx,fy)<temp) && checkMove(px-2,py-1))
      {temp=checkSteps(px-2,py-1,fx,fy);
       tx=px-2;ty=py-1;}}
      if(!(a==1 && b==2))
      {if((checkSteps(px+1,py+2,fx,fy)<temp) && checkMove(px+1,py+2))
      {temp=checkSteps(px+1,py+2,fx,fy);
       tx=px+1;ty=py+2;}}
      if(!(a==1 && b==-2))
      {if((checkSteps(px+1,py-2,fx,fy)<temp) && checkMove(px+1,py-2))
      {temp=checkSteps(px+1,py-2,fx,fy);
       tx=px+1;ty=py-2;}}
      if(!(a==-1 && b==2))
      {if((checkSteps(px-1,py+2,fx,fy)<temp) && checkMove(px-1,py+2))
      {temp=checkSteps(px-1,py+2,fx,fy);
       tx=px-1;ty=py+2;}}
      if(!(a==-1 && b==-2))
      {if((checkSteps(px-1,py-2,fx,fy)<temp) && checkMove(px-1,py-2))
      {temp=checkSteps(px-1,py-2,fx,fy);
       tx=px-1;ty=py-2;}}
       t1=tx-px;//the step taken in the current move in the x direction.
       t2=ty-py;//" " " " " " " " " " " " " " " " " " " " " y " " " " ".
       px=tx;
       py=ty;
       printf("(%d, %d)",px,py);
       futrLegalMove(px,py,t1,t2);
       a=m1;
       b=m2;
   }

} 

/*
The method checkMove() checks whether the move in consideration is beyond the scope of
board or not.
*/   

int checkMove(int a, int b)
{
    if(a>7 || b>7 || a<0 || b<0)
        return 0;
    else
        return 1;
}

/*Out of the 8 possible moves, this function futrLegalMove() sets the valid move by
  applying the following constraints
      1. The next move should not be beyond the scope of the board.
      2. The next move should not be the exact opposite of the previous move.
  The 1st constraint is checked by sending all possible moves to the checkMove() 
  method;
  The 2nd constraint is checked by passing as parameters(i.e. a and b) the steps of the 
  previous move and checking whether or not it is the exact opposite of the current move.
*/

void futrLegalMove(int px,int py,int a,int b)
{
     if(checkMove(px+2,py+1) && (a!=-2 && b!=-1))
         m1=2,m2=1;
     else
     {
         if(checkMove(px+2,py-1)&& (a!=-2 && b!=1))
             m1=2,m2=-1;
     else
     {
         if(checkMove(px-2,py+1)&& (a!=2 && b!=-1))
              m1=-2,m2=1;
     else
     {
         if(checkMove(px-2,py-1)&& (a!=2 && b!=1))
               m1=-2,m2=-1;
     else
     {
         if(checkMove(px+1,py+2)&& (b!=-2 && a!=-1))
               m2=2,m1=1;
     else
     {
         if(checkMove(px+1,py-2)&& (a!=-1 && b!=2))
               m2=-2,m1=1;
     else
     {
         if(checkMove(px-1,py+2)&& (a!=1 && b!=-2))
               m2=2,m1=-1;
     else
     {
         if(checkMove(px-1,py-2)&& (a!=1 && b!=2))
               m2=-2,m1=-1;
     }}}}}}}
}

//End of Program.

Я еще не изучал графики ... что касается проблемы реализации этого с помощью простых массивов, я не мог найти никакого другого решения, кроме этого. Я рассматривал позиции не как ряды и файлы (обычная шахматная запись), а как индексы массива. К вашему сведению, это только для шахматной доски 8 * 8. Всегда приветствуются любые советы по улучшению.

* Комментарии должны быть достаточными для вашего понимания логики. Однако вы всегда можете спросить.

* Проверено на компиляторе DEV-C ++ 4.9.9.2 (Bloodshed Software).

Думаю, это тоже может вам помочь ..

NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2)); 

и используя динамическое программирование, чтобы получить решение.

PS: Он вроде как использует BFS без необходимости объявлять узлы и ребра графа.

Вот решение этой конкретной проблемы, реализованное на Perl. Он покажет один из кратчайших путей - в некоторых случаях их может быть несколько.

Я не использовал ни один из описанных выше алгоритмов - но было бы неплохо сравнить его с другими решениями.

#!/usr/local/bin/perl -w

use strict;

my $from = [0,0];
my $to   = [7,7];

my $f_from = flat($from);
my $f_to   = flat($to);

my $max_x = 7;
my $max_y = 7;
my @moves = ([-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1]);
my %squares = ();
my $i = 0;
my $min = -1;

my @s = ( $from );

while ( @s ) {

   my @n = ();
   $i++;

   foreach my $s ( @s ) {
       unless ( $squares{ flat($s) } ) {
            my @m = moves( $s );
            push @n, @m;
            $squares{ flat($s) } = { i=>$i, n=>{ map {flat($_)=>1} @m }, };

            $min = $i if $squares{ flat($s) }->{n}->{$f_to};
       }
   }

   last if $min > -1;
   @s = @n;
}

show_path( $f_to, $min );

sub show_path {
    my ($s,$i) = @_;

    return if $s eq $f_from;

    print "$i => $f_to\n" if $i == $min;

    foreach my $k ( keys %squares ) {
       if ( $squares{$k}->{i} == $i && $squares{$k}->{n}->{$s} ) {
            $i--;
            print "$i => $k\n";
            show_path( $k, $i );
            last;
       }
    }
}

sub flat { "$_[0]->[0],$_[0]->[1]" }

sub moves {
    my $c = shift;
    my @s = ();

    foreach my $m ( @moves ) {
       my $x = $c->[0] + $m->[0];
       my $y = $c->[1] + $m->[1];

       if ( $x >= 0 && $x <=$max_x && $y >=0 && $y <=$max_y) {
           push @s, [$x, $y];
       }
    }
    return @s;
}

__END__

public class Horse {

    private int[][] board;
    private int[] xer = { 2, 1, -1, -2, -2, -1, 1, 2 };
    private int[] yer = { 1, 2, 2, 1, -1, -2, -2, -1 };
    private final static int A_BIG_NUMBER = 10000;
    private final static int UPPER_BOUND = 64;


    public Horse() {
        board =  new int[8][8];
    }

    private int solution(int x, int y, int destx, int desty, int move) {

        if(move == UPPER_BOUND) {
            /* lets put an upper bound to avoid stack overflow */
            return A_BIG_NUMBER;
        }

        if(x == 6 && y ==5) {
            board[6][5] = 1;
            return 1;
        }
        int min = A_BIG_NUMBER;
        for (int i = 0 ; i < xer.length; i++) {
            if (isMoveGood(x + xer[i], y + yer[i])) {
                if(board[x + xer[i]][y + yer[i]] != 0) {
                    min = Integer.min(min, 1 + board[x +xer[i]] [y +yer[i]]);                   
                } else {
                    min = Integer.min(min, 1 + solution(x + xer[i], y + yer[i], destx, desty, move + 1));   
                }                   
            }
        }   
        board[x][y] = min;
        return min;
    }


    private boolean isMoveGood(int x, int y) {
        if (x >= 0 && x < board.length && y >= 0 && y < board.length)
            return true;
        return false;
    }


    public static void main(String[] args) {

        int destX = 6;
        int destY = 7;
        final Horse h = new Horse();
        System.out.println(h.solution(0, 0, destX, destY, 0));
    }
}

Просто рубиновый код из jsfiddle ответа Грэма Пайла выше , выделил весь дополнительный код и преобразовал оставшийся в рубин, чтобы получить решение по его алгоритму, похоже, работает. Тем не менее, все еще тестирую:

def getBoardOffset(board)
  return board.length / 2
end

def setMoveCount(x, y, count, board)
  offset = getBoardOffset(board)
  board[y + offset][x + offset] = count
end

def getMoveCount(x, y, board)
    offset = getBoardOffset(board)
    row = board[y + offset]
    return row[x + offset]
end

def isBottomOfVerticalCase(x, y)
    return (y - 2 * x) % 4 == 0
end

def isPrimaryDiagonalCase(x, y)
    return (x + y) % 2 == 0
end

def isSecondaryDiagonalCase(x, y)
    return (x + y) % 2 == 1
end

def simplifyBySymmetry(x, y)
    x = x.abs
    y = y.abs
    if (y < x)
      t = x
      x = y
      y = t
    end
    return {x: x, y: y}
end

def getPrimaryDiagonalCaseMoveCount(x, y)
    var diagonalOffset = y + x
    var diagonalIntersect = diagonalOffset / 2
    return ((diagonalIntersect + 2) / 3).floor * 2
end

def getSpecialCaseMoveCount(x, y)
    specials = [{
            x: 0,
            y: 0,
            d: 0
        },
        {
            x: 0,
            y: 1,
            d: 3
        },
        {
            x: 0,
            y: 2,
            d: 2
        },
        {
            x: 0,
            y: 3,
            d: 3
        },
        {
            x: 2,
            y: 2,
            d: 4
        },
        {
            x: 1,
            y: 1,
            d: 2
        },
        {
            x: 3,
            y: 3,
            d: 2
        }
    ];
    matchingSpecial=nil
    specials.each do |special|
      if (special[:x] == x && special[:y] == y)
        matchingSpecial = special
      end
    end
    if (matchingSpecial)
      return matchingSpecial[:d]
    end
end

def isVerticalCase(x, y)
  return y >= 2 * x
end

def getVerticalCaseMoveCount(x, y)
    normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y)
    groupIndex = (normalizedHeight/4).floor
    groupStartMoveCount = groupIndex * 2 + x
    return groupStartMoveCount + getIndexInVerticalGroup(x, y)
end

def getIndexInVerticalGroup(x, y)
    return getNormalizedHeightForVerticalGroupCase(x, y) % 4
end

def getYOffsetForVerticalGroupCase(x) 
    return x * 2
end

def getNormalizedHeightForVerticalGroupCase(x, y)
    return y - getYOffsetForVerticalGroupCase(x)
end

def getSecondaryDiagonalCaseMoveCount(x, y)
    diagonalOffset = y + x
    diagonalIntersect = diagonalOffset / 2 - 1
    return ((diagonalIntersect + 2) / 3).floor * 2 + 1
end

def getMoveCountO1(x, y)
    newXY = simplifyBySymmetry(x, y)
    x = newXY[:x]
    y = newXY[:y]
    specialMoveCount = getSpecialCaseMoveCount(x ,y)
    if (specialMoveCount != nil)
      return specialMoveCount
    elsif (isVerticalCase(x, y))
      return getVerticalCaseMoveCount(x ,y)
    elsif (isPrimaryDiagonalCase(x, y))
      return getPrimaryDiagonalCaseMoveCount(x ,y)
    elsif (isSecondaryDiagonalCase(x, y))
      return getSecondaryDiagonalCaseMoveCount(x ,y)
    end
end

def solution(x ,y)
  return getMoveCountO1(x, y)
end


puts solution(0,0)

Единственное намерение - сэкономить время на преобразовании кода, если кому-то нужен полный код.

вот версия PHP функции Жюля Мэя

function knightDistance($x, $y)
{
    $x = abs($x);
    $y = abs($y);

    if($x < $y)
    {
        $tmp = $x;
        $x = $y;
        $y = $tmp;
    }

    if($x > 2 * $y)
    {
        $n7 = 0;
        $n8 = floor(($x + 2*$y) / 4);
        $n10 = floor(($x - 2*$y +1) / 4);
    }
    else
    {
        $n7 = floor((2*$y - $x) / 3);
        $n8 = floor((2*$x - $y) / 3);
        $n10 = 0;
    }

    $x -= 2 * $n8 + $n7 + 2 * $n10;
    $y -= $n8 + 2 * $n7 - $n10;

    if($x == 1 && $y == 0)
    {
        if($n8 > 0)
        {
            $x = 3;
            $y = 1;
            $n8--;
        }
    }
    if($x == 2 && $y == 2)
    {
        if($n8 > 0)
        {
            $x = 3;
            $y = 1;
            $n8--;
            $n7++;
        }
    }

    $cheatsheet = [[0, 3, 2], [2, 0, 2], [4]];

    return $n7 + $n8 + $n10 + $cheatsheet [$y][$x-$y];
}

Вот моя программа. Это не идеальное решение. В функцию рекурсии нужно внести множество изменений. Но конечный результат идеален. Пытался немного оптимизировать.

public class KnightKing2 {
    private static int tempCount = 0;

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int ip1 = Integer.parseInt(in.nextLine().trim());
        int ip2 = Integer.parseInt(in.nextLine().trim());
        int ip3 = Integer.parseInt(in.nextLine().trim());
        int ip4 = Integer.parseInt(in.nextLine().trim());
        in.close();
        int output = getStepCount(ip1, ip2, ip3, ip4);
        System.out.println("Shortest Path :" + tempCount);

    }

    // 2 1 6 5 -> 4
    // 6 6 5 5 -> 2

    public static int getStepCount(int input1, int input2, int input3, int input4) {
        return recurse(0, input1, input2, input3, input4);

    }

    private static int recurse(int count, int tx, int ty, int kx, int ky) {

        if (isSolved(tx, ty, kx, ky)) {
            int ccount = count+1;
            System.out.println("COUNT: "+count+"--"+tx+","+ty+","+ccount);
            if((tempCount==0) || (ccount<=tempCount)){
                tempCount = ccount;
            }
            return ccount;
        }

            if ((tempCount==0 || count < tempCount) && ((tx < kx+2) && (ty < ky+2))) {
                if (!(tx + 2 > 8) && !(ty + 1 > 8)) {
                    rightTop(count, tx, ty, kx, ky);

                }
                if (!(tx + 2 > 8) && !(ty - 1 < 0)) {
                    rightBottom(count, tx, ty, kx, ky);
                }
                if (!(tx + 1 > 8) && !(ty + 2 > 8)) {
                    topRight(count, tx, ty, kx, ky);
                }
                if (!(tx - 1 < 0) && !(ty + 2 > 8)) {
                    topLeft(count, tx, ty, kx, ky);
                }
                if (!(tx + 1 > 8) && !(ty - 2 < 0)) {
                     bottomRight(count, tx, ty, kx, ky);
                }
                if (!(tx - 1 < 0) && !(ty - 2 < 0)) {
                     bottomLeft(count, tx, ty, kx, ky);
                }
                if (!(tx - 2 < 0) && !(ty + 1 > 8)) {
                    leftTop(count, tx, ty, kx, ky);
                }
                if (!(tx - 2 < 0) && !(ty - 1 < 0)) {
                    leftBottom(count, tx, ty, kx, ky);
                }
            }

        return count;

    }

    private static int rightTop(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 2, ty + 1, kx, ky);

    }

    private static int topRight(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 1, ty + 2, kx, ky);
    }

    private static int rightBottom(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 2, ty - 1, kx, ky);
    }

    private static int bottomRight(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx + 1, ty - 2, kx, ky);
    }

    private static int topLeft(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 1, ty + 2, kx, ky);
    }

    private static int bottomLeft(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 1, ty - 2, kx, ky);
    }

    private static int leftTop(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 2, ty + 1, kx, ky);
    }

    private static int leftBottom(int count, int tx, int ty, int kx, int ky) {
        return count + recurse(count + 1, tx - 2, ty - 1, kx, ky);
    }

    private static boolean isSolved(int tx, int ty, int kx, int ky) {
        boolean solved = false;
        if ((tx == kx) && (ty == ky)) {
            solved = true;
        } else if ((tx + 2 == kx) && (ty + 1 == ky)) { // right top
            solved = true;
        } else if ((tx + 2 == kx) && (ty - 1 == ky)) { // right bottom
            solved = true;
        } else if ((ty + 2 == ky) && (tx + 1 == kx)) {// top right
            solved = true;
        } else if ((ty + 2 == ky) && (tx - 1 == kx)) {// top left
            solved = true;
        } else if ((tx - 2 == kx) && (ty + 1 == ky)) { // left top
            solved = true;
        } else if ((tx - 2 == kx) && (ty - 1 == ky)) {// left bottom
            solved = true;
        } else if ((ty - 2 == ky) && (tx + 1 == kx)) { // bottom right
            solved = true;
        } else if ((ty - 2 == ky) && (tx - 1 == kx)) { // bottom left
            solved = true;
        }

        return solved;
    }

}

Вот версия C, основанная на коде Мустафы Сердара Шанлы, которая работает для конечной доски:

#include <stdio.h>
#include <math.h>

#define test(x1, y1, x2, y2) (sx == x1 && sy == y1 &&tx == x2 &&ty == y2) || (sx == x2 && sy == y2 && tx == x1 && ty==y1)

int distance(int sx, int sy, int tx, int ty) {
    int x, y, t;
    double delta;

    // special corner cases 
    if (test(1, 1, 2, 2) || 
        test(7, 7, 8, 8) || 
        test(7, 2, 8, 1) || 
        test(1, 8, 2, 7))
        return 4;

    // axes symmetry 
    x = abs(sx - tx);
    y = abs(sy - ty);

    // diagonal symmetry 
    if (x < y) {
        t = x;
        x = y;
        y = t;
    }

    // 2 corner cases
    if (x == 1 && y == 0)
        return 3;
    if (x == 2 && y == 2)
        return 4;

    // main
    delta = x - y;
    if (y > delta) {
        return (int)(delta - 2 * floor((delta - y) / 3));
    }
    else {
        return (int)(delta - 2 * floor((delta - y) / 4));
    }
}

Проверьте это здесь с доказательством против рекурсивного решения