Foros del Web » Programación para mayores de 30 ;) » Java »

Explicación de lógica de sopa de letras Backtracking java

Estas en el tema de Explicación de lógica de sopa de letras Backtracking java en el foro de Java en Foros del Web. hola buenas necesito conprender la logica de este script en java. yo programo en php... algo se de java... en principio tengo las declaraciones.... del ...
  #1 (permalink)  
Antiguo 26/05/2017, 22:13
 
Fecha de Ingreso: junio-2010
Mensajes: 752
Antigüedad: 14 años, 6 meses
Puntos: 5
Explicación de lógica de sopa de letras Backtracking java

hola buenas necesito conprender la logica de este script en java. yo programo en php...

algo se de java...

en principio tengo las declaraciones.... del 5 a la 12. todo dentro de la clase..

luego se declara un array multidimnsional de char. (un caracter)...

en la linea 30 no se bien que sucede.. declaro un array de enteros... new int que es? bueno es sus indices tendra el valor cantidad total de elementos de la matriz y en el otro indice tendra el el total de la primera fila ...

luego en la 32 el main inicia y se ejecuta el metodo. se instancia la clase parciambactrking ()

luego el metodo que llama al metodo buscarconbacktracking (0,0,'especial')
pienso q al iniciar sera 0 y 0 y bueno el texto a buscar

luego tengo la funcion importante...
hay un condicinal largo que dice que x tiene que ser mayor a cero e y mayor a 0,

no entindo novistos() ese metodo. que es marca1 y marca.

en fin...necesito la logica de todo lo que hace. paso por paso...


https://gist.github.com/godie007/12640a2ac335154f1b5b
  #2 (permalink)  
Antiguo 26/05/2017, 22:15
 
Fecha de Ingreso: junio-2010
Mensajes: 752
Antigüedad: 14 años, 6 meses
Puntos: 5
Respuesta: Explicación de lógica de sopa de letras Backtracking java

