[JAVA] Classe testa Sudoku

[Alfredo_88]

Ciao a tutti popolo di HTML!
Sono alle prime armi con java e dopo aver studiato gli array e array di array sto cercando di fare un esercizio. E volevo chiedervi un vostro consiglio. Vi riporto il testo: "La classe Sudoku ha il solo metodo di classe seguente:
public static boolean verificaSchema(int[][] schema)
che riceve in ingresso una matrice di interi di dimensione 9×9 e restituisce true se la matrice rappresenta una soluzione valida per il gioco del Sudoku, false altrimenti. Scrivere la classe Sudoku e la classe ProvaSudoku che la testa."

Dato che chiede un solo metodo, io ho risolto così (non ho ancora scritto il codice che testa i singoli quadrati 3x3 ma solo quelli che testano le righe e le colonne):

class Sudoku{

	public static boolean verificaSchema(int[][] schema){

		//verifica righe
		int i=0; //indice riga
		int j=0; //indice colonna
		int k=0;
		boolean diversi = true;
		while(i<9 && diversi){
			while(j<9 && diversi){
				while(k>=j+1 && k<=9 && diversi){
					if(schema[i][j]==schema[i][k])
						diversi=false;
					k++;
				}
				j++;
			}
			i++;
		}

		//verifica colonne
		boolean diversi2=true;
		if(diversi==true){
			j=0;
			k=0;
			while(j<9 && diversi2){
				while(i<9 && diversi2){
					while(k>=i+1 && k<=9 && diversi2){
						if(schema[i][j]==schema[k][j])
							diversi2=false;
						k++;
					}
					i++;
				}
				j++;
			}
		}

		boolean corretto = diversi && diversi2;
		return corretto;
	}
}

Ho scritto anche la classe ProvaSudoku, e facendo una prova inserendo tutte le righe pari a 1,2,3,4,5,6,7,8,9 mi dice che la griglia è corretta quando invece è sbagliata!!! Non riesco a capire dove sta l'errore fin qui.

[andbin]

Originariamente inviato da Alfredo_88
riceve in ingresso una matrice di interi di dimensione 9×9 e restituisce true se la matrice rappresenta una soluzione valida per il gioco del Sudoku, false altrimenti.

Ho scritto anche la classe ProvaSudoku, e facendo una prova inserendo tutte le righe pari a 1,2,3,4,5,6,7,8,9 mi dice che la griglia è corretta quando invece è sbagliata!!! Non riesco a capire dove sta l'errore fin qui.

Scusa, ma prima di scrivere il codice hai ragionato su cosa significa "soluzione valida per il gioco del Sudoku"?

In un Sudoku completato (quindi senza più celle vuote), la matrice è "valida", cioè è stato risolto, quando in ogni riga/colonna si ha una qualunque disposizione dei numeri 1..9 purché in ogni riga/colonna non ci siano ripetizioni.

E come potresti testarlo con quel codice? Oltre al fatto che il while più interno mi lascia perplesso, visto che la condizione k>=j+1 è inizialmente false (quindi non entri nemmeno nel while!).

[Alfredo_88]

Si hai ragione! Non ci avevo proprio fatto caso alla condizione del while più interno. Ho modificato il codice in questa maniera:

class Sudoku{

	public static boolean verificaSchema(int[][] schema){

		//verifica righe
		int i=0; //indice riga
		int j=0; //indice colonna
		int k=1;
		boolean diversi = true;
		while(i<9 && diversi){
			while(j<8 && diversi){
				while(k>=j+1 && k<=8 && diversi){
					if(schema[i][j]==schema[i][k])
						diversi=false;
					k++;
				}
				j++;
			}
			i++;
		}

		//verifica colonne
		boolean diversi2=true;
		if(diversi==true){
			i=0; //indice riga
			j=0; //indice colonna
			k=1;
			while(j<9 && diversi2){
				while(i<8 && diversi2){
					while(k>=i+1 && k<=8 && diversi2){
						if(schema[i][j]==schema[k][j])
							diversi2=false;
						k++;
					}
					i++;
				}
				j++;
			}
		}

		//verifica quadrato
		if(diversi && diversi2){


		return diversi && diversi2;
	}
}

Credo dovrebbe andar bene..

E come potresti testarlo con quel codice?

Come potrei fare altrimenti?

[Andrea1979]

Se mi posso permettere, una possibile strategia diversa che limiterebbe i cicli for/while annidati:

fatti un array(9) di boolean inizialmente settati a false.
Man mano che scorri una riga (colonna) controlli se nell'array di boolean il posto di indice "elemento riga/colonna - 1" è false (non è ancora stato trovato) o true (è già stato trovato).

Se non fosse già stato trovato, lo setti a true. Se fosse già true vorrà dire che si tratta di un elemento duplicato.

[Alfredo_88]

Ho fatto come mi dici:
mi sono scritto 3 metodi private: uno che testa ogni singola riga, uno per le colonne e l'atro i settori 3x3.

//VERIFICA RIGA
	private static boolean controllaRiga(int[][] schema, int i){
		boolean[] flags = new boolean[9];

		for(int j=0; j<9; j++){
			flags[schema[i][j]-1]=true;
		}

		boolean result=true;
		for(int j=0; j<9; j++){
			if(!flags[j])
				result=false;
		}
		return result;
	}

