Caminho mais curto de Knight no tabuleiro de xadrez
https://stackoverflow.com/questions/2339101
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho praticado para uma próxima competição de programação e tropecei em uma pergunta em que estou completamente confuso. No entanto, sinto que é um conceito que devo aprender agora, em vez de cruzar os dedos que nunca aparece.
Basicamente, ele lida com uma peça de cavaleiro em um tabuleiro de xadrez. Você recebe duas entradas: localização inicial e localização final. O objetivo é calcular e imprimir o caminho mais curto que o cavaleiro pode seguir para chegar ao local do destino.
Eu nunca lidei com coisas mais curtas e nem sei por onde começar. Que lógica eu emprego para enfrentar isso?
PS Se for de alguma relevância, eles querem que você complemente os movimentos normais do cavaleiro, permitindo que ele se mova para os quatro cantos do quadrado formado pelos (potencialmente) oito movimentos que um cavaleiro pode fazer, dado que o centro do quadrado é A localização do cavaleiro.
Solução
Você tem um gráfico aqui, onde todos os movimentos disponíveis estão conectados (valor = 1) e movimentos indisponíveis são desconectados (valor = 0), a matriz esparsa seria como:
(a1,b3)=1,
(a1,c2)=1,
.....
E o caminho mais curto de dois pontos em um gráfico pode ser encontrado usando http://en.wikipedia.org/wiki/dijkstra's_algorithm
Pseudo-código da Página da Wikipedia:
function Dijkstra(Graph, source):
for each vertex v in Graph: // Initializations
dist[v] := infinity // Unknown distance function from source to v
previous[v] := undefined // Previous node in optimal path from source
dist[source] := 0 // Distance from source to source
Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized - thus are in Q
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[]
if dist[u] = infinity:
break // all remaining vertices are inaccessible from source
remove u from Q
for each neighbor v of u: // where v has not yet been removed from Q.
alt := dist[u] + dist_between(u, v)
if alt < dist[v]: // Relax (u,v,a)
dist[v] := alt
previous[v] := u
return dist[]
EDITAR:
- como idiota, disse usando ohttp://en.wikipedia.org/wiki/a*_algorithmpode ser mais rápido.
- A maneira mais rápida é pré-calcular todas as distâncias e salvá-las em uma matriz completa de 8x8. Bem, eu chamaria isso de trapaça e funciona apenas porque o problema é pequeno. Mas às vezes as competições verificarão a rapidez com que seu programa é executado.
- O ponto principal é que, se você estiver se preparando para uma competição de programação, deve conhecer algoritmos comuns, incluindo o Dijkstra's. Um bom ponto de partida é ler
Introduction to AlgorithmsISBN 0-262-03384-4. Ou você pode tentar a Wikipedia, http://en.wikipedia.org/wiki/list_of_algorithms
Outras dicas
EDITAR: Veja a resposta de Simon, onde ele consertou a fórmula apresentada aqui.
Na verdade, existe uma fórmula O (1)
Esta é uma imagem que fiz para visualizá -la (quadrados que um cavaleiro pode alcançar em nº mover são pintados com a mesma cor).
Você pode notar o padrão aqui?
Embora possamos ver o padrão, é realmente difícil encontrar a função f( x , y ) que retorna o número de movimentos necessários para ir do quadrado ( 0 , 0 ) para quadrado ( x , y )
Mas aqui está a fórmula que funciona 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: Esta pergunta foi feita em Saco 2007 Dia 1
E soluções são aqui
Aqui está uma solução O (1) correta, mas para o caso em que o cavaleiro se move como apenas um cavaleiro de xadrez e em um quadro de xadrez infinito:
https://jsfiddle.net/graemian/5qgvr1ba/11/
A chave para descobrir isso é observar os padrões que emergem quando você desenha a placa. No diagrama abaixo, o número no quadrado é o número mínimo de movimentos necessários para alcançar esse quadrado (você pode usar a primeira pesquisa para encontrar isso):
Como a solução é simétrica entre os eixos e as diagonais, eu apenas desenhei o caso x> = 0 e y> = x.
O bloco inferior esquerdo é a posição inicial e os números nos blocos representam o número mínimo de movimentos para atingir esses blocos.
Existem 3 padrões para perceber:
- Os grupos verticais azuis incrementadores de 4
- As diagonais vermelhas "primárias" (elas correm de cima para o canto superior direito, como uma barra de barragem)
- As diagonais verdes "secundárias" (a mesma orientação que o vermelho)
(Certifique-se de ver os dois conjuntos de diagonais como superior esquerdo para o canto inferior direito. Eles têm uma contagem de movimentos constantes. As diagonais superiores à direita inferior direita são muito mais complexas.)
Você pode derivar fórmulas para cada uma. Os blocos amarelos são casos especiais. Então a solução se torna:
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);
}
Com o mais difícil de ser os grupos verticais:
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);
}
Veja o violino para os outros casos.
Talvez haja padrões mais simples ou mais elegantes que eu perdi? Nesse caso, eu adoraria vê -los. Em particular, noto alguns padrões diagonais nos casos verticais azuis, mas não os explorei. Independentemente disso, esta solução ainda satisfaz a restrição O (1).
Problema muito interessante que fui encontrado recentemente. Depois de procurar algumas soluções, tentei recuperar a fórmula analítica (O(1) time and space complexity) dado em Saco 2007 Dia 1 soluções.
Primeiro de tudo, quero apreciar Graeme Pyle Para uma visualização muito boa, que me ajudou a consertar a fórmula.
Por algum motivo (talvez por simplificação ou beleza ou apenas um erro), eles se mudaram minus entre para floor Operador, como resultado, eles erraram a fórmula errada floor(-a) != -floor(a) for any a.
Aqui está a fórmula analítica correta:
var delta = x-y;
if (y > delta) {
return delta - 2*Math.floor((delta-y)/3);
} else {
return delta - 2*Math.floor((delta-y)/4);
}
A fórmula funciona para todos os pares (x, y) (depois de aplicar eixos e simetria diagonal), exceto (1,0) e (2,2) casos de canto, que não são satisfeitos com o padrão e codificados no snippet seguinte:
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: o jQuery usado apenas para ilustração, para o código, consulte distance função.
Sim, Dijkstra e BFS receberão a resposta, mas acho que o contexto de xadrez desse problema fornece conhecimento que pode produzir uma solução muito mais rápida que um algoritmo genérico de caminho mais curto, especialmente em uma placa de xadrez infinita.
Para simplificar, vamos descrever o quadro de xadrez como o avião (x, y). O objetivo é encontrar o caminho mais curto de (x0, y0) a (x1, y1) usando apenas as etapas do candidato (+-1,+-2), (+-2,+-1) e (+-2 , +-2), conforme descrito no PS da pergunta
Aqui está a nova observação: Desenhe um quadrado com cantos (X-4, Y-4), (X-4, Y+4), (x+4, Y-4), (x+4, y+4) . Este conjunto (Call It S4) contém 32 pontos. O caminho mais curto de qualquer um desses 32 pontos para (x, y) requer Exatamente dois movimentos.
O caminho mais curto de qualquer um dos 24 pontos no conjunto S3 (definido da mesma forma) a (x, y) requer pelo menos dois movimentos.
Portanto, se | x1-x0 |> 4 ou | y1-y0 |> 4, o caminho mais curto de (x0, y0) a (x1, y1) é exatamente dois movimentos maiores que o caminho mais curto de (x0, y0) para S4. E o último problema pode ser resolvido rapidamente com iteração direta.
Seja n = max (| x1-x0 |, | y1-y0 |). Se n> = 4, então o caminho mais curto de (x0, y0) para (x1, y1) tem CEIL (N/2) degraus.
A resposta O (1) acima [https://stackoverflow.com/a/8778592/4288232 Por Mustafa Serdar şanlı] não está realmente funcionando. (Verifique (1,1) ou (3,2) ou (4,4), além dos casos óbvios de (1,0) ou (2,2)).
Abaixo está uma solução muito mais feia (Python), que funciona (com "testes adicionais"):
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()
O que você precisa fazer é pensar nos possíveis movimentos do cavaleiro como um gráfico, onde todas as posições da placa são um nó e os possíveis movimentos para outra posição como uma borda. Não há necessidade do algoritmo de Dijkstra, porque cada borda tem o mesmo peso ou distância (todos são igualmente fáceis ou curtos). Você pode simplesmente fazer uma pesquisa de BFS no seu ponto de partida até chegar à posição final.
Solução dos primeiros princípios em Python
Eu encontrei esse problema pela primeira vez em um teste de codilidade. Eles me deram 30 minutos para resolvê -lo - levei consideravelmente mais do que isso para chegar a esse resultado! O problema era: quantos movimentos são necessários para um cavaleiro passar de 0,0 para x, y usando apenas os movimentos do Cavaleiro Legal. X e Y eram mais ou menos ilimitados (por isso não estamos falando aqui sobre um quadro de xadrez 8x8 simples).
Eles queriam uma solução O (1). Eu queria uma solução em que o programa estava resolvendo claramente o problema (ou seja, eu queria algo mais obviamente certo do que o padrão de Graeme - os padrões têm o hábito de quebrar onde você não está olhando), e eu realmente queria não ter que confiar em um fórmula sem seqüência, como na solução de Mustafa
Então, aqui está minha solução, pelo que vale a pena. Iniciar, como outros, observando a solução é simétrica sobre os eixos e diagonais, precisamos resolver apenas para 0> = y> = x. Para simplificar a explicação (e o código), vou reverter o problema: o cavaleiro começa em x, y e está buscando 0,0.
Suponhamos que diminuamos o problema até a vizinhança da origem. Vamos chegar ao que 'Vicinty' realmente significa no devido tempo, mas, por enquanto, vamos apenas escrever algumas soluções em uma folha de trapaça (origem no canto inferior esquerdo):
2 1 4 3
3 2 1 2
0 3 2 3
Então, dado o X, Y na grade, podemos apenas ler o número de movimentos para a origem.
Se começamos fora da grade, temos que voltar a ele. Introduzimos a 'linha média', que é a linha representada por y = x/2. Qualquer cavaleiro em x, y nessa linha pode voltar à folha de trapaceiros usando uma série de movimentos das 8 horas (ou seja: (-2, -1) movimentos). Se x, y estiver acima da linha média, precisaremos de uma sucessão de 8 horas e 7 horas e se estiver abaixo da linha média, precisaremos de uma sucessão de 8 horas e 10 o 'O relógio se move. Duas coisas a serem observadas aqui:
- Essas seqüências são caminhos comprovadamente mais curtos. (Quer que eu prove isso, ou é óbvio?)
- Nós nos preocupamos apenas com o número desses movimentos. Podemos misturar e combinar os movimentos em qualquer ordem.
Então, vamos olhar para os movimentos acima do meio da linha. O que estamos afirmando é que:
(dx; dy) = (2,1; 1,2) (n8; n7) (notação da matriz, sem matemática - vetor de coluna (dx; dy) é igual à matriz quadrada multiplicada pelo vetor de coluna (n8; n7) - o número de movimentos das 8 horas e o número de movimentos das 7 horas) e da mesma forma;
(dx; dy) = (2,2; 1, -1) (n8; n10)
Estou alegando que o dx, dy será aproximadamente (x, y), então (x-dx, y-dy) estará nas proximidades da origem (qualquer que seja a 'vizinhança').
As duas linhas no código que calculam esses termos são a solução para elas, mas são selecionadas para ter algumas propriedades úteis:
- A fórmula acima da linha média se move (x, y) para um dos (0,0), (1,1) ou (2,2).
- A fórmula abaixo da linha média se move (x, y) para um dos (0,0), (1,0), (2,0) ou (1,1).
(Você gostaria de provas dessas?) Então, a distância do cavaleiro será a soma de N7, N8, N10 e Cheatsheet [x-dx, y-dy], e nossa folha de dicas reduz a isso:
. . 4
. 2 .
0 3 2
Agora, este não é exatamente o fim da história. Olhe para os 3 na linha inferior. As únicas maneiras pelas quais podemos alcançar isso são:
- Começamos lá, ou
- Nós nos mudamos para lá, por uma sequência de 8 horas e movimentos das 10 horas. Mas se a última jogada foi um às 8 horas (que tem o direito de ser, pois podemos fazer nossos movimentos em qualquer ordem), então devemos ter passado (3,1), cuja distância é realmente 2 (como você pode veja na folha de dicas originais). Então, o que devemos fazer é traseira, uma movimentação de 8 horas, salvando dois movimentos no total.
Há uma otimização semelhante a ser obtida com o 4 no canto superior direito. Além de começar por lá, a única maneira de alcançar isso é uma mudança das 8 horas de (4,3). Isso não está na folha de trapaceiros, mas se estivesse lá, sua distância seria 3, porque poderíamos ter 7 horas para (3,1), que tem uma distância de apenas 2. Então, devemos traseira 8-O'Clock Mova-se e depois vá em frente um 7-O'Clock.
Então, precisamos adicionar mais um número à folha de trapaceiros:
. . 4
. 2 . 2
0 3 2
(Nota: há um monte de otimizações de rastreamento de fundo de (0,1) e (0,2), mas como o solucionador nunca nos levará até lá, não precisamos nos preocupar com eles.)
Então, aqui, há algum código Python para avaliar isso:
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]
Aliás, se você quiser conhecer uma rota real, esse algoritmo também fornece isso: é simplesmente uma sucessão de movimentos N7 7-O'Clock, seguido de (ou intercalado com) N8 8-O'Clock Moves, N10 10- O'Clock se move, e qualquer dança ditada pela folha de dicas (que, por si só, pode estar em uma folha de trapaceiros).
Agora: como provar isso é certo. Não basta apenas comparar esses resultados com uma tabela de respostas certas, porque o problema em si é ilimitado. Mas podemos dizer que, se a distância do cavaleiro de um quadrado S for D, se {m} for o conjunto de movimentos legais de s, a distância do cavaleiro de (s+m) deve ser d-1 ou d+1 para todos m. (Você precisa de uma prova disso?) Além disso, deve haver pelo menos um desses quadrados cuja distância é D-1, a menos que S seja a origem. Portanto, podemos provar a correção mostrando que essa propriedade é mantida para cada quadrado. Desta forma:
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")
Como alternativa, podemos provar a correção de qualquer um quadrado s perseguindo a rota de S ladeira abaixo para a origem. Primeiro, verifique se a razoabilidade acima e selecione qualquer s+m de modo que a distância (s+m) == d-1. Repita até chegarmos à origem.
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.
Ainda não estudei gráficos ... como o problema de implementá -lo por meio de simplesmente matrizes, não pude derivar nenhuma solução além disso. Tratei as posições não como classificações e arquivos (a notação usual de xadrez), mas como índices de matriz. Para sua informação, isso é apenas para um quadro de xadrez de 8*8. Qualquer conselho de melhoria é sempre bem -vindo.
*Os comentários devem ser suficientes para sua compreensão da lógica. No entanto, você pode sempre perguntar.
*Verificado no dev-c ++ 4.9.9.2 Compilador (software de derramamento de sangue).
Eu acho que isso também pode ajudá -lo ..
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
e usando programação dinâmica para obter a solução.
PS: Ele meio que usa o BFS sem precisar ter o trabalho de declarar os nós e as bordas do gráfico.
Aqui está uma solução para esse problema específico implementado no Perl. Ele mostrará um dos caminhos mais curtos - pode haver mais de um em alguns casos.
Não usei nenhum dos algoritmos descritos acima - mas seria bom compará -lo com outras soluções.
#!/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));
}
}
Apenas o código rubi de JSfiddle da resposta de Graeme Pyle acima, listrou todo o código extra e convertido restante para Ruby apenas para obter solução pelo algoritmo, parece funcionar. Ainda está testando:
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)
Somente a intenção é salvar alguém algum tempo convertendo código se alguém precisar de código completo.
Aqui está a versão PHP da função de Jules May
function knightDistance($x, $y)
{
$x = abs($x);
$y = abs($y);
if($x < $y)
{
$tmp = $x;
$x = $y;
$y = $tmp;
}
if($x > 2 * $y)
{
$n7 = 0;
$n8 = floor(($x + 2*$y) / 4);
$n10 = floor(($x - 2*$y +1) / 4);
}
else
{
$n7 = floor((2*$y - $x) / 3);
$n8 = floor((2*$x - $y) / 3);
$n10 = 0;
}
$x -= 2 * $n8 + $n7 + 2 * $n10;
$y -= $n8 + 2 * $n7 - $n10;
if($x == 1 && $y == 0)
{
if($n8 > 0)
{
$x = 3;
$y = 1;
$n8--;
}
}
if($x == 2 && $y == 2)
{
if($n8 > 0)
{
$x = 3;
$y = 1;
$n8--;
$n7++;
}
}
$cheatsheet = [[0, 3, 2], [2, 0, 2], [4]];
return $n7 + $n8 + $n10 + $cheatsheet [$y][$x-$y];
}
Aqui está o meu programa. Esta não é uma solução perfeita. Existem muitas alterações a serem feitas na função de recursão. Mas esse resultado final é perfeito. Eu tentei otimizar um pouco.
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;
}
}
Aqui está uma versão C baseada no código Mustafa Serdar şanlı que funciona para uma placa 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));
}
}
Teste aqui com prova contra uma solução recursiva
