ordine griglia 3x3 da 2x2 ruotando subgrids

Question

sto cercando di risolvere il seguente problema:

Data una griglia 3x3 con i numeri 1-9, ad esempio:

2 8 3 
1 4 5 
7 9 6 

devo ordinare la griglia ruotando una subgrid 2x2 in senso orario o antiorario. L'esempio di cui sopra potrebbe essere risolto in questo modo:

Ruotare la parte superiore sinistra piece senso orario:

2 8 3  1 2 3 
1 4 5 => 4 8 5 
7 9 6  7 9 6 

ruotare la parte inferiore destra piece antiorario:

1 2 3  1 2 3 
4 8 5 => 4 5 6 
7 9 6  7 8 9 

La griglia è ora 'ordinato' .

Questo è un compito a casa, ma non sto ottenendo questo. Forza brutale non ha funzionato; Devo essere in grado di risolvere tutte le griglie date in < = 2000ms. Una cosa che ho provato è stata cercare di calcolare un valore per tutte le 8 possibili mosse successive (ruotare tutti e 4 i pezzi in entrambe le direzioni), quindi ruotare il pezzo con il valore migliore. Questo valore è stato calcolato sommando tutte le distanze di tutti i numeri dalle loro posizioni corrette.

Questo ha funzionato per l'esempio precedente, ma quelli più difficili sono un no-go.

Qualcuno potrebbe indicarmi la direzione corretta? Dove dovrei iniziare? Questo problema ha un nome?

Tutte le griglie sono 3x3 e le parti rotanti sono sempre 2x2.

Grazie in anticipo.

MODIFICA: Ho dimenticato di menzionare la cosa più grande: devo trovare la più piccola quantità possibile di curve che ordinano la griglia.

EDIT2:

ho implementato un algoritmo di lavorare con piccoli consigli da tutto il suggerimento che ho ricevuto. La cosa fastidiosa è che sulla mia macchina viene eseguito lo scenario peggiore (987654321) in 1,5 secondi, ma sul server che esegue il test del programma viene eseguito> 2s, il che significa che devo ancora ottimizzare. Il mio codice di lavoro com'è ora

Qualcuno può venire con qualche consiglio di ottimizzazione?

Edit3:

Un'implementazione dal look-up table un'idea di Sirko, come ho capito:

import java.util.*; 

class Permutation { 
    String str; 
    int stage; 
    public Permutation(String str, int stage) { 
     this.str = str; 
     this.stage = stage; 
    } 
} 

public class Kiertopeli {  
    // initialize the look-up table 
    public static Map<String, Integer> lookUp = createLookup(); 

    public static int etsiLyhin(int[][] grid) { 
     String finale = ""; 
     for(int[] row : grid) 
      for(int num : row) 
       finale += Integer.toString(num); 

     // fetch the wanted situation from the look-up table 
     return lookUp.get(finale); 
    } 

    public static Map<String, Integer> createLookup() { 
     // will hold the list of permutations we have already visited. 
     Map<String, Integer> visited = new HashMap<String, Integer>(); 

     Queue<Permutation> q = new ArrayDeque<Permutation>(); 
     q.add(new Permutation("123456789", 0)); 

     // just for counting. should always result in 362880. 
     int permutations = 0; 

     Permutation permutation; 

     creation: 
     while(!q.isEmpty()) 
     { 
      permutation = q.poll(); 

      // pick the next non-visited permutation. 
      while(visited.containsKey(permutation.str)) { 
       if(q.isEmpty()) break creation; 
       permutation = q.poll(); 
      } 

      // mark the permutation as visited. 
      visited.put(permutation.str, permutation.stage); 

      // loop through all the rotations. 
      for(int i = 0; i < 4; i++) { 

       // get a String array with arr[0] being the permutation with clockwise rotation, 
       // and arr[1] with counter-clockwise rotation. 
       String[] rotated = rotate(permutation.str, i); 

       // if the generated permutations haven't been created before, add them to the queue. 
       if(!visited.containsKey(rotated[0])) q.add(new Permutation(rotated[0], permutation.stage+1)); 
       if(!visited.containsKey(rotated[1])) q.add(new Permutation(rotated[1], permutation.stage+1)); 

      } 

      permutations++; 
     } 

     System.out.println(permutations); 

     return visited; 
    } 

