[JAVA] Algoritmo generazione cartelle tombola.

[corzand]

Salve a tutti ragazzi, avevo postato una reply in un vecchio post, dove chiedevo delucidazioni sull'algoritmo di generazione cartelle per la tombola, ma ne apro direttamente un altro per due motivi:
1) Ho cambiato la struttura che descrivevo nell'altro topic;
2) Il titolo è ben formattato come richiesto dai mods.

Allora sto cercando di sviluppare un'applicazione java che simuli il gioco della tombola.
L'ostacolo maggiore è però la generazione delle cartelle.

Le ipotesi che ho tenuto in considerazione sono:
1) Ogni cartella è composta da una matrice di interi 3x9, dove le celle vuote contengono degli zeri;
2) Ogni cartella ha almeno un numero per ogni colonna;
3) Ogni cartella ha al massimo 5 numeri per riga;
4) Ogni colonna contiene i numeri della decina di competenza con un'eccezione particolare:
- la prima colonna contiene numeri da 1 a 9;
- l'ultima colonna contiene numeri da 80 a 90;
5) Le cartelle vengono generate in "fogli" da 6, ognuno dei quali contiene 6 cartelle che a loro volta unite contengono tutti i 90 numeri SENZA RIPETIZIONI

Date per assunte queste ipotesi, ho deciso di partire da questo metodo:

	public List<Cartella> CreaCartelle(int numeroCartelle) {
		List<Cartella> cartelleNuove = new ArrayList<Cartella>();
		List<Cartella> cartelleUscita = new ArrayList<Cartella>();
		List<String> listaNumeri = new LinkedList<String>();
		int[] indiciDecine = new int[] { 9, 10, 10, 10, 10, 10, 10, 10, 11 };
		Random rand = new Random();

		// Riempio la linked list con numeri interi da 1 a 90.
		for (int i = 1; i <= 90; i++) {
			listaNumeri.add("" + i);
		}

		// Aggiungo all'arrayList di Cartelle 6 cartelle vuote.
		for (int i = 0; i < 6; i++) {
			Cartella cart = new Cartella();
			cartelleNuove.add(cart);
		}

		// Inserisco in ogni cartella un numero per ogni colonna (decina)
		for (int j = 0; j < numeroCartelle; j++) {
			for (int k = 0; k < 9; k++) {

				int cont = 0;
				for (int h = 0; h < k; h++) {
					cont += indiciDecine[h];
				}
				int ixListaNum = cont + rand.nextInt(indiciDecine[k]);
				int num = Integer.parseInt(listaNumeri.get(ixListaNum));
				listaNumeri.remove(ixListaNum);
				indiciDecine[k]--;

				cartelleNuove.get(j).addNumber(num);
			}
		}
		// Completo l'inserimento dei numeri per ogni cartella
		for (int j = 0; j < numeroCartelle; j++) {
			for (int k = 0; k < 6; k++) {
				boolean inserito = false;
				int num;
				int ixListaNum;

				do {
					ixListaNum = rand.nextInt(listaNumeri.size());
					num = Integer.parseInt(listaNumeri.get(ixListaNum));
					if (cartelleNuove.get(j).addNumber(num))
						inserito = true;
				} while (!inserito);
				listaNumeri.remove(ixListaNum);
			}
		}

		for (int i = 0; i < numeroCartelle; i++) {
			cartelleUscita.add(cartelleNuove.get(i));
		}

		return cartelleUscita;
}

In pratica prima inserisco all'interno di ogni cartella un numero per ogni decina, dopodichè completo le cartelle una alla volta, inserendo i restanti 6 numeri per ognuna di esse.