Código Java:
Ver original
  1. package parcialbactraking;
  2.  
  3. public class ParcialBactraking {
  4.  
  5.     String vertivalDecendente = "";
  6.     String verticalAcendente = "";
  7.     String horizontalDecendente = "";
  8.     String horizontalAcendente = "";
  9.     String diagonalDecendente = "";
  10.     String diagonalAcendente = "";
  11.     String transversalDecendente = "";
  12.     String transversalAcendente = "";
  13.  
  14.     private char matrizSopaDeLetras[][]
  15.             = {{'F', 'L', 'O', 'R', 'E', 'C', 'E', 'X', 'P', 'K', 'A', 'N', 'M', 'H', 'L'},
  16.             {'G', 'W', 'P', 'S', 'M', 'B', 'B', 'F', 'S', 'V', 'D', 'A', 'S', 'E', 'B'},
  17.             {'Y', 'R', 'J', 'Ù', 'J', 'A', 'O', 'D', 'W', 'A', 'O', 'O', 'M', 'R', 'C'},
  18.             {'K', 'Q', 'A', 'L', 'Z', 'K', 'R', 'Á', 'M', 'C', 'R', 'S', 'A', 'M', 'E'},
  19.             {'A', 'E', 'C', 'C', 'G', 'C', 'V', 'A', 'U', 'A', 'A', 'O', 'D', 'O', 'T'},
  20.             {'Y', 'F', 'U', 'Z', 'I', 'I', 'U', 'I', 'V', 'C', 'R', 'Z', 'R', 'S', 'F'},
  21.             {'U', 'V', 'I', 'N', 'D', 'A', 'I', 'I', 'M', 'I', 'F', 'B', 'E', 'A', 'A'},
  22.             {'D', 'I', 'D', 'I', 'O', 'E', 'S', 'Z', 'L', 'O', 'L', 'Ñ', 'H', 'S', 'M'},
  23.             {'A', 'C', 'A', 'Ñ', 'F', 'V', 'D', 'A', 'H', 'N', 'O', 'L', 'N', 'Ñ', 'I'},
  24.             {'N', 'L', 'R', 'O', 'K', 'M', 'I', 'N', 'É', 'E', 'J', 'E', 'O', 'W', 'L'},
  25.             {'T', 'W', 'A', 'S', 'I', 'C', 'O', 'O', 'R', 'S', 'B', 'É', 'Í', 'S', 'I'},
  26.             {'E', 'V', 'K', 'Ú', 'E', 'S', 'C', 'E', 'L', 'E', 'B', 'R', 'A', 'N', 'A'},
  27.             {'L', 'V', 'C', 'P', 'M', 'Q', 'E', 'M', 'E', 'J', 'O', 'R', 'P', 'R', 'U'},
  28.             {'R', 'M', 'S', 'Z', 'P', 'R', 'E', 'S', 'E', 'N', 'T', 'E', 'Ñ', 'R', 'A'},
  29.             {'B', 'E', 'K', 'W', 'A', 'K', 'O', 'B', 'S', 'E', 'Q', 'U', 'I', 'O', 'S'}};
  30.     private final int[][] marca = new int[matrizSopaDeLetras.length][matrizSopaDeLetras[0].length];
  31.  
  32.     public static void main(String[] args) {
  33.         new ParcialBactraking();
  34.     }
  35.  
  36.     public ParcialBactraking() {
  37.         buscarConBactraking(0, 0, "ESPECIAL");
  38.     }
  39.  
  40.     private void buscarConBactraking(int x, int y, String palabra) {
  41.         if (x >= 0 && y >= 0 && x < matrizSopaDeLetras.length && y < matrizSopaDeLetras[0].length && marca[x][y] != 1) {
  42.             if (noVistos() != 0) {
  43.                 if (palabra.charAt(0) == matrizSopaDeLetras[x][y]) {
  44.                     recorrer(x, y, palabra, 0, 0);
  45.                     String resultado = imprirResultado(x, y, palabra);
  46.                     if (!resultado.equals("vacio")) {
  47.                         marcarVistos();
  48.                         System.out.println(resultado);
  49.                         return;
  50.                     }
  51.                 }
  52.             }
  53.         } else {
  54.             return;
  55.         }
  56.         marca[x][y] = 1;
  57.         buscarConBactraking(x + 1, y + 1, palabra);
  58.         buscarConBactraking(x - 1, y - 1, palabra);
  59.         buscarConBactraking(x + 1, y - 1, palabra);
  60.         buscarConBactraking(x - 1, y + 1, palabra);
  61.         buscarConBactraking(x + 1, y, palabra);
  62.         buscarConBactraking(x, y + 1, palabra);
  63.         buscarConBactraking(x - 1, y, palabra);
  64.         buscarConBactraking(x, y - 1, palabra);
  65.     }
  66.  
  67.     private void recorrer(int x, int y, String comparacion, int m, int i) {
  68.         if (m < comparacion.length()) {
  69.             if (i < matrizSopaDeLetras.length) {
  70.  
  71.                 if (x + i < matrizSopaDeLetras.length) {
  72.                     vertivalDecendente += matrizSopaDeLetras[x + i][y];
  73.                 }
  74.                 if (x - i >= 0) {
  75.                     verticalAcendente += matrizSopaDeLetras[x - i][y];
  76.                 }
  77.                 if (y + i < matrizSopaDeLetras[0].length) {
  78.                     horizontalDecendente += matrizSopaDeLetras[x][y + i];
  79.                 }
  80.                 if (y - i >= 0) {
  81.                     horizontalAcendente += matrizSopaDeLetras[x][y - i];
  82.                 }
  83.                 if (x + i < matrizSopaDeLetras.length && y + i < matrizSopaDeLetras[0].length) {
  84.                     diagonalDecendente += matrizSopaDeLetras[x + i][y + i];
  85.                 }
  86.                 if (x - i >= 0 && y - i > 0) {
  87.                     diagonalAcendente += matrizSopaDeLetras[x - i][y - i];
  88.                 }
  89.                 if (x - i >= 0 && y + i < matrizSopaDeLetras[0].length) {
  90.                     transversalAcendente += matrizSopaDeLetras[x - i][y + i];
  91.                 }
  92.                 if (y - i >= 0 && x + i < matrizSopaDeLetras.length) {
  93.                     transversalDecendente += matrizSopaDeLetras[x + i][y - i];
  94.                 }
  95.                 recorrer(x, y, comparacion, m, i + 1);
  96.             } else {
  97.                 recorrer(x, y, comparacion, m + 1, 0);
  98.             }
  99.         }
  100.     }
  101.  
  102.     private String imprirResultado(int x, int y, String comparacion) {
  103.  
  104.         if (verticalAcendente.contains(comparacion)) {
  105.             return ("Si encontro en verticar Acendente: " + x + "," + y);
  106.         }
  107.  
  108.         if (horizontalDecendente.contains(comparacion)) {
  109.             return ("Si encontro en horizontal decreciente: " + x + "," + y);
  110.         }
  111.  
  112.         if (horizontalAcendente.contains(comparacion)) {
  113.             return ("Si encontro en horizontal Acendente: " + x + "," + y);
  114.         }
  115.  
  116.         if (diagonalAcendente.contains(comparacion)) {
  117.             return ("Si encontro en diagonal Acendente: " + x + "," + y);
  118.         }
  119.  
  120.         if (diagonalDecendente.contains(comparacion)) {
  121.             return ("Si encontro en diagonal Decendente: " + x + "," + y);
  122.         }
  123.  
  124.         if (transversalAcendente.contains(comparacion)) {
  125.             return ("Si encontro en transversal Acendente: " + x + "," + y);
  126.         }
  127.  
  128.         if (transversalDecendente.contains(comparacion)) {
  129.             return ("Si encontro en transversal Decendente: " + x + "," + y);
  130.         }
  131.         return "vacio";
  132.     }
  133.  
  134.     private int noVistos() {
  135.         for (int[] marca1 : marca) {
  136.             for (int j = 0; j < marca.length; j++) {
  137.                 if (marca1[j] == 0) {
  138.                     return 1;
  139.                 }
  140.             }
  141.         }
  142.         return 0;
  143.     }
  144.  
  145.     private void marcarVistos() {
  146.         for (int[] marca1 : marca) {
  147.             for (int j = 0; j < marca.length; j++) {
  148.                 marca1[j] = 1;
  149.             }
  150.         }
  151.     }
  152.  
  153. }
  #3 (permalink)  
