Algoritmo Para resolver Sopa de Letras Con Backtracking by godie007

examen.java

package parcialbactraking;

public class ParcialBactraking {

    String vertivalDecendente = "";
    String verticalAcendente = "";
    String horizontalDecendente = "";
    String horizontalAcendente = "";
    String diagonalDecendente = "";
    String diagonalAcendente = "";
    String transversalDecendente = "";
    String transversalAcendente = "";

    private char matrizSopaDeLetras[][]
            = {{'F', 'L', 'O', 'R', 'E', 'C', 'E', 'X', 'P', 'K', 'A', 'N', 'M', 'H', 'L'},
            {'G', 'W', 'P', 'S', 'M', 'B', 'B', 'F', 'S', 'V', 'D', 'A', 'S', 'E', 'B'},
            {'Y', 'R', 'J', 'Ù', 'J', 'A', 'O', 'D', 'W', 'A', 'O', 'O', 'M', 'R', 'C'},
            {'K', 'Q', 'A', 'L', 'Z', 'K', 'R', 'Á', 'M', 'C', 'R', 'S', 'A', 'M', 'E'},
            {'A', 'E', 'C', 'C', 'G', 'C', 'V', 'A', 'U', 'A', 'A', 'O', 'D', 'O', 'T'},
            {'Y', 'F', 'U', 'Z', 'I', 'I', 'U', 'I', 'V', 'C', 'R', 'Z', 'R', 'S', 'F'},
            {'U', 'V', 'I', 'N', 'D', 'A', 'I', 'I', 'M', 'I', 'F', 'B', 'E', 'A', 'A'},
            {'D', 'I', 'D', 'I', 'O', 'E', 'S', 'Z', 'L', 'O', 'L', 'Ñ', 'H', 'S', 'M'},
            {'A', 'C', 'A', 'Ñ', 'F', 'V', 'D', 'A', 'H', 'N', 'O', 'L', 'N', 'Ñ', 'I'},
            {'N', 'L', 'R', 'O', 'K', 'M', 'I', 'N', 'É', 'E', 'J', 'E', 'O', 'W', 'L'},
            {'T', 'W', 'A', 'S', 'I', 'C', 'O', 'O', 'R', 'S', 'B', 'É', 'Í', 'S', 'I'},
            {'E', 'V', 'K', 'Ú', 'E', 'S', 'C', 'E', 'L', 'E', 'B', 'R', 'A', 'N', 'A'},
            {'L', 'V', 'C', 'P', 'M', 'Q', 'E', 'M', 'E', 'J', 'O', 'R', 'P', 'R', 'U'},
            {'R', 'M', 'S', 'Z', 'P', 'R', 'E', 'S', 'E', 'N', 'T', 'E', 'Ñ', 'R', 'A'},
            {'B', 'E', 'K', 'W', 'A', 'K', 'O', 'B', 'S', 'E', 'Q', 'U', 'I', 'O', 'S'}};
    private final int[][] marca = new int[matrizSopaDeLetras.length][matrizSopaDeLetras[0].length];

    public static void main(String[] args) {
        new ParcialBactraking();
    }

    public ParcialBactraking() {
        buscarConBactraking(0, 0, "ESPECIAL");
    }

    private void buscarConBactraking(int x, int y, String palabra) {
        if (x >= 0 && y >= 0 && x < matrizSopaDeLetras.length && y < matrizSopaDeLetras[0].length && marca[x][y] != 1) {
            if (noVistos() != 0) {
                if (palabra.charAt(0) == matrizSopaDeLetras[x][y]) {
                    recorrer(x, y, palabra, 0, 0);
                    String resultado = imprirResultado(x, y, palabra);
                    if (!resultado.equals("vacio")) {
                        marcarVistos();
                        System.out.println(resultado);
                        return;
                    }
                }
            }
        } else {
            return;
        }
        marca[x][y] = 1;
        buscarConBactraking(x + 1, y + 1, palabra);
        buscarConBactraking(x - 1, y - 1, palabra);
        buscarConBactraking(x + 1, y - 1, palabra);
        buscarConBactraking(x - 1, y + 1, palabra);
        buscarConBactraking(x + 1, y, palabra);
        buscarConBactraking(x, y + 1, palabra);
        buscarConBactraking(x - 1, y, palabra);
        buscarConBactraking(x, y - 1, palabra);
    }

    private void recorrer(int x, int y, String comparacion, int m, int i) {
        if (m < comparacion.length()) {
            if (i < matrizSopaDeLetras.length) {

                if (x + i < matrizSopaDeLetras.length) {
                    vertivalDecendente += matrizSopaDeLetras[x + i][y];
                }
                if (x - i >= 0) {
                    verticalAcendente += matrizSopaDeLetras[x - i][y];
                }
                if (y + i < matrizSopaDeLetras[0].length) {
                    horizontalDecendente += matrizSopaDeLetras[x][y + i];
                }
                if (y - i >= 0) {
                    horizontalAcendente += matrizSopaDeLetras[x][y - i];
                }
                if (x + i < matrizSopaDeLetras.length && y + i < matrizSopaDeLetras[0].length) {
                    diagonalDecendente += matrizSopaDeLetras[x + i][y + i];
                }
                if (x - i >= 0 && y - i > 0) {
                    diagonalAcendente += matrizSopaDeLetras[x - i][y - i];
                }
                if (x - i >= 0 && y + i < matrizSopaDeLetras[0].length) {
                    transversalAcendente += matrizSopaDeLetras[x - i][y + i];
                }
                if (y - i >= 0 && x + i < matrizSopaDeLetras.length) {
                    transversalDecendente += matrizSopaDeLetras[x + i][y - i];
                }
                recorrer(x, y, comparacion, m, i + 1);
            } else {
                recorrer(x, y, comparacion, m + 1, 0);
            }
        }
    }

