sudoku_human
Class Griglia

java.lang.Object
  sudoku_human.Griglia

All Implemented Interfaces:

java.lang.Comparable

public class Griglia
extends java.lang.Object
implements java.lang.Comparable

Classe che definisce una griglia composta da 9x9 caselle, utilizzabile durante l'esecuzione dell'algoritmo di risoluzione del sudoku per rappresentare uno stato.
one line to give the program's name and an idea of what it does. Copyright (C) 2005 Marco Cornolti (cornolti@cli.di.unipi.it)
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 2 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, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

Author:

Marco Cornolti

Field Summary

private int	caselleDefinite
private Casella[][]	griglia
private boolean	verificata

Constructor Summary

Griglia(Casella[][] contenuto)
Da un array di 9x9 caselle, costruisce uno stato.

Griglia(int[][] contenuto)
Da un array di 9x9 interi rappresentanti il valore delle caselle, costruisce uno stato.

Method Summary

int	caselleDefinite()
Griglia	cloneModificato(int xDaModificare, int yDaModificare, int n) restituisce un clone della griglia con l'eccezione di una casella definita diversamente
int	compareTo(java.lang.Object arg0)
int	countOccurrences(int n, int xcasella, int ycasella)
boolean	possibile()
Griglia	risolvi() lancia l'algoritmo per risolvere la griglia.
private boolean	risolviIstanza(java.util.PriorityQueue statesQueue) esegue un passaggio per avvicinarsi alla risoluzione di una singola istanza.
private boolean	scanABBlocco() Applicazione delle regole A e B ai blocchi.
private boolean	scanARigaColonna() scan di ogni casella: A) se viste le altre caselle della riga e della la colonna, la casella e' l'unica che puo' essere in un modo, verra' definita in quel modo.
private boolean	scanBRigaColonna() scan di ogni casella: B) se in una riga ci sono caselle definite, tutte le altre caselle della stessa riga e colonna non possono avere la possibilita' della casella definita.
private boolean	scanC() Applicazione della regola C.
private boolean	scanD() OBSOLETO: e' piu' potente scanA scan di ogni casella: D) se viste le altre caselle della riga, della colonna e del blocco, la casella e' l'unica che puo' essere in un modo, verra' definita in quel modo.
void	sortByOccurrences(int[] possibilita, int x, int y) ordina un array con le possibilita' per una casella. e' messa per prima la possibilita' che ha piu' occorrenze tra le possibilita' del resto del blocco, della riga, e della linea.
int[]	sortByPossibilityCountAndImpact() Ordinamento delle caselle dando priorita' a quelle con meno possibilita', diamo priorita' anche a quelle con maggiore impatto tra le varie possibilita', ovvero per una singola possibilita' hanno maggiore possibilita'.
java.lang.String	toString()
java.lang.String	toStringUndefined()
boolean	verifica() verifica che un'istanza sia una soluzione, ovvero che siano applicate tutte le regole del sudoku

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

verificata

private boolean verificata

griglia

private Casella[][] griglia

caselleDefinite

private int caselleDefinite

Constructor Detail

Griglia

public Griglia(Casella[][] contenuto)

Da un array di 9x9 caselle, costruisce uno stato.

Parameters:

contenuto - le caselle da inserire nella griglia

Griglia

public Griglia(int[][] contenuto)

Da un array di 9x9 interi rappresentanti il valore delle caselle, costruisce uno stato. Se una casella vale 0, la casella diventa indefinita.

Parameters:

contenuto - array di 9x9 interi con le caselle definite.

Method Detail

risolvi

public Griglia risolvi()

lancia l'algoritmo per risolvere la griglia.

Returns:

null se e' impossibile trovare la soluzione, altrimenti la griglia rappresentante la soluzione.

risolviIstanza

private boolean risolviIstanza(java.util.PriorityQueue statesQueue)

