Oi,
eu fiz um programa em Java que resolve o seguinte jogo.
Tenho que construir um quadrado 3x3 onde cada peça contêm 4 valores de 6 valores no total. O objectivo é emparelhar os quadrados um com o outro. Vou dar o seguinte exemplo:
Uma peça pode conter valores de 1 a 6. Cada peça tem espaço apenas para 4 valores.
Sendo um quadrado 3x3, as peças têm que estar emparelhados da sequinte forma:
Este é um exemplo que como as 9 peças do jogo ficam emparelhadas de forma correcta. As peças não têm repetições de números.
Das 9 peças, elas podem rodar de forma a que fiquem emparelhadas numa forma correcta. Por exemplo:
Eu encontrei a solução para este problema através da força bruta. Calculei todas as permutações possível (são milhões delas), e a cada permutação vou rodando cada uma peça até encontrar a solução.
Os únicos pequenos melhoramento que realizei no código para não perder muito tempo a encontrar a solução é quando se encontra uma permutação em que alguma peça não contenha os mesmos números que as peças vizinha, esta permutação é inútil e passa-se para a seguinte. O outro melhoramento foi, no momento da rotação das peças para encontrar uma solução, se numa rotação encontrar-se uma situação em que o emparelhamento não funciona, passa-se para a próxima rotação.
Eu vou pôr o código em anexo para consultarem.
O problema é que eu demoro cerca de uma hora e tal a encontrar a solução. Ou seja, isto não é a melhor solução, mas é preciso em conta que o pior caso possível vai ser preciso de fazer-se “um milhão e tal de permutações” x 4^9. Ou seja, o total de permutações e rotações a realizar é enorme.
Eu acho que usar a recursividade não vai dar grande ajuda, porque o tempo para calcular todas as permutações é pequena. Onde o programa demora mais tempo é no cálculo das rotações e a validar o resultado. Mas no momento da rotação, eu aborto logo a validação ao encontrar uma rotação incorrecta.
Alguém consegue dar uma sugestão de como abordar este problema de forma a reduzir o tempo de execução?
package puzzle;
public class Permutation {
private int[][] permutations;
private int j=0;
public Permutation(int nr) {
int factorial = 1;
for(int i = 1; i<=nr; i++)
factorial*=i;
permutations = new int[factorial][];
}
// print N! permutation of the elements of array a (not in order)
public void perm2(int[] a) {
perm2(a, a.length);
}
private void perm2(int[] a, int n) {
if (n == 1) {
permutations[j++] = a.clone();
return;
}
for (int i = 0; i < n; i++) {
swap(a, i, n-1);
perm2(a, n-1);
swap(a, i, n-1);
}
}
// swap the characters at indices i and j
private static void swap(int[] a, int i, int j) {
int c;
c = a[i];
a[i] = a[j];
a[j] = c;
}
public int[][] getPermutation()
{
return permutations;
}
}
package puzzle;
public class Puzzle {
/* Os bonecos das pe�as est�o enumeradas da seguinte maneira:
1 - pistoleiro
2 - festa
3 - dedo
4 - anarca
5 - rabo
6 - algema
1 - topo
2 - esquerda
3 - baixo
4 - direita
_______ _______ _______ _______
| A | | B | | C | | D |
|B D| |C A| |D B| |A C|
|__C__| |__D__| |__A__| |__B__|
{2,5,4,1} {5,4,1,2} {4,1,2,5} {1,2,5,4}
Como se v�, pela ordem das imagens/numera��o escolhida,
o rodar a pe�a implica mudar a primeira posi��o
do array para a �ltima e fazer o respectivo ajustamento
_______
| A |
|B D|
|__C__|
| C |
|D B|
|__A__|
{2,5,4,1}
{4,1,2,5}
*/
private final int[] piece1 = new int[]{2,5,4,1};
private final int[] piece2 = new int[]{2,1,3,4};
private final int[] piece3 = new int[]{2,3,5,6};
private final int[] piece4 = new int[]{1,3,4,6};
private final int[] piece5 = new int[]{1,2,3,4};
private final int[] piece6 = new int[]{1,6,2,5};
private final int[] piece7 = new int[]{2,5,6,4};
private final int[] piece8 = new int[]{5,3,4,6};
private final int[] piece9 = new int[]{3,6,1,5};
private final int NROFPLACES = 9;
private final int SIDE = 3;
// private final int[] piece1 = new int[]{2,5,4,1};
// private final int[] piece2 = new int[]{2,1,6,5};
// private final int[] piece3 = new int[]{4,5,1,6};
// private final int[] piece4 = new int[]{6,3,4,2};
// private final int[] piece5 = new int[]{4,5,6,3};
// private final int[] piece6 = new int[]{1,2,5,3};
// private final int[] piece7 = new int[]{5,3,4,2};
// private final int[] piece8 = new int[]{4,2,1,3};
// private final int[] piece9 = new int[]{6,1,4,2};
private Permutation p;
public Puzzle() {
// long s = System.currentTimeMillis();
int[] seqNumber = {1,2,3,4,5,6,7,8,9};
// it's the permutations that distribute the pieces at the table
p = new Permutation(NROFPLACES);
p.perm2(seqNumber);
}
/**
* Rotate the piece n times
* @param piece
* @param nrOfTimes
*/
private void rotateNTimes(int[] piece, int nrOfTimes)
{
while(nrOfTimes > 0)
{
rotate(piece);
nrOfTimes--;
}
}
/**
* Rotate the piece for the right side. See example below.
*
* @param piece Piece to rotate
*/
private void rotate(int[] piece)
{
/*
_______ _______ _______ _______
| A | | B | | C | | D |
|B D| |C A| |D B| |A C|
|__C__| |__D__| |__A__| |__B__|
{2,5,4,1} {5,4,1,2} {4,1,2,5} {1,2,5,4}
*/
int aux = piece[0];
for(int i=1;i<piece.length; i++)
piece[i-1] = piece[i];
piece[piece.length -1 ] = aux;
}
/**
* Calculate all the permutations, to set the initial set
*/
public boolean startLooking()
{
int[][] perms = p.getPermutation();
// for each permutation
int[] perm;
for(int i = (perms.length-1); i>=0; i--)
{
perm = perms[i];
int[][] orderedSet = new int[NROFPLACES][];
boolean result = setPiece(perm, orderedSet);
// if this permutation has a piece that has a number that doesn't match his partner
// go to the next permutation
if(!result) break;
int[][] copySet = new int[orderedSet.length][];
if(findOrderWithRotations(orderedSet, copySet))
{
print(copySet);
return true;
}
}
return false;
}
private boolean findOrderWithRotations(final int[][] orderedSet, int[][] copySet)
{
boolean end = false;
int [] p = new int[NROFPLACES];
// When there's no rotation to do
copy(orderedSet, copySet);
if(validateResult(orderedSet))
return true;
while(!end){
end = nextPosition(p);
copy(orderedSet, copySet);
for(int i = 0; i<p.length; i++)
{
if(p[i] > 0)
{
int[] piece = copySet[i];
rotateNTimes(piece, p[i]);
}
}
if(validateResult(copySet))
return true;
}
return false;
}
private void copy(int[][] src, int dest[][])
{
for(int i=0; i<src.length; i++)
dest[i] = src[i].clone();
}
/**
* Calculate all the possible rotations that each piece must do
* @param p Array that will contain all the number of rotation to do
* @return Next set that says what pieces must rotate
*/
private boolean nextPosition(int [] p){
int MAX_NUMBER_ROTATIONS = 4;
int pos = 0;
int val = p[0];
// change the position of the array to increase
while(val +1 >= MAX_NUMBER_ROTATIONS && pos < p.length-1 ){
p[pos] =0;
pos +=1;
val = p[pos];
}
// Increment the positions
if(pos<p.length && val<MAX_NUMBER_ROTATIONS-1){
p[pos] +=1;
return false;
}
return true;
}
/**
* Set order for pieces before start the search
* @param pieceNumber contains the order of the permutation
* @param pieces contains the pieces placed in the right order
*
* @return return pieces ordered in a place
*/
private boolean setPiece(int[] pieceNumber, int[][] pieces)
{
for(int i=0; i<pieceNumber.length; i++)
{
if(pieceNumber[i] == 1)
pieces[i] = piece1.clone();
else if(pieceNumber[i] == 2)
pieces[i] = piece2.clone();
else if(pieceNumber[i] == 3)
pieces[i] = piece3.clone();
else if(pieceNumber[i] == 4)
pieces[i] = piece4.clone();
else if(pieceNumber[i] == 5)
pieces[i] = piece5.clone();
else if(pieceNumber[i] == 6)
pieces[i] = piece6.clone();
else if(pieceNumber[i] == 7)
pieces[i] = piece7.clone();
else if(pieceNumber[i] == 8)
pieces[i] = piece8.clone();
else if(pieceNumber[i] == 9)
pieces[i] = piece9.clone();
if(!comparePieces(i, pieces))
return false;
}
return true;
}
/**
* Validate if the candidate piece can be placed in the chosen table's position
*
* @param piece Candidate piece
* @param position Position of the candidate piece in the table
* @param whatPositionsToCompare
* @return
*/
private boolean comparePieces(int position, int[][] orderedSet)
{
boolean result = true;
// validate the chosen piece
int[] piece1;
int[] piece2;
if(position!=0 && position!=1 && position!=2) //not first row
{
piece1 = orderedSet[position-SIDE];
piece2 = orderedSet[position];
result &= contains(piece1,piece2);
}
if(position!=0 && position!=SIDE && position!=(2*SIDE)) //not first column
{
piece1 = orderedSet[position-1];
piece2 = orderedSet[position];
result &= contains(piece1,piece2);
}
return result;
}
/**
* Find if piece1 contains numbers as defined in piece2
* @param piece1
* @param piece2
*/
private boolean contains(int[] piece1, int[] piece2)
{
for(int i=0; i<piece1.length; i++)
{
for(int j=0; j<piece2.length; j++)
{
if(piece1[i] == piece2[j])
return true;
}
}
return false;
}
/**
* Validate if the candidate piece can be placed in the chosen table's position
*
* @param piece Candidate piece
* @param position Position of the candidate piece in the table
* @param whatPositionsToCompare
* @return
*/
private boolean comparePieces(int[] piece, int position, int[][] orderedSet)
{
boolean result = true;
// validate the chosen piece
int[] pieceInTable;
if(position==0 || position==1 || position==2 //first row
|| position == 4)
{
pieceInTable = orderedSet[position+SIDE];// compare with piece below
result &= (piece[2] == pieceInTable[0]);
}
if(position==0 || position==SIDE || position==(2*SIDE) //first column
|| position == 4)
{
pieceInTable = orderedSet[position+1];// compare with piece below
result &= (piece[3] == pieceInTable[1]);
}
if(position==(SIDE-1) || position==((2*SIDE)-1) || position==((3*SIDE)-1) //last column
|| position == 4)
{
pieceInTable = orderedSet[position-1];// compare with piece below
result &= (piece[1] == pieceInTable[3]);
}
if(position==6 || position==7 || position==8 //last row
|| position == 4)
{
pieceInTable = orderedSet[position-SIDE];// compare with piece below
result &= (piece[0] == pieceInTable[2]);
}
return result;
}
/**
* Check if it finds a position not filled in the table. If so, the solution isn't the right one.
* @return
*/
private boolean validateResult(int[][] orderedSet)
{
for(int i=0; i<orderedSet.length; i++)
{
if(!comparePieces(orderedSet[i], i, orderedSet))
return false;
}
return true;
}
private void print(int[][] set)
{
String str = "";
for(int i = 0; i<set.length; i++)
{
int[] piece = set[i];
str += print(piece);
}
System.out.println(str);
}
private String print(int[] piece)
{
String result = "[";
for(int i=0; i<piece.length; i++)
result += piece[i] + ",";
result = result.substring(0, result.length() -1 );
result +="]";
return result;
}
public static void main(String[] args) {
Puzzle pz = new Puzzle();
long start = System.currentTimeMillis();
pz.startLooking();
long end = System.currentTimeMillis();
System.out.println("Solution in: " + (end-start) + " ms");
}
}
Obrigado,
Pedro