Рыцарь Самый короткий путь Шахматный вопрос

Ответ 1

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

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

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

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

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[]

EDIT:

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

Ответ 2

EDIT: См. ответ simon, где он исправил представленную здесь формулу.

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

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

Вы можете заметить шаблон здесь?

Несмотря на то, что мы можем видеть шаблон, очень трудно найти функцию 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 Day 1
И решения здесь

Ответ 3

Здесь правильное решение 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).

Ответ 4

Да, Dijkstra и 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).

Ответ 5

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

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

По какой-то причине (возможно, для упрощения или красоты или просто ошибки) они переместили знак 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>

Ответ 6

Ответ O (1) выше [fooobar.com/questions/66620/... от Mustafa Serdar Şanlı] на самом деле не работает. (Проверить (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()

Ответ 7

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

Ответ 8

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

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

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

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

Предположим, что мы сжимаем задачу до точки начала координат. Мы перейдем к тому, что на самом деле означает "vicinty", но на данный момент давайте просто напишем некоторые решения в чит-карте (происхождение внизу слева):

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 o 'часы перемещаются. Здесь есть две вещи:

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

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

• (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 и cheatsheet [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-часовое движение, и любой танец продиктован читшетом (который сам может быть в чит-карте).

Теперь: Как доказать, что это правильно. Недостаточно просто сравнить эти результаты с таблицей правильных ответов, потому что сама проблема не ограничена. Но мы можем сказать, что если расстояние Рыцаря квадрата s равно d, то если {m} - множество правовых движений из s, расстояние Найта (s + m) должно быть либо d-1, либо d + 1 для всех m. (Вам нужно доказательство этого?) Кроме того, должен быть хотя бы один такой квадрат, расстояние 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, такой, что расстояние (s + m) == d-1. Повторяйте, пока мы не достигнем начала.

Howzat?

Ответ 9

/*
This program takes two sets of cordinates on a 8*8 chessboard, representing the
starting and ending points of a knight 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 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 
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 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 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.

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

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

* Проверено на компиляторе DEV-С++ 4.9.9.2 (Программное обеспечение Bloodshed).

Ответ 10

Я думаю, что это также может помочь вам.

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

и используя Dynamic Programming для получения решения.

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

Ответ 11

Вот решение для этой конкретной проблемы, реализованной в 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__

Ответ 12

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 Qaru */
            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));
    }
}

Ответ 13

Просто рубиновый код из Graeme Pyle отвечает 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)

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

Ответ 14

здесь PHP-версия Jules May функционирует

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];
}

Ответ 15

Вот версия C, основанная на коде Mustafa Serdar Şanlı, которая работает на конечной плате:

#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));
    }
}

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

Ответ 16

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

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;
    }

}