Le chemin le plus court du chevalier sur l'échiquier
https://stackoverflow.com/questions/2339101
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je me suis entraîné pour un prochain concours de programmation et je suis tombé sur une question qui me laisse complètement déconcerté.Cependant, j'ai l'impression que c'est un concept que je devrais apprendre maintenant plutôt que de croiser les doigts pour qu'il ne revienne jamais.
Fondamentalement, il s’agit d’une pièce de chevalier sur un échiquier.Vous disposez de deux entrées :lieu de départ et lieu d'arrivée.Le but est ensuite de calculer et d'imprimer le chemin le plus court que le chevalier peut emprunter pour se rendre à l'emplacement cible.
Je n'ai jamais eu affaire à des problèmes de type « chemin le plus court » et je ne sais même pas par où commencer.Quelle logique dois-je employer pour aborder ce problème ?
P.S.Si cela est pertinent, ils veulent que vous complétiez les mouvements normaux du chevalier en lui permettant également de se déplacer vers les quatre coins du carré formé par les (potentiellement) huit mouvements qu'un chevalier peut effectuer, étant donné que le centre du carré est le emplacement du chevalier.
La solution
Vous avez ici un graphique, où tous les mouvements sont connectés disponibles (valeur = 1), et se déplace non disponibles sont déconnectés (valeur = 0), la matrice clairsemée serait comme:
(a1,b3)=1,
(a1,c2)=1,
.....
Et le chemin de deux points le plus court dans un graphique peut être trouvé en utilisant http: // fr. wikipedia.org/wiki/Dijkstra's_algorithm
pseudo-code de wikipedia page:
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:
- comme crétin, dit à l'aide du http://en.wikipedia.org/wiki/A*_algorithm peut être plus rapide.
- la façon la plus rapide, est pré-calculer toutes les distances et l'enregistrer dans une matrice pleine 8x8. eh bien, je dirais que la tricherie, et ne fonctionne que parce que le problème est petite. Mais parfois, les compétitions va vérifier la vitesse de votre programme fonctionne.
- Le point principal est que si vous prépariez
pour un concours de programmation, vous devez savoir
algorithmes communs, y compris Dijkstra.
Un bon point de départ est en train de lire
Introduction to AlgorithmsISBN 0-262-03384-4. Ou vous pouvez essayer wikipedia, http://en.wikipedia.org/wiki/List_of_algorithms
Autres conseils
EDIT:. Voir réponse de simon, où il a fixé la formule présentée ici
En fait, il y a un joint (1) formule
Ceci est une image que je l'ai fait pour le visualiser (Squares un chevalier peut atteindre sur N e move sont peints avec la même couleur).
Pouvez-vous remarquez le modèle ici?
Bien que nous puissions voir le modèle, il est vraiment difficile de trouver la fonction f( x , y ) qui retourne le nombre de mouvements nécessaires pour aller de ( 0 , 0 ) carré ( x , y ) carré
Mais voici la formule qui fonctionne lorsque 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 );
}
Note: Cette question a été posée sur 2007 Jour 1 CESO
Et les solutions sont
Voici une solution O (1) correcte, mais pour le cas où le chevalier se déplace comme un chevalier d'échecs seulement, et sur un échiquier infini:
https://jsfiddle.net/graemian/5qgvr1ba/11/
La clé pour trouver est de remarquer les tendances qui se dégagent lorsque vous dessinez la carte. Dans le diagramme ci-dessous, le numéro de la place est le nombre minimum de coups nécessaires pour atteindre cette place (vous pouvez utiliser la recherche en largeur pour trouver cela):
Parce que la solution est symétrique à travers les axes et les diagonales, j'ai seulement tiré les x> = 0 et y> = x cas.
Le bloc inférieur gauche est la position de départ et les numéros des blocs représente le nombre minimum de coups pour atteindre ces blocs.
Il y a 3 modèles pour avis:
- Les groupes de bleu verticaux incrémentation 4
- Les rouges « primaires diagonales » (ils courent en haut à gauche en bas à droite, comme une barre oblique inverse)
- Les verts "secondaires diagonales" (même orientation en rouge)
(Assurez-vous de voir les deux ensembles de diagonales en haut à gauche en bas à droite. Ils ont un mouvement de comptage constant. En bas à gauche en haut à droite des diagonales sont beaucoup plus complexes.)
Vous pouvez obtenir des formules pour chacun. Les blocs jaunes sont des cas particuliers. Donc, la solution devient:
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);
}
avec le plus dur étant les groupes verticaux:
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);
}
Voir le violon pour les autres cas.
Peut-être il y a des modèles plus simples ou plus élégantes je ratées? Si oui, j'aimerais les voir. En particulier, je constate des motifs en diagonale dans les cas verticaux bleus, mais je ne les ai pas exploré. Quoiqu'il en soit, cette solution répond toujours aux O (1) contrainte.
problème très intéressant que je rencontrais récemment. Après avoir examiné quelques solutions que j'essayé de récupérer la formule analytique (de O(1) time and space complexity) donnée sur CESO 2007 jour 1 .
D'abord tout ce que je veux apprécier Graeme Pyle pour la visualisation très agréable qui m'a aidé à fixer la formule.
Pour une raison quelconque (peut-être pour la simplification ou la beauté ou tout simplement une erreur) ils ont déménagé dans minus signer opérateur floor, par conséquent, ils ont obtenu mauvaise formule floor(-a) != -floor(a) for any a.
Voici la formule analytique correcte:
var delta = x-y;
if (y > delta) {
return delta - 2*Math.floor((delta-y)/3);
} else {
return delta - 2*Math.floor((delta-y)/4);
}
La formule fonctionne pour tous les (x, y) des paires (après application axes et la symétrie diagonale) sauf (1,0) et (2,2) des cas de coin, qui sont satisfont pas à motif et dur dans l'extrait suivant:
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>
Note: Le jQuery utilisé à titre indicatif uniquement, pour le code voir fonction distance
Oui, Dijkstra et BFS vous obtiendrez la réponse, mais je pense que le contexte d'échecs de ce problème fournit des connaissances qui peuvent donner une solution qui est beaucoup plus rapide qu'un algorithme de chemin le plus court générique, en particulier sur un échiquier infini.
Par souci de simplicité, nous allons décrire l'échiquier comme le plan (x, y). L'objectif est de trouver le chemin le plus court de (X0, Y0) à (x1, y1) en utilisant uniquement les étapes candidats (+ -1, + -2), (+ -2, + -1) et (+ -2 , + -2), comme décrit dans la question est PS
Voici la nouvelle observation: dessiner un carré avec des coins (x-4, y-4), (x-4, Y + 4), (x + 4, y-4), (x + 4, y +4). Cet ensemble (appeler S4) contient 32 points. Le chemin le plus court de l'une de ces 32 points (x, y) nécessite exactement deux mouvements .
Le chemin le plus court de l'un des 24 points dans le jeu S3 (définie de manière similaire) à (x, y) nécessite au moins deux mouvements .
Par conséquent, si | x1-x0 |> 4 ou | y1-y0 |> 4, le chemin le plus court à partir de (x0, y0) de (x1, y1) est exactement deux mouvements plus grand que le plus court chemin de (x0, y0) à S4. Et ce dernier problème peut être résolu rapidement avec l'itération simple.
Soit N = max (| x1-x0 |, | y1-y0 |). Si N> = 4, alors le chemin le plus court à partir de (x0, y0) de (x1, y1) a ceil (N / 2) étapes.
O (1) ci-dessus en réponse Mustafa [ https://stackoverflow.com/a/8778592/4288232 Serdar Şanlı] ne fonctionne pas vraiment. (Voir les (1,1) ou (3,2) ou (4,4), hormis pour les cas limites évidentes de (1,0) ou (2,2)).
Voici une solution beaucoup plus laid (python), qui fonctionne (avec adjonction de "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()
Ce que vous devez faire est de penser des mouvements possibles du chevalier sous forme de graphique, où chaque position sur la carte est un nœud et les mouvements possibles à un autre poste comme un bord. Il n'y a pas besoin de l'algorithme de Dijkstra, parce que chaque bord a le même poids ou la distance (ils sont tous tout aussi facile ou courte à faire). Vous pouvez juste faire une recherche BFS à partir de votre point de départ jusqu'à la position finale.
Solution de premiers principes en Python
J'ai d'abord rencontré ce problème lors d'un test Codility. On m'a donné 30 minutes pour le résoudre - il m'a fallu beaucoup plus de temps que pour arriver à ce résultat! Le problème est: combien de mouvements faut-il pour un chevalier pour aller de 0,0 à x, y en utilisant uniquement juridique se déplace de Knight. x et y sont plus ou moins sans bornes (donc nous ne parlons pas ici d'un jeu d'échecs simple 8x8).
Ils voulaient une solution de O (1). Je voulais une solution où le programme résolvait clairement le problème (à savoir que je voulais quelque chose de plus évidemment droit que motif de Graeme - modèles ont l'habitude de tomber là où vous ne cherchez pas), et je voulais vraiment ne pas avoir à compter sur une formule argumentée, comme dans la solution de Mustafa
Alors, voici ma solution, pour ce que ça vaut la peine. Cliquez sur Démarrer, comme d'autres, en notant la solution est symétrique autour des axes et des diagonales, donc nous devons résoudre uniquement pour 0> = y> = x. Pour simplifier l'explication (et code) Je vais inverser le problème:. Le chevalier commence à x, y, et vise 0,0
Supposons que nous réduire le problème à proximité de l'origine. Nous allons arriver à ce que « vicinty » signifie en temps voulu, mais pour l'instant, nous allons écrire quelques-unes des solutions dans une antisèche (origine en bas à gauche):
2 1 4 3
3 2 1 2
0 3 2 3
, x données, y sur la grille, nous pouvons simplement lire le nombre de mouvements à l'origine.
Si nous avons commencé à l'extérieur de la grille, nous devons travailler notre chemin de retour à elle. Nous introduisons la « ligne médiane », qui est la ligne représentée par y = x / 2. Toute chevalier en x, y sur cette ligne peut se frayer un chemin vers le cheatsheet utilisant une série de 8 heures se déplace (qui est: (-2, -1) se déplace). Si x, y est au-dessus de la ligne médiane, alors nous aurons besoin d'une succession de 8 heures et 7 heures se déplace, et si elle se trouve en dessous de la ligne médiane, nous aurons besoin d'une succession de 8 heures et 10 o « horloge se déplace. Deux choses à noter ici:
- Ces séquences sont prouvablement chemins les plus courts. (Tu veux que je le prouverai, ou est-il évident?)
- Nous ne se soucient que le nombre de ces mouvements. Nous pouvons mélanger et match les mouvements dans un ordre quelconque.
Alors, regardons les mouvements-midline ci-dessus. Ce que nous réclamons est que:
-
(dx; dy) = (2,1; 1,2) (n8, N7) (notation matricielle, sans calcul de composition - vecteur colonne (dx; dy) est égale à la matrice carrée multipliée par le vecteur de colonne ( n8; N7) - le nombre de mouvements 8 heures et le nombre de mouvements de 7 HEURES), et similaire;
-
(dx; dy) = (2,2, 1, -1) (n8, n10)
J'affirmant que dx, dy sera à peu près (x, y), alors (x-dx, y-dy) sera à proximité de l'origine (quel que soit 'voisinage' se révèle être).
Les deux lignes dans le code qui calculent ces termes sont la solution à ces derniers, mais ils sont sélectionnés pour avoir des propriétés utiles:
- La formule ci-dessus la ligne médiane se déplace (x, y) à l'une (0,0), (1,1) ou (2,2).
- la formule ci-médianes se déplace (x, y) à l'une (0,0), (1,0), (2,0) ou (1,1).
(Souhaitez-vous des preuves de ces?) Ainsi, la distance de chevalier sera la somme des n7, n8, n10 et antisèche [x-dx, y-dy], et notre antisèche réduit à ceci:
. . 4
. 2 .
0 3 2
Maintenant, ce n'est pas tout à fait la fin de l'histoire. Regardez le 3 sur la ligne inférieure. Les seuls moyens que nous pouvons atteindre ce sont soit:
- Nous y a commencé, ou
- Nous avons déménagé là-bas, par une séquence de 8 heures et 10 heures se déplace. Mais si le dernier mouvement était huit heures (ce qui a le droit d'être, puisque nous pouvons faire nos mouvements dans un ordre quelconque), nous devons avoir passé à travers (3,1), dont la distance est en fait 2 (que vous pouvez voir du antisèche original). Donc, ce que nous devrions faire est de revenir en arrière un move 8 heures, économiser deux mouvements au total.
Il y a une optimisation similaire à avoir avec 4 en haut à droite. A part à partir de là, la seule façon d'y parvenir est par un mouvement de 8 heures de (4,3). CetteEst pas sur le antisèche, mais si elle était là, la distance aurait 3, parce que nous pourrions avoir 7 au lieu o'clocked à (3,1), qui a une distance de seulement 2. Ainsi, nous devrions revenir en arrière un mouvement de 8 heures, puis aller de l'avant un 7 heures.
Donc, nous avons besoin d'ajouter un numéro à la antisèche:
. . 4
. 2 . 2
0 3 2
(Remarque: il y a une charge de toute Optimisations retours en arrière de (0,1) et (0,2) mais étant donné que le solveur ne nous prendre là-bas, on n'a pas besoin de vous en soucier.)
Alors ici, est donc un code Python pour évaluer ceci:
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]
Par ailleurs, si vous voulez savoir une route réelle, alors cet algorithme prévoit que trop: il est tout simplement une succession de mouvements de N7 7 o'clock, suivie (ou entrecoupées) se déplace n8 8 o'clock, n10 10 o'clock se déplace, et quelle que soit la danse est dictée par l'antisèche (qui, lui-même, peut être dans une antisèche).
: Comment prouver cela est juste. Il ne suffit pas de comparer ces résultats avec une table de bonnes réponses, parce que le problème lui-même est sans bornes. Mais nous pouvons dire que, si est d la distance de d'un carré de chevalier, alors si {m} est l'ensemble des mouvements de s juridiques, la distance du chevalier de (s + m) doit être soit d-1 ou d + 1 pour tout m. (Avez-vous besoin d'une preuve?) De plus, il doit y avoir au moins un tel carré dont la distance est d-1, à moins que s est à l'origine. Ainsi, nous pouvons prouver la justesse en montrant cette propriété est valable pour toutes les places. Ainsi:
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")
Sinon, nous pouvons prouver l'exactitude de tout un s carré en chassant la route de s en descente à l'origine. Tout d'abord, vérifier la vraisemblance s comme ci-dessus, puis sélectionner les s + m de telle sorte que la distance (s + m) == D-1. Répétez jusqu'à ce que nous atteignons l'origine.
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.
Je n'ai pas étudié les graphiques yet..as par le problème de la mise en œuvre à travers des réseaux simplement, je ne pouvais pas obtenir une autre solution que cela. Je traitais les positions non comme grades et fichiers (La notation d'échecs d'habitude), mais comme indices de tableau. Pour votre information, c'est un 8 * 8 seulement chessboard. Des conseils d'amélioration est toujours la bienvenue.
* Les commentaires devraient suffire pour votre compréhension de la logique. Cependant, vous pouvez toujours demander.
* Contrôlé le compilateur DEV-C ++ 4.9.9.2 (Bloodshed Software).
Je pense que cela pourrait également vous aider ..
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
et en utilisant la programmation dynamique pour obtenir la solution.
P.S. Il utilise un peu le BFS sans avoir à prendre la peine de déclarer les nœuds et les arêtes du graphe
Voici une solution pour ce problème particulier mis en oeuvre en Perl. Elle montrera l'un des chemins les plus courts -. Il pourrait y avoir plus d'un dans certains cas,
Je n'ai pas utilisé des algorithmes décrits ci-dessus - mais ce serait bien de le comparer à d'autres solutions
.#!/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));
}
}
Juste du code Ruby de Jsfiddle de la réponse de Graeme Pyle ci-dessus, supprimé tout le code supplémentaire et converti le reste en rubis juste pour obtenir une solution par son algorithme, semble fonctionner.Je teste quand même :
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)
La seule intention est de faire gagner du temps à quelqu'un lors de la conversion du code si quelqu'un a besoin du code complet.
voici la version PHP de la fonction de Jules mai
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];
}
Voici mon programme. Ce n'est pas une solution parfaite. Il y a beaucoup de changements à faire dans la fonction récursive. Mais ce résultat final est parfait. J'ai essayé d'optimiser un peu.
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;
}
}
Voici une version C basée sur le code Mustafa Serdar Şanlı qui travaille pour un conseil en finit:
#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));
}
}
Testez ici une preuve contre une solution récursive