Il problema che mi si presenta è che spesso, arrivato agli ultimi due/tre numeri da inserire nell'ultima cartella, rimane in loop nel punto evidenziato di rosso, impedendo al programma di procedere.
Questo perchè vengono violate le ipotesi iniziali (o massimo numero in riga, o massimo numero in colonna) ed il metodo addNumber(..) restituisce false.
Ora ve lo posto qui di seguito:

	public boolean addNumber(int num) {

		boolean primaRiga = true;
		boolean secondaRiga = true;
		boolean terzaRiga = true;

		Random rand = new Random();

		int columnIndex = (num == 90 ? 8 : num / 10);
		int rowIndex;
		//Controllo se è possibile aggiungere quel numero in colonna
		for (rowIndex = 0; rowIndex < 3 && tabNums[rowIndex][columnIndex] != 0; rowIndex++);
		if (rowIndex == 3)
			return false;
		else {
			while (primaRiga || secondaRiga || terzaRiga) {
				int contRow = 0;
				rowIndex = rand.nextInt(3);

				switch (rowIndex) {
				case 0:
					if (primaRiga) {
						for (int i = 0; i < 9; i++) {
							if (tabNums[rowIndex][i] != 0)
								contRow++;
						}
						if (contRow == 5)
							primaRiga = false;
						else if (tabNums[rowIndex][columnIndex] == 0) {
							tabNums[rowIndex][columnIndex] = num;
							return true;
						}
						else
						{
							primaRiga = false;
						}
					}
					break;
				case 1:
					if (secondaRiga) {
						for (int i = 0; i < 9; i++) {
							if (tabNums[rowIndex][i] != 0)
								contRow++;
						}
						if (contRow == 5)
							secondaRiga = false;
						else if (tabNums[rowIndex][columnIndex] == 0) {
							tabNums[rowIndex][columnIndex] = num;
							return true;
						}
						else
						{
							secondaRiga = false;
						}
					}
					break;
				case 2:
					if (terzaRiga) {
						for (int i = 0; i < 9; i++) {
							if (tabNums[rowIndex][i] != 0)
								contRow++;
						}
						if (contRow == 5)
							terzaRiga = false;
						else if (tabNums[rowIndex][columnIndex] == 0) {
							tabNums[rowIndex][columnIndex] = num;
							return true;
						}
						else
						{
							terzaRiga = false;
						}
					}
					break;
				}
			}
			return false;
		}
	}

sinceramente non so da che parte farmi per risolvere questo problema..spero tanto che qualche buona anima (molto capace negli algoritmi) mi dia una mano!!
Grazie, Andrea..

PS: se non vi è chiaro qualcosa non esitate a postare per delucidazioni!!

[Barbalbero]

Il metodo più semplice e rapido (da implementare) che mi viene in mente è il metodo euristico.
Riempi le cartelle casualmente ma secondo un albero.
Una volta trovato il loop torni al nodo precedente dell'albero e scegli l'altra strada. Se hai già scelto tutte le strade di quel nodo torni al nodo ancora precedente... e così via fino a raggiungere la radice.
Certo potrebbe essere computazionalmente pesante.
E' solo una formulazione teorica la mia...vedi tu se è fattibile

[corzand]

Originariamente inviato da Barbalbero

Il metodo più semplice e rapido (da implementare) che mi viene in mente è il metodo euristico.
Riempi le cartelle casualmente ma secondo un albero.
Una volta trovato il loop torni al nodo precedente dell'albero e scegli l'altra strada. Se hai già scelto tutte le strade di quel nodo torni al nodo ancora precedente... e così via fino a raggiungere la radice.
Certo potrebbe essere computazionalmente pesante.
E' solo una formulazione teorica la mia...vedi tu se è fattibile

mmm, è molto interessante come metodologia, ma credo sia pesantissima..anche perchè comunque il loop si verifica circa un esecuzione su tre, quindi non spesso da rendere la generazione a buon fine molto improbabile..
Perciò penso che forse, non sarebbe male inserire un controllo nel metodo evidenziato in rosso che mi "rilevi" un eventuale loop, ricominciando l'algoritmo da capo..
Certo, non è molto bello dal punto di vista dell'esecuzione, ma potrebbe funzionare..che ne dite?

[gugoXX]

Cerco una soluzione plausibile delle 6 cartelle.
Piazzo ciascuna delle 6 cartelle come faccia di un cubo di rubik custom.
Eseguo un numero casuale di mosse casuali, e mi fermo ritirando il risultato ottenuto.

http://www.youtube.com/watch?v=_jGGLZUcpbQ
http://www.youtube.com/watch?v=tiMvA...eature=related
http://www.youtube.com/watch?v=w0W5I...eature=related

Scusami, non so quello che sto dicendo.
Ho guidato tutto il giorno ed ho bevuto 2 birre a stomaco vuoto con i colleghi.