esegue un passaggio per avvicinarsi alla risoluzione di una singola istanza. se i metodi di scan normali non hanno avuto effetto ma la griglia non e' ancora giunta ad una contraddizione, inserisce nella coda le istanze semplificate da provare a risolvere.

Returns:

true ses e' riuscito a cambiare qualcosa

caselleDefinite

public int caselleDefinite()

scanD

private boolean scanD()

OBSOLETO: e' piu' potente scanA scan di ogni casella: D) se viste le altre caselle della riga, della colonna e del blocco, la casella e' l'unica che puo' essere in un modo, verra' definita in quel modo. funzionamento: -definizione delle possibilita' nella riga -definizione delle possibilita' nella colonna -definizione delle possibilita' nel blocco -intersezione dei 3 insiemi -se intersezione ha cadinalita' 8, la possibilita' esclusa va assegnata alla casella.

Returns:

true ses e' stata applicata una qualsiasi modifica

scanARigaColonna

private boolean scanARigaColonna()

scan di ogni casella: A) se viste le altre caselle della riga e della la colonna, la casella e' l'unica che puo' essere in un modo, verra' definita in quel modo.

Returns:

true ses e' stata applicata una qualsiasi modifica

scanBRigaColonna

private boolean scanBRigaColonna()

scan di ogni casella: B) se in una riga ci sono caselle definite, tutte le altre caselle della stessa riga e colonna non possono avere la possibilita' della casella definita.

scanABBlocco

private boolean scanABBlocco()

Applicazione delle regole A e B ai blocchi. A) se viste le altre caselle del blocco, la casella e' l'unica che puo' essere in un modo, verra' definita in quel modo. B) se in un blocco ci sono caselle definite, tutte le altre caselle dello stesso blocco non possono avere la possibilita' della casella definita.

Returns:

true ses la griglia e' cambiata.

scanC

private boolean scanC()

Applicazione della regola C.

Returns:

true ses e' stata eliminata almeno una possibilita'

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

toStringUndefined

public java.lang.String toStringUndefined()

Returns:

la stringa rappresentante la griglia con 0 al posto delle caselle non definite

verifica

public boolean verifica()

verifica che un'istanza sia una soluzione, ovvero che siano applicate tutte le regole del sudoku

Returns:

true ses l'istanza rispetta tutte le regole del sudoku.

possibile

public boolean possibile()

Returns:

true ses le caselle attualmente determinate non sono in contraddizione tra loro.

cloneModificato

public Griglia cloneModificato(int xDaModificare,
                               int yDaModificare,
                               int n)

restituisce un clone della griglia con l'eccezione di una casella definita diversamente

Parameters:

xDaModificare - coordinata x della casella da definire

yDaModificare - coordinata y della casella da definire

n - intero col quale definire la casella.

Returns:

la griglia modificata

countOccurrences

public int countOccurrences(int n,
                            int xcasella,
                            int ycasella)

Parameters:

n - il numero da 1 a 9

Returns:

la quantita' di caselle che ammettono quel numero come possibilita' nel blocco, nella riga e nella colonna

sortByOccurrences

public void sortByOccurrences(int[] possibilita,
                              int x,
                              int y)

ordina un array con le possibilita' per una casella. e' messa per prima la possibilita' che ha piu' occorrenze tra le possibilita' del resto del blocco, della riga, e della linea.

Parameters:

possibilita - array con le possibilita' 1-9 da ordinare

sortByPossibilityCountAndImpact

public int[] sortByPossibilityCountAndImpact()

Ordinamento delle caselle dando priorita' a quelle con meno possibilita', diamo priorita' anche a quelle con maggiore impatto tra le varie possibilita', ovvero per una singola possibilita' hanno maggiore possibilita'.

Returns:

l'array con le posizioni delle caselle. array[i] dove i%9 e' la coordinata y e i/9 la coordinata x

compareTo

public int compareTo(java.lang.Object arg0)

Specified by:

compareTo in interface java.lang.Comparable