    private String imprirResultado(int x, int y, String comparacion) {

        if (verticalAcendente.contains(comparacion)) {
            return ("Si encontro en verticar Acendente: " + x + "," + y);
        }

        if (horizontalDecendente.contains(comparacion)) {
            return ("Si encontro en horizontal decreciente: " + x + "," + y);
        }

        if (horizontalAcendente.contains(comparacion)) {
            return ("Si encontro en horizontal Acendente: " + x + "," + y);
        }

        if (diagonalAcendente.contains(comparacion)) {
            return ("Si encontro en diagonal Acendente: " + x + "," + y);
        }

        if (diagonalDecendente.contains(comparacion)) {
            return ("Si encontro en diagonal Decendente: " + x + "," + y);
        }

        if (transversalAcendente.contains(comparacion)) {
            return ("Si encontro en transversal Acendente: " + x + "," + y);
        }

        if (transversalDecendente.contains(comparacion)) {
            return ("Si encontro en transversal Decendente: " + x + "," + y);
        }
        return "vacio";
    }

    private int noVistos() {
        for (int[] marca1 : marca) {
            for (int j = 0; j < marca.length; j++) {
                if (marca1[j] == 0) {
                    return 1;
                }
            }
        }
        return 0;
    }

    private void marcarVistos() {
        for (int[] marca1 : marca) {
            for (int j = 0; j < marca.length; j++) {
                marca1[j] = 1;
            }
        }
    }

}

Cómo se utiliza???

Dejo otra version, en donde piden que devuelvas true o false si una palabra está (true) o no (false) dentro de una sopa de letras.

Consigna:

Objetivo

El objetivo de este ejercicio es implementar una función que determine si una palabra está en una sopa de letras.

Reglas

• Las palabras pueden estar dispuestas direcciones horizontal o vertical, no en diagonal.
• Las palabras pueden estar orientadas en cualquier sentido, esto es, de derecha a izquierda o viceversa, y de arriba
  para abajo o viceversa.
• El cambio de dirección puede estar a media palabra, de modo que, por ejemplo, parte de la palabra
  esté horizontal y de izquierda a derecha, parte esté vertical y de arriba hacia abajo, y otra parte horizontal
  de derecha a la izquierda.

A continuación se muestran un par de ejemplos:

Horizontal

X X X X X X X
P A L A B R A
X X X X X X X
X X X X X X X
X X X X X X X

Vertical

A X X X X X X
R X X X X X X
B X X X X X X
A X X X X X X
L X X X X X X
A X X X X X X
P X X X X X X

Horizontal y Vertical

X X P X X X X X
X X A X X X X X
X X L X X X X X
X X A B R A X X
X X X X X X X X

X X X X X X X X
X A R B X X X X
X X X A X X X X
X X X L A P X X
X X X X X X X X

Resolución:

public class WordSearcher {

private final char[][] alphabetSoup;
private final int[][] mark;

public WordSearcher(char[][] alphabetSoup) {
	this.alphabetSoup = alphabetSoup; // sopa de letras
	this.mark = new int[alphabetSoup.length][alphabetSoup[0].length]; //sirve para marcar las posiciones visitadas
}

/**
 * El objetivo de este ejercicio es implementar una función que determine si una
 * palabra está en una sopa de letras.
 *
 * ### Reglas - Las palabras pueden estar dispuestas direcciones horizontal o
 * vertical, _no_ en diagonal. - Las palabras pueden estar orientadas en
 * cualquier sentido, esto es, de derecha a izquierda o viceversa, y de arriba
 * para abajo o viceversa. - El cambio de dirección puede estar a media palabra,
 * de modo que, por ejemplo, parte de la palabra esté horizontal y de izquierda
 * a derecha, parte esté vertical y de arriba hacia abajo, y otra parte
 * horizontal de derecha a la izquierda.
 *
 * @param word Palabra a buscar en la sopa de letras.
 *
 * @return {@link Boolean} true si la palabra se encuentra en la sopa de letras.
 */
public boolean isPresent(String word) {

	for (int i = 0; i < alphabetSoup.length; i++) {
		for (int j = 0; j < alphabetSoup[0].length; j++) {
			if (searchWordFromPosition(i, j, word, 0)) {
				return true;
			}
		}
	}
	return false;
}

private boolean searchWordFromPosition(int x, int y, String word, int index) {
	if (index == word.length()) {
		return true;
	}

	if (x < 0 || y < 0 || x >= alphabetSoup.length || y >= alphabetSoup[0].length || mark[x][y] == 1 || alphabetSoup[x][y] != word.charAt(index)) {
		return false;
	}

	mark[x][y] = 1;

	return
		searchWordFromPosition(x + 1, y, word, index + 1) ||
		searchWordFromPosition(x - 1, y, word, index + 1) ||
		searchWordFromPosition(x, y + 1, word, index + 1) ||
		searchWordFromPosition(x, y - 1, word, index + 1) ||
		searchWordFromPosition(x + 1, y + 1, word, index + 1) ||
		searchWordFromPosition(x - 1, y - 1, word, index + 1) ||
		searchWordFromPosition(x - 1, y + 1, word, index + 1) ||
		searchWordFromPosition(x + 1, y - 1, word, index + 1);
}

}