4
I am implementing a problem in Java. The problem consists of an Nxn board, 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 positions
- Wolves can move a house in any direction
- In one move, the chicken moves in one of 4 possible directions
- The wolves will move after the chicken
- If a wolf is in the same row/column as the hen, it moves only in the row/column, chasing the hen
- If it is not in the same row/column of the chicken, it moves in the correct diagonal to the chase
- After all movements, it is checked whether the chicken has been caught
The problem is to develop an algorithm based on backtracking who, after 10 rounds, finds out whether or not the chicken can escape the wolves.
My problem is in backtracking of wolves. After the chicken is captured the first time, I can make it go back to its previous position to try another alternative, but I can’t get the wolves back to their previous position. Follow 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;
}
}
I’m sorry, but what is backtracing? Could you clarify better what your doubt is?
– Math
Backtracking is a method of building algorithms. It basically works like this:An initial search in a program with backtracking follows the pattern deep search, that is, the tree is systematically traversed from top to bottom and from left to right. When this search fails, or a terminal node of the tree is found, the backtracking mechanism comes into operation.This procedure causes the system to return by the same path traveled in order to find alternative solutions.That is, It’s nothing more than a "go back" mechanism. If something fails, return.
– Pedro Webber
You must keep a record of the nodes you’ve traveled to do this.
– Jorge B.
Uses the project pattern Memento.
– Oralista de Sistemas