I use a script wrote in Java, let me share you all my source code, it needs to be optimized a little I suppose... But, by the moment, it was usefull for my porpuse.
Here's my source code... Sorry for the comments in Spanish, that's my native language....
Principal.java
Code: Select all
package dpwmasters;
import java.util.Date;
public class Principal {
/**
* @param args
*/
public static void main(String[] args) {
// Se creará un objeto para manejar el tiempo de ejecución.
Date date = new Date();
// Se guardará el tiempo inicial de ejecución.
long tiempoInicial = date.getTime();
// Se guardarán los parámetros de la URL del tablero.
String parametrosTablero = "00012,10202,11102,11002,02022";
// Se guardarán los parámetros de la URL del tablero.
String parametrosPiezas = "X..,XXX,.X. X.,X.,XX,X. XX...,XX..X,.XXXX,....X ...XX,...XX,...X.,XXXX.,...X. XX,.X XX.,.XX,XX.,X.. X..,XXX,XX. XXXX,X... .X,XX,X. ..XX,.XX.,XX..,X... X..,XXX,..X";
// Se creará un nuevo tablero.
Tablero tablero = new Tablero(parametrosTablero);
// Se guardará la información de cada pieza en un arreglo.
String[] piezas = parametrosPiezas.split(" ");
// Se leerá la información de cada pieza.
for (int i = 0; i < piezas.length; i++) {
// Se guardará la información recodificada de la pieza.
String informacionPieza = piezas[i].replace("X", "1").replace(".",
"0");
// Se agregará cada pieza disponible.
tablero.AgregarPieza(informacionPieza);
}
// Se encontrará e imprimirá la solución del tablero.
tablero.ObtenerSolucion();
// Se guardará el tiempo inicial de ejecución.
long tiempoFinal = date.getTime() - tiempoInicial;
// Se imprimirá el tiempo total de ejecución en milisegundos.
System.out.println("Tiempo Total Ejecución: " + tiempoFinal);
}
}
Code: Select all
package dpwmasters;
import java.util.ArrayList;
import java.util.Iterator;
public class Tablero {
// Se confirgurará el estado inicial.
private String[][] estadoInicialTablero;
// Se creará una lista de piezas disponibles.
private ArrayList<String[][]> piezasDisponibles = new ArrayList<String[][]>();
// Se contará la cantidad de piezas del objeto.
private int cantidadPiezas = 0;
// Se contará la cantidad de permutaciones realizadas.
private int permutacionesRealizadas = 0;
// Se controlará el estado de la búsqueda de una solución.
private boolean solucionEncontrada = false;
// Constructor de la clase.
public Tablero(String estadoInicialTableroCadena) {
// Se guardará el estado inicial en un arreglo.
String[] estadoInicialCadenaArreglo = estadoInicialTableroCadena
.split(",");
// Se guardará el ancho del tablero.
int anchoTablero = estadoInicialCadenaArreglo[0].length();
// Se guardará el alto del tablero.
int altoTablero = estadoInicialCadenaArreglo.length;
// Se creará el arreglo del estado inicial.
this.estadoInicialTablero = new String[anchoTablero][altoTablero];
// Se leerá cada posición del ancho del tablero.
for (int i = 0; i < anchoTablero; i++) {
// Se leerá cada posición del alto del tablero.
for (int j = 0; j < altoTablero; j++) {
// Se agregará el valor de la posición.
this.estadoInicialTablero[i][j] = estadoInicialCadenaArreglo[j]
.substring(i, i + 1);
}
}
}
// Esta función permitirá agregar piezas disponibles al tablero.
public void AgregarPieza(String piezaCadena) {
// Se contará la pieza.
this.cantidadPiezas++;
// Se guardará la pieza en un arreglo.
String[] piezaCadenaArreglo = piezaCadena.split(",");
// Se guardará el ancho de la pieza.
int anchoPieza = piezaCadenaArreglo[0].length();
// Se guardará el alto de la pieza.
int altoPieza = piezaCadenaArreglo.length;
// Se creará el arreglo de la pieza.
String[][] nuevaPieza = new String[anchoPieza][altoPieza];
// Se leerá cada posición del ancho de la pieza.
for (int i = 0; i < anchoPieza; i++) {
// Se leerá cada posición del alto de la pieza.
for (int j = 0; j < altoPieza; j++) {
// Se agregará el valor de la posición.
nuevaPieza[i][j] = piezaCadenaArreglo[j].substring(i, i + 1);
}
}
// Se agregará la nueva pieza al listado.
this.piezasDisponibles.add(nuevaPieza);
}
// Esta función encontrará la solución del tablero.
public void ObtenerSolucion() {
// Se instanciará el arreglo encargado de obtener las posiciones
// disponibles para cada pieza dentro del tablero.
int[][] posicionesDisponibles = new int[this.cantidadPiezas][2];
// Se guardará la posición de la pieza leída.
int piezaLeída = 0;
// Se iterará cada una de las piezas disponibles.
for (Iterator<String[][]> iterador = piezasDisponibles.listIterator(); iterador
.hasNext();) {
// Se guardará la pieza leída.
piezaLeída++;
// Se extraera la pieza disponible.
String[][] pieza = (String[][]) iterador.next();
// Se guardarán las posiciones disponibles para el ancho.
posicionesDisponibles[piezaLeída - 1][0] = this.estadoInicialTablero.length
- pieza.length + 1;
// Se guardarán las posiciones disponibles para el alto.
posicionesDisponibles[piezaLeída - 1][1] = this.estadoInicialTablero[0].length
- pieza[0].length + 1;
}
// Se creará un arreglo para guardar las posiciones disponibles sin
// combinación por cada pieza.
Object[] posicionesDisponiblesSinCombinación = new Object[this.cantidadPiezas];
// Se guardará el total de valores posibles combinatorios.
int totalValoresCombinatorios = 1;
// Se leerán las piezas disponibles.
for (int i = 0; i < this.cantidadPiezas; i++) {
// Se creará un arreglo con las posiciones disponibles para cada
// pieza leída.
int[][] posicionesPiezaLeida = new int[posicionesDisponibles[i][0]
* posicionesDisponibles[i][1]][2];
// Se guardará el total de valores combinatorios.
totalValoresCombinatorios *= posicionesDisponibles[i][0]
* posicionesDisponibles[i][1];
// Se leerán las posibles posiciones de x por cada pieza.
for (int j = 0; j < posicionesDisponibles[i][0]; j++) {
// Se leerán las posibles posiciones de y por cada pieza.
for (int k = 0; k < posicionesDisponibles[i][1]; k++) {
// Se guardará cada posición por pieza leída.
posicionesPiezaLeida[j * posicionesDisponibles[i][1] + k][0] = j;
posicionesPiezaLeida[j * posicionesDisponibles[i][1] + k][1] = k;
}
}
// Se guardarán las posiciones disponibles para cada pieza.
posicionesDisponiblesSinCombinación[i] = (Object) posicionesPiezaLeida;
}
// Se imprimirá el número máximo de iteraciones posibles.
System.out.println("Iteraciones Máximas Posibles: "
+ totalValoresCombinatorios);
// Aquí se guardarán todas las posiciones disponibles en la
// combinatoria de piezas.
int[][] combinacionesDisponibles = new int[this.cantidadPiezas][2];
// Se obtendrán las combinaciones disponibles entre las posiciones
// disponibles para cada pieza.
combinacionesDisponibles = this.ObtenerPermutacionesPosicionesPiezas(
posicionesDisponiblesSinCombinación, combinacionesDisponibles,
0);
}
// Esta función retornará todas las combinaciones disponibles entre cada una
// de las posiciones disponibles para cada pieza.
public int[][] ObtenerPermutacionesPosicionesPiezas(
Object[] posicionesSinCombinacion,
int[][] combinacionesDisponibles, int piezaInicial) {
// Se evaluará si la pieza a examinar existe.
if (piezaInicial < this.cantidadPiezas && !this.solucionEncontrada) {
// Se leerá cada combinación posible para cada pieza.
int[][] posicionesPieza = (int[][]) posicionesSinCombinacion[piezaInicial];
// Se leerá cada una de las posiciones de cada pieza.
// for (int i = 0; i < posicionesPieza.length; i++) {
for (int i = posicionesPieza.length - 1; i >= 0; i--) {
// Se actualizará el arreglo de combinaciones.
combinacionesDisponibles[piezaInicial][0] = posicionesPieza[i][0];
combinacionesDisponibles[piezaInicial][1] = posicionesPieza[i][1];
// Se evaluará el la última pieza evaluada.
if (piezaInicial == this.cantidadPiezas - 1) {
// Se contará la permutación encontrada.
permutacionesRealizadas++;
// Se instanciará el nuevo tablero.
String[][] estadoTableroReconstruido = new String[this.estadoInicialTablero.length][this.estadoInicialTablero[0].length];
// Se leerá el ancho del tablero.
for (int j = 0; j < estadoTableroReconstruido.length; j++) {
// Se leerá el alto del tablero.
for (int k = 0; k < estadoTableroReconstruido[0].length; k++) {
// Se guardarán los valores en el tablero de
// trabajo.
estadoTableroReconstruido[j][k] = this.estadoInicialTablero[j][k];
}
}
// Se instanciará el objeto encargado de evaluar la solución
// propuesta.
SolucionTablero solucionTablero = new SolucionTablero(
this.piezasDisponibles, combinacionesDisponibles);
// Se evaluará que hayan transcurrido 10 millones.
if (permutacionesRealizadas % 10000000 == 0) {
// Se imprimirá cada 10 millones de iteraciones.
System.out.println("Permutaciones Actuales: "
+ permutacionesRealizadas);
}
// Se evaluará la solución leída.
if (solucionTablero.ObtenerSolucion(
permutacionesRealizadas, estadoTableroReconstruido)) {
// Se imprimirá la solución encontrada.
solucionTablero.ImprimirSolucion(
permutacionesRealizadas,
estadoTableroReconstruido);
// Se marcará la solución como encontrada.
this.solucionEncontrada = true;
}
}
// Se buscarán las opciones de la siguiente pieza.
combinacionesDisponibles = this
.ObtenerPermutacionesPosicionesPiezas(
posicionesSinCombinacion,
combinacionesDisponibles, piezaInicial + 1);
}
}
// Se retornarán las combinaciones disponibles.
return combinacionesDisponibles;
}
}
Code: Select all
package dpwmasters;
import java.util.ArrayList;
import java.util.Iterator;
public class SolucionTablero {
// Se creará una lista de piezas disponibles.
private ArrayList<String[][]> piezasDisponibles = null;
// Se obtendrán las posiciones y combinaciones disponibles para cada
// pieza dentro del tablero.
private int[][] posicionesPiezasDisponibles = null;
// Constructor de la clase.
public SolucionTablero(ArrayList<String[][]> piezasDisponibles,
int[][] posicionesPiezasDisponibles) {
super();
// Se guardarán las piezas disponibles.
this.piezasDisponibles = piezasDisponibles;
// Se guardarán las piezas disponibles.
this.posicionesPiezasDisponibles = posicionesPiezasDisponibles;
}
// Esta función encontrará la solución del tablero.
public boolean ObtenerSolucion(int numeroSolucion, String[][] tableroTrabajo) {
// Se guardará aquí si la solución fue exitosa.
boolean solucionExitosa = false;
// Se reiniciará la posición de la pieza leída.
int piezaLeída = 0;
// Se iterará cada una de las piezas disponibles.
for (Iterator<String[][]> iterador = piezasDisponibles.listIterator(); iterador
.hasNext();) {
// Se guardará la pieza leída.
piezaLeída++;
// Se extraera la pieza disponible.
String[][] pieza = (String[][]) iterador.next();
// Se actualizará el estado del trabajo.
tableroTrabajo = this.ActualizarEstadoTablero(tableroTrabajo,
pieza, posicionesPiezasDisponibles[piezaLeída - 1][0],
posicionesPiezasDisponibles[piezaLeída - 1][1]);
}
// Se evaluará la solución encontrada.
solucionExitosa = this.esSolucionTablero(tableroTrabajo);
// Se retornará el estado de la solución.
return solucionExitosa;
}
// Esta función imprimirá la solución del tablero.
public void ImprimirSolucion(int numeroSolucion, String[][] tableroTrabajo) {
// Aquí se guardará el texto informativo de la solución.
String informacionSolucion = "Número Solución: " + numeroSolucion
+ "\n";
// Se reiniciará la posición de la pieza leída.
int piezaLeída = 0;
// Se guardará la información del tablero.
// informacionSolucion += this.ImprimirObjeto(tableroTrabajo) + "\n";
// Se iterará cada una de las piezas disponibles.
for (Iterator<String[][]> iterador = piezasDisponibles.listIterator(); iterador
.hasNext();) {
// Se guardará la pieza leída.
piezaLeída++;
// Se extraera la pieza disponible.
String[][] pieza = (String[][]) iterador.next();
// Se guardará la información del tablero.
// informacionSolucion += this.ImprimirObjeto(pieza) + "\n";
// Se imprimirá la posición de la pieza.
informacionSolucion += "Posiciones:"
+ (posicionesPiezasDisponibles[piezaLeída - 1][0] + 1)
+ "-"
+ (posicionesPiezasDisponibles[piezaLeída - 1][1] + 1)
+ "\n";
// Se actualizará el estado del trabajo.
tableroTrabajo = this.ActualizarEstadoTablero(tableroTrabajo,
pieza, posicionesPiezasDisponibles[piezaLeída - 1][0],
posicionesPiezasDisponibles[piezaLeída - 1][1]);
// Se guardará la información del tablero.
// informacionSolucion += this.ImprimirObjeto(tableroTrabajo) +
// "\n\n";
}
// Se imprimirá la solución.
System.out.println(informacionSolucion);
}
// Esta función actualizará el estado del tablero de acuerdo a la pieza y a
// la posición recibida.
public String[][] ActualizarEstadoTablero(String[][] tableroTrabajo,
String[][] pieza, int posX, int posY) {
// Se leerá cada posición del alto de la pieza.
for (int j = 0; j < pieza[0].length; j++) {
// Se leerá cada posición del ancho de la pieza.
for (int i = 0; i < pieza.length; i++) {
// Se evaluará si la pieza afecta al estado.
if (pieza[i][j].equals("1")) {
// Se evaluará si la posición esta ocupada.
if (tableroTrabajo[i + posX][j + posY].equals("0")) {
// Se actualizará el estado del tablero.
tableroTrabajo[i + posX][j + posY] = "1";
// Si no.
} else {
// Se evaluará si la posición esta ocupada.
if (tableroTrabajo[i + posX][j + posY].equals("1")) {
// Se actualizará el estado del tablero.
tableroTrabajo[i + posX][j + posY] = "2";
// Si no.
} else {
// Se evaluará si la posición esta ocupada.
if (tableroTrabajo[i + posX][j + posY].equals("2")) {
// Se actualizará el estado del tablero.
tableroTrabajo[i + posX][j + posY] = "0";
}
}
}
}
}
}
// Se retornará el estado del tablero actualizado.
return tableroTrabajo;
}
// Esta función evaluará si el estado de tablero es la solución esperada.
public boolean esSolucionTablero(String[][] estadoTablero) {
// Se guardará el estado del tablero como solucionado.
boolean solucionTablero = true;
// Se leerá cada posición del alto del tablero.
for (int j = 0; j < estadoTablero[0].length; j++) {
// Se leerá cada posición del ancho del tablero.
for (int i = 0; i < estadoTablero.length; i++) {
// Se evaluará si existe algún valor lleno.
if (!estadoTablero[i][j].equals("0")) {
// Se marcará la solución como incorrecta.
solucionTablero = false;
// Se detendrá el análisis de la solución.
break;
}
}
}
// Se retornará la solución.
return solucionTablero;
}
// Esta función imprimirá el objeto recibido, existiendo 2 posibilidades,
// tablero o pieza.
public String ImprimirObjeto(String[][] objetoImprimir) {
// Aquí se guardará el string que será impreso.
String estadoTableroImpresion = "";
// Se leerá cada posición del alto del tablero.
for (int j = 0; j < objetoImprimir[0].length; j++) {
// Se leerá cada posición del ancho del tablero.
for (int i = 0; i < objetoImprimir.length; i++) {
// Se imprimirá cada celda del tablero.
estadoTableroImpresion += objetoImprimir[i][j];
}
// Se imprimirá un salto de línea.
estadoTableroImpresion += "\n";
}
// Se retirnará el tablero actual.
return estadoTableroImpresion;
}
}
Now I have to improve this source code or look for other way to have the high scores in this puzzle. "Tails" I'm gonna go for you!!!
