Otto Regine

Dispone su una scacchiera 8 * 8 otto regine in modo tale che non siano una sotto scacco dell'altra.

La soluzione viene cercata esplorando tutte le possibili combinazioni. Per ottimizzare i tempi di ricerca, alcune disposizioni parziali che non porterebbero alla soluzione e tutte quelle che hanno quella disposizione, vengono scartate in blocco.
Per esempio due regine sulla prima riga violano la condizione imposta dal rompicapo, è inutile provare a posizionare le altre 6 regine!
Da quanto detto il programma può limitarsi a cercare di posizionare una regina su ogni riga, questo ha impatto anche sulla struttura dati utilizzata per rappresentare la disposizione delle regine sulla schacchiera, si veda più avanti.
Comunque dobbiamo scartare anche altre combinazioni parziali che violano la condizione del rompicapo e che non hanno due regine sulla stessa riga.

Prima di procedere oltre vale la pena vedere l'algoritmo all'opera! Guardando con attenzione si vede che a volte il programma non riesce a mettere la regina sulla riga, non c'è una posizione valida, che insieme alle regine già messe vada bene. Invece di procedere con le righe successive (sarebbero tutti tentativi inutili) torna indietro e sposta la regina posizionata in precedenza.

A B C D E F G H
8
7
6
5
4
3
2
1

Si parte dalla schacchiera vuota. Si aggiunge la prima regina sulla prima colonna e si passa alla riga successiva. La configurazione iniziale, nessuna regina sulla scacchiera è rappresentata dall'array [-1, -1, -1, -1, -1, -1, -1, -1]. A partire da questa configurazione si posiziona una regina per volta sulla scacchiera e ogni volta si effettua un controllo per vedere se ci sono situazioni di scacco reciproco, se così è si trova un'altra posizione per l'ultima regina inserita, se non è possibile trovare una posizione valida si torna a cambiare la regina sulla riga precedente. Il procedimento va avanti finché non è stopPropagation(); posizionata l'ottava regina.

Per rappresentare la soluzione utilizziamo un array di 8 interi. Ciascuna posizione dell'array è collegata ad una riga della scacchiera, mentre il valore in quella posizione indica la colonna dove è posta la regina. Per esempio l'array [0, 5, 7, 6, 4, 3, 1, 2] sta a rappresentare 8 regine nelle seguenti posizioni:

NB: nell'array la prima posizione viene indicata con 0... 

                        ...
                         5    *
                         4         *
                         3   *
                         2 *
                         1   * 
                           A B C D...