Najkrótsza ścieżka rycerza na szachownicy

Ćwiczyłem przed zbliżającym się konkursem programistycznym i natknąłem się na pytanie, które mnie całkowicie oszołomiło. Jednak czuję, że jest to koncepcja, której powinienem się nauczyć teraz, zamiast trzymać kciuki, że nigdy się nie pojawi.

Zasadniczo chodzi o figurę rycerza na szachownicy. Masz dwa dane wejściowe: lokalizację początkową i lokalizację końcową. Celem jest obliczenie i wydrukowanie najkrótszej ścieżki, jaką może pokonać rycerz, aby dostać się do miejsca docelowego.

Nigdy nie miałem do czynienia z rzeczami o najkrótszej ścieżce i nawet nie wiem, od czego zacząć. Jaką logiką się posługuję, aby rozwiązać ten problem?

PS Jeśli ma to jakiekolwiek znaczenie, chcą, abyś uzupełnił normalne ruchy skoczka, umożliwiając mu również przesunięcie się do czterech rogów kwadratu utworzonego przez (potencjalnie) osiem ruchów, które może wykonać rycerz, biorąc pod uwagę, że środek kwadratu jest lokalizacja rycerza.

Masz tutaj wykres, na którym wszystkie dostępne ruchy są połączone (wartość = 1), a niedostępne ruchy są odłączone (wartość = 0), rzadka macierz wyglądałaby tak:

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

Najkrótszą ścieżkę dwóch punktów na wykresie można znaleźć za pomocą http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Pseudo-kod ze strony 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[]

EDYTOWAĆ:

1. jak kretyn, powiedział, że użycie http://en.wikipedia.org/wiki/A*_algorithm może być szybsze.
2. Najszybszym sposobem jest wstępne obliczenie wszystkich odległości i zapisanie ich w pełnej macierzy 8x8. cóż, nazwałbym to oszustwem i działa tylko dlatego, że problem jest mały. Ale czasami konkursy sprawdzają, jak szybko działa twój program.
3. Najważniejsze jest to, że jeśli przygotowujesz się do konkursu programistycznego, musisz znać popularne algorytmy, w tym algorytmy Dijkstry. Dobrym punktem wyjścia jest przeczytanie Introduction to AlgorithmsISBN 0-262-03384-4. Lub możesz wypróbować wikipedię, http://en.wikipedia.org/wiki/List_of_algorithms

EDYCJA: Zobacz odpowiedź Simona , gdzie poprawił przedstawiony tutaj wzór.

W rzeczywistości istnieje wzór O (1)

To jest obraz, który zrobiłem, aby go zwizualizować (kwadraty, do których rycerz może sięgnąć w N- ^tym ruchu, są pomalowane na ten sam kolor).

Czy widzisz tutaj wzór?

Chociaż widzimy wzór, naprawdę trudno jest znaleźć funkcję, f( x , y )która zwraca liczbę ruchów potrzebnych do przejścia z kwadratu ( 0 , 0 )do kwadratu( x , y )

Ale oto formuła, która działa, kiedy 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 );
}

Uwaga: to pytanie zostało zadane w dniu 1 SACO 2007,
a rozwiązania są tutaj

Oto poprawne rozwiązanie O (1), ale w przypadku, gdy skoczek porusza się tylko jak skoczek w szachy i na nieskończonej szachownicy:

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

Kluczem do znalezienia tego jest zauważenie wzorców, które pojawiają się podczas rysowania planszy. Na poniższym diagramie liczba w kwadracie to minimalna liczba ruchów potrzebna do osiągnięcia tego kwadratu (możesz użyć wyszukiwania wszerz, aby to znaleźć):

Ponieważ rozwiązanie jest symetryczne na osiach i przekątnych, narysowałem tylko przypadek x> = 0 i y> = x.

Lewy dolny blok jest pozycją początkową, a liczby w blokach reprezentują minimalną liczbę ruchów, aby dotrzeć do tych bloków.

Należy zwrócić uwagę na 3 wzorce:

• Rosnące niebieskie pionowe grupy po 4
• „Podstawowe” czerwone przekątne (biegną od lewej górnej do prawej dolnej, jak ukośnik odwrotny)
• „Drugorzędne” zielone przekątne (taka sama orientacja jak czerwona)

(Upewnij się, że oba zestawy przekątnych są widoczne od lewej górnej do prawej dolnej. Mają stałą liczbę ruchów. Przekątne w lewym górnym rogu są znacznie bardziej złożone).