Antiguo 26/05/2017, 22:16
 
Fecha de Ingreso: junio-2010
Mensajes: 752
Antigüedad: 14 años, 6 meses
Puntos: 5
Respuesta: Explicación de lógica de sopa de letras Backtracking java

Ese es el código... Fuente
  #4 (permalink)  
Antiguo 27/05/2017, 10:06
 
Fecha de Ingreso: junio-2008
Ubicación: Seattle, USA
Mensajes: 733
Antigüedad: 16 años, 6 meses
Puntos: 61
Respuesta: Explicación de lógica de sopa de letras Backtracking java

Lo tipico es que las busquedas recursivas sean ciegas y visiten sin parar, por lo tanto, se hace necesario saber por donde uno ya paso' para no pasar otra vez por ahi.
Ese debe ser el sentido de las marcas, y que sus valores sean 1 o 0. Inicialmente valen cero, si ya pasaste por una cierta posicion, se marca como 1 para luego preguntar si ya pasaste por ahi y no hacerlo otra vez.
__________________
Visita mi perfil en LinkedIn
  #5 (permalink)  
Antiguo 27/05/2017, 13:58
 
Fecha de Ingreso: junio-2010
Mensajes: 752
Antigüedad: 14 años, 6 meses
Puntos: 5
Respuesta: Explicación de lógica de sopa de letras Backtracking java

Pero los lugares visitados se almacenan en un Array?.. Mmm ahora veo java tiene cosas distintas a php
  #6 (permalink)  
Antiguo 27/05/2017, 16:13
 
Fecha de Ingreso: junio-2008
Ubicación: Seattle, USA
Mensajes: 733
Antigüedad: 16 años, 6 meses
Puntos: 61
Respuesta: Explicación de lógica de sopa de letras Backtracking java

Cómo se hace en Php?
__________________
Visita mi perfil en LinkedIn
  #7 (permalink)  
Antiguo 27/05/2017, 16:47
 
Fecha de Ingreso: junio-2010
Mensajes: 752
Antigüedad: 14 años, 6 meses
Puntos: 5
Respuesta: Explicación de lógica de sopa de letras Backtracking java

Con sublime. Vos. Usas (?)

Etiquetas: letras, sopa
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 06:52.