Galera, tudo bem? To com um probleminha num trabalho que tenho que entregar aqui na facul..tenho que fazer um programa que resolva um 8-Puzzle utilizando busca em largura e em profundidade (disciplina de Inteligência Artificial). Bom, criei uma arvore com base no livro do Deitel, se eu insiro os dados manualmente, beleza, eu consigo fazer a arvore imprimir (ou "buscar") os dados da forma desejada no trabalho. Mas como a intenção é que o programa resolva o 8-puzzle (segue o link para quem não sabe o que é um 8-puzzçe: http://mypuzzle.org/sliding), não posso inserir esses dados manualmente. Segue abaixo o código que fiz para manipular o jogo:
import java.util.ArrayList;
/**
*
* @author Henrique
*/
public class Puzzle {
boolean t2;
public static int m[][] = new int[3][3];
public static int back[][] = new int[3][3];
public static int aux[][] = new int[3][3];
public int pos[] = new int[2];
public String string = "";
private static ArrayList<int[][]> lista = new ArrayList<int[][]>();
public static String transfString(int n[][]) {
String newstring = "";
for (int k = 0; k < 3; k++) {
for (int l = 0; l < 3; l++) {
newstring = newstring + Integer.toString(n[k][l]);
}
}
return newstring;
}
public static void imprimirMatriz(int t[][]) {
System.out.println("Matriz:");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.printf(" %d ", t[i][j]);
}
System.out.println();
}
}
public static int[] acharZero(int n[][]) {
int zero[] = new int[2];
for (int i = 0; i < 3; i++) { //achar o 0
for (int j = 0; j < 3; j++) {
if (n[i][j] == 0) {
zero[0] = i;
zero[1] = j;
}
}
}
return zero;
}
public static void iniciar() {
int a;
Puzzle p1 = new Puzzle();
Tree a1 = new Tree();
m[0][0] = 1;
m[0][1] = 2;
m[0][2] = 3;
m[1][0] = 4;
m[1][1] = 0;
m[1][2] = 7;
m[2][0] = 8;
m[2][1] = 5;
m[2][2] = 6;
lista.clear();
p1.string = transfString(m);
a1.insertNode(p1.string);
lista.add(m);
//while
while (lista.isEmpty() == false) {
m = lista.get(lista.size() - 1);
System.out.println("SIZE: " + lista.size());
System.out.println("VALOR INSIDE:" + transfString(lista.get(lista.size() - 1)));
lista.remove(lista.size() - 1);
a = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
back[i][j] = m[i][j];
}
}
while (a < 4) {
//--------------------------UP-----------------------------------------------
a++;
p1.pos = acharZero(m);
//imprimirMatriz(m);
if (((p1.pos[0]) - 1) > -1) { //Verifica se a mudança pode ocorrer
m[p1.pos[0]][p1.pos[1]] = m[(p1.pos[0]) - 1][p1.pos[1]]; //Troca valor (OCORRE UP)
m[p1.pos[0] - 1][p1.pos[1]] = 0;
// imprimirMatriz(m);
p1.string = transfString(m);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
aux[i][j] = m[i][j];
}
}
if (lista.contains(m) == false) {
a1.insertNode(p1.string);
lista.add(aux);
}
}
//END_UP
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
m[i][j] = back[i][j];
}
}
//--------------------------DOWN-----------------------------------------------
a++;
// imprimirMatriz(m);
if ((p1.pos[0]) + 1 <= 2) {
m[p1.pos[0]][p1.pos[1]] = m[p1.pos[0] + 1][(p1.pos[1])];
m[p1.pos[0] + 1][p1.pos[1]] = 0;
// imprimirMatriz(m);
p1.string = transfString(m);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
aux[i][j] = m[i][j];
}
}
if (lista.contains(m) == false) {
a1.insertNode(p1.string);
lista.add(aux);
}
}
//END_DOWN
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
m[i][j] = back[i][j];
}
}
//--------------------------RIGHT-----------------------------------------------
a++;
// imprimirMatriz(m);
if ((p1.pos[1]) + 1 <= 2) {
m[p1.pos[0]][p1.pos[1]] = m[p1.pos[0]][p1.pos[1] + 1];
m[p1.pos[0]][p1.pos[1] + 1] = 0;
// imprimirMatriz(m);
p1.string = transfString(m);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
aux[i][j] = m[i][j];
}
}
if (lista.contains(m) == false) {
a1.insertNode(p1.string);
lista.add(aux);
}
}
//END_RIGHT
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
m[i][j] = back[i][j];
}
}
//--------------------------LEFT-----------------------------------------------
a++;
// imprimirMatriz(m);
if ((p1.pos[1]) - 1 > -1) {
m[p1.pos[0]][p1.pos[1]] = m[p1.pos[0]][(p1.pos[1]) - 1];
m[p1.pos[0]][(p1.pos[1]) - 1] = 0;
// imprimirMatriz(m);
p1.string = transfString(m);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
aux[i][j] = m[i][j];
}
}
if (lista.contains(m) == false) {
a1.insertNode(p1.string);
lista.add(aux);
}
}
}
}
a1.preorderTraversal();
}
}
Segue a arvore:
package arvorebusca;
/**
*
* @author Henrique
*/
/*REFERÊNCIA:
* DEITEL, P. J.; DEITEL, Harvey M.. Java TM: como programar. 8ª ed. São Paulo, RS: Bookman, 2010. Capítulo 22.
*/
class TreeNode< T extends Comparable<T>> {
TreeNode<T> leftNode;
T data;
TreeNode<T> rightNode;
public TreeNode(T nodeData) {
data = nodeData;
leftNode = rightNode = null;
}
public void insert(T insertValue) {
if (insertValue.compareTo(data) < 0) {
if (leftNode == null) {
leftNode = new TreeNode<T>(insertValue);
} else {
leftNode.insert(insertValue);
}
} else if (insertValue.compareTo(data) > 0) {
if (rightNode == null) {
rightNode = new TreeNode<T>(insertValue);
} else {
rightNode.insert(insertValue);
}
}
}
}
public class Tree<T extends Comparable<T>> {
int verificar;
private TreeNode<T> root;
public Tree() {
root = null;
}
public void insertNode(T insertValue) {
if (root == null) {
root = new TreeNode<T>(insertValue);
} else {
root.insert(insertValue);
}
}
public void preorderTraversal() {
preorderHelper(root);
}
private void preorderHelper(TreeNode<T> node) {
if (node == null) {
return;
}
System.out.println(node.data);
preorderHelper(node.leftNode);
preorderHelper(node.rightNode);
}
public void inorderTraversal() {
inorderHelper(root);
}
public void verifyexist(T comp) {
verifyexistHelper(root, comp);
}
private void verifyexistHelper(TreeNode<T> node, T comp) {
if (node != null && node.data.equals(comp)) {
verificar++;
} else if (node == null) {
verificar *= 2;
} else {
verifyexistHelper(node.rightNode, comp);
verifyexistHelper(node.leftNode, comp);
}
}
private void inorderHelper(TreeNode<T> node) {
if (node == null) {
return;
}
inorderHelper(node.leftNode);
System.out.printf("\n%s", node.data);
inorderHelper(node.rightNode);
}
}
E a main que utilizei apenas para chamar o método iniciar dentro do Puzzle:
package arvorebusca;
/**
*
* @author Henrique
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Puzzle.iniciar();
}
}
O problema é o seguinte: eu fiz um arraylist para guardar as matrizes geradas após a mudança de posição do 0 (que é o espaço em branco do 8-puzzle), para tirar a redundancia, ou seja, para não utilizar valores que já foram inseridos na arvore para nao entrar em loop. Mas minha arvore fica incompleta, ela adiciona 4 ou 5 valores e para, nunca chega na solução que seria uma matriz 3x3 na seguinte ordem: 1 2 3 | 4 5 6 | 7 8 9.
Agradeço desde já, sou novo com java, então deve ter erros bem grotescos ai!
Espero respostas :)