N regine con più vincoli

[Javino89]

Salve! Devo scrivere un algoritmo per risolvere un problema simile alle n regine. Dico simile perché ci sono 3 sostanziali differenze:

1) devo ritornare il numero massimo di regine che è possibile piazzare sulla griglia (non mi interessa dove le metto o la configurazione finale)

2) vincolo 1: ci sono celle riservate, sulla quale non posso piazzare nulla

3) vincolo 2: ci sono celle dette "pedine", le quali interrompono l'effetto della regina su quella riga/colonna. Cioè, sulla stessa riga possono esserci due regine se fra di loro c'è una pedina (stessa cosa per la colonna) poiché l'effetto della regina si ferma al punto in cui è presente la pedina. Non so se mi sono spiegato.

L'algoritmo deve essere polinomiale quindi ho escluso la ricorsione con backtracking. La programmazione dinamica non saprei come sfruttarla in questo caso. Per ora sto provando un normale algoritmo ricorsivo, andando ad intuito.. ma ci deve essere il trucco ._.

Qualsiasi consiglio è ben accetto ^^

[Javino89]

Ok ho cominciato a buttar giù del codice senza pensare ad un algoritmo efficiente.

Problemi:

1) inefficienza
2) qualche errore nella logica o dei controlli riga/colonna o nel metodo ricorsivo

Esempio:

Matrice originaria:
A A A P A A A
A A A P A A A
A A A P A A A
R R R R R R R


Matrice risolta:
T A A P A A A
A T A P A A A
A A T P A A A
R R R R R R R


Answer: 3

La risposta deve essere 6 e la matrice risolta deve essere così:
T A A P T A A
A T A P A T A
A A T P A A T
R R R R R R R

private static int solveRic(char[][] board, int i, int j) {
        // passi base
        if(i > board.length - 1 || j > board[0].length - 1) {
            return 0;
        }
        
        if(board[i][j] == 'P' || board[i][j] == 'R') {
            return Math.max(solveRic(board, i + 1, j), solveRic(board, i, j + 1));
        }
        
        // chiamate ricorsive
        if(board[i][j] == 'A') {
            boolean cr = checkRiga(board, i, j);
            boolean cc = checkColonna(board, i, j);
            if(cr == true && cc == false) { // riga buona, colonna cattiva
                return solveRic(board, i, j + 1); // cambio colonna
            }
            if(cr == false && cc == true) { // riga cattiva, colonna buona
                return solveRic(board, i + 1, j); // cambio riga
            }
            if(cr == true && cc == true) { // riga buona, colonna buona
                board[i][j] = 'T';
                return Math.max(solveRic(board, i + 1, j) + 1, solveRic(board, i, j + 1) + 1); // scelgo la strada migliore
            }
        }
        
        // credo che questo sia backtracking
        
        if(board[i][j] == 'T') {
            boolean cr = checkRiga(board, i, j);
            boolean cc = checkColonna(board, i, j);
            if(cr == false || cc == false) { // la torre non può stare qua
                board[i][j] = 'A';
                return Math.max(solveRic(board, i + 1, j) - 1, solveRic(board, i, j + 1) - 1);
            }
        }
        
        return 0;
    }


     private static boolean checkRiga(char[][] board, int i, int j) {		
		boolean checkTorre = false;
		boolean checkPedina = false;
		
		// controllo se sulla stessa riga ci sono altre torri, ottenendone la prima occorrenza se presente
		int jTorre = 0;
		for(int x = j + 1; x < board[0].length; x++) {
			if(board[i][x] == 'T') {
				jTorre = x;
				checkTorre = true;
				break;
			}
		}
		
		int jPedina = 0;
		// se ho trovato una torre...
		if(checkTorre) {
			// controllo se c'è una P prima della torre trovata
			for(int x = j + 1; x < jTorre; x ++) {
				if(board[i][x] == 'P') {
					jPedina = x;
					checkPedina = true;
					break;
				}
			}
			// ho trovato una pedina!
			if(checkPedina) {
				// controllo se c'è spazio prima della pedina
				for(int x = j; x < jPedina; x++) {
					if(board[i][x] == 'A') {
						return true;
					}
				}
			}
			
		} else { // non ho trovato una torre
			// controllo se c'è spazio
			for(int x = j + 1; x < board[0].length; x++) {
				if(board[i][x] == 'A') {
					return true;
				}
			}
		}
		
		return false;
	}


	private static boolean checkColonna(char[][] board, int i, int j) {
		
		boolean checkTorre = false;
		boolean checkPedina = false;
		// controllo se sulla stessa riga ci sono altre torri, ottenendone la prima occorrenza se presente
		int iTorre = 0;
		for(int x = i; x < board.length; x++) {
			if(board[x][j] == 'T') {
				checkTorre = true;
				break;
			}
		}
		
		int iPedina = 0;
		// se ho trovato una torre...
		if(checkTorre) {
			// controllo se c'è una P prima della torre trovata
			for(int x = i; x < iTorre; x++) {
				if(board[x][j] == 'P') {
				    iPedina = x;
					checkPedina = true;
					break;
				}
			}
			// ho trovato una pedina!
			if(checkPedina) {
				// controllo se c'è spazio prima della pedina
				for(int x = i; x < iPedina; x++) {
					if(board[x][j] == 'A') {
						return true;
					}
				}
			}
			
		} else { // non ho trovato una torre
			// controllo se c'è spazio
			for(int x = i; x < board.length; x++) {
				if(board[x][j] == 'A') {
					return true;
				}
			}
		}
		
		return false;
	}
    }

Ok sono una totale disgrazia i controlli per controllare righe e colonne, help