/* Program: JSudokuResolver | Class: Resolver
Copyright (C) 2014 Ruggiero Altini
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package com.ithsoft.sudoku;
/**
* <b>Classe</b> Resolver. <p>
* Questa classe si occupa di risolvere il gioco del sudoku. <br>
* Una volta inizializzata, i valori delle variabili vengono opportunamente assegnati.
* Le variabili che si assegnano al momento della dichiarazione sono
* <ul>
* <li> <b>b</b> ovvero la tavola di gioco da analizzare (istanza di oggetto Board)
* <li> <b>vmode</b> ovvero la modalita' testuale completa
* </ul>
* Per utilizzare questa classe occorre dichiararne un'istanza, e nei parametri inserire un oggetto Board.
* E' inoltre possibile con il parametro vmode true, vedere l'esecuzione mossa per mossa.
* <p> Con la funzione Solve() si risolve (se e' possibile) la griglia inserita.
* Per stampare il risultato e' sufficiente mandare in output l'istanza di oggetto.
* @author Ruggiero Altini
* @version 1.0
*/
{
/**
* Indica la lunghezza degli elementi nella tavola di gioco
*/
int size;
/**
* Indica la tavola del gioco da risolvere
*/
Board b;
/**
* Indica il valore boolean della modalita' testuale completa
*/
private boolean vmode;
/**
* Indica la posizione delle celle da vietare
*/
private boolean[][] avoided;
/**
* Qui si impostano le variabili con i valori rispettivamente azzerati.
* @since 1.0
*/
/**
* Qui viene data una tavola di gioco. La modalita' vmode e' automaticamente off se non specificato.
* @param b L'istanza di oggetto della tavola di gioco da risolvere
* @since 1.0
*/
public Resolver(Board b
) {this(b,
false);}
/**
* Qui si impostano le variabili con i valori rispettivamente azzerati
* @param b L'istanza di oggetto della tavola di gioco da risolvere
* @param vmode La variabile della modalita' testuale completa
* @since 1.0
*/
{
size = b.getSize();
// Imposta alla griglia del resolver la griglia presa in input da parametro
this.b = b;
this.vmode = vmode;
if(vmode)
{ System.
out.
println("Griglia da risolvere:\n");
}
avoided = new boolean[size][9];
for(int i = 0; i < size; i++)
for(int j = 0; j < 9; j++)
avoided[i][j] = false;
Sort(b);
}
/**
* Il metodo {@code Sort} non e' necessario allo stretto funzionamento del programma. Tuttavia,
* grazie all'ordinamento che effettua sulla variabile {@code pwhites}, ovvero dalla casella piu' idonea
* a essere riempita alla meno idonea (basandosi sul punteggio dato da {@code getScore}).
* La funzione Solve non cominciera' quindi dall'inizio, ma dalla cella piu' idonea e in base alla complessita'
* della posizione, il tempo di calcolo viene ridotto dal 30% (posizioni semplici) al 98% (posizioni difficili).
* @param lb Tavola di gioco da ordinare
* @see getScore
* @since 1.0
*/
public void Sort(Board lb)
{
int blanks = lb.getBlanks();
int[] scores = new int[blanks];
int[] pscores = new int[blanks];
// Ricerca all'interno dell'array b le posizioni degli 0 con piu' numeri vicino (Righe e colonne)
// Questo servira' a velocizzare la ricerca
for(int i = 0; i < blanks; i++)
{
scores[i] = getScore(lb, lb.pwhites[i]);
pscores[i] = lb.pwhites[i];
}
for(int i = 0; i < blanks; i++)
for(int j = i + 1; j < blanks; j++)
{
if(scores[i] < scores[j])
{
int tmp, tmp2;
tmp = scores[i];
scores[i] = scores[j];
scores[j] = tmp;
tmp2 = pscores[i];
pscores[i] = pscores[j];
pscores[j] = tmp2;
}
}
for(int i = 0; i < blanks; i++)
{
lb.pwhites[i] = pscores[i];
}
}
/**
* <p>La funzione {@code getScore} e' utilizzata per valutare il "punteggio" di un determinato punto vuoto.</p>
* Data una tavola del Sudoku, infatti, il punto in cui e' meglio iniziare, e' il punto con piu' numeri nella sua colonna
* e nella sua riga, infatti, piu' e' ristretta la ricerca, piu' e' veloce. <br>
* Questa funzione viene impiegata dalla funzione {@code Sort(Board lb)} per analizzare tutta la griglia.
* @param lb Tavola di gioco da ordinare
* @param pos La posizione da analizzare
* @return Il punteggio della posizione data
* @see Sort
* @since 1.0
*/
public int getScore(Board lb, int pos)
{ // Se si chiede il punteggio di un elemento disuguale a 0, restituire -1
if(lb.elems[pos] != 0) return -1;
int score = 0;
int n = 0;
// Dividi la posizione inserita in forma di serie di interi in righe e colonne
int col = pos % 9;
int row = pos / 9;
if(col == -1) col = 0;
// Converti la serie di interi in una griglia
int[][] grid = new int[9][9];
int c = 0;
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
grid[i][j] = lb.elems[c];
if(c == pos) grid[i][j] = n;
c++;
}
}
// Verifica se c'e' un numero diverso da 0 nella riga di n
for(int i = 0; i < 9; i++)
{
if(col != i && grid[row][i] != 0)
score++;
}
// Verifica se c'e' un numero diverso da 0 nella colonna di n
for(int i = 0; i < 9; i++)
{
if(row != i && grid[i][col] != 0)
score++;
}
return score;
}
/**
* <p>La funzione {@code Solve} cerca in maniera ricorsiva la soluzione. </p>
* Verifica che ci siano celle libere, dopo di che prova a vedere
* da 1 a 9, quale numero e' possibile inserire. Il primo trovato viene inserito (pushed)
* Dopo di ché chiama sé stessa per eseguire un altro push nello stack
* Se non e' possibile inserire alcun numero, vuol dire che si e' commesso un errore
* In tal caso si esegue il pop nello stack per rimuovere il numero
* inserito precedentemente (Last In First Out), visto che e' errato
* e si continua a inserire in quella cella i numeri successivi
* Se la griglia e' piena, il gioco e' stato risolto
* @return true o false in base alla soluzione trovata
* @since 1.0
*/
public boolean Solve()
{
boolean libero = false; //Variabile per sapere se trovato o no buco libero
int added = 0; // Contatore
// Verifico se ci sono celle libere
libero = b.getTop() < b.getBlanks() -1;
if(libero)
{
for(int i=1; i<=9; i++)
if(isLegit(b, b.pwhites[b.getTop()+1], i)) // Verifica se la mossa e' legale
{
b.push(i); // Immetti un valore nella griglia
added++;
if(vmode)
{
System.
out.
println("Solving...");
}
if(Solve()) return true; // Se la funzione ricorsiva ritorna true, ritorna true
else{ // Altrimenti cancello l'errore
b.pop();
added--;
}
}
// Se non ho aggiunto nemmeno un elemento ritorna falso
if(added==0) return false;
}else return true;
return true;
}
/** Il metodo {@code setVmode} serve per impostare dall'esterno il valore della variabile vmode,
* ovvero la modalita' testuale. Se vmode = true, l'utente vedra' in output
* tutto il calcolo effettuato per arrivare alla soluzione
* @param toggle, valore boolean che vmode assume
* @since 1.0
*/
public void setVmode(boolean toggle)
{
vmode = toggle;
}
/**
* La funzione {@code getVmode} restituisce il valore della variabile vmode
* @return vmode
* @see setVmode
* @since 1.0
*/
public boolean getVmode()
{
return vmode;
}
/**
* Il metodo {@code avoidMove} serve per vietare una mossa dall'esterno
* @param pos la posizione del numero da verificare
* @param n il numero da verificare
*/
public void avoidMove(int pos, int n)
{
n -= 1;
avoided[pos][n] = true;
}
/**
* La funzione {@code isAvoided} controlla se la mossa e' stata vietata dall'esterno
* @param pos la posizione del numero da verificare
* @param n il numero da verificare
* @return true o false in base al valore della variabile avoided
*/
public boolean isAvoided(int pos, int n)
{
n -= 1;
return avoided[pos][n];
}
/**
* <p>La funzione {@code isLegit} controlla se la mossa data in input in una determinata posizione
* e' legale o no. Prima si converte la Board (che e' un array monodimensionale) in
* una griglia di [9][9], per semplificare il controllo, dopo di ché si procede </p>
* Il controllo si articola in 4 fasi <br><ul>
* <li>Se c'e' un numero uguale a quello inserito (escluso sé stesso) nella sua riga, la mossa e' illegale
* <li>Se c'e' un numero uguale a quello inserito (escluso sé stesso) nella sua colonna, la mossa e' illegale
* <li>Se c'e' un numero uguale a quello inserito (escluso sé stesso) nel suo settore, la mossa e' illegale
* <li>Se la mossa e' legale, ma e' stata vietata (attraverso la variabile avoided), si considera illegale.
* </ul>
* @param lb La Board del sudoku da analizzare
* @param pos la posizione del numero da inserire
* @param n il numero da inserire
* @return true o false in base alla legalita' della mossa
*/
private boolean isLegit(Board lb, int pos, int n)
{
// Dividi la posizione inserita in forma di serie di interi in righe e colonne
int col = pos % 9;
int row = pos / 9;
if(col == -1) col = 0;
// Converti la serie di interi in una griglia
int[][] grid = new int[9][9];
int c = 0;
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
grid[i][j] = lb.elems[c];
if(c == pos) grid[i][j] = n;
c++;
}
}
// Verifica se c'e' un numero identico a n nella riga
for(int i = 0; i < 9; i++)
{
if(col != i && grid[row][i] == n)
return false;
}
// Verifica se c'e' un numero identico a n nella colonna
for(int i = 0; i < 9; i++)
{
if(row != i && grid[i][col] == n) return false;
}
// Verifica se c'e' un numero identico a n nel suo quadrante
int sectorRow = row / 3;
int sectorCol = col / 3;
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
int sr, sc;
sr = i / 3;
sc = j / 3;
if(sr == sectorRow && sc == sectorCol) // Se il numero inserito e uno verificato sono nello stesso settore
{
if(grid[i][j] == n && j != col && i != row) return false;
}
}
}
// Verifica se la mossa e' stata vietata dall'esterno
if(isAvoided(pos,n)) return false;
return true;
}
/**
* La funzione {@code toString} si occupa di stampare la griglia risolta o non risolta
* (in base a quando viene chiamata)
* Richiama a sua volta la funzione toString dell'oggetto b (board)
* @return Restituisce la griglia del Resolver.
*/
{
return b.toString();
}
}