O passeio do cavalo é um problema baseado nos movimentos do cavalo no tabuleiro de xadrez, sempe em 'L'. Este problema é dito intratável por conta do número de movimentos possíveis, desta forma não é viável a utilização de algoritmos de força bruta para resolve-lo. A solução consiste em passear com o cavalo por todas as casas de um tabuleiro com 64 posições (8 x 8), para tanto utiliza-se a teoria dos grafos ou algum tipo de heurística para modelagem do problema. No exemplo que a ser demonstrado é utilizada a heurística do diamante e do quadrado.
A heurística do diamante e quadrado consiste em dividir o tabuleiro em quatro quadrantes e apartir de um ponto qualquer preencher as posições por onde o cavalo pode passar de acordo 4 tipos de figuras, como demonstrado na imagem acima. Deve-se preencher tipos intercalados de figura, por exemplo, se iniciar preenchendo um diamante na diagonal principal, esta figura é preenchida em todos os outros quadrante e a próxima figura a ser preenchida deverá ser um quadrado. O inverso também é válido, se iniciar com um quadrado, a próxima figura deverá ser um diamante. No desenvolvimento do algoritmo alguns cuidados devem ser tomados, como certificar-se de que o ponto final da figura que está sendo preenchida permita acesso a mesma figura no próximo quadrante ou no caso de ser o último quadrante, para a próxima figura a ser preenchida.
Na imagem acima, o programa desenvolvido em java, onde o usuário seleciona uma determinada posição do tabuleiro e visualiza os possíveis trajetos percorridos pelo cavalo. Se cruzarmos uma linha na sequencia em que os números aparecem na tela pode-se conferir o formato das figuras diamante e quadrado.
Segue abaixo o código fonte, com as seis classes implementadas.
// classe PasseioDoCavalo
package passeiodocavalo;
/**
*
* @author jaison
*/
public class PasseioDoCavalo {
private Celula[][] tabuleiro = new Celula[8][8];
public PasseioDoCavalo(){
for(int x=0; x
for(int y=0; y
getTabuleiro()[x][y] = new Celula();
}
}
}
public void impimeTabuleiro(){
for(int x=0; x
for(int y=0; y
System.out.println(" [ "+x+ " "+y+" ] "+ getTabuleiro()[x][y].getPasso() + "\t"); //+ getTabuleiro()[x][y].getQuadrante());
}
System.out.println("\n");
}
}
public boolean preencheFigura(int x_pos, int y_pos){
boolean ret = false;
switch(getTabuleiro()[x_pos][y_pos].getFigura()){
case ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL:
if(getTabuleiro()[x_pos][y_pos].getQuadrante() == ConstantDataManager.PRIMEIRO_QUADRANTE){
}
System.out.println("TRIANGULO_DIAGONAL_PRINCIPAL");
break;
case ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA:
System.out.println("TRIANGULO_DIAGONAL_SECUNDARIA");
break;
case ConstantDataManager.QUADRADO_HORIZONTAL:
System.out.println("QUADRADO_HORIZONTAL");
break;
case ConstantDataManager.QUADRADO_INCLINADO:
System.out.println("QUADRADO_INCLINADO");
break;
}
return false;
}
/**
* @return the tabuleiro
*/
public Celula[][] getTabuleiro() {
return tabuleiro;
}
/**
* @param tabuleiro the tabuleiro to set
*/
public void setTabuleiro(Celula[][] tabuleiro) {
this.tabuleiro = tabuleiro;
}
}
// Classe TelaTabuleiro
package passeiodocavalo;
import java.awt.GridLayout;
import java.awt.Point;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
/**
*
* @author jaison
*/
public class TelaTabuleiro extends JFrame {
static JPanel panel;
JButton[][] casas = new JButton[8][8];
public TelaTabuleiro(){
init();
}
public void init(){
panel=new JPanel(new GridLayout(8,8));
for(int x=0; x
for(int y=0; y
casas[x][y] = new JButton(String.valueOf(x)+" "+String.valueOf(y));
casas[x][y].setSize(80,80);
casas[x][y].setActionCommand(String.valueOf(x)+String.valueOf(y));
casas[x][y].addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
carregaTelaTabuleiro(arg0);
}
});
panel.add(casas[x][y]);
}
}
super.setTitle("Selecione a posição inicial no tabuleiro");
super.add(panel);
super.pack();
}
public void carregaTelaTabuleiro(java.awt.event.ActionEvent e){
for(int x=0; x
for(int y=0; y
casas[x][y].setText(" ");
}
}
System.out.println(e.getActionCommand().charAt(0)+" "+e.getActionCommand().charAt(1));
vai(Integer.parseInt(String.valueOf(e.getActionCommand().charAt(0))),
Integer.parseInt(String.valueOf(e.getActionCommand().charAt(1))));
}
public void vai(int x, int y){
ControleMovimentacao c = new ControleMovimentacao();
PasseioDoCavalo p = new PasseioDoCavalo();
c.setTabuleiro(p.getTabuleiro()); // manda o tabuleiro para o controle de movimentação
c.iniciar(x, y); // inicia com a coordenada desejada
if(c.temEstaFiguraNoQuadrante(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL,ConstantDataManager.SEGUNDO_QUADRANTE)){
}
//for(int i=0; i
ArrayList aux = c.caminhosPossiveis(3, 3);
for(int j=0; j
System.out.println( "aqui-> " + aux.get(j));
}
for(int linha=0; linha
for(int coluna=0; coluna
casas[linha][coluna].setText(String.valueOf(p.getTabuleiro()[linha][coluna].getPasso()));
}
}
}
}
// classe ControleMovimentacao
package passeiodocavalo;
import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author jaison
*/
public class ControleMovimentacao {
private Celula[][] tabuleiro;
private Point pontoInicial;
private Point pontoFinal;
private boolean inicio = false;
private List possibilidades = new ArrayList();
private int contadorPassos = 0;
/**
* @return the tabuleiro
*/
public Celula[][] getTabuleiro() {
return tabuleiro;
}
/**
* @param tabuleiro the tabuleiro to set
*/
public void setTabuleiro(Celula[][] tabuleiro) {
this.tabuleiro = tabuleiro;
}
public void iniciar(int x, int y) {
resetTabuleiro(ConstantDataManager.PRIMEIRO_QUADRANTE);
resetTabuleiro(ConstantDataManager.SEGUNDO_QUADRANTE);
resetTabuleiro(ConstantDataManager.TERCEIRO_QUADRANTE);
resetTabuleiro(ConstantDataManager.QUARTO_QUADRANTE);
int figuraAtual;
int quadranteAtual;
int indexPontofinal = 0;
int indexQuadrante = 0;
int contadorCaminhoAlternativo = 0;
int aux_x;
int aux_y;
setInicio(true); // inicia
boolean fluxoNormal = false;
boolean inverteu = false;
setPontoInicial(new Point(x, y));
//setPontoFinal(pontoFinal(getPontoInicial().x, getPontoInicial().y)[0]); // primeira opção de ponto final
figuraAtual = getTabuleiro()[getPontoInicial().x][getPontoInicial().y].getFigura(); // encontra a figura do ponto inicial
quadranteAtual = getTabuleiro()[getPontoInicial().x][getPontoInicial().y].getQuadrante(); // encoontra o quadrante
for (int teste = 0; teste < 55; teste++) {
if(indexPontofinal == 0){
indexPontofinal = 1;
}else{
indexPontofinal = 0;
}
setPontoFinal(pontoFinal(getPontoInicial().x, getPontoInicial().y)[indexPontofinal]);
for (int saltos = 0; saltos < caminhosPossiveis(getPontoFinal().x, getPontoFinal().y).size(); saltos++) {
aux_x = caminhosPossiveis(getPontoFinal().x, getPontoFinal().y).get(saltos).x;
aux_y = caminhosPossiveis(getPontoFinal().x, getPontoFinal().y).get(saltos).y;
if ( getTabuleiro()[aux_x][aux_y].getFigura() == figuraAtual &&
getTabuleiro()[aux_x][aux_y].getQuadrante() == proximoQuadrante(quadranteAtual)[0] &&
getTabuleiro()[aux_x][aux_y].isOcupada() == false ) {
// se encontrar a mesma figura na primeira opção do proximo quadrante
preencheFigura(getPontoInicial(),getPontoFinal());
setPontoInicial(new Point(aux_x, aux_y));
quadranteAtual = getTabuleiro()[aux_x][aux_y].getQuadrante();
figuraAtual = getTabuleiro()[aux_x][aux_y].getFigura();
break;
}else if ( getTabuleiro()[aux_x][aux_y].getFigura() == figuraAtual &&
getTabuleiro()[aux_x][aux_y].getQuadrante() == proximoQuadrante(quadranteAtual)[1] &&
getTabuleiro()[aux_x][aux_y].isOcupada() == false ) {
// se encontrar a mesma figura na segunda opção do proximo quadrante
preencheFigura(getPontoInicial(),getPontoFinal());
setPontoInicial(new Point(aux_x, aux_y));
quadranteAtual = getTabuleiro()[aux_x][aux_y].getQuadrante();
figuraAtual = getTabuleiro()[aux_x][aux_y].getFigura();
break;
} else if (quantasVezesPreenchida(figuraAtual) == 3){
// se a figura atual ja foi preenchida 3 vezes
//preencheFigura(getPontoInicial(),getPontoFinal());
//figuraAtual = proximaFigura(figuraAtual);
if ( getTabuleiro()[aux_x][aux_y].getFigura() == proximaFigura(figuraAtual) &&
getTabuleiro()[aux_x][aux_y].getQuadrante() == proximoQuadrante(quadranteAtual)[0] &&
getTabuleiro()[aux_x][aux_y].isOcupada() == false ) {
preencheFigura(getPontoInicial(),getPontoFinal());
}else if ( getTabuleiro()[aux_x][aux_y].getFigura() == proximaFigura(figuraAtual) &&
getTabuleiro()[aux_x][aux_y].getQuadrante() == proximoQuadrante(quadranteAtual)[1] &&
getTabuleiro()[aux_x][aux_y].isOcupada() == false ){
preencheFigura(getPontoInicial(),getPontoFinal());
}else{
int fim = quantasFigurasPreenchidasNesteQuadrante(ConstantDataManager.PRIMEIRO_QUADRANTE) +
quantasFigurasPreenchidasNesteQuadrante(ConstantDataManager.SEGUNDO_QUADRANTE ) +
quantasFigurasPreenchidasNesteQuadrante(ConstantDataManager.TERCEIRO_QUADRANTE) +
quantasFigurasPreenchidasNesteQuadrante(ConstantDataManager.QUARTO_QUADRANTE );
if(fim == 15){
preencheFigura(getPontoInicial(),getPontoFinal());
}
}
}
}
if(quantasVezesPreenchida(figuraAtual) == 4){
figuraAtual = proximaFigura(figuraAtual);
}
}
}
public boolean proximoPasso() {
boolean ret = false;
if (isInicio()) { // se já iniciou
}
return ret;
}
/*Recebe as coordenadas xy e retorna quais são as casas atingiveis apartir
* deste ponto
**/
public ArrayList caminhosPossiveis(int x, int y) {
getPossibilidades().clear();
if (x + 2 <= 7 && y + 1 <= 7) { // 1
getPossibilidades().add(new Point(x + 2, y + 1));
}
if (x + 2 <= 7 && y - 1 >= 0) { // 2
getPossibilidades().add(new Point(x + 2, y - 1));
}
if (x - 2 >= 0 && y + 1 <= 7) { // 3
getPossibilidades().add(new Point(x - 2, y + 1));
}
if (x - 2 >= 0 && y - 1 >= 0) { // 4
getPossibilidades().add(new Point(x - 2, y - 1));
}
if (y + 2 <= 7 && x + 1 <= 7) { // 5
getPossibilidades().add(new Point(x + 1, y + 2));
}
if (y + 2 <= 7 && x - 1 >= 0) { // 6
getPossibilidades().add(new Point(x - 1, y + 2));
}
if (y - 2 >= 0 && x + 1 <= 7) { // 7
getPossibilidades().add(new Point(x + 1, y - 2));
}
if (y - 2 >= 0 && x - 1 >= 0) { // 8
getPossibilidades().add(new Point(x - 1, y - 2));
}
return (ArrayList) getPossibilidades();
}
/*Recebe uma coordenada e verifica quais as coordenadas finais de acordo com
* o tipo de figura da coordenada
**/
public Point[] pontoFinal(int px, int py) {
Point[] pontosFinais = new Point[2];
pontosFinais[0] = new Point(-1, -1);
pontosFinais[1] = new Point(-1, -1);
getTabuleiro()[px][py].getFigura();
int x = -1;
int y = -1;
switch (getTabuleiro()[px][py].getQuadrante()) {
case ConstantDataManager.PRIMEIRO_QUADRANTE:
x = 0;
y = 0;
break;
case ConstantDataManager.SEGUNDO_QUADRANTE:
x = 0;
y = 4;
break;
case ConstantDataManager.TERCEIRO_QUADRANTE:
x = 4;
y = 0;
break;
case ConstantDataManager.QUARTO_QUADRANTE:
x = 4;
y = 4;
break;
}
switch (getTabuleiro()[px][py].getFigura()) {
case ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL:
if ((px == 0 + x && py == 0 + y) || (px == 3 + x && py == 3 + y)) {
pontosFinais[0] = new Point(1 + x, 2 + y);
pontosFinais[1] = new Point(2 + x, 1 + y);
} else {
pontosFinais[0] = new Point(0 + x, 0 + y);
pontosFinais[1] = new Point(3 + x, 3 + y);
}
break;
case ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA:
if ((px == 0 + x && py == 3 + y) || (px == 3 + x && py == 0 + y)) {
pontosFinais[0] = new Point(1 + x, 1 + y);
pontosFinais[1] = new Point(2 + x, 2 + y);
} else {
pontosFinais[0] = new Point(0 + x, 3 + y);
pontosFinais[1] = new Point(3 + x, 0 + y);
}
break;
case ConstantDataManager.QUADRADO_HORIZONTAL:
if ((px == 0 + x && py == 1 + y) || (px == 3 + x && py == 2 + y)) {
pontosFinais[0] = new Point(2 + x, 0 + y);
pontosFinais[1] = new Point(1 + x, 3 + y);
} else {
pontosFinais[0] = new Point(0 + x, 1 + y);
pontosFinais[1] = new Point(3 + x, 2 + y);
}
break;
case ConstantDataManager.QUADRADO_INCLINADO:
if ((px == 0 + x && py == 2 + y) || (px == 3 + x && py == 1 + y)) {
pontosFinais[0] = new Point(1 + x, 0 + y);
pontosFinais[1] = new Point(2 + x, 3 + y);
} else {
pontosFinais[0] = new Point(0 + x, 2 + y);
pontosFinais[1] = new Point(3 + x, 1 + y);
}
break;
}
return pontosFinais;
}
/*Recebe um quadrante e retorna os próximos quadrantes possíveis
**/
public int[] proximoQuadrante(int quadranteAtual) {
int[] ret = new int[2];
switch (quadranteAtual) {
case ConstantDataManager.PRIMEIRO_QUADRANTE:
ret[0] = ConstantDataManager.SEGUNDO_QUADRANTE;
ret[1] = ConstantDataManager.TERCEIRO_QUADRANTE;
break;
case ConstantDataManager.SEGUNDO_QUADRANTE:
ret[0] = ConstantDataManager.PRIMEIRO_QUADRANTE;
ret[1] = ConstantDataManager.QUARTO_QUADRANTE;
break;
case ConstantDataManager.TERCEIRO_QUADRANTE:
ret[0] = ConstantDataManager.PRIMEIRO_QUADRANTE;
ret[1] = ConstantDataManager.QUARTO_QUADRANTE;
break;
case ConstantDataManager.QUARTO_QUADRANTE:
ret[0] = ConstantDataManager.SEGUNDO_QUADRANTE;
ret[1] = ConstantDataManager.TERCEIRO_QUADRANTE;
break;
default:
ret[0] = 0;
ret[1] = 0;
break;
}
return ret;
}
public int proximaFigura(int figura) {
int ret = 0;
switch (figura) {
case ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL:
ret = ConstantDataManager.QUADRADO_INCLINADO;
break;
case ConstantDataManager.QUADRADO_INCLINADO:
ret = ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA;
break;
case ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA:
ret = ConstantDataManager.QUADRADO_HORIZONTAL;
break;
case ConstantDataManager.QUADRADO_HORIZONTAL:
ret = ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL;
break;
}
return ret;
}
/*Recebe os pontos inicial e final e preenche a figura na tabuleiro
**/
public void preencheFigura(Point pontoInicial, Point pontoFinal) {
if (!getTabuleiro()[pontoInicial.x][pontoInicial.y].isOcupada()) {
incrementaPasso();
getTabuleiro()[pontoInicial.x][pontoInicial.y].setPasso(getContadorPassos());
getTabuleiro()[pontoInicial.x][pontoInicial.y].setOcupada(true);
if (pontoFinal(pontoInicial.x, pontoInicial.y)[0].x != pontoFinal.x &&
pontoFinal(pontoInicial.x, pontoInicial.y)[0].y != pontoFinal.y) {
incrementaPasso();
getTabuleiro()[pontoFinal(pontoInicial.x, pontoInicial.y)[0].x][pontoFinal(pontoInicial.x, pontoInicial.y)[0].y].setPasso(getContadorPassos());
getTabuleiro()[pontoFinal(pontoInicial.x, pontoInicial.y)[0].x][pontoFinal(pontoInicial.x, pontoInicial.y)[0].y].setOcupada(true);
} else {
incrementaPasso();
getTabuleiro()[pontoFinal(pontoInicial.x, pontoInicial.y)[1].x][pontoFinal(pontoInicial.x, pontoInicial.y)[1].y].setPasso(getContadorPassos());
getTabuleiro()[pontoFinal(pontoInicial.x, pontoInicial.y)[1].x][pontoFinal(pontoInicial.x, pontoInicial.y)[1].y].setOcupada(true);
}
if (pontoFinal(pontoFinal.x, pontoFinal.y)[0].x != pontoInicial.x &&
pontoFinal(pontoFinal.x, pontoFinal.y)[0].y != pontoInicial.y) {
incrementaPasso();
getTabuleiro()[pontoFinal(pontoFinal.x, pontoFinal.y)[0].x][pontoFinal(pontoFinal.x, pontoFinal.y)[0].y].setPasso(getContadorPassos());
getTabuleiro()[pontoFinal(pontoFinal.x, pontoFinal.y)[0].x][pontoFinal(pontoFinal.x, pontoFinal.y)[0].y].setOcupada(true);
} else {
incrementaPasso();
getTabuleiro()[pontoFinal(pontoFinal.x, pontoFinal.y)[1].x][pontoFinal(pontoFinal.x, pontoFinal.y)[1].y].setPasso(getContadorPassos());
getTabuleiro()[pontoFinal(pontoFinal.x, pontoFinal.y)[1].x][pontoFinal(pontoFinal.x, pontoFinal.y)[1].y].setOcupada(true);
}
incrementaPasso();
getTabuleiro()[pontoFinal.x][pontoFinal.y].setPasso(getContadorPassos());
getTabuleiro()[pontoFinal.x][pontoFinal.y].setOcupada(true);
}
}
/*Verifica se a referida figura está totalmente preenchida do quadrante indicado
**/
public boolean temEstaFiguraNoQuadrante(int fgr, int quadrante) {
boolean ret = false;
int x = -1;
int y = -1;
switch (quadrante) {
case ConstantDataManager.PRIMEIRO_QUADRANTE:
x = 0;
y = 0;
break;
case ConstantDataManager.SEGUNDO_QUADRANTE:
x = 0;
y = 4;
break;
case ConstantDataManager.TERCEIRO_QUADRANTE:
x = 4;
y = 0;
break;
case ConstantDataManager.QUARTO_QUADRANTE:
x = 4;
y = 4;
break;
}
switch (fgr) {
case ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL:
ret = getTabuleiro()[0 + x][0 + y].isOcupada() &&
getTabuleiro()[1 + x][2 + y].isOcupada() &&
getTabuleiro()[2 + x][1 + y].isOcupada() &&
getTabuleiro()[3 + x][3 + y].isOcupada();
break;
case ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA:
ret = getTabuleiro()[0 + x][3 + y].isOcupada() &&
getTabuleiro()[1 + x][1 + y].isOcupada() &&
getTabuleiro()[2 + x][2 + y].isOcupada() &&
getTabuleiro()[3 + x][0 + y].isOcupada();
break;
case ConstantDataManager.QUADRADO_HORIZONTAL:
ret = getTabuleiro()[0 + x][1 + y].isOcupada() &&
getTabuleiro()[2 + x][0 + y].isOcupada() &&
getTabuleiro()[3 + x][2 + y].isOcupada() &&
getTabuleiro()[1 + x][3 + y].isOcupada();
break;
case ConstantDataManager.QUADRADO_INCLINADO:
ret = getTabuleiro()[0 + x][2 + y].isOcupada() &&
getTabuleiro()[1 + x][0 + y].isOcupada() &&
getTabuleiro()[3 + x][1 + y].isOcupada() &&
getTabuleiro()[2 + x][3 + y].isOcupada();
break;
}
System.out.println(quadrante + " " + fgr);
return ret;
}
/*Verifica quantas figuras estão preenchidas em um quadrante
**/
public int quantasFigurasPreenchidasNesteQuadrante(int q) {
int ret = 0;
if (temEstaFiguraNoQuadrante(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL, q)) {
ret++;
}
if (temEstaFiguraNoQuadrante(ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA, q)) {
ret++;
}
if (temEstaFiguraNoQuadrante(ConstantDataManager.QUADRADO_HORIZONTAL, q)) {
ret++;
}
if (temEstaFiguraNoQuadrante(ConstantDataManager.QUADRADO_INCLINADO, q)) {
ret++;
}
return ret;
}
public int quantasVezesPreenchida(int figura) {
int ret = 0;
if (temEstaFiguraNoQuadrante(figura, ConstantDataManager.PRIMEIRO_QUADRANTE)) {
ret++;
}
if (temEstaFiguraNoQuadrante(figura, ConstantDataManager.SEGUNDO_QUADRANTE)) {
ret++;
}
if (temEstaFiguraNoQuadrante(figura, ConstantDataManager.TERCEIRO_QUADRANTE)) {
ret++;
}
if (temEstaFiguraNoQuadrante(figura, ConstantDataManager.QUARTO_QUADRANTE)) {
ret++;
}
return ret;
}
public void resetTabuleiro(int quadrante) {
int x = -1;
int y = -1;
switch (quadrante) {
case ConstantDataManager.PRIMEIRO_QUADRANTE:
x = 0;
y = 0;
break;
case ConstantDataManager.SEGUNDO_QUADRANTE:
x = 0;
y = 4;
break;
case ConstantDataManager.TERCEIRO_QUADRANTE:
x = 4;
y = 0;
break;
case ConstantDataManager.QUARTO_QUADRANTE:
x = 4;
y = 4;
break;
}
// ---------------------------------------------------------------------
getTabuleiro()[0 + x][0 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL);
getTabuleiro()[1 + x][2 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL);
getTabuleiro()[2 + x][1 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL);
getTabuleiro()[3 + x][3 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL);
getTabuleiro()[0 + x][0 + y].setQuadrante(quadrante);
getTabuleiro()[1 + x][2 + y].setQuadrante(quadrante);
getTabuleiro()[2 + x][1 + y].setQuadrante(quadrante);
getTabuleiro()[3 + x][3 + y].setQuadrante(quadrante);
getTabuleiro()[0 + x][0 + y].setOcupada(false);
getTabuleiro()[1 + x][2 + y].setOcupada(false);
getTabuleiro()[2 + x][1 + y].setOcupada(false);
getTabuleiro()[3 + x][3 + y].setOcupada(false);
// ---------------------------------------------------------------------
getTabuleiro()[0 + x][3 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA);
getTabuleiro()[1 + x][1 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA);
getTabuleiro()[2 + x][2 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA);
getTabuleiro()[3 + x][0 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA);
getTabuleiro()[0 + x][3 + y].setQuadrante(quadrante);
getTabuleiro()[1 + x][1 + y].setQuadrante(quadrante);
getTabuleiro()[2 + x][2 + y].setQuadrante(quadrante);
getTabuleiro()[3 + x][0 + y].setQuadrante(quadrante);
getTabuleiro()[0 + x][3 + y].setOcupada(false);
getTabuleiro()[1 + x][1 + y].setOcupada(false);
getTabuleiro()[2 + x][2 + y].setOcupada(false);
getTabuleiro()[3 + x][0 + y].setOcupada(false);
// ---------------------------------------------------------------------
getTabuleiro()[0 + x][1 + y].setFigura(ConstantDataManager.QUADRADO_HORIZONTAL);
getTabuleiro()[2 + x][0 + y].setFigura(ConstantDataManager.QUADRADO_HORIZONTAL);
getTabuleiro()[3 + x][2 + y].setFigura(ConstantDataManager.QUADRADO_HORIZONTAL);
getTabuleiro()[1 + x][3 + y].setFigura(ConstantDataManager.QUADRADO_HORIZONTAL);
getTabuleiro()[0 + x][1 + y].setQuadrante(quadrante);
getTabuleiro()[2 + x][0 + y].setQuadrante(quadrante);
getTabuleiro()[3 + x][2 + y].setQuadrante(quadrante);
getTabuleiro()[1 + x][3 + y].setQuadrante(quadrante);
getTabuleiro()[0 + x][1 + y].setOcupada(false);
getTabuleiro()[2 + x][0 + y].setOcupada(false);
getTabuleiro()[3 + x][2 + y].setOcupada(false);
getTabuleiro()[1 + x][3 + y].setOcupada(false);
// ---------------------------------------------------------------------
getTabuleiro()[0 + x][2 + y].setFigura(ConstantDataManager.QUADRADO_INCLINADO);
getTabuleiro()[1 + x][0 + y].setFigura(ConstantDataManager.QUADRADO_INCLINADO);
getTabuleiro()[3 + x][1 + y].setFigura(ConstantDataManager.QUADRADO_INCLINADO);
getTabuleiro()[2 + x][3 + y].setFigura(ConstantDataManager.QUADRADO_INCLINADO);
getTabuleiro()[0 + x][2 + y].setQuadrante(quadrante);
getTabuleiro()[1 + x][0 + y].setQuadrante(quadrante);
getTabuleiro()[3 + x][1 + y].setQuadrante(quadrante);
getTabuleiro()[2 + x][3 + y].setQuadrante(quadrante);
getTabuleiro()[0 + x][2 + y].setOcupada(false);
getTabuleiro()[1 + x][0 + y].setOcupada(false);
getTabuleiro()[3 + x][1 + y].setOcupada(false);
getTabuleiro()[2 + x][3 + y].setOcupada(false);
}
/*Se todas as posições do tabuleiro já foram preenchidas
**/
public boolean terminouPreencher() {
boolean ret = true;
for (int linha = 0; linha < getTabuleiro().length; linha++) {
for (int coluna = 0; coluna < getTabuleiro().length; coluna++) {
if (!getTabuleiro()[linha][coluna].isOcupada()) {
ret = false;
}
}
}
return ret;
}
public void incrementaPasso() {
setContadorPassos(getContadorPassos() + 1);
}
/**
* @return the pontoInicial
*/
public Point getPontoInicial() {
return pontoInicial;
}
/**
* @param pontoInicial the pontoInicial to set
*/
public void setPontoInicial(Point pontoInicial) {
this.pontoInicial = pontoInicial;
}
/**
* @return the inicio
*/
public boolean isInicio() {
return inicio;
}
/**
* @param inicio the inicio to set
*/
public void setInicio(boolean inicio) {
this.inicio = inicio;
}
/**
* @return the possibilidades
*/
private List getPossibilidades() {
return possibilidades;
}
/**
* @param possibilidades the possibilidades to set
*/
private void setPossibilidades(List possibilidades) {
this.possibilidades = possibilidades;
}
/**
* @return the contadorPassos
*/
public int getContadorPassos() {
return contadorPassos;
}
/**
* @param contadorPassos the contadorPassos to set
*/
public void setContadorPassos(int contadorPassos) {
this.contadorPassos = contadorPassos;
}
/**
* @return the pontoFinal
*/
public Point getPontoFinal() {
return pontoFinal;
}
/**
* @param pontoFinal the pontoFinal to set
*/
public void setPontoFinal(Point pontoFinal) {
this.pontoFinal = pontoFinal;
}
}
// Classe constantDataManager
package passeiodocavalo;
/**
*
* @author jaison
*/
public class ConstantDataManager {
public static final int PRIMEIRO_QUADRANTE = 1;
public static final int SEGUNDO_QUADRANTE = 2;
public static final int TERCEIRO_QUADRANTE = 3;
public static final int QUARTO_QUADRANTE = 4;
public static final int TRIANGULO_DIAGONAL_PRINCIPAL = 5;
public static final int TRIANGULO_DIAGONAL_SECUNDARIA = 6;
public static final int QUADRADO_HORIZONTAL = 7;
public static final int QUADRADO_INCLINADO = 8;
}
// classe Celula
package passeiodocavalo;
/**
*
* @author jaison
*/
public class Celula {
private int figura;
private int quadrante;
private int passo = 0;
private boolean ocupada = false;
/**
* @return the figura
*/
public int getFigura() {
return figura;
}
/**
* @param figura the figura to set
*/
public void setFigura(int figura) {
this.figura = figura;
}
/**
* @return the quadrante
*/
public int getQuadrante() {
return quadrante;
}
/**
* @param quadrante the quadrante to set
*/
public void setQuadrante(int quadrante) {
this.quadrante = quadrante;
}
/**
* @return the ocupada
*/
public boolean isOcupada() {
return ocupada;
}
/**
* @param ocupada the ocupada to set
*/
public void setOcupada(boolean ocupada) {
this.ocupada = ocupada;
}
/**
* @return the passo
*/
public int getPasso() {
return passo;
}
/**
* @param passo the passo to set
*/
public void setPasso(int passo) {
this.passo = passo;
}
}
// Classe Main
package passeiodocavalo;
import javax.swing.JFrame;
/**
*
* @author jaison
*/
public class Main extends JFrame{
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
TelaTabuleiro frame=new TelaTabuleiro();
frame.setDefaultCloseOperation(EXIT_ON_CLOSE);
frame.setVisible(true);
}
}
A heurística do diamante e quadrado consiste em dividir o tabuleiro em quatro quadrantes e apartir de um ponto qualquer preencher as posições por onde o cavalo pode passar de acordo 4 tipos de figuras, como demonstrado na imagem acima. Deve-se preencher tipos intercalados de figura, por exemplo, se iniciar preenchendo um diamante na diagonal principal, esta figura é preenchida em todos os outros quadrante e a próxima figura a ser preenchida deverá ser um quadrado. O inverso também é válido, se iniciar com um quadrado, a próxima figura deverá ser um diamante. No desenvolvimento do algoritmo alguns cuidados devem ser tomados, como certificar-se de que o ponto final da figura que está sendo preenchida permita acesso a mesma figura no próximo quadrante ou no caso de ser o último quadrante, para a próxima figura a ser preenchida.
Na imagem acima, o programa desenvolvido em java, onde o usuário seleciona uma determinada posição do tabuleiro e visualiza os possíveis trajetos percorridos pelo cavalo. Se cruzarmos uma linha na sequencia em que os números aparecem na tela pode-se conferir o formato das figuras diamante e quadrado.
Segue abaixo o código fonte, com as seis classes implementadas.
// classe PasseioDoCavalo
package passeiodocavalo;
/**
*
* @author jaison
*/
public class PasseioDoCavalo {
private Celula[][] tabuleiro = new Celula[8][8];
public PasseioDoCavalo(){
for(int x=0; x
for(int y=0; y
getTabuleiro()[x][y] = new Celula();
}
}
}
public void impimeTabuleiro(){
for(int x=0; x
for(int y=0; y
System.out.println(" [ "+x+ " "+y+" ] "+ getTabuleiro()[x][y].getPasso() + "\t"); //+ getTabuleiro()[x][y].getQuadrante());
}
System.out.println("\n");
}
}
public boolean preencheFigura(int x_pos, int y_pos){
boolean ret = false;
switch(getTabuleiro()[x_pos][y_pos].getFigura()){
case ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL:
if(getTabuleiro()[x_pos][y_pos].getQuadrante() == ConstantDataManager.PRIMEIRO_QUADRANTE){
}
System.out.println("TRIANGULO_DIAGONAL_PRINCIPAL");
break;
case ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA:
System.out.println("TRIANGULO_DIAGONAL_SECUNDARIA");
break;
case ConstantDataManager.QUADRADO_HORIZONTAL:
System.out.println("QUADRADO_HORIZONTAL");
break;
case ConstantDataManager.QUADRADO_INCLINADO:
System.out.println("QUADRADO_INCLINADO");
break;
}
return false;
}
/**
* @return the tabuleiro
*/
public Celula[][] getTabuleiro() {
return tabuleiro;
}
/**
* @param tabuleiro the tabuleiro to set
*/
public void setTabuleiro(Celula[][] tabuleiro) {
this.tabuleiro = tabuleiro;
}
}
import java.awt.GridLayout;
import java.awt.Point;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
/**
*
* @author jaison
*/
public class TelaTabuleiro extends JFrame {
static JPanel panel;
JButton[][] casas = new JButton[8][8];
public TelaTabuleiro(){
init();
}
public void init(){
panel=new JPanel(new GridLayout(8,8));
for(int x=0; x
for(int y=0; y
casas[x][y] = new JButton(String.valueOf(x)+" "+String.valueOf(y));
casas[x][y].setSize(80,80);
casas[x][y].setActionCommand(String.valueOf(x)+String.valueOf(y));
casas[x][y].addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
carregaTelaTabuleiro(arg0);
}
});
panel.add(casas[x][y]);
}
}
super.setTitle("Selecione a posição inicial no tabuleiro");
super.add(panel);
super.pack();
}
public void carregaTelaTabuleiro(java.awt.event.ActionEvent e){
for(int x=0; x
for(int y=0; y
casas[x][y].setText(" ");
}
}
System.out.println(e.getActionCommand().charAt(0)+" "+e.getActionCommand().charAt(1));
vai(Integer.parseInt(String.valueOf(e.getActionCommand().charAt(0))),
Integer.parseInt(String.valueOf(e.getActionCommand().charAt(1))));
}
public void vai(int x, int y){
ControleMovimentacao c = new ControleMovimentacao();
PasseioDoCavalo p = new PasseioDoCavalo();
c.setTabuleiro(p.getTabuleiro()); // manda o tabuleiro para o controle de movimentação
c.iniciar(x, y); // inicia com a coordenada desejada
if(c.temEstaFiguraNoQuadrante(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL,ConstantDataManager.SEGUNDO_QUADRANTE)){
}
//for(int i=0; i
ArrayList
for(int j=0; j
System.out.println( "aqui-> " + aux.get(j));
}
for(int linha=0; linha
for(int coluna=0; coluna
casas[linha][coluna].setText(String.valueOf(p.getTabuleiro()[linha][coluna].getPasso()));
}
}
}
}
package passeiodocavalo;
import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author jaison
*/
public class ControleMovimentacao {
private Celula[][] tabuleiro;
private Point pontoInicial;
private Point pontoFinal;
private boolean inicio = false;
private List
private int contadorPassos = 0;
/**
* @return the tabuleiro
*/
public Celula[][] getTabuleiro() {
return tabuleiro;
}
/**
* @param tabuleiro the tabuleiro to set
*/
public void setTabuleiro(Celula[][] tabuleiro) {
this.tabuleiro = tabuleiro;
}
public void iniciar(int x, int y) {
resetTabuleiro(ConstantDataManager.PRIMEIRO_QUADRANTE);
resetTabuleiro(ConstantDataManager.SEGUNDO_QUADRANTE);
resetTabuleiro(ConstantDataManager.TERCEIRO_QUADRANTE);
resetTabuleiro(ConstantDataManager.QUARTO_QUADRANTE);
int figuraAtual;
int quadranteAtual;
int indexPontofinal = 0;
int indexQuadrante = 0;
int contadorCaminhoAlternativo = 0;
int aux_x;
int aux_y;
setInicio(true); // inicia
boolean fluxoNormal = false;
boolean inverteu = false;
setPontoInicial(new Point(x, y));
//setPontoFinal(pontoFinal(getPontoInicial().x, getPontoInicial().y)[0]); // primeira opção de ponto final
figuraAtual = getTabuleiro()[getPontoInicial().x][getPontoInicial().y].getFigura(); // encontra a figura do ponto inicial
quadranteAtual = getTabuleiro()[getPontoInicial().x][getPontoInicial().y].getQuadrante(); // encoontra o quadrante
for (int teste = 0; teste < 55; teste++) {
if(indexPontofinal == 0){
indexPontofinal = 1;
}else{
indexPontofinal = 0;
}
setPontoFinal(pontoFinal(getPontoInicial().x, getPontoInicial().y)[indexPontofinal]);
for (int saltos = 0; saltos < caminhosPossiveis(getPontoFinal().x, getPontoFinal().y).size(); saltos++) {
aux_x = caminhosPossiveis(getPontoFinal().x, getPontoFinal().y).get(saltos).x;
aux_y = caminhosPossiveis(getPontoFinal().x, getPontoFinal().y).get(saltos).y;
if ( getTabuleiro()[aux_x][aux_y].getFigura() == figuraAtual &&
getTabuleiro()[aux_x][aux_y].getQuadrante() == proximoQuadrante(quadranteAtual)[0] &&
getTabuleiro()[aux_x][aux_y].isOcupada() == false ) {
// se encontrar a mesma figura na primeira opção do proximo quadrante
preencheFigura(getPontoInicial(),getPontoFinal());
setPontoInicial(new Point(aux_x, aux_y));
quadranteAtual = getTabuleiro()[aux_x][aux_y].getQuadrante();
figuraAtual = getTabuleiro()[aux_x][aux_y].getFigura();
break;
}else if ( getTabuleiro()[aux_x][aux_y].getFigura() == figuraAtual &&
getTabuleiro()[aux_x][aux_y].getQuadrante() == proximoQuadrante(quadranteAtual)[1] &&
getTabuleiro()[aux_x][aux_y].isOcupada() == false ) {
// se encontrar a mesma figura na segunda opção do proximo quadrante
preencheFigura(getPontoInicial(),getPontoFinal());
setPontoInicial(new Point(aux_x, aux_y));
quadranteAtual = getTabuleiro()[aux_x][aux_y].getQuadrante();
figuraAtual = getTabuleiro()[aux_x][aux_y].getFigura();
break;
} else if (quantasVezesPreenchida(figuraAtual) == 3){
// se a figura atual ja foi preenchida 3 vezes
//preencheFigura(getPontoInicial(),getPontoFinal());
//figuraAtual = proximaFigura(figuraAtual);
if ( getTabuleiro()[aux_x][aux_y].getFigura() == proximaFigura(figuraAtual) &&
getTabuleiro()[aux_x][aux_y].getQuadrante() == proximoQuadrante(quadranteAtual)[0] &&
getTabuleiro()[aux_x][aux_y].isOcupada() == false ) {
preencheFigura(getPontoInicial(),getPontoFinal());
}else if ( getTabuleiro()[aux_x][aux_y].getFigura() == proximaFigura(figuraAtual) &&
getTabuleiro()[aux_x][aux_y].getQuadrante() == proximoQuadrante(quadranteAtual)[1] &&
getTabuleiro()[aux_x][aux_y].isOcupada() == false ){
preencheFigura(getPontoInicial(),getPontoFinal());
}else{
int fim = quantasFigurasPreenchidasNesteQuadrante(ConstantDataManager.PRIMEIRO_QUADRANTE) +
quantasFigurasPreenchidasNesteQuadrante(ConstantDataManager.SEGUNDO_QUADRANTE ) +
quantasFigurasPreenchidasNesteQuadrante(ConstantDataManager.TERCEIRO_QUADRANTE) +
quantasFigurasPreenchidasNesteQuadrante(ConstantDataManager.QUARTO_QUADRANTE );
if(fim == 15){
preencheFigura(getPontoInicial(),getPontoFinal());
}
}
}
}
if(quantasVezesPreenchida(figuraAtual) == 4){
figuraAtual = proximaFigura(figuraAtual);
}
}
}
public boolean proximoPasso() {
boolean ret = false;
if (isInicio()) { // se já iniciou
}
return ret;
}
/*Recebe as coordenadas xy e retorna quais são as casas atingiveis apartir
* deste ponto
**/
public ArrayList
getPossibilidades().clear();
if (x + 2 <= 7 && y + 1 <= 7) { // 1
getPossibilidades().add(new Point(x + 2, y + 1));
}
if (x + 2 <= 7 && y - 1 >= 0) { // 2
getPossibilidades().add(new Point(x + 2, y - 1));
}
if (x - 2 >= 0 && y + 1 <= 7) { // 3
getPossibilidades().add(new Point(x - 2, y + 1));
}
if (x - 2 >= 0 && y - 1 >= 0) { // 4
getPossibilidades().add(new Point(x - 2, y - 1));
}
if (y + 2 <= 7 && x + 1 <= 7) { // 5
getPossibilidades().add(new Point(x + 1, y + 2));
}
if (y + 2 <= 7 && x - 1 >= 0) { // 6
getPossibilidades().add(new Point(x - 1, y + 2));
}
if (y - 2 >= 0 && x + 1 <= 7) { // 7
getPossibilidades().add(new Point(x + 1, y - 2));
}
if (y - 2 >= 0 && x - 1 >= 0) { // 8
getPossibilidades().add(new Point(x - 1, y - 2));
}
return (ArrayList
}
/*Recebe uma coordenada e verifica quais as coordenadas finais de acordo com
* o tipo de figura da coordenada
**/
public Point[] pontoFinal(int px, int py) {
Point[] pontosFinais = new Point[2];
pontosFinais[0] = new Point(-1, -1);
pontosFinais[1] = new Point(-1, -1);
getTabuleiro()[px][py].getFigura();
int x = -1;
int y = -1;
switch (getTabuleiro()[px][py].getQuadrante()) {
case ConstantDataManager.PRIMEIRO_QUADRANTE:
x = 0;
y = 0;
break;
case ConstantDataManager.SEGUNDO_QUADRANTE:
x = 0;
y = 4;
break;
case ConstantDataManager.TERCEIRO_QUADRANTE:
x = 4;
y = 0;
break;
case ConstantDataManager.QUARTO_QUADRANTE:
x = 4;
y = 4;
break;
}
switch (getTabuleiro()[px][py].getFigura()) {
case ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL:
if ((px == 0 + x && py == 0 + y) || (px == 3 + x && py == 3 + y)) {
pontosFinais[0] = new Point(1 + x, 2 + y);
pontosFinais[1] = new Point(2 + x, 1 + y);
} else {
pontosFinais[0] = new Point(0 + x, 0 + y);
pontosFinais[1] = new Point(3 + x, 3 + y);
}
break;
case ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA:
if ((px == 0 + x && py == 3 + y) || (px == 3 + x && py == 0 + y)) {
pontosFinais[0] = new Point(1 + x, 1 + y);
pontosFinais[1] = new Point(2 + x, 2 + y);
} else {
pontosFinais[0] = new Point(0 + x, 3 + y);
pontosFinais[1] = new Point(3 + x, 0 + y);
}
break;
case ConstantDataManager.QUADRADO_HORIZONTAL:
if ((px == 0 + x && py == 1 + y) || (px == 3 + x && py == 2 + y)) {
pontosFinais[0] = new Point(2 + x, 0 + y);
pontosFinais[1] = new Point(1 + x, 3 + y);
} else {
pontosFinais[0] = new Point(0 + x, 1 + y);
pontosFinais[1] = new Point(3 + x, 2 + y);
}
break;
case ConstantDataManager.QUADRADO_INCLINADO:
if ((px == 0 + x && py == 2 + y) || (px == 3 + x && py == 1 + y)) {
pontosFinais[0] = new Point(1 + x, 0 + y);
pontosFinais[1] = new Point(2 + x, 3 + y);
} else {
pontosFinais[0] = new Point(0 + x, 2 + y);
pontosFinais[1] = new Point(3 + x, 1 + y);
}
break;
}
return pontosFinais;
}
/*Recebe um quadrante e retorna os próximos quadrantes possíveis
**/
public int[] proximoQuadrante(int quadranteAtual) {
int[] ret = new int[2];
switch (quadranteAtual) {
case ConstantDataManager.PRIMEIRO_QUADRANTE:
ret[0] = ConstantDataManager.SEGUNDO_QUADRANTE;
ret[1] = ConstantDataManager.TERCEIRO_QUADRANTE;
break;
case ConstantDataManager.SEGUNDO_QUADRANTE:
ret[0] = ConstantDataManager.PRIMEIRO_QUADRANTE;
ret[1] = ConstantDataManager.QUARTO_QUADRANTE;
break;
case ConstantDataManager.TERCEIRO_QUADRANTE:
ret[0] = ConstantDataManager.PRIMEIRO_QUADRANTE;
ret[1] = ConstantDataManager.QUARTO_QUADRANTE;
break;
case ConstantDataManager.QUARTO_QUADRANTE:
ret[0] = ConstantDataManager.SEGUNDO_QUADRANTE;
ret[1] = ConstantDataManager.TERCEIRO_QUADRANTE;
break;
default:
ret[0] = 0;
ret[1] = 0;
break;
}
return ret;
}
public int proximaFigura(int figura) {
int ret = 0;
switch (figura) {
case ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL:
ret = ConstantDataManager.QUADRADO_INCLINADO;
break;
case ConstantDataManager.QUADRADO_INCLINADO:
ret = ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA;
break;
case ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA:
ret = ConstantDataManager.QUADRADO_HORIZONTAL;
break;
case ConstantDataManager.QUADRADO_HORIZONTAL:
ret = ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL;
break;
}
return ret;
}
/*Recebe os pontos inicial e final e preenche a figura na tabuleiro
**/
public void preencheFigura(Point pontoInicial, Point pontoFinal) {
if (!getTabuleiro()[pontoInicial.x][pontoInicial.y].isOcupada()) {
incrementaPasso();
getTabuleiro()[pontoInicial.x][pontoInicial.y].setPasso(getContadorPassos());
getTabuleiro()[pontoInicial.x][pontoInicial.y].setOcupada(true);
if (pontoFinal(pontoInicial.x, pontoInicial.y)[0].x != pontoFinal.x &&
pontoFinal(pontoInicial.x, pontoInicial.y)[0].y != pontoFinal.y) {
incrementaPasso();
getTabuleiro()[pontoFinal(pontoInicial.x, pontoInicial.y)[0].x][pontoFinal(pontoInicial.x, pontoInicial.y)[0].y].setPasso(getContadorPassos());
getTabuleiro()[pontoFinal(pontoInicial.x, pontoInicial.y)[0].x][pontoFinal(pontoInicial.x, pontoInicial.y)[0].y].setOcupada(true);
} else {
incrementaPasso();
getTabuleiro()[pontoFinal(pontoInicial.x, pontoInicial.y)[1].x][pontoFinal(pontoInicial.x, pontoInicial.y)[1].y].setPasso(getContadorPassos());
getTabuleiro()[pontoFinal(pontoInicial.x, pontoInicial.y)[1].x][pontoFinal(pontoInicial.x, pontoInicial.y)[1].y].setOcupada(true);
}
if (pontoFinal(pontoFinal.x, pontoFinal.y)[0].x != pontoInicial.x &&
pontoFinal(pontoFinal.x, pontoFinal.y)[0].y != pontoInicial.y) {
incrementaPasso();
getTabuleiro()[pontoFinal(pontoFinal.x, pontoFinal.y)[0].x][pontoFinal(pontoFinal.x, pontoFinal.y)[0].y].setPasso(getContadorPassos());
getTabuleiro()[pontoFinal(pontoFinal.x, pontoFinal.y)[0].x][pontoFinal(pontoFinal.x, pontoFinal.y)[0].y].setOcupada(true);
} else {
incrementaPasso();
getTabuleiro()[pontoFinal(pontoFinal.x, pontoFinal.y)[1].x][pontoFinal(pontoFinal.x, pontoFinal.y)[1].y].setPasso(getContadorPassos());
getTabuleiro()[pontoFinal(pontoFinal.x, pontoFinal.y)[1].x][pontoFinal(pontoFinal.x, pontoFinal.y)[1].y].setOcupada(true);
}
incrementaPasso();
getTabuleiro()[pontoFinal.x][pontoFinal.y].setPasso(getContadorPassos());
getTabuleiro()[pontoFinal.x][pontoFinal.y].setOcupada(true);
}
}
/*Verifica se a referida figura está totalmente preenchida do quadrante indicado
**/
public boolean temEstaFiguraNoQuadrante(int fgr, int quadrante) {
boolean ret = false;
int x = -1;
int y = -1;
switch (quadrante) {
case ConstantDataManager.PRIMEIRO_QUADRANTE:
x = 0;
y = 0;
break;
case ConstantDataManager.SEGUNDO_QUADRANTE:
x = 0;
y = 4;
break;
case ConstantDataManager.TERCEIRO_QUADRANTE:
x = 4;
y = 0;
break;
case ConstantDataManager.QUARTO_QUADRANTE:
x = 4;
y = 4;
break;
}
switch (fgr) {
case ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL:
ret = getTabuleiro()[0 + x][0 + y].isOcupada() &&
getTabuleiro()[1 + x][2 + y].isOcupada() &&
getTabuleiro()[2 + x][1 + y].isOcupada() &&
getTabuleiro()[3 + x][3 + y].isOcupada();
break;
case ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA:
ret = getTabuleiro()[0 + x][3 + y].isOcupada() &&
getTabuleiro()[1 + x][1 + y].isOcupada() &&
getTabuleiro()[2 + x][2 + y].isOcupada() &&
getTabuleiro()[3 + x][0 + y].isOcupada();
break;
case ConstantDataManager.QUADRADO_HORIZONTAL:
ret = getTabuleiro()[0 + x][1 + y].isOcupada() &&
getTabuleiro()[2 + x][0 + y].isOcupada() &&
getTabuleiro()[3 + x][2 + y].isOcupada() &&
getTabuleiro()[1 + x][3 + y].isOcupada();
break;
case ConstantDataManager.QUADRADO_INCLINADO:
ret = getTabuleiro()[0 + x][2 + y].isOcupada() &&
getTabuleiro()[1 + x][0 + y].isOcupada() &&
getTabuleiro()[3 + x][1 + y].isOcupada() &&
getTabuleiro()[2 + x][3 + y].isOcupada();
break;
}
System.out.println(quadrante + " " + fgr);
return ret;
}
/*Verifica quantas figuras estão preenchidas em um quadrante
**/
public int quantasFigurasPreenchidasNesteQuadrante(int q) {
int ret = 0;
if (temEstaFiguraNoQuadrante(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL, q)) {
ret++;
}
if (temEstaFiguraNoQuadrante(ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA, q)) {
ret++;
}
if (temEstaFiguraNoQuadrante(ConstantDataManager.QUADRADO_HORIZONTAL, q)) {
ret++;
}
if (temEstaFiguraNoQuadrante(ConstantDataManager.QUADRADO_INCLINADO, q)) {
ret++;
}
return ret;
}
public int quantasVezesPreenchida(int figura) {
int ret = 0;
if (temEstaFiguraNoQuadrante(figura, ConstantDataManager.PRIMEIRO_QUADRANTE)) {
ret++;
}
if (temEstaFiguraNoQuadrante(figura, ConstantDataManager.SEGUNDO_QUADRANTE)) {
ret++;
}
if (temEstaFiguraNoQuadrante(figura, ConstantDataManager.TERCEIRO_QUADRANTE)) {
ret++;
}
if (temEstaFiguraNoQuadrante(figura, ConstantDataManager.QUARTO_QUADRANTE)) {
ret++;
}
return ret;
}
public void resetTabuleiro(int quadrante) {
int x = -1;
int y = -1;
switch (quadrante) {
case ConstantDataManager.PRIMEIRO_QUADRANTE:
x = 0;
y = 0;
break;
case ConstantDataManager.SEGUNDO_QUADRANTE:
x = 0;
y = 4;
break;
case ConstantDataManager.TERCEIRO_QUADRANTE:
x = 4;
y = 0;
break;
case ConstantDataManager.QUARTO_QUADRANTE:
x = 4;
y = 4;
break;
}
// ---------------------------------------------------------------------
getTabuleiro()[0 + x][0 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL);
getTabuleiro()[1 + x][2 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL);
getTabuleiro()[2 + x][1 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL);
getTabuleiro()[3 + x][3 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_PRINCIPAL);
getTabuleiro()[0 + x][0 + y].setQuadrante(quadrante);
getTabuleiro()[1 + x][2 + y].setQuadrante(quadrante);
getTabuleiro()[2 + x][1 + y].setQuadrante(quadrante);
getTabuleiro()[3 + x][3 + y].setQuadrante(quadrante);
getTabuleiro()[0 + x][0 + y].setOcupada(false);
getTabuleiro()[1 + x][2 + y].setOcupada(false);
getTabuleiro()[2 + x][1 + y].setOcupada(false);
getTabuleiro()[3 + x][3 + y].setOcupada(false);
// ---------------------------------------------------------------------
getTabuleiro()[0 + x][3 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA);
getTabuleiro()[1 + x][1 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA);
getTabuleiro()[2 + x][2 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA);
getTabuleiro()[3 + x][0 + y].setFigura(ConstantDataManager.TRIANGULO_DIAGONAL_SECUNDARIA);
getTabuleiro()[0 + x][3 + y].setQuadrante(quadrante);
getTabuleiro()[1 + x][1 + y].setQuadrante(quadrante);
getTabuleiro()[2 + x][2 + y].setQuadrante(quadrante);
getTabuleiro()[3 + x][0 + y].setQuadrante(quadrante);
getTabuleiro()[0 + x][3 + y].setOcupada(false);
getTabuleiro()[1 + x][1 + y].setOcupada(false);
getTabuleiro()[2 + x][2 + y].setOcupada(false);
getTabuleiro()[3 + x][0 + y].setOcupada(false);
// ---------------------------------------------------------------------
getTabuleiro()[0 + x][1 + y].setFigura(ConstantDataManager.QUADRADO_HORIZONTAL);
getTabuleiro()[2 + x][0 + y].setFigura(ConstantDataManager.QUADRADO_HORIZONTAL);
getTabuleiro()[3 + x][2 + y].setFigura(ConstantDataManager.QUADRADO_HORIZONTAL);
getTabuleiro()[1 + x][3 + y].setFigura(ConstantDataManager.QUADRADO_HORIZONTAL);
getTabuleiro()[0 + x][1 + y].setQuadrante(quadrante);
getTabuleiro()[2 + x][0 + y].setQuadrante(quadrante);
getTabuleiro()[3 + x][2 + y].setQuadrante(quadrante);
getTabuleiro()[1 + x][3 + y].setQuadrante(quadrante);
getTabuleiro()[0 + x][1 + y].setOcupada(false);
getTabuleiro()[2 + x][0 + y].setOcupada(false);
getTabuleiro()[3 + x][2 + y].setOcupada(false);
getTabuleiro()[1 + x][3 + y].setOcupada(false);
// ---------------------------------------------------------------------
getTabuleiro()[0 + x][2 + y].setFigura(ConstantDataManager.QUADRADO_INCLINADO);
getTabuleiro()[1 + x][0 + y].setFigura(ConstantDataManager.QUADRADO_INCLINADO);
getTabuleiro()[3 + x][1 + y].setFigura(ConstantDataManager.QUADRADO_INCLINADO);
getTabuleiro()[2 + x][3 + y].setFigura(ConstantDataManager.QUADRADO_INCLINADO);
getTabuleiro()[0 + x][2 + y].setQuadrante(quadrante);
getTabuleiro()[1 + x][0 + y].setQuadrante(quadrante);
getTabuleiro()[3 + x][1 + y].setQuadrante(quadrante);
getTabuleiro()[2 + x][3 + y].setQuadrante(quadrante);
getTabuleiro()[0 + x][2 + y].setOcupada(false);
getTabuleiro()[1 + x][0 + y].setOcupada(false);
getTabuleiro()[3 + x][1 + y].setOcupada(false);
getTabuleiro()[2 + x][3 + y].setOcupada(false);
}
/*Se todas as posições do tabuleiro já foram preenchidas
**/
public boolean terminouPreencher() {
boolean ret = true;
for (int linha = 0; linha < getTabuleiro().length; linha++) {
for (int coluna = 0; coluna < getTabuleiro().length; coluna++) {
if (!getTabuleiro()[linha][coluna].isOcupada()) {
ret = false;
}
}
}
return ret;
}
public void incrementaPasso() {
setContadorPassos(getContadorPassos() + 1);
}
/**
* @return the pontoInicial
*/
public Point getPontoInicial() {
return pontoInicial;
}
/**
* @param pontoInicial the pontoInicial to set
*/
public void setPontoInicial(Point pontoInicial) {
this.pontoInicial = pontoInicial;
}
/**
* @return the inicio
*/
public boolean isInicio() {
return inicio;
}
/**
* @param inicio the inicio to set
*/
public void setInicio(boolean inicio) {
this.inicio = inicio;
}
/**
* @return the possibilidades
*/
private List
return possibilidades;
}
/**
* @param possibilidades the possibilidades to set
*/
private void setPossibilidades(List
this.possibilidades = possibilidades;
}
/**
* @return the contadorPassos
*/
public int getContadorPassos() {
return contadorPassos;
}
/**
* @param contadorPassos the contadorPassos to set
*/
public void setContadorPassos(int contadorPassos) {
this.contadorPassos = contadorPassos;
}
/**
* @return the pontoFinal
*/
public Point getPontoFinal() {
return pontoFinal;
}
/**
* @param pontoFinal the pontoFinal to set
*/
public void setPontoFinal(Point pontoFinal) {
this.pontoFinal = pontoFinal;
}
}
// Classe constantDataManager
package passeiodocavalo;
/**
*
* @author jaison
*/
public class ConstantDataManager {
public static final int PRIMEIRO_QUADRANTE = 1;
public static final int SEGUNDO_QUADRANTE = 2;
public static final int TERCEIRO_QUADRANTE = 3;
public static final int QUARTO_QUADRANTE = 4;
public static final int TRIANGULO_DIAGONAL_PRINCIPAL = 5;
public static final int TRIANGULO_DIAGONAL_SECUNDARIA = 6;
public static final int QUADRADO_HORIZONTAL = 7;
public static final int QUADRADO_INCLINADO = 8;
}
// classe Celula
package passeiodocavalo;
/**
*
* @author jaison
*/
public class Celula {
private int figura;
private int quadrante;
private int passo = 0;
private boolean ocupada = false;
/**
* @return the figura
*/
public int getFigura() {
return figura;
}
/**
* @param figura the figura to set
*/
public void setFigura(int figura) {
this.figura = figura;
}
/**
* @return the quadrante
*/
public int getQuadrante() {
return quadrante;
}
/**
* @param quadrante the quadrante to set
*/
public void setQuadrante(int quadrante) {
this.quadrante = quadrante;
}
/**
* @return the ocupada
*/
public boolean isOcupada() {
return ocupada;
}
/**
* @param ocupada the ocupada to set
*/
public void setOcupada(boolean ocupada) {
this.ocupada = ocupada;
}
/**
* @return the passo
*/
public int getPasso() {
return passo;
}
/**
* @param passo the passo to set
*/
public void setPasso(int passo) {
this.passo = passo;
}
}
// Classe Main
import javax.swing.JFrame;
/**
*
* @author jaison
*/
public class Main extends JFrame{
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
TelaTabuleiro frame=new TelaTabuleiro();
frame.setDefaultCloseOperation(EXIT_ON_CLOSE);
frame.setVisible(true);
}
Nenhum comentário:
Postar um comentário