    public static String[] rotate(String string, int place) { 

     StringBuilder str1 = new StringBuilder(string); 
     StringBuilder str2 = new StringBuilder(string); 

     if(place == 0) { // top left piece 
      str1.setCharAt(0, string.charAt(3)); 
      str1.setCharAt(1, string.charAt(0)); // clockwise rotation 
      str1.setCharAt(4, string.charAt(1)); // 
      str1.setCharAt(3, string.charAt(4)); 

      str2.setCharAt(3, string.charAt(0)); 
      str2.setCharAt(0, string.charAt(1)); // counter-clockwise 
      str2.setCharAt(1, string.charAt(4)); // 
      str2.setCharAt(4, string.charAt(3)); 
     } 
     if(place == 1) { // top right 
      str1.setCharAt(1, string.charAt(4)); 
      str1.setCharAt(2, string.charAt(1)); 
      str1.setCharAt(5, string.charAt(2)); 
      str1.setCharAt(4, string.charAt(5)); 

      str2.setCharAt(4, string.charAt(1)); 
      str2.setCharAt(1, string.charAt(2)); 
      str2.setCharAt(2, string.charAt(5)); 
      str2.setCharAt(5, string.charAt(4)); 
     } 
     if(place == 2) { // bottom left 
      str1.setCharAt(3, string.charAt(6)); 
      str1.setCharAt(4, string.charAt(3)); 
      str1.setCharAt(7, string.charAt(4)); 
      str1.setCharAt(6, string.charAt(7)); 

      str2.setCharAt(6, string.charAt(3)); 
      str2.setCharAt(3, string.charAt(4)); 
      str2.setCharAt(4, string.charAt(7)); 
      str2.setCharAt(7, string.charAt(6)); 
     } 
     if(place == 3) { // bottom left 
      str1.setCharAt(4, string.charAt(7)); 
      str1.setCharAt(5, string.charAt(4)); 
      str1.setCharAt(8, string.charAt(5)); 
      str1.setCharAt(7, string.charAt(8)); 

      str2.setCharAt(7, string.charAt(4)); 
      str2.setCharAt(4, string.charAt(5)); 
      str2.setCharAt(5, string.charAt(8)); 
      str2.setCharAt(8, string.charAt(7)); 
     } 

     return new String[] { str1.toString(), str2.toString() }; 
    } 

    public static void main(String[] args) { 

     String grids = "2 8 3 1 4 5 7 9 6 " 
       + "1 6 5 8 7 2 3 4 9 " 
       + "1 6 5 8 7 2 3 4 9 " 
       + "1 7 6 8 2 5 3 4 9 " 
       + "8 1 5 7 4 6 3 9 2 " 
       + "9 8 7 6 5 4 3 2 1 "; 

     Scanner reader = new Scanner(grids); 

     System.out.println(); 
     while (reader.hasNext()) { 
      System.out.println("Enter grid:"); 
      int[][] grid = new int[3][3]; 
      for (int i = 0; i < 3; i++) { 
       for (int j = 0; j < 3; j++) { 
        grid[i][j] = reader.nextInt(); 
       } 
      } 
      System.out.println(" Smallest: " + etsiLyhin(grid)); 
     } 
    } 
} 

corre per circa 1500-1600ms ogni volta.

EDIT4: Seguendo il consiglio di Sirko sono riuscito a ridurre i tempi di esecuzione a 600 ms. Ecco il codice come è ora:

import java.util.*; 

class Permutation { 
    Byte[] value; 
    int stage; 
    public Permutation(Byte[] value, int stage) { 
     this.value = value; 
     this.stage = stage; 
    } 

    public Byte[][] rotate(int place) { 

     Byte[] code1 = value.clone(); 
     Byte[] code2 = value.clone(); 

     if(place == 0) { // top left piece 
      code1[0] = value[3]; 
      code1[1] = value[0]; 
      code1[4] = value[1]; 
      code1[3] = value[4]; 

      code2[3] = value[0]; 
      code2[0] = value[1]; 
      code2[1] = value[4]; 
      code2[4] = value[3]; 
     } 

     if(place == 1) { // top right 
      code1[1] = value[4]; 
      code1[2] = value[1]; 
      code1[5] = value[2]; 
      code1[4] = value[5]; 

      code2[4] = value[1]; 
      code2[1] = value[2]; 
      code2[2] = value[5]; 
      code2[5] = value[4]; 
     } 
     if(place == 2) { // bottom left 
      code1[3] = value[6]; 
      code1[4] = value[3]; 
      code1[7] = value[4]; 
      code1[6] = value[7]; 

      code2[6] = value[3]; 
      code2[3] = value[4]; 
      code2[4] = value[7]; 
      code2[7] = value[6]; 
     } 
     if(place == 3) { // bottom left 
      code1[4] = value[7]; 
      code1[5] = value[4]; 
      code1[8] = value[5]; 
      code1[7] = value[8]; 

      code2[7] = value[4]; 
      code2[4] = value[5]; 
      code2[5] = value[8]; 
      code2[8] = value[7]; 
     } 

     return new Byte[][] { code1, code2 }; 
    } 

    public Integer toInt() { 
     Integer ival = value[8] * 1 + 
         value[7] * 10 + 
         value[6] * 100 + 
         value[5] * 1000 + 
         value[4] * 10000 + 
         value[3] * 100000 + 
         value[2] * 1000000 + 
         value[1] * 10000000 + 
         value[0] * 100000000; 

     return ival; 
    } 
} 

public class Kiertopeli {  
    // initialize the look-up table 
    public static Map<Integer, Integer> lookUp = createLookup(); 

    public static int etsiLyhin(int[][] grid) { 
     Integer finale = toInt(grid); 

     // fetch the wanted situation from the look-up table 
     return lookUp.get(finale); 
    } 

    public static Map<Integer, Integer> createLookup() { 
     // will hold the list of permutations we have already visited. 
     Map<Integer, Integer> visited = new HashMap<Integer, Integer>(); 
     Map<Integer, Boolean> queued = new HashMap<Integer, Boolean>(); 

     Queue<Permutation> q = new ArrayDeque<Permutation>(); 
     q.add(new Permutation(new Byte[] { 1,2,3,4,5,6,7,8,9 }, 0)); 
     queued.put(123456789, true); 

     // just for counting. should always result in 362880. 
     int permutations = 0; 

     Permutation permutation; 

     creation: 
     while(!q.isEmpty()) 
     { 
      permutation = q.poll(); 

      // pick the next non-visited permutation. 
      while(visited.containsKey(permutation.toInt())) { 
       if(q.isEmpty()) break creation; 
       permutation = q.poll(); 
      } 

      // mark the permutation as visited. 
      visited.put(permutation.toInt(), permutation.stage); 

      // loop through all the rotations. 
      for(int i = 0; i < 4; i++) { 

       // get a String array with arr[0] being the permutation with clockwise rotation, 
       // and arr[1] with counter-clockwise rotation. 
       Byte[][] rotated = permutation.rotate(i); 

       // if the generated permutations haven't been created before, add them to the queue. 
       if(!visited.containsKey(toInt(rotated[0])) && !queued.containsKey(toInt(rotated[0]))) { 
        q.add(new Permutation(rotated[0], permutation.stage+1)); 
        queued.put(toInt(rotated[0]), true); 
       } 
       if(!visited.containsKey(toInt(rotated[1])) && !queued.containsKey(toInt(rotated[1]))) { 
        q.add(new Permutation(rotated[1], permutation.stage+1)); 
        queued.put(toInt(rotated[1]), true); 
       } 

      } 

      permutations++; 
     } 

     System.out.println(permutations); 

     return visited; 
    } 

    public static Integer toInt(Byte[] value) { 
     Integer ival = value[8] * 1 + 
         value[7] * 10 + 
         value[6] * 100 + 
         value[5] * 1000 + 
         value[4] * 10000 + 
         value[3] * 100000 + 
         value[2] * 1000000 + 
         value[1] * 10000000 + 
         value[0] * 100000000; 

     return ival; 
    } 

    public static Integer toInt(int[][] value) { 
     Integer ival = value[2][2] * 1 + 
         value[2][1] * 10 + 
         value[2][0] * 100 + 
         value[1][2] * 1000 + 
         value[1][1] * 10000 + 
         value[1][0] * 100000 + 
         value[0][2] * 1000000 + 
         value[0][1] * 10000000 + 
         value[0][0] * 100000000; 

     return ival; 
    } 

    public static void main(String[] args) { 

     String grids = "2 8 3 1 4 5 7 9 6 " 
       + "1 6 5 8 7 2 3 4 9 " 
       + "1 6 5 8 7 2 3 4 9 " 
       + "1 7 6 8 2 5 3 4 9 " 
       + "8 1 5 7 4 6 3 9 2 " 
       + "9 8 7 6 5 4 3 2 1 "; 

     Scanner reader = new Scanner(grids); 

     System.out.println(); 
     while (reader.hasNext()) { 
      System.out.println("Enter grid:"); 
      int[][] grid = new int[3][3]; 
      for (int i = 0; i < 3; i++) { 
       for (int j = 0; j < 3; j++) { 
        grid[i][j] = reader.nextInt(); 
       } 
      } 
      System.out.println(" Smallest: " + etsiLyhin(grid)); 
     } 
    } 
} 