	//VERIFICA COLONNA
	private static boolean controllaColonna(int[][] schema, int j){
		boolean[] flags = new boolean[9];

		for(int i=0; i<9; i++)
			flags[schema[i][j]-1]=true;

		boolean result=true;
		for(int i=0; i<9; i++){
			if(!flags[i])
				result=false;
		}
		return result;
	}

	//VERIFICA SETTORE
	private static boolean controllaSettore(int[][]schema, int h){
		boolean[] flags = new boolean[9];
		int i0 = (h/3)*3;
		int j0 = (h%3)*3;

		for(int i=j0; i<i0+3; i++){
			for(int j=j0; j<j0+3; j++){
				flags[schema[i][j]-1]=true;
			}
		}
		boolean result=true;
		for(int k=0; k<9; k++){
			if(!flags[k])
				result=false;
		}
		return result;
	}

Infine ho scritto il metodo public(di istanza) che sfruttando i 3 metodi sopra mi restituisce un boolean true o false a seconda che lo schema sia corretto o meno:

//VERIFICA SCHEMA
	public static boolean verificaSchema(int[][] schema){
		boolean corretto=true;
		int i=0;
		while(i<9 && corretto){
			if(!controllaRiga(schema,i))
				corretto=false;
			i++;
		}

		if(corretto){
			int k=0;
			while(k<9 && corretto){
				if(!controllaColonna(schema,k))
					corretto=false;
				k++;
			}
		}

		if(corretto){
			int j=0;
			while(j<9 && corretto){
				if(!controllaSettore(schema, j))
					corretto=false;
				j++;
			}
		}
		return corretto;
	}

Ho testato il codice (realizzando una classe di prova e mettendo un array 9x9) ma a quanto pare non funziona e secondo me il problema stà nel metodo public (verificaSchema() per intenderci). Potrei fare 3 cicli for, uno per le righe, uno per le colonne e l'altro per i settori. Però credo (almeno) che sia più efficiente se il metodo verificaSchema() si stoppasse nel momento in cui già una condizione non sia verificata. Per esempio se già riscontro una riga sbagliata è inutile che mi metta a controllare le colonne e i settori.
Come potrei fare?

[andbin]

Originariamente inviato da Alfredo_88
Come potrei fare altrimenti?

Di soluzioni, come spesso succede, ce ne sarebbero svariate. Una te l'ha detta Andrea1979, cioè quella di usare dei boolean per verificare le occorrenze dei numeri 1..9.
Ma anche volendo usare i cicli innestati si può fare, essendo (immagino) un esercizio "didattico" non credo proprio sia necessario "spremere" a livello di performance.

Il punto è che se vuoi usare l'approccio dei cicli annidati, dovresti farlo in modo appropriato.
Cioè un ciclo esterno per le righe e un altro esterno per le colonne. Dentro il ciclo principale ci dovrebbero stare 2 ulteriori cicli annidati. Però gli indici in questi due cicli vanno gestiti in modo oculato. Il primo numero devi verificare che non si trovi nelle 8 celle successive, il secondo numero devi verificare che non si trovi nelle 7 celle successive, ecc..
Insomma, l'indice più interno parte dal <indice del numero> + 1.

E non è questo che succede nei tuoi primi codici che hai postato, visto che k lo inizializzi solo una volta fuori dal ciclo esterno e va sempre solo avanti.

[Alfredo_88]

Ok! Perfetto! Grazie mille! Alla fine ho risolto utilizzando 3 cicli for. Comunque per esercizio proverò ad implementare il metodo verificaSchema() con un while che mi consenta di ottenere false non appena una condizione non sia soddisfatta!
Grazie a tutti!

[andbin]

Originariamente inviato da Alfredo_88
con un while che mi consenta di ottenere false non appena una condizione non sia soddisfatta!

Ma questo tecnicamente puoi farlo anche con un for. E se il tuo test della matrice è in un metodo che restituisce appunto true/false, appena vedi che ci sono ripetizioni potresti anche ritornare subito false. (nota: c'è chi ritiene che avere un metodo con più punti di uscita non sia una buona cosa, concordo in parte, ma credo che si debba anche vedere l'algoritmo, la lunghezza, ecc..)