Solo un piccolo spunto iniziale.
Puoi usare un approccio alternativo e considerare una singola mina come una configurazione nella tua matrice così fatta:
1..1..1
1..0..1
1..1..1
nella tua matrice NxN. L'aggiunta di mine sarà data semplicemente dalla sovrapposizione lineare di blocchetti di questo tipo. Sommi i singoli valori e dove si sovrappongono gli "1" semplicemente li sommi. Mi sembra che, miracolosamente, così tutto torni.
Dunque, in teoria, sembrerebbe che qualsiasi sovrapposizione di mine genererebbe la stessa somma complessiva.
MA: ciò che fa la differenza è
- lo "zero" dove collochi la mina che azzera qualsiasi valore fosse presente nella casella e
- i bordi della matrice, perché eventuali "1" che escano dalla matrice sono persi.
Dunque: qualsiasi combinazione di mine in cui le mine
- abbiano come distanza minima tra loro due caselle
(cioè: una, ad esempio, in (1,2) e l'altra in (3,2))
- e come distanza minima dal bordo di nuovo due caselle
(nel senso che se la matrice ha indici che vanno da 1 ad N, le mine hanno come indice minimo 2)
ti genera la stessa somma su tutti gli elementi della matrice. E tale somma è la somma massima che puoi produrre. Perché tutti i singoli blocchetti aggiunti si sovrappongono linearmente ma nessuno "zero" di centro mina va ad azzerare un "uno" di confine con la mina; e nessun "uno" di confine esce dalla tabella.
La configurazione più semplice è quella a scacchiera. Ad esempio:
0.0.0.0.0.0.0.0.0.0
0.x.0.x.0.x.0.x.0.0
0.0.0.0.0.0.0.0.0.0
0.x.0.x.0.x.0.x.0.0
0.0.0.0.0.0.0.0.0.0
0.x.0.x.0.x.0.x.0.0
0.0.0.0.0.0.0.0.0.0
0.x.0.x.0.x.0.x.0.0
0.0.0.0.0.0.0.0.0.0
0.0.0.0.0.0.0.0.0.0
Il numero generato da questa configurazione è pari a:
(numero di mine) x 8
La domanda successiva sarebbe: e quante mine al massimo si possono infilare in una matrice senza diminuirne la somma massima?
A naso ti direi, per una matrice NxM:
int[(N-1)/2] x int[(M-1)/2]
Ma qui ci ho pensato poco...
Ciao!
*********
Mi scuso con l'utente di sopra, ma rimango più convinto della mia formula. Ogni mina in realtà occupa uno slot da due, cui va aggiunta una casella per il bordo.
La mia formula mi convince in via "sperimentale":
N = 3 --> 1 mina
N = 4 --> 1 mina
N = 5 --> 2 mine
N = 6 --> 2 mine
N = 7 --> 3 mine
N = 8 --> 3 mine
...
La formula di sopra per N= 5 darebbe una sola mina, mentre invece ce ne stanno due
Stavo anche pensando a qualche generalizzazione per risolvere il problema più generale.
Una risposta complessiva è difficile.
Come spunto iniziale pensavo: una volta esaurite le caselle "libere", se ci sono caselle libere a bordo campo le più convenienti risultano le combinazioni di questo tipo:
....0.0.0.0
....0.x.x.0
....0.0.0.0
....0.x.0.0
Cioè: si iniziano ad aggiungere mine che:
- non sono sul bordo, se no si perdono tre punti almeno (5 sulla spigolo).
- con un numero minimo di vicini adiacenti (anche in diagonali).
Sono dunque da scartare la posizioni a bordo campo.
Le posizioni interne hanno tutte almeno due vicini e dunque perdono 4 punti.
Se il numero di righe o di colonne è pari, ci sono a bordo campo due colonne vuote dove si possono collocare mine perdendo soltanto due punti.
Notare che la combinazione presentata è meglio della:
....0.0.0.0
....0.x.0.0
....0.0.x.0
....0.x.0.0
che aggiungendo una mina con due vicini, perde 4 punti.
Dunque aggiungendo mine che "valgono" soltanto 6 punti si può arrivare alla combinazione massima del tipo:
0.0.0.0.0.0.0.0.0.0
0.x.0.x.0.x.0.x.x.0
0.0.0.0.0.0.0.0.0.0
0.x.0.x.0.x.0.x.x.0
0.0.0.0.0.0.0.0.0.0
0.x.0.x.0.x.0.x.x.0
0.0.0.0.0.0.0.0.0.0
0.x.0.x.0.x.0.x.0.0
0.x.0.x.0.x.0.0.x.0
0.0.0.0.0.0.0.0.0.0
Notare che l'ultima mina in basso a destra l'ho inserita lì per amore di simmetria, ma avrei potuto inserirla in mille altri posti.
Il passo successivo è molto delicato. Non si possono più aggiungere mine con valore "sei" e dunque... che fare? Inserire una combinazione tipo
...0.x.x.x.0.
ha penalità quattro (aggiunge dunque solo 4 punti).
A questo punto sembrerebbe preferibile spostare la mina più a sinistra a bordo campo (perdendo tre punti) per inserirne un'altra. Ma quell'altra non si sa dove metterla. Questo vale anche se la scacchiera ha dimensione dispari. Andare ad infilarsi nelle righe vuote non aggiunge niente, perché sono sempre mine con almeno due vicini. Dunque la combinazione migliore mi sembrerebbe quella:
0.0.0.0.0.0.0.0.0.0
0.x.x.x.x.x.x.x.x.0
0.0.0.0.0.0.0.0.0.0
0.x.x.x.x.x.x.x.x.0
0.0.0.0.0.0.0.0.0.0
0.x.x.x.x.x.x.x.x.0
0.0.0.0.0.0.0.0.0.0
0.x.0.x.0.x.0.x.0.0
0.x.0.x.0.x.0.0.x.0
0.0.0.0.0.0.0.0.0.0
L'ultima riga è critica e non ci ho ancora pensato.
Però sto procedendo a braccia, non ho ancora una teoria elegante... E non escludo che esistano configurazioni "lontane" e vincenti. Anche se ne dubito.