grazie enorme a Sirko e tutti gli altri che mi hanno dato suggerimenti, come pure!

Answer 1

Una variante della soluzione già proposta sarebbe quella di generare una tabella di ricerca.

Come già accennato ci sono al massimo

9! = 362880 

permutazioni possibili per la vostra matrice.

Ogni permutazione può essere rappresentata utilizzando un numero a 9 cifre contenente ciascuna cifra compresa tra 1 e 9 esattamente una volta. Facciamo questo leggendo il rowwise matrice, così, ad esempio:

1 2 3 
4 5 6 => 123456789 
7 8 9 

4 8 6 
1 5 3 => 486153729 
7 2 9 

partire da questa, si potrebbe utilizzare un semplice programma ricorsivo precalcolare il numero di permutazioni necessari per ogni matrice iniziando con la soluzione e generare tutta permutazioni. Mentre facciamo così, ricordiamo quante rotazioni ci sono voluti, per arrivare a una permutazione specifica. Utilizziamo una tabella di ricerca per archiviare i nostri risultati e uno stack per archiviare i nodi, dobbiamo ancora elaborare. Nello stack utilizziamo le coppie { node, distance to solution } e inizializziamo con la coppia { 123456789, 0 }, che descrive il nodo iniziale ordinato.

lookup = []; 
queue = [ { 123456789, 0 } ]: 

while(there is a node in the queue) { 

    take the first node out of the queue 

    // skip nodes we already processed 
    if(!(node in lookup)) { 

    generate all permutations possible by using 1 rotation starting form node 
     push all generated nodes to the queue using a distance + 1 
    } 
} 

In seguito, possiamo rispondere per tutte le matrici indicate eseguendo una ricerca nel nostro risultato.

Con la coda sempre ordinata in base alla distanza dalla soluzione, ci assicuriamo di trovare il percorso più breve. Se non ci fosse tale ordinamento, potremmo trovare prima un percorso più lungo e lasciar cadere quelli più brevi in ​​seguito.

---

Si potrebbe ottimizzare ulteriormente l'algoritmo:

• introdurre un'altra ricerca, quali segnali, che un nodo come già stato aggiunto alla coda. In questo modo ridurremmo drasticamente la dimensione della coda.

Answer 2

Questa domanda può essere ridotta al problema dei percorsi più brevi in un grafico non ponderato non orientato.

I numeri 1 ... 9 possono essere disposti nei 9 riquadri in 9! modi. Quindi ci possono essere un massimo di 9 stati fattoriali. I vertici del grafico saranno questi 9! stati. Per ogni configurazione della griglia 3x3, puoi applicare 8 diverse rotazioni. Quindi da ciascun vertice ci saranno 8 spigoli in altri 8 stati.

Ora viene visualizzato il vertice di inizio del grafico e si desidera trovare il modo più breve per raggiungere il vertice di destinazione (con i numeri ordinati). Quindi applica semplicemente breadth first search da questo vertice sorgente per trovare il percorso più breve al vertice di destinazione.

Tempo di esecuzione: per ogni query, il percorso più breve verrà individuato nel caso peggiore di O(E + V). Nel grafico sopra descritto,

V = 9! = 362880

E = 9! * 8 = 2903040.

Ma il grafico non conterrà la maggior parte di questi vertici in quanto non tutti gli stati sono possibili dallo stato di partenza specificato. Quindi, usando il metro di valutazione che 10 milioni di calcoli vengono eseguiti su un computer in 1 secondo, a ciascuna query può essere data risposta in meno di 1 secondo come desiderato.

Answer 3

mi scuso per la scrittura di una nuova risposta, ma io non posso commentare la risposta di invin (causa di non avere 50 reputazione) così ho dovuto farlo qui.

Questo algoritmo BFS può essere ulteriormente ottimizzato assicurandosi che non si stia espandendo da nessuno stato già visitato.

Con factoradic è possibile rappresentare qualsiasi stato possibile con un numero compreso tra 1 e 9! (362880). Puoi utilizzare un semplice array bool (dimensione 362880) per tenere traccia se hai già visitato uno stato prima in BFS. Espandi solo gli stati non visitati che ritengo possano ridurre drasticamente i tempi di operatività in caso di passaggi più grandi.