La via più breve del cavaliere sulla scacchiera
https://stackoverflow.com/questions/2339101
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Mi sto esercitando per un imminente concorso di programmazione e mi sono imbattuto in una domanda di cui sono completamente sconcertato.Tuttavia, sento che è un concetto che dovrei imparare ora piuttosto che incrociare le dita perché non venga mai fuori.
Fondamentalmente si tratta di un pezzo del cavallo su una scacchiera.Ti vengono forniti due input:luogo di partenza e luogo di arrivo.L'obiettivo è quindi calcolare e stampare il percorso più breve che il cavaliere può intraprendere per raggiungere la posizione target.
Non mi sono mai occupato di cose tipo il percorso più breve e non so nemmeno da dove cominciare.Quale logica utilizzo per affrontare questo problema?
PSSe ha qualche rilevanza, vogliono che tu integri le normali mosse del cavaliere permettendogli anche di spostarsi ai quattro angoli del quadrato formato dalle (potenzialmente) otto mosse che un cavaliere può fare, dato che il centro del quadrato è il posizione del cavaliere.
Soluzione
Hai un grafico qui, in cui sono collegati tutti i mosse disponibili (valore = 1), e si muove non disponibili sono scollegati (valore = 0), la matrice sparsa sarebbe come:
(a1,b3)=1,
(a1,c2)=1,
.....
E il percorso più breve di due punti in un grafico può essere trovata utilizzando http: // it. wikipedia.org/wiki/Dijkstra's_algorithm
pseudo-codice da 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:
- come Moron, detto con il http://en.wikipedia.org/wiki/A*_algorithm può essere più veloce.
- il modo più veloce, è di pre-calcolare tutte le distanze e salvarla in una matrice 8x8 pieno. beh, direi che barare, e funziona solo perché il problema è piccolo. Ma a volte i concorsi controllerà quanto velocemente il vostro programma di viene eseguito.
- Il punto principale è che se si sta preparando
per un concorso di programmazione, è necessario conoscere
algoritmi comuni, tra cui Dijkstra di.
Un buon punto di partenza è la lettura
Introduction to AlgorithmsISBN 0-262-03384-4. Oppure si potrebbe provare wikipedia, http://en.wikipedia.org/wiki/List_of_algorithms
Altri suggerimenti
EDIT:. veda la risposta di Simon, dove ha fissato la formula presentata qui
In realtà c'è un O (1) formula
Questa è l'immagine che ho fatto di visualizzarla (Piazze un cavaliere può raggiungere il N th mossa sono verniciate con lo stesso colore).
Si può notare il modello qui?
Anche se siamo in grado di vedere il modello, è davvero difficile trovare la funzione f( x , y ) che restituisce il numero di mosse necessarie per passare da ( 0 , 0 ) quadrato per ( x , y ) piazza
Ma qui è la formula che funziona quando 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 );
}
Nota: Questa domanda è stato chiesto su SACO 2007 Day 1
E le soluzioni sono qui
Ecco un (1) soluzione corretta O, ma per il caso in cui il Cavaliere si muove come un cavaliere scacchi solo, e su una scacchiera infinita:
https://jsfiddle.net/graemian/5qgvr1ba/11/
La chiave per trovare questo è quello di notare i modelli che emergono quando si disegna la scheda. Nel diagramma qui sotto, il numero nella piazza è il numero minimo di mosse necessarie per raggiungere quella piazza (è possibile utilizzare ricerca in ampiezza per trovare questo):
Poiché la soluzione è simmetrico di tutti gli assi e le diagonali, ho disegnato solo x> = 0 e y> = x caso.
Il blocco in basso a sinistra è la posizione iniziale ei numeri nei blocchi rappresentano il numero minimo di mosse per raggiungere tali blocchi.
Ci sono 3 modelli di avviso:
- I incrementali gruppi verticali blu di 4
- Le diagonali rosse "primari" (che corrono in alto a sinistra in basso a destra, come un backslash)
- Le diagonali verdi "secondari" (stesso orientamento rosso)
(assicuratevi di vedere entrambe le serie di diagonali da in alto a sinistra in basso a destra. Hanno una mossa-count costante. Le diagonali in alto a destra in basso a sinistra sono molto più complesse.)
È possibile derivare formule per ciascuno. I blocchi gialli sono casi speciali. Quindi la soluzione diventa:
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);
}
con i più duri che sono i gruppi verticali:
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);
}
Si veda il violino per gli altri casi.
Forse ci sono modelli più semplici o più eleganti che ho perso? Se è così, mi piacerebbe vederli. In particolare, ho notato alcuni modelli diagonali nei casi verticali blu, ma io non li ho esplorato. Indipendentemente, questa soluzione soddisfa ancora la O (1) vincolo.
problema molto interessante, che mi è stato incontrato di recente. Dopo aver guardato alcune soluzioni sono stato tentato di recuperare formula analitica (O(1) time and space complexity) indicato sulla SACO 2007 Day 1 soluzioni .
Prima di tutto voglio apprezzare Graeme Pyle per la visualizzazione molto bello, che mi ha aiutato a risolvere formula.
Per qualche motivo (forse per la semplificazione o la bellezza o semplicemente un errore) si trasferirono minus accedere a operatore floor, di conseguenza hanno ottenuto sbagliato floor(-a) != -floor(a) for any a formula.
Ecco la formula analitica corretta:
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 formula funziona per tutti (x, y) coppie (dopo aver applicato assi e simmetria diagonale) eccetto (1,0) e (2,2) casi angolo, che non sono rispondenti al modello e codificato nel seguente frammento:
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>
Nota: Il jQuery utilizzato solo per illustrazione, per il codice vedere funzione distance
Sì, Dijkstra e BFS si arriva la risposta, ma penso che il contesto di scacchi di questo problema prevede la conoscenza che può produrre una soluzione che è molto più veloce di un algoritmo di percorso più breve generica, in particolare su una scacchiera infinita.
Per semplicità, descriviamo la scacchiera come (x, y). L'obiettivo è quello di trovare il percorso più breve da (x0, y0) a (x1, y1) utilizzando solo i passi candidati (+ -1, + -2), (+ -2, + -1) e (+ -2 , + -2), come descritto nella domanda di PS
Ecco la nuova osservazione: disegnare un quadrato con gli angoli (x-4, y-4), (x-4, y + 4), (x + 4, y-4), (x + 4, y 4). Questo insieme (lo chiamano S4) contiene 32 punti. Il percorso più breve da qualsiasi di questi 32 punti (x, y) richiede esattamente due movimenti .
Il percorso più breve da uno qualsiasi dei 24 punti nel set S3 (definito simile) a (x, y) richiede almeno due mosse .
Pertanto, se | x1-x0 |> 4 o | y1-y0 |> 4, il percorso più breve da (x0, y0) a (x1, y1) è esattamente due mosse maggiore del percorso più breve da (x0, y0) a S4. E quest'ultimo problema può essere risolto rapidamente con l'iterazione semplice.
Sia N = max (| x1-x0 |, | y1-y0 |). Se N> = 4, allora il percorso più breve da (x0, y0) a (x1, y1) ha ceil (N / 2) passaggi.
L'O (1) risposta di cui sopra [ https://stackoverflow.com/a/8778592/4288232 da Mustafa Serdar Şanlı] non è davvero lavorando. (Vedi (1,1) o (3,2) o (4,4), parte per i casi evidenti bordo di (1,0) o (2,2)).
Di seguito è una soluzione molto più brutto (Python), che fa il lavoro (con "prove", ha aggiunto):
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()
Quello che dovete fare è pensare le possibili mosse del cavaliere come un grafico, in cui ogni posizione sulla scacchiera è un nodo e le possibili mosse per altra posizione come un vantaggio. Non è necessario per l'algoritmo di Dijkstra, perché ogni bordo ha lo stesso peso o la distanza (sono tutti altrettanto facile o breve per fare). Si può solo fare una ricerca BFS dal punto di partenza fino a raggiungere la posizione finale.
Soluzione da principi primi in Python
ho incontrato questo problema in un test Codility. Mi hanno dato 30 minuti per risolverlo - mi ci sono voluti molto più lungo di quello per arrivare a questo risultato! Il problema era: il numero di mosse ci vuole per un cavaliere per andare da 0,0 a x, y utilizzando solo legale movimenti di Knight. x ed y sono stati più o meno illimitata (quindi non stiamo parlando di una semplice scacchiera 8x8).
Volevano un O (1) soluzione. Volevo una soluzione in cui il programma è stato chiaramente risolvere il problema (cioè volevo qualcosa di più, ovviamente, diritto di modello di Graeme - modelli hanno l'abitudine di abbattere in cui non siete in cerca), e volevo davvero di non fare affidamento su un formula indiscusse, come nella soluzione di Mustafa
Quindi, ecco la mia soluzione, per quello che vale. Iniziare, come altri hanno, notando la soluzione è simmetrico attorno agli assi e diagonali, quindi dobbiamo risolvere solo per 0> = y> = x. Per semplicità di spiegazione (e codice) ho intenzione di invertire il problema:. Il cavaliere inizia alle x, y, e punta a 0,0
Supponiamo di ridurre il problema verso il basso per la vicinanza della provenienza. Arriveremo a cio 'vicinty' significa in realtà a tempo debito, ma per ora, facciamo solo scrivere alcune soluzioni in giù in un bigino (origine in basso a sinistra):
2 1 4 3
3 2 1 2
0 3 2 3
Quindi, dato x, y sulla griglia, si può solo leggere il numero di mosse all'origine.
Se abbiamo iniziato al di fuori della griglia, dobbiamo lavorare il nostro modo di nuovo esso. Si introduce il 'linea mediana', che è la linea rappresentata da y = x / 2. Qualsiasi cavaliere in x, y su quella linea può funzionare suo ritorno in bigino utilizzando una serie di 8 mosse in punto (cioè: (-2, -1) si muove). Se x, y si trova sopra la linea mediana, allora avremo bisogno una successione di ore 8 e ore 7 si muove, e se si trova al di sotto della linea mediana, avremo bisogno di una successione ore 8 e 10 o 'orologio si muove. Due cose da notare qui:
- Queste sequenze sono dimostrabilmente percorsi più brevi. (Vuoi che lo dimostri, o è evidente?)
- ci interessa solo il numero di tali movimenti. Siamo in grado di mix-and-match le mosse in qualsiasi ordine.
Quindi, diamo un'occhiata alle mosse sopra della linea mediana. Quello che stiamo affermando è che:
-
(dx, dy) = (2,1; 1,2) (n8; n7) (notazione matriciale, senza la matematica, - vettore colonna (dx, dy) è uguale alla matrice quadrata applica vettore colonna ( n8; n7) - il numero di 8 mosse in punto e il numero di 7 mosse in punto), e allo stesso modo;
-
(dx, dy) = (2,2, 1, -1) (n8; n10)
sto sostenendo che dx, dy sarà grosso modo (x, y), quindi (x-dx, y-dy) sarà in prossimità della provenienza (qualunque cosa 'prossimita' risulta essere).
Le due righe nel codice che calcolano questi termini sono la soluzione a questi, ma sono selezionati per avere alcune proprietà utili:
- I movimenti sopra mediana formula (x, y) ad una di (0,0), (1,1), o (2,2).
- La formula muove sotto-linea mediana (x, y) ad una di (0,0), (1,0), (2,0), o (1,1).
(Volete prove di questi?) Quindi, la distanza del Cavaliere sarà la somma di N7, N8, N10 e bigino [x-dx, y-dy], e la nostra bigino riduce a questo:
. . 4
. 2 .
0 3 2
Ora, questo non è proprio la fine della storia. Guardate il 3 sulla riga in basso. Gli unici modi in cui possiamo raggiungere questo sono o:
- Abbiamo iniziato lì, o
- Ci siamo trasferiti lì, da una sequenza di 8 ore e 10 mosse in punto. Ma se l'ultima mossa era un ore 8 (che è il diritto di essere, dal momento che possiamo fare le nostre mosse in qualsiasi ordine), allora dobbiamo aver attraversato (3,1), la cui distanza è in realtà 2 (come si può vedere dal bigino originale). Quindi, quello che dovremmo fare è di nuovo in pista 01:00 8 mossa, risparmiando due mosse in totale.
C'è un'ottimizzazione simile per essere avuto con i 4 in alto a destra. Oltre a partire da lì, l'unico modo per raggiungere cioè da una mossa ore 8 da (4,3). Quello'S non sul bigino, ma se fosse lì, la sua distanza sarebbe 3, perché potremmo avere 7 o'clocked a (3,1), invece, che ha una distanza di soli 2. Quindi, dovremmo back-track un 8-in punto movimento, e poi andare avanti di un 7-in punto.
Quindi, abbiamo bisogno di aggiungere più un numero al bigino:
. . 4
. 2 . 2
0 3 2
(Nota: ci sono un intero carico di ottimizzazioni back-tracking da (0,1) e (0,2), ma dal momento che il solutore non potrà mai portarci lì, non hanno bisogno di preoccuparsi di loro.)
Quindi, ecco, allora, è un codice Python per valutare questa:
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]
Per inciso, se si vuole conoscere un percorso vero e proprio, quindi questo algoritmo prevede che troppo: si tratta semplicemente di una successione di n7 7 in punto si muove, seguito da (o) intervallati da n8 8 in punto si muove, n10 movimenti 10-in punto, e qualsiasi ballo è dettata dalla bigino (che, a sua volta, può essere in un bigino).
Ora: come dimostrare questo è giusto. Non è sufficiente solo per confrontare questi risultati con una tabella di risposte giuste, perché il problema stesso è illimitato. Ma possiamo dire che, se la distanza del Cavaliere di una piazza s è d, quindi se {m} è l'insieme di mosse legali da s, la distanza del Cavaliere di (s + m) deve essere o d-1 o D + 1 per tutti m. (Avete bisogno di una prova di questo?) Inoltre, ci deve essere almeno una di queste quadrato la cui distanza è D-1, a meno che non s è l'origine. Quindi, siamo in grado di dimostrare la correttezza, mostrando questa proprietà vale per ogni quadrato. Così:
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")
In alternativa, possiamo dimostrare la correttezza di una qualsiasi piazza s inseguendo il percorso da s in discesa all'origine. Innanzitutto, controllare s per ragionevolezza come sopra, quindi selezionare qualsiasi s + m tale che la distanza (s + m) == d-1. Ripetere fino a quando si raggiunge 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.
Non ho ancora studiato i grafici...per quanto riguarda il problema di implementarlo tramite semplici array, non sono riuscito a ricavare alcuna soluzione diversa da questa.Ho trattato le posizioni non come ranghi e file (la solita notazione degli scacchi), ma come indici di array.Per tua informazione, questo è solo per una scacchiera 8*8.Qualsiasi consiglio migliorativo è sempre ben accetto.
*I commenti dovrebbero essere sufficienti per comprendere la logica.Tuttavia, puoi sempre chiedere.
*Verificato sul compilatore DEV-C++ 4.9.9.2 (Bloodshed Software).
Credo che questo potrebbe anche aiutare ..
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
e l'utilizzo di programmazione dinamica per ottenere la soluzione.
P.S:. Esso utilizza pò BFS senza dover prendere il disturbo di dichiarare nodi e bordi del grafico
Ecco una soluzione per questo problema particolare implementato in Perl. Si mostrerà uno dei percorsi più brevi -. Ci potrebbe essere più di una, in alcuni casi
non ho usato uno qualsiasi degli algoritmi di cui sopra - ma sarebbe bello per confrontarlo con altre soluzioni
.#!/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));
}
}
codice appena rubino da jsfiddle di risposta di Graeme Pyle sopra , a righe tutto il codice in più e convertito rimanendo al rubino solo per ottenere la soluzione dal suo algoritmo, sembra funzionare. Ancora test però:
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)
Solo intenzione è quella di salvare qualcuno qualche tempo la conversione di codice, se qualcuno ha bisogno di codice completo.
Ecco la versione di PHP della funzione di Jules maggio
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];
}
Ecco il mio programma. Questa non è una soluzione perfetta. Ci sono un sacco di cambiamenti per rendere nella funzione ricorsione. Ma questo risultato finale è perfetto. Ho cercato di ottimizzare un po '.
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;
}
}
Ecco una versione C sulla base di Mustafa codice Serdar Şanlı che funziona per una scheda 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));
}
}
Prova qui con la prova contro una soluzione ricorsiva
