Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
JSudokuResolver - Resolver.java

Resolver.java

Caricato da: R0gerblack
Scarica il programma completo

  1. /* Program: JSudokuResolver | Class: Resolver
  2.     Copyright (C) 2014  Ruggiero Altini
  3.  
  4.     This program is free software: you can redistribute it and/or modify
  5.     it under the terms of the GNU General Public License as published by
  6.     the Free Software Foundation, either version 3 of the License, or
  7.     (at your option) any later version.
  8.  
  9.     This program is distributed in the hope that it will be useful,
  10.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.     GNU General Public License for more details.
  13.  
  14.     You should have received a copy of the GNU General Public License
  15.     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16. */
  17.  
  18. package com.ithsoft.sudoku;
  19. /**
  20.  * <b>Classe</b> Resolver. <p>
  21.  * Questa classe si occupa di risolvere il gioco del sudoku. <br>
  22.  * Una volta inizializzata, i valori delle variabili vengono opportunamente assegnati.
  23.  * Le variabili che si assegnano al momento della dichiarazione sono
  24.  * <ul>
  25.  * <li> <b>b</b> ovvero la tavola di gioco da analizzare (istanza di oggetto Board)
  26.  * <li> <b>vmode</b> ovvero la modalita' testuale completa
  27.  * </ul>
  28.  * Per utilizzare questa classe occorre dichiararne un'istanza, e nei parametri inserire un oggetto Board.
  29.  * E' inoltre possibile con il parametro vmode true, vedere l'esecuzione mossa per mossa.
  30.  * <p> Con la funzione Solve() si risolve (se e' possibile) la griglia inserita.
  31.  * Per stampare il risultato e' sufficiente mandare in output l'istanza di oggetto.
  32.  * @author      Ruggiero Altini
  33.  * @version     1.0
  34.  */
  35. public class Resolver
  36. {
  37.         /**
  38.         * Indica la lunghezza degli elementi nella tavola di gioco
  39.         */
  40.         int size;
  41.         /**
  42.         * Indica la tavola del gioco da risolvere
  43.         */
  44.         Board b;
  45.         /**
  46.         * Indica il valore boolean della modalita' testuale completa
  47.         */
  48.         private boolean vmode;
  49.         /**
  50.         * Indica la posizione delle celle da vietare
  51.         */
  52.         private boolean[][] avoided;
  53.        
  54.         /**
  55.         * Qui si impostano le variabili con i valori rispettivamente azzerati.
  56.         * @since 1.0
  57.         */
  58.         public Resolver() {this(new Board());}
  59.         /**
  60.         * Qui viene data una tavola di gioco. La modalita' vmode e' automaticamente off se non specificato.
  61.         * @param b L'istanza di oggetto della tavola di gioco da risolvere
  62.         * @since 1.0
  63.         */
  64.         public Resolver(Board b) {this(b, false);}
  65.         /**
  66.         * Qui si impostano le variabili con i valori rispettivamente azzerati
  67.         * @param b L'istanza di oggetto della tavola di gioco da risolvere
  68.         * @param vmode La variabile della modalita' testuale completa
  69.         * @since 1.0
  70.         */
  71.         public Resolver(Board b, boolean vmode)
  72.         {
  73.                 size = b.getSize();
  74.                 // Imposta alla griglia del resolver la griglia presa in input da parametro
  75.                 this.b = b;
  76.                 this.vmode = vmode;
  77.                 if(vmode)
  78.                 {       System.out.println("Griglia da risolvere:\n");
  79.                         System.out.println(b);
  80.                 }
  81.                 avoided = new boolean[size][9];
  82.                 for(int i = 0; i < size; i++)
  83.                         for(int j = 0; j < 9; j++)
  84.                                 avoided[i][j] = false;
  85.                 Sort(b);
  86.         }
  87.        
  88.         /**
  89.         * Il metodo {@code Sort} non e' necessario allo stretto funzionamento del programma. Tuttavia,
  90.         * grazie all'ordinamento che effettua sulla variabile {@code pwhites}, ovvero dalla casella piu' idonea
  91.         * a essere riempita alla meno idonea (basandosi sul punteggio dato da {@code getScore}).
  92.         * La funzione Solve non cominciera' quindi dall'inizio, ma dalla cella piu' idonea e in base alla complessita'
  93.         * della posizione, il tempo di calcolo viene ridotto dal 30% (posizioni semplici) al 98% (posizioni difficili).
  94.         * @param lb Tavola di gioco da ordinare
  95.         * @see getScore
  96.         * @since 1.0
  97.         */
  98.         public void Sort(Board lb)
  99.         {
  100.                 int blanks = lb.getBlanks();
  101.                 int[] scores = new int[blanks];
  102.                 int[] pscores = new int[blanks];
  103.                 // Ricerca all'interno dell'array b le posizioni degli 0 con piu' numeri vicino (Righe e colonne)
  104.                 // Questo servira' a velocizzare la ricerca
  105.                 for(int i = 0; i < blanks; i++)
  106.                 {
  107.                         scores[i] = getScore(lb, lb.pwhites[i]);
  108.                         pscores[i] = lb.pwhites[i];
  109.                 }
  110.                
  111.                 for(int i = 0; i < blanks; i++)
  112.                         for(int j = i + 1; j < blanks; j++)
  113.                         {
  114.                                 if(scores[i] < scores[j])
  115.                                 {
  116.                                         int tmp, tmp2;
  117.                                         tmp = scores[i];
  118.                                         scores[i] = scores[j];
  119.                                         scores[j] = tmp;
  120.                                        
  121.                                         tmp2 = pscores[i];
  122.                                         pscores[i] = pscores[j];
  123.                                         pscores[j] = tmp2;
  124.                                 }
  125.                         }
  126.                
  127.                 for(int i = 0; i < blanks; i++)
  128.                 {
  129.                         lb.pwhites[i] = pscores[i];
  130.                 }
  131.         }
  132.        
  133.         /**
  134.         * <p>La funzione {@code getScore} e' utilizzata per valutare il "punteggio" di un determinato punto vuoto.</p>
  135.         * Data una tavola del Sudoku, infatti, il punto in cui e' meglio iniziare, e' il punto con piu' numeri nella sua colonna
  136.         * e nella sua riga, infatti, piu' e' ristretta la ricerca, piu' e' veloce. <br>
  137.         * Questa funzione viene impiegata dalla funzione {@code Sort(Board lb)} per analizzare tutta la griglia.
  138.         * @param lb Tavola di gioco da ordinare
  139.         * @param pos La posizione da analizzare
  140.         * @return Il punteggio della posizione data
  141.         * @see Sort
  142.         * @since 1.0
  143.         */
  144.         public int getScore(Board lb, int pos)
  145.         { // Se si chiede il punteggio di un elemento disuguale a 0, restituire -1
  146.                 if(lb.elems[pos] != 0) return -1;
  147.                 int  score = 0;
  148.                 int n = 0;
  149.                 // Dividi la posizione inserita in forma di serie di interi in righe e colonne
  150.                 int col = pos % 9;
  151.                 int row = pos / 9;
  152.                 if(col == -1) col = 0;
  153.                
  154.                 // Converti la serie di interi in una griglia
  155.                 int[][] grid = new int[9][9];
  156.                 int c = 0;
  157.                 for(int i = 0; i < 9; i++)
  158.                 {
  159.                         for(int j = 0; j < 9; j++)
  160.                         {
  161.                                 grid[i][j] = lb.elems[c];
  162.                                 if(c == pos) grid[i][j] = n;
  163.                                 c++;
  164.                         }
  165.                 }
  166.                 // Verifica se c'e' un numero diverso da 0 nella riga di n
  167.                 for(int i = 0; i < 9; i++)
  168.                 {
  169.                         if(col != i && grid[row][i] != 0)
  170.                                 score++;
  171.                 }
  172.                 // Verifica se c'e' un numero diverso da 0 nella colonna di n
  173.                 for(int i = 0; i < 9; i++)
  174.                 {
  175.                         if(row != i && grid[i][col] != 0)
  176.                                 score++;
  177.                 }
  178.                 return score;
  179.         }
  180.        
  181.         /**
  182.         * <p>La funzione {@code Solve} cerca in maniera ricorsiva la soluzione. </p>
  183.         * Verifica che ci siano celle libere, dopo di che prova a vedere
  184.         * da 1 a 9, quale numero e' possibile inserire. Il primo trovato viene inserito (pushed)
  185.         * Dopo di ché chiama sé stessa per eseguire un altro push nello stack
  186.         * Se non e' possibile inserire alcun numero, vuol dire che si e' commesso un errore
  187.         * In tal caso si esegue il pop nello stack per rimuovere il numero
  188.         * inserito precedentemente (Last In First Out), visto che e' errato
  189.         * e si continua a inserire in quella cella i numeri successivi
  190.         * Se la griglia e' piena, il gioco e' stato risolto
  191.         * @return      true o false in base alla soluzione trovata
  192.         * @since 1.0
  193.         */
  194.         public boolean Solve()
  195.         {
  196.                 boolean libero = false;    //Variabile per sapere se trovato o no buco libero
  197.                 int added = 0; // Contatore
  198.         // Verifico se ci sono celle libere
  199.                 libero = b.getTop() < b.getBlanks() -1;
  200.                 if(libero)
  201.                 {
  202.                         for(int i=1; i<=9; i++)
  203.                                 if(isLegit(b, b.pwhites[b.getTop()+1], i)) // Verifica se la mossa e' legale
  204.                                 {
  205.                                         b.push(i); // Immetti un valore nella griglia
  206.                                         added++;
  207.                                         if(vmode)
  208.                                         {
  209.                                                 System.out.println("Solving...");
  210.                                                 System.out.println(b);
  211.                                                 System.out.println("");
  212.                                         }
  213.                                         if(Solve()) return true; // Se la funzione ricorsiva ritorna true, ritorna true
  214.                                 else{   //      Altrimenti cancello l'errore
  215.                                         b.pop();
  216.                                         added--;
  217.                                 }
  218.                                 }
  219.                 // Se non ho aggiunto nemmeno un elemento ritorna falso
  220.                 if(added==0) return false;
  221.                 }else return true;
  222.                
  223.                
  224.                 return true;
  225.         }
  226.        
  227.         /** Il metodo {@code setVmode} serve per impostare dall'esterno il valore della variabile vmode,
  228.         * ovvero la modalita' testuale. Se vmode = true, l'utente vedra' in output
  229.         * tutto il calcolo effettuato per arrivare alla soluzione
  230.         * @param  toggle, valore boolean che vmode assume
  231.         * @since 1.0
  232.         */
  233.         public void setVmode(boolean toggle)
  234.         {      
  235.                 vmode = toggle;
  236.         }
  237.        
  238.         /**
  239.         * La funzione {@code getVmode} restituisce il valore della variabile vmode
  240.         * @return vmode
  241.         * @see setVmode
  242.         * @since 1.0
  243.         */
  244.         public boolean getVmode()
  245.         {      
  246.                 return vmode;
  247.         }
  248.        
  249.         /**
  250.         * Il metodo {@code avoidMove} serve per vietare una mossa dall'esterno
  251.         * @param  pos la posizione del numero da verificare
  252.         * @param  n il numero da verificare
  253.         */
  254.         public void avoidMove(int pos, int n)
  255.         {      
  256.                 n -= 1;
  257.                 avoided[pos][n] = true;
  258.         }
  259.        
  260.         /**
  261.         * La funzione {@code isAvoided} controlla se la mossa e' stata vietata dall'esterno
  262.         * @param  pos la posizione del numero da verificare
  263.         * @param  n il numero da verificare
  264.         * @return   true o false in base al valore  della variabile avoided
  265.         */
  266.         public boolean isAvoided(int pos, int n)
  267.         {      
  268.                 n -= 1;
  269.                 return avoided[pos][n];
  270.                
  271.         }
  272.         /**
  273.         * <p>La funzione {@code isLegit} controlla se la mossa data in input in una determinata posizione
  274.         * e' legale o no. Prima si converte la Board (che e' un array monodimensionale) in
  275.         * una griglia di [9][9], per semplificare il controllo, dopo di ché si procede </p>
  276.         * Il controllo si articola in 4 fasi <br><ul>
  277.         * <li>Se c'e' un numero uguale a quello inserito (escluso sé stesso) nella sua riga, la mossa e' illegale
  278.         * <li>Se c'e' un numero uguale a quello inserito (escluso sé stesso) nella sua colonna, la mossa e' illegale
  279.         * <li>Se c'e' un numero uguale a quello inserito (escluso sé stesso) nel suo settore, la mossa e' illegale
  280.         * <li>Se la mossa e' legale, ma e' stata vietata (attraverso la variabile avoided), si considera illegale.
  281.         * </ul>
  282.         * @param  lb  La Board del sudoku da analizzare
  283.         * @param  pos la posizione del numero da inserire
  284.         * @param  n il numero da inserire
  285.         * @return     true o false in base alla legalita' della mossa
  286.         */
  287.         private boolean isLegit(Board lb, int pos, int n)
  288.         {
  289.                 // Dividi la posizione inserita in forma di serie di interi in righe e colonne
  290.                 int col = pos % 9;
  291.                 int row = pos / 9;
  292.                
  293.                 if(col == -1) col = 0;
  294.                
  295.                 // Converti la serie di interi in una griglia
  296.                 int[][] grid = new int[9][9];
  297.                 int c = 0;
  298.                 for(int i = 0; i < 9; i++)
  299.                 {
  300.                         for(int j = 0; j < 9; j++)
  301.                         {
  302.                                 grid[i][j] = lb.elems[c];
  303.                                 if(c == pos) grid[i][j] = n;
  304.                                 c++;
  305.                         }
  306.                 }
  307.                 // Verifica se c'e' un numero identico a n nella riga
  308.                 for(int i = 0; i < 9; i++)
  309.                 {
  310.                         if(col != i && grid[row][i] == n)
  311.                                 return false;
  312.                 }
  313.                 // Verifica se c'e' un numero identico a n nella colonna
  314.                 for(int i = 0; i < 9; i++)
  315.                 {
  316.                         if(row != i && grid[i][col] == n) return false;
  317.                 }
  318.                 // Verifica se c'e' un numero identico a n nel suo quadrante
  319.                 int sectorRow = row / 3;
  320.                 int sectorCol = col / 3;
  321.                 for(int i = 0; i < 9; i++)
  322.                 {
  323.                         for(int j = 0; j < 9; j++)
  324.                         {
  325.                                 int sr, sc;
  326.                                 sr = i / 3;
  327.                                 sc = j / 3;
  328.                                 if(sr == sectorRow && sc == sectorCol) // Se il numero inserito e uno verificato sono nello stesso settore
  329.                                 {
  330.                                         if(grid[i][j] == n && j != col && i != row) return false;
  331.                                 }
  332.                         }
  333.                 }
  334.                 // Verifica se la mossa e' stata vietata dall'esterno
  335.                 if(isAvoided(pos,n)) return false;
  336.                 return true;
  337.         }
  338.        
  339.         /**
  340.         * La funzione {@code toString} si occupa di stampare la griglia risolta o non risolta
  341.         * (in base a quando viene chiamata)
  342.         * Richiama a sua volta la funzione toString dell'oggetto b (board)
  343.         * @return Restituisce la griglia del Resolver.
  344.         */
  345.         public String toString()
  346.         {
  347.                 return b.toString();
  348.         }
  349. }