I'm implementing a problem in Java. The problem consists of a NxN tray, where a chicken and X wolves are placed. I get the size of the board, the position of the chicken, the number of wolves and the position of the wolves via standard input, something like this:
8 //tamanho do tabuleiro
2 3 //coluna e linha da galinha
3 //quantidade de lobos
6 0 //coluna e linha lobo1
3 7 //coluna e linha lobo2
2 1 //coluna e linha lobo3
The problem has the following rules:
- The chicken can move a single house in the north, south, east, west
- Wolves can move a house in any direction
- In a move, the chicken moves in one of the 4 possible directions
- The wolves will move after the chicken
- If a wolf is in the same line / column as the chicken, it moves only in the row / column, chasing the chicken
- If it is not in the same row / column as the chicken, it moves on the correct diagonal for the chase
- After all the movements, it is checked if the chicken has been captured
The problem is to develop an backtracking algorithm that, after 10 rounds, finds out whether or not the hen can escape from the wolves.
My problem lies in the backtracking of the wolves. After the hen is captured at a first time, I can get her back to the previous position to try another alternative, but I can not get the wolves back to the previous position. Here is my code below:
public class Galinha {
protected int X;
protected int Y;
public Galinha(int x, int y){
X = x;
Y = y;
}
protected Galinha thisClone() {
Galinha g = new Galinha(this.X, this.Y);
return g;
}
}
public class Lobo {
protected int X;
protected int Y;
public Lobo(int x, int y){
X = x;
Y = y;
}
public void persegueGalinha(Galinha g){
if( this.X > g.X)
this.X--;
if( this.X < g.X)
this.X++;
if(this.Y > g.Y)
this.Y--;
if(this.Y < g.Y)
this.Y++;
}
public boolean comeuGalinha(Galinha g){
return (X == g.X && Y == g.Y);
}
public Lobo thisClone() {
Lobo l = new Lobo(this.X, this.Y);
return l;
}
}
public class TrabComplex {
private static char[][] tabuleiro;
private static Galinha galinha;
private static Lobo[] lobos;
private static int nroLobos;
private static int rodada = 100;
private static int cont = 0;
public static void main(String[] args) {
int tamanho = 8;
tabuleiro = new char[tamanho][tamanho];
galinha = new Galinha(3, 1);
tabuleiro[galinha.X][galinha.Y] = 'G';
nroLobos = 3;
lobos = new Lobo[nroLobos];
Lobo l1 = new Lobo(7, 0);
Lobo l2 = new Lobo(0, 6);
Lobo l3 = new Lobo(3, 6);
lobos[0] = l1;
lobos[1] = l2;
lobos[2] = l3;
tabuleiro[l1.X][l1.Y] = 'L';
tabuleiro[l2.X][l2.Y] = 'L';
tabuleiro[l3.X][l3.Y] = 'L';
moveGalinha(galinha, lobos);
}
public static void printMatriz() {
for (int i = 0; i < tabuleiro.length; i++) {
for (int j = 0; j < tabuleiro.length; j++) {
if (tabuleiro[i][j] == 'L') {
System.out.print("L");
} else if (tabuleiro[i][j] == 'G') {
System.out.print("G");
} else {
System.out.print(".");
}
}
System.out.println("");
}
}
public static void moveGalinha(Galinha galinhaLoop, Lobo[] lobosLoop) {
Galinha galinhaAux = galinhaLoop.thisClone();
cont++;
printMatriz();
System.out.println("--------------------------");
Lobo[] lobosAux = cloneLobos(lobosLoop);
for (int x = galinhaLoop.X - 1; x <= galinhaLoop.X + 1; x++) {
if (cont < rodada && x > -1 && x < 8) {
tabuleiro[galinhaLoop.X][galinhaLoop.Y] = '.';
galinhaAux.X = x;
galinhaAux.Y = galinhaLoop.Y;
tabuleiro[x][galinhaAux.Y] = 'G';
for (int i = 0; i < lobos.length; i++) {
tabuleiro[lobosLoop[i].X][lobosLoop[i].Y] = '.';
Lobo loboAux = lobosLoop[i].thisClone();
loboAux.X = lobosLoop[i].X;
loboAux.Y = lobosLoop[i].Y;
loboAux.persegueGalinha(galinhaLoop);
if (!TestaPosicaoLobo(loboAux.X, loboAux.Y)) {
loboAux.X = lobosLoop[i].X;
loboAux.Y = lobosLoop[i].Y;
tabuleiro[lobosLoop[i].X][lobosLoop[i].Y] = 'L';
}
tabuleiro[loboAux.X][loboAux.Y] = 'L';
lobosAux[i] = loboAux;
if (lobosLoop[i].comeuGalinha(galinhaLoop)) {
System.out.println("Lobo pegou a galinha!");
return;
}
}
moveGalinha(galinhaAux, lobosAux);
}
}
for (int y = galinhaLoop.Y - 1; y <= galinhaLoop.Y + 1; y++) {
if (cont < rodada && y > -1 && y < 8) {
tabuleiro[galinhaLoop.X][galinhaLoop.Y] = '.';
galinhaAux.X = galinhaLoop.X;
galinhaAux.Y = y;
tabuleiro[galinhaAux.X][y] = 'G';
for (int i = 0; i < lobos.length; i++) {
tabuleiro[lobosLoop[i].X][lobosLoop[i].Y] = '.';
Lobo loboAux = lobosLoop[i].thisClone();
loboAux.X = lobosLoop[i].X;
loboAux.Y = lobosLoop[i].Y;
loboAux.persegueGalinha(galinhaLoop);
if (!TestaPosicaoLobo(loboAux.X, loboAux.Y)) {
loboAux.X = lobosLoop[i].X;
loboAux.Y = lobosLoop[i].Y;
tabuleiro[lobosLoop[i].X][lobosLoop[i].Y] = 'L';
}
tabuleiro[loboAux.X][loboAux.Y] = 'L';
lobosAux[i] = loboAux;
if (lobosLoop[i].comeuGalinha(galinhaLoop)) {
System.out.println("Lobo pegou a galinha!");
return;
}
}
moveGalinha(galinhaAux, lobosAux);
}
}
}
public static boolean TestaPosicaoLobo(int x, int y) {
return tabuleiro[x][y] != 'L';
}
private static Lobo[] cloneLobos(Lobo[] listaLobos) {
Lobo[] lobos = new Lobo[nroLobos];
for (int i = 0; i < listaLobos.length; i++) {
lobos[i] = listaLobos[i].thisClone();
}
return lobos;
}
private boolean LobosComeramGalinha(Lobo[] listaLobos, Galinha g){
for(int i = 0; i < listaLobos.length; i++){
if(listaLobos[i].X == g.X && listaLobos[i].Y == g.Y){
return true;
}
}
return false;
}
}