Możesz uzyskać formuły dla każdego. Żółte bloki to szczególne przypadki. Tak więc rozwiązaniem jest:

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

}

z najtrudniejszymi grupami pionowymi:

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

}

Zobacz skrzypce w innych przypadkach.

Może są jakieś prostsze lub bardziej eleganckie wzory, które przegapiłem? Jeśli tak, bardzo chciałbym je zobaczyć. W szczególności dostrzegam pewne ukośne wzory w niebieskich pionowych obudowach, ale ich nie zbadałem. Niezależnie od tego, to rozwiązanie nadal spełnia ograniczenie O (1).

Bardzo ciekawy problem, z którym ostatnio się spotkałem. Po patrząc pewne rozwiązania I próbowano odzyskać formułę analityczną ( O(1) time and space complexity) podany na SACO 2007 Dzień 1 rozwiązań .

Przede wszystkim chcę docenić Graeme Pyle za bardzo ładną wizualizację, która pomogła mi naprawić formułę.

Z jakiegoś powodu (może dla uproszczenia, piękna lub po prostu pomyłka) przenieśli się minusdo flooroperatora, w wyniku czego otrzymali złą formułęfloor(-a) != -floor(a) for any a .

Oto poprawna formuła analityczna:

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

Formuła działa dla wszystkich par (x, y) (po zastosowaniu osi i symetrii ukośnej) z wyjątkiem przypadków narożnych (1,0) i (2,2), które nie spełniają wzoru i są zakodowane na stałe w następującym fragmencie:

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>

Uwaga: jQuery służy tylko do ilustracji, kod patrz distancefunkcja.

Tak, Dijkstra i BFS dadzą ci odpowiedź, ale myślę, że szachowy kontekst tego problemu dostarcza wiedzy, która może dać rozwiązanie, które jest znacznie szybsze niż ogólny algorytm najkrótszej ścieżki, szczególnie na nieskończonej szachownicy.

Dla uproszczenia opiszmy szachownicę jako płaszczyznę (x, y). Celem jest znalezienie najkrótszej ścieżki od (x0, y0) do (x1, y1) przy użyciu tylko kroków kandydujących (+ -1, + -2), (+ -2, + -1) i (+ -2 , + -2), jak opisano w PS pytania

Oto nowa obserwacja: narysuj kwadrat z narożnikami (x-4, y-4), (x-4, y + 4), (x + 4, y-4), (x + 4, y + 4) . Ten zbiór (nazwij go S4) zawiera 32 punkty. Najkrótsza droga od dowolnego z tych 32 punktów do (x, y) wymaga dokładnie dwóch ruchów .

Najkrótsza ścieżka z dowolnego z 24 punktów w zbiorze S3 (zdefiniowana podobnie) do (x, y) wymaga co najmniej dwóch ruchów .

Dlatego, jeśli | x1-x0 |> 4 lub | y1-y0 |> 4, najkrótsza ścieżka od (x0, y0) do (x1, y1) jest dokładnie o dwa ruchy większa niż najkrótsza ścieżka od (x0, y0) do S4. Ten ostatni problem można szybko rozwiązać za pomocą prostej iteracji.

Niech N = max (| x1-x0 |, | y1-y0 |). Jeśli N> = 4, to najkrótsza ścieżka od (x0, y0) do (x1, y1) ma ceil (N / 2) kroki.

