Knight ' s Kürzesten Weg auf Schachbrett
https://stackoverflow.com/questions/2339101
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe geübt für eine bevorstehende Programmierung Wettbewerb, und ich stolperte über eine Frage, ich bin nur völlig verwirrt an.Allerdings habe ich das Gefühl, als ob es ein Konzept, das ich lernen sollte lieber jetzt als drücke die Daumen, dass es nie kommt.
Im Grunde, es handelt sich um einen Ritter Figur auf einem Schachbrett.Erhalten Sie zwei Eingänge:Start und Ende Position.Das Ziel ist dann zu berechnen und zu drucken, den kürzesten Weg, der Ritter kann, um an den Zielort.
Ich habe noch nie befasst mit kürzesten-Pfad-artige Dinge, und ich weiß gar nicht, wo zu beginnen.Welche Logik kann ich einsetzen, um zu gehen zu der Bekämpfung dieser?
P. S.Wenn es von Relevanz, Sie wollen, dass Sie zur Ergänzung der Ritter ist normal bewegt auch so dass es zu bewegen, um die vier Ecken des Quadrats gebildet durch die (vermutlich) acht bewegt sich ein Ritter machen kann, da die Mitte des Platzes befindet sich der Ritter der Standort.
Lösung
Sie haben ein Diagramm hier, wo alle verfügbaren Züge verbunden sind (Wert = 1), und nicht verfügbar bewegt getrennt wird (Wert = 0), die spärliche Matrix aussehen würde:
(a1,b3)=1,
(a1,c2)=1,
.....
Und der kürzeste Weg von zwei Punkten in einem Diagramm kann mit http finden. wikipedia.org/wiki/Dijkstra's_algorithm
Pseudo-Code aus wikipedia-Seite:
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:
- als Trottel, sagte der Verwendung von http://en.wikipedia.org/wiki/A*_algorithm kann schneller sein.
- der schnellste Weg ist alle die Abstände vorab berechnen und speichern Sie es auf eine 8x8-Matrix voll. na ja, ich würde diesen Betrug nennen, und funktioniert nur, weil das Problem ist klein. Aber manchmal Wettbewerbe überprüfen, wie schnell Ihr Programm läuft.
- Der wichtigste Punkt ist, dass, wenn Sie bereiten
für einen Programmierwettbewerb, müssen Sie wissen
gemeinsame Algorithmen einschließlich Dijkstra.
Ein guter Ausgangspunkt ist das Lesen
Introduction to AlgorithmsISBN 0-262-03384-4. Oder Sie könnten wikipedia versuchen, http://en.wikipedia.org/wiki/List_of_algorithms
Andere Tipps
EDIT: Siehe Simons Antwort , wo er die Formel festgelegt präsentiert hier
Eigentlich gibt es einen O (1) Formel
Dies ist ein Bild, das ich gemacht habe, es zu visualisieren (Squares ein Ritter auf N erreichen th Bewegung werden mit der gleichen Farbe lackiert).
Können Sie feststellen, das Muster hier?
Obwohl wir das Muster sehen kann, ist es wirklich schwierig, die Funktion f( x , y ) zu finden, dass die Renditen der Anzahl der Züge von Platz ( 0 , 0 ) auf Platz ( x , y ) gehen erforderlich
Aber hier ist die Formel, die funktioniert, wenn 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 );
}
Hinweis: Diese Frage wurde gebeten, auf SACO 2007 Tag 1
Und Lösungen sind hier
Hier ist eine richtige O (1) Lösung, aber für den Fall, dass die Ritter bewegt sich wie ein Schach-Ritter nur, und auf einem unendlichen Schachbrett:
https://jsfiddle.net/graemian/5qgvr1ba/11/
Der Schlüssel dies zu finden ist, die Muster zu bemerken, die entstehen, wenn Sie die Tafel zeichnen. Im Diagramm unten, Anzahl der Züge die Zahl auf dem Platz ist das Minimum erforderlich, dass Platz zu erreichen (man diese Breitensuche zu finden verwenden):
Da die Lösung über die Achsen und die Diagonalen symmetrisch ist, habe ich nur gezogen, um das x> = 0 und y> = x Fall.
der untere linke Block ist die Ausgangsposition und die Zahlen in den Blöcken stellen die minimale Anzahl von Bewegungen, diese Blöcke zu erreichen.
Es gibt 3 Muster Hinweis:
- Die Inkrementieren blaue vertikale Gruppen von 4
- Die „primäre“ roten Diagonalen (sie laufen von links oben nach rechts unten, wie ein umgekehrter Schrägstrich)
- Die "sekundären" grünen Diagonalen (gleiche Ausrichtung wie rot)
(Achten Sie darauf, sehen Sie beide Sätze von Diagonalen wie oben links nach unten rechts. Sie haben eine konstante Bewegung Zählungs. Die unteren linken oberen rechten Diagonalen sind viel komplexer.)
Sie können Formeln für jeden ableiten. Die gelben Blöcke sind Sonderfälle. So ist die Lösung wird:
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);
}
mit den härtesten der senkrechten Gruppen:
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);
}
Sehen Sie die Geige für die anderen Fälle.
Vielleicht gibt es einfachere oder elegante Muster habe ich verpasst? Wenn ja, würde ich lieben, sie zu sehen. Insbesondere sehe ich einige diagonale Muster in den blauen vertikalen Fällen, aber ich habe sie nicht erforscht. Unabhängig davon, diese Lösung immer noch erfüllt die O (1) constraint.
Sehr interessantes Problem, das ich vor kurzem festgestellt wurde. Nachdem einige Lösungen suchte ich versuche analytische Formel (O(1) time and space complexity) auf SACO gegeben zu erholen 2007 Day 1 Lösungen .
Als erstes habe ich zu schätzen wissen will Graeme Pyle für sehr schöne Visualisierung, die mir fix Formel geholfen.
Aus irgendeinem Grund (vielleicht für eine Vereinfachung oder Schönheit oder einfach nur einen Fehler) sie bewegt minus Zeichen in floor Operator, wodurch sie falsche Formel floor(-a) != -floor(a) for any a bekommen haben.
Hier ist die korrekte analytische Formel:
var delta = x-y;
if (y > delta) {
return delta - 2*Math.floor((delta-y)/3);
} else {
return delta - 2*Math.floor((delta-y)/4);
}
Die Formel funktioniert für all (x, y) paarweise (nach den Achsen und diagonale Symmetrie Anwendung) mit Ausnahme von (1,0) und (2,2) Ecke Fälle, die nicht dem Muster entsprechen und im folgenden Ausschnitt einprogrammiert:
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>
. Hinweis: Die jQuery dienen nur zur Illustration verwendet, für Code siehe distance Funktion
Ja, Dijkstra und BFS finden Ihnen die Antwort bekommen, aber ich denke, der Schach Kontext dieses Problems Wissen bereitstellt, die eine Lösung ergeben kann, die viel schneller als ein generischer Shortest-Path-Algorithmus ist, vor allem auf einem unendlichen Schachbrett.
Der Einfachheit halber wollen wir die Schachbrett als (x, y) Ebene beschreiben. Das Ziel ist, den kürzesten Weg von (x0, y0) bis (x1, y1) nur mit den Kandidaten Schritte (+ -1, + -2), (+ -2, + -1) zu finden, und (+ -2 wie in der Frage der PS beschrieben, + -2),
Hier ist die neue Beobachtung: ein Quadrat mit Ecken zeichnen (x-4, Y-4), (x-4, y + 4), (x + 4, y-4), (x + 4, y +4). Dieser Satz (nennen wir es S4) enthält 32 Punkte. Der kürzeste Weg von einem dieser 32 Punkten (x, y) erfordert genau zwei Bewegungen .
der kürzeste Weg von einem der 24 Punkte in dem Satz S3 (definiert in ähnlicher Weise) bis (x, y) erfordert mindestens zwei Bewegungen .
Wenn daher | x1-x0 |> 4 oder | y1-y0 |> 4, der kürzeste Weg von (x0, y0) bis (x1, y1) genau zwei Bewegungen größer als der kürzeste Weg von (x0, y0) bis S4. Und das letztere Problem schnell mit einfachen Iteration gelöst werden kann.
Es sei N = max (| x1-x0 |, | y1-y0 |). Wenn N> = 4 ist, dann wird der kürzeste Pfad von (x0, y0) nach (x1, y1) hat ceil (N / 2) Schritte.
Die O (1) Antwort oben [ https://stackoverflow.com/a/8778592/4288232 von Mustafa Serdar Şanlı] nicht wirklich funktioniert. (Check (1,1) oder (3,2) oder (4,4), abgesehen für die offensichtlichen Randfälle (1,0) oder (2,2)).
Im Folgenden finden Sie eine viel hässliche Lösung (Python), die Arbeit macht (mit Zusatz "Tests"):
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()
Was Sie tun müssen, ist man denke an die möglichen Züge des Ritters als Diagramm, in dem jede Position auf dem Brett ein Knoten ist und die möglichen Züge zu einer anderen Position als Kante. Es besteht keine Notwendigkeit für Dijkstra-Algorithmus, weil jede Kante das gleiche Gewicht oder Abstand hat (sie sind alle so einfach oder kurz zu tun). Sie können nur eine BFS Suche von Ihrem Ausgangspunkt tun, bis Sie die Endposition erreichen.
Lösung von Grund auf in Python
Meine erste Begegnung dieses Problem in einem Codility Test. Sie gaben mir 30 Minuten, es zu lösen - es hat mich wesentlich länger als die zu diesem Ergebnis zu gelangen! Das Problem war: Wie viele Züge dauert es, bis ein Ritter von 0,0 bis x zu gehen, y nur mit Rechtsritter bewegt. x und y waren mehr oder weniger unbegrenzt (so dass wir hier nicht über ein einfaches 8x8 Schachbrett im Gespräch).
Sie wollten eine O (1) Lösung. Ich wollte eine Lösung, bei der das Programm war eindeutig das Problem zu lösen (dh ich etwas mehr offensichtlich Recht als Graeme Muster wollte - Muster haben eine Gewohnheit brechen, wo Sie nicht suchen), und ich wollte wirklich nicht auf einem verlassen müssen unangefochten Formel, wie in Mustafas Lösung
So, hier ist meine Lösung, für das, was es wert ist. Start, als andere haben, indem die Lösung der Feststellung, ist symmetrisch um die Achsen und Diagonalen, so dass wir nur für 0> = y> = x lösen müssen. Zur Vereinfachung der Erklärung (und Code) Ich werde das Problem umkehren. Die Ritter beginnt bei x, y, und strebt 0,0
Nehmen wir an, wir das Problem auf die Nähe des Ursprungs schrumpfen. Wir kommen zu dem, was ‚vicinty‘ tatsächlich Mittel in gegebener Zeit, aber jetzt wollen wir nur einige Lösungen aufschreiben in einem Spickzettel (Ursprung links unten):
2 1 4 3
3 2 1 2
0 3 2 3
So, da x, y auf dem Gitter, können wir ablesen nur die Anzahl der Züge auf den Ursprung.
Wenn wir außerhalb des Gitters begonnen haben, haben wir uns auf den Weg zurück, um es zu arbeiten. Wir führen die ‚Mittellinie‘, die die Linie, die durch y = x / 2 ist, dargestellt. Jeder Ritter bei x, y auf dieser Linie kann seinen Weg zurück zu dem Spickzettel unter Verwendung eine Reihe von 08.00 Uhr bewegt arbeiten (das heißt: (-2, -1) bewegt). Wenn x, oberhalb der Mittellinie y liegt, dann werden wir eine Reihe von 08.00 Uhr und 07.00 Uhr bewegt brauchen, und wenn sie unterhalb der Mittellinie liegen, müssen wir eine Reihe von 8 Uhr und 10 o Uhr bewegt. Zwei Dinge beachten hier:
- Diese Sequenzen beweisbar kürzesten Wege. (Willst du mich, es zu beweisen, oder ist es offensichtlich?)
- Wir kümmern sich nur um die Anzahl solcher Bewegungen. Wir können Mix-and-Match die Bewegungen in beliebiger Reihenfolge.
So lassen Sie uns Blick auf die oben Mittellinie bewegt. Was wir behaupten, dass:
-
(dx; dy) = (2,1; 1,2) (N8; N7) (Matrixnotation, ohne math Satz- - Spaltenvektor (dx, dy) gleich die quadratische Matrix von Spaltenvektor multipliziert ( N8, N7) - die Anzahl von 08.00 Uhr bewegt und die Anzahl von 07.00 bewegt), und in ähnlicher Weise;
-
(dx; dy) = (2,2; 1, -1) (N8; n10)
Ich behaupte, dass dx, wird dy sein grob (x, y), so (x-dx, y-dy) in der Nähe des Ursprungs sein (was auch immer 'Nähe' erweist).
Die beiden Zeilen im Code, die diese Bedingungen zu berechnen sind die Lösung für diese, aber sie sind ausgewählt einige nützliche Eigenschaften haben:
- Die oben bewegt Formel Mittellinie (x, y) zu einem von (0,0), (1,1) oder (2,2).
- Das unten bewegt Formel Mittellinie (x, y) zu einem von (0,0), (1,0), (2,0) oder (1,1).
(Möchten Sie Beweise für diese?) Also, die Entfernung der Ritter wird die Summe von n7, n8, n10 und Spickzettel [x-dx, y-dy] sein, und unsere Spickzettel reduziert auf diese:
. . 4
. 2 .
0 3 2
Nun, dies ist nicht ganz das Ende der Geschichte. Betrachten Sie die 3 in der unteren Reihe. Die einzigen Möglichkeiten, wie wir können dies erreichen sind entweder:
- Wir begannen dort, oder
- Wir zogen es, durch eine Folge von 8 Uhr und 10 Uhr bewegt. Aber wenn der letzte Zug ist 08 Uhr (die es berechtigt ist zu sein, da wir unsere Bewegungen in beliebiger Reihenfolge machen), dann müssen wir durchlaufen haben (3,1), dessen Abstand ist eigentlich 2 (wie möglich sieht von dem Original-Spickzettel). Also, was wir tun sollten, ist Back-Track ein 8 Uhr bewegen, spart zwei Züge insgesamt.
Es gibt eine ähnliche Optimierung mit den 4 oben rechts werden mußte. Abgesehen von dort ausgehend, ist der einzige Weg, das zu erreichen, ist durch einen 08 Uhr Umzug von (4,3). DasIst nicht auf dem Spickzettel, aber wenn es dort wäre, würde seine Entfernung 3 sein, weil wir 7 o'clocked bis (3,1) haben könnte stattdessen, was einen Abstand von nur 2. So hat, sollten wir wieder Spur einen 8-Uhr-Zug, und dann vorwärts geht eine 7-Uhr.
So müssen wir noch eine Nummer an den Spickzettel hinzuzufügen:
. . 4
. 2 . 2
0 3 2
(Hinweis: Es gibt eine ganze Menge von Back-Tracking-Optimierungen von (0,1) und (0,2), aber da der Solver uns dort nie stattfinden wird, wissen wir nicht über sie zu kümmern.)
So, hier ist also einiger Python-Code diese zu bewerten:
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]
Übrigens, wenn Sie eine aktuelle Route wissen wollen, dann bietet dieser Algorithmus das auch: es ist einfach eine Folge von n7 7-Uhr bewegt, gefolgt von (oder streut) n8 8-Uhr bewegt, n10 10 Uhr bewegt, und was auch immer Tanz wird von dem Spickzettel diktiert (welche selbst kann in einem Spickzettel sein).
Jetzt: Wie um zu beweisen, das ist richtig. Es ist einfach nicht genug, um diese Ergebnisse mit einer Tabelle der richtigen Antworten zu vergleichen, weil das Problem selbst unbeschränkt ist. Aber wir können sagen, dass, wenn der Abstand des Ritters eines Quadrates s d ist, dann, wenn {m} ist die Menge der legalen Züge von s, das Ritter Abstand von (n + m) muss entweder d-1 oder d sein + 1 für alle m. (Haben Sie einen Beweis dafür brauchen?) Darüber hinaus muss es mindestens einen solchen Platz, deren Abstand d-1, es sei denn, ist der Ursprung ist. So können wir die Richtigkeit beweisen, indem sie zeigen diese Eigenschaft für jeden Platz hält. Also:
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")
Alternativ können wir die Richtigkeit des einem Quadrat s von der Jagd nach dem Weg von s bergab zum Ursprung beweisen. Zunächst überprüfen s auf Plausibilität, wie oben, und wählen irgendeine s + m, so dass die Entfernung (s + m) == d-1. Wiederholen, bis wir den Ursprung erreichen.
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.
Ich habe nicht Graphen yet..as pro das Problem der Implementierung es durch einfach Arrays untersucht, konnte ich ableiten keine andere Lösung als diese. Ich behandelte die Positionen nicht als Reihen und Dateien (Die übliche Schachnotation), aber als Array-Indizes. FYI, ist dies für ein 8 * 8 Schachbrett nur. Jede Verbesserung Beratung ist immer willkommen.
* Die Kommentare sollten für Ihr Verständnis für die Logik genügen. Sie können jedoch immer fragen.
* Geprüft auf DEV-C ++ 4.9.9.2 Compiler (Bloodshed Software).
Ich glaube, dass dies auch Ihnen helfen ..
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
und mit Dynamic die Lösung erhalten Programmierung.
P. S:. Es verwendet ein bisschen die BFS ohne sich die Mühe zu nehmen, die die Knoten und Kanten des Graphen erklärt
Hier ist eine Lösung für dieses spezielle Problem in Perl implementiert. Es wird eines der kürzesten Wege zeigen -. Es könnte mehr sein als ein in einigen Fällen
Ich habe keine der Algorithmen verwenden oben beschrieben -. Aber es wäre schön, es zu anderen Lösungen zu vergleichen
#!/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));
}
}
Nur ruby-code aus Graeme Pyle Antwort ist jsfiddle oben, gestreifte alle zusätzlichen code umgewandelt und von der verbleibenden ruby nur um die Lösung seines Algorithmus, scheint, wie Sie arbeiten.Noch in der Testphase aber:
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)
Einzige Absicht ist es, jemand retten einige Zeit konvertieren von code, wenn jemand braucht vollständigen code.
hier ist die PHP-Version von Jules May Funktion
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];
}
Hier ist mein Programm. Dies ist keine perfekte Lösung. Es gibt viele Änderungen in der Rekursion Funktion zu machen. Aber das Endergebnis ist perfekt. Ich habe versucht, ein wenig zu optimieren.
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;
}
}
Hier ist eine C-Version basiert auf Mustafa Serdar Şanlı Code, dass die Arbeiten für eine finit Bord:
#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));
}
}
Test hier mit Beweis gegen eine rekursive Lösung