Powyższa odpowiedź O (1) [ https://stackoverflow.com/a/8778592/4288232 autor: Mustafa Serdar Şanlı] tak naprawdę nie działa. (Sprawdź (1,1) lub (3,2) lub (4,4), pomijając oczywiste skrajne przypadki (1,0) lub (2,2)).

Poniżej znajduje się dużo brzydsze rozwiązanie (python), które działa (z dodanymi „testami”):

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()

To, co musisz zrobić, to pomyśleć o możliwych ruchach skoczka jako o wykresie, gdzie każda pozycja na planszy jest węzłem, a możliwe ruchy na inną pozycję jako krawędź. Nie ma potrzeby stosowania algorytmu Dijkstry, ponieważ każda krawędź ma taką samą wagę lub odległość (wszystkie są równie łatwe lub krótkie). Możesz po prostu przeprowadzić wyszukiwanie BFS od punktu początkowego do pozycji końcowej.

Rozwiązanie od pierwszych zasad w Pythonie

Po raz pierwszy napotkałem ten problem w teście Codility. Dali mi 30 minut na rozwiązanie tego problemu - zajęło mi znacznie więcej czasu, zanim doszedłem do tego wyniku! Problem polegał na tym, że ile ruchów potrzebuje skoczek, aby przejść od 0,0 do x, y używając tylko legalnych ruchów skoczka. x i y były mniej więcej nieograniczone (więc nie mówimy tutaj o prostej szachownicy 8x8).

Chcieli rozwiązania O (1). Chciałem rozwiązania, w którym program wyraźnie rozwiązuje problem (tj. Chciałem czegoś bardziej oczywistego niż wzorzec Graeme'a - wzorce mają zwyczaj załamania się tam, gdzie nie patrzysz) i naprawdę nie chciałem polegać na bezsporna formuła, jak w rozwiązaniu Mustafy

Więc oto moje rozwiązanie, jakie jest warte. Zacznij, tak jak inni, zauważając, że rozwiązanie jest symetryczne względem osi i przekątnych, więc musimy rozwiązać tylko dla 0> = y> = x. Dla uproszczenia wyjaśnienia (i kodu) zamierzam odwrócić problem: skoczek zaczyna od x, y i celuje w 0,0.

Załóżmy, że ograniczymy problem do okolic źródła. W odpowiednim czasie dojdziemy do tego, co właściwie oznacza `` zwycięstwo '', ale na razie zapiszmy kilka rozwiązań w ściągawce (początek w lewym dolnym rogu):

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

Zatem mając x, y na siatce, możemy po prostu odczytać liczbę ruchów do początku.

Jeśli zaczęliśmy poza polem startowym, musimy wrócić do tego. Wprowadzamy „linię środkową”, która jest linią reprezentowaną przez y = x / 2. Każdy skoczek znajdujący się w pozycji x, y w tej linii może wrócić do ściągawki, wykonując serię ruchów na godzinę 8 (czyli: (-2, -1) ruchów). Jeśli x, y leży powyżej linii środkowej, będziemy potrzebować kolejnych ruchów na godzinie 8 i 7, a jeśli leży poniżej linii środkowej, będziemy potrzebować sekwencji o godzinie 8 i 10. zegar się rusza. Dwie rzeczy, na które należy zwrócić uwagę:

• Te sekwencje są prawdopodobnie najkrótszymi ścieżkami. (Chcesz, żebym to udowodnił, czy to oczywiste?)
• Dbamy tylko o ilość takich ruchów. Możemy łączyć ruchy w dowolnej kolejności.

Spójrzmy więc na ruchy powyżej linii środkowej. Twierdzimy, że:

• (dx; dy) = (2,1; 1,2) (n8; n7) (notacja macierzowa, bez składu matematycznego - wektor kolumnowy (dx; dy) równa się macierzy kwadratowej pomnożonej przez wektor kolumnowy (n8; n7) - ilość ruchów na godz. 8 i ilość ruchów na godz. 7) i podobnie;

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

Twierdzę, że dx, dy będzie w przybliżeniu równe (x, y), więc (x-dx, y-dy) będzie w pobliżu źródła (jakiekolwiek „sąsiedztwo” się okaże).

Dwa wiersze w kodzie, które obliczają te terminy, są rozwiązaniem tych warunków, ale zostały wybrane tak, aby miały kilka przydatnych właściwości:

• Formuła powyżej linii środkowej przenosi (x, y) do jednej z (0,0), (1,1) lub (2,2).
• Formuła poniżej linii środkowej przenosi (x, y) do jednego z (0,0), (1,0), (2,0) lub (1,1).

(Czy chciałbyś mieć na to dowody?) Tak więc odległość skoczka będzie sumą n7, n8, n10 i ściągawki [x-dx, y-dy], a nasza ściągawka sprowadza się do tego:

. . 4
. 2 .
0 3 2

To jeszcze nie koniec historii. Spójrz na 3 w dolnym rzędzie. Jedyne sposoby, w jakie możemy to osiągnąć, to:

• Zaczęliśmy tam, lub
• Przenieśliśmy się tam sekwencją ruchów na godz. 8 i 10. Ale jeśli ostatnim ruchem była godzina ósma (do której ma prawo, ponieważ możemy wykonywać nasze ruchy w dowolnej kolejności), to musieliśmy przejść przez (3,1), którego odległość wynosi w rzeczywistości 2 (jak możesz patrz z oryginalnej ściągawki). Więc to, co powinniśmy zrobić, to cofnąć się o jeden ruch na godzinę ósmą, oszczędzając w sumie dwa ruchy.

Podobną optymalizację można zastosować z 4 w prawym górnym rogu. Oprócz rozpoczęcia w tym miejscu, jedynym sposobem na to jest przejście z (4,3) o godzinie ósmej. Tego nie ma w ściągawce, ale gdyby tak było, jego odległość wyniosłaby 3, ponieważ zamiast tego moglibyśmy mieć godzinę 7 do (3,1), która ma odległość tylko 2. Więc powinniśmy cofnąć się o jeden Ruch na godz. Ósmej, a następnie o godz. 7 do przodu.

Musimy więc dodać jeszcze jeden numer do ściągawki:

. . 4
. 2 . 2
0 3 2

(Uwaga: istnieje cały ładunek optymalizacji śledzenia wstecznego z (0,1) i (0,2), ale ponieważ solver nigdy nas tam nie zabierze, nie musimy się o nie martwić.)

Oto więc kod Pythona do oceny tego:

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]

Nawiasem mówiąc, jeśli chcesz poznać rzeczywistą trasę, ten algorytm również to zapewnia: jest to po prostu ciąg n7 ruchów na godzinę 7, po których następują (lub przeplatane) n8 ruchów na godzinę 8, n10 10- porusza się godzina i jakikolwiek taniec jest dyktowany przez ściągawkę (która sama może znajdować się w ściągawce).

Teraz: jak udowodnić, że to prawda. Nie wystarczy porównać tych wyników z tabelą poprawnych odpowiedzi, ponieważ sam problem jest nieograniczony. Ale możemy powiedzieć, że jeśli odległość skoczka kwadratu s wynosi d, to jeśli {m} jest zbiorem prawidłowych ruchów z s, odległość skoczka (s + m) musi wynosić d-1 lub d + 1 dla wszystkich m. (Potrzebujesz na to dowodu?) Ponadto musi istnieć co najmniej jeden taki kwadrat o odległości d-1, chyba że s jest początkiem. Możemy więc udowodnić poprawność, pokazując tę ​​właściwość dla każdego kwadratu. A zatem:

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")

Alternatywnie, możemy udowodnić poprawność dowolnego kwadratu s, ścigając trasę od s w dół do początku. Najpierw sprawdź s pod względem zasadności jak powyżej, a następnie wybierz dowolne s + m takie, że odległość (s + m) == d-1. Powtarzaj, aż dotrzemy do początku.

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.

Nie studiowałem jeszcze wykresów… biorąc pod uwagę problem implementacji go za pomocą prostych tablic, nie mogłem znaleźć innego rozwiązania niż to. Potraktowałem pozycje nie jako rangi i pliki (zwykły zapis szachowy), ale jako indeksy tablicowe. FYI, to jest tylko dla szachownicy 8 * 8. Wszelkie porady dotyczące ulepszeń są zawsze mile widziane.

* Komentarze powinny wystarczyć do zrozumienia logiki. Zawsze możesz jednak zapytać.

* Sprawdzone na kompilatorze DEV-C ++ 4.9.9.2 (oprogramowanie Bloodshed).

Myślę, że to też może ci pomóc ...

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

i używając programowania dynamicznego, aby uzyskać rozwiązanie.

PS: Trochę używa BFS bez konieczności zadeklarowania węzłów i krawędzi grafu.

Oto rozwiązanie tego konkretnego problemu zaimplementowane w Perlu. Pokaże jedną z najkrótszych ścieżek - w niektórych przypadkach może być więcej niż jedna.

Nie korzystałem z żadnego z opisanych wyżej algorytmów - ale fajnie byłoby porównać to z innymi rozwiązaniami.

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

Po prostu kod ruby ​​z odpowiedzi jsfiddle Graeme'a Pyle'a powyżej , rozłożony na cały dodatkowy kod i przekonwertowany pozostały do ​​ruby ​​tylko po to, aby uzyskać rozwiązanie przez jego algorytm, wydaje się działać. Jednak wciąż testujemy:

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)

Jedynym zamiarem jest zaoszczędzenie komuś czasu na konwersji kodu, jeśli ktoś potrzebuje pełnego kodu.

oto wersja PHP funkcji Julesa Maya

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

Oto mój program. To nie jest idealne rozwiązanie. Istnieje wiele zmian do wprowadzenia w funkcji rekursji. Ale ten efekt końcowy jest doskonały. Próbowałem trochę zoptymalizować.

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

}

Oto wersja C oparta na kodzie Mustafa Serdar Şanlı, który działa dla skończonej tablicy:

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

Przetestuj tutaj, sprawdzając rozwiązanie rekurencyjne