Să se aşeze n dame pe o tablă de şah n×n încât ele să nu se atace două câte două.

n =      diagrama (click pentru o nouă poziţie)

Principii de lucru

Orice câmp al tablei de şah poate fi indicat prin perechea (row, col) indicând respectiv linia şi coloana care se intersectează pe acel câmp. Dar nu este necesar să implicăm un tablou bidimensional, fiindcă putem asocia implicit valorile col cu indicii de acces într-un vector unidimensional, iar valorile row cu valorile existente în acest vector.

Vom considera un vector ROW[n] în care pentru fiecare indice i_col = 0..n-1 avem

ROW[i_col] == i_row <=> există o damă în poziţia (i_row, i_col).

Două dame ROW[i] şi ROW[j] (cu i ≠ j) se atacă <=>

ROW[i] == ROW[j] (sunt pe o aceeaşi linie), sau

|i - j| == |ROW[i] - ROW[j]| (sunt pe o aceeaşi diagonală).

Soluţie a problemei va fi orice vector ROW[] care satisface condiţia ca damele ROW[i] şi ROW[j] să nu se atace (pentru i, j = 0..n-1). Nu vom "afişa" vectorul-soluţie ROW[] ca atare, ci (vizând o aplicaţie pentru browser) vom implica obiectele DOM necesare pentru a reprezenta chiar tabla de şah corespunzătoare soluţiei ROW[].

Putem alege între mai multe metode sau algoritmi de rezolvare, în funcţie de ce sau cât vrem să obţinem: pentru o soluţie, metoda randomizării ar fi suficientă; dacă vrem toate soluţiile - atunci putem folosi metoda backtracking. Pe de altă parte, problema poate fi interpretată ca fiind o problemă de colorare pe un anumit graf.

În practica de masă a rezolvărilor expeditive se obişnuieşte să se evidenţieze doar aspectele algoritmice; se neglijează faptul că algoritmul respectiv angajează proprietăţi ale unor anumite obiecte definite anterior.
De exemplu, algoritmul de rezolvare a ecuaţiei de gradul întâi este unul singur, dacă se conştientizează faptul că el se bazează pe proprietăţile clasei de obiecte din care sunt individualizaţi coeficienţii (fie numere reale, fie numerele complexe, matricele pătratice, clasele de resturi modulo n, etc.).

În principiu, lucrăm cu trei fişiere-text: unul în care definim obiectele Javascript necesare rezolvării, un altul pentru a defini stilurile CSS convenabile prezentării soluţiei şi al treilea reprezentând la nivel text un document HTML (acesta va fi primul încărcat de browser şi va trebui să conţină specificaţiile de legătură necesare pentru încărcarea celorlalte fişiere, etc.).

O modalitate de modelare obiectuală

Componentele problemei noastre ar putea fi sintetizate astfel:

Queens(N, DEST) {
      N      indică dimensiunea tablei de şah
      ROW[]  vector unidimensional pentru constituirea soluţiei
      DEST   indică locul în care să fie prezentată soluţia

      show_solution()  prezintă soluţia la DEST, într-o formă sau alta
      is_good()        testează dacă în ROW[] avem o soluţie corectă
      gen_solutions()  generează soluţii, într-un mod sau altul
}

În Javascript putem considera întâi un şablon al proprietăţilor de bază:

function Queens(n) {
    this.Dim = n > 3 ?  n : 4;
    this.Row = new Array(n);
}

Invocând această funcţie prin intermediul operatorului new, vom putea crea obiecte individuale (având propriile valori Dim şi Row, fiindcă new asociază this cu obiectul construit):

      var obj1 = new Queens(5);
      var obj2 = new Queens(7);
      alert(obj1.Dim + '\n' + obj2.Dim);

Angajând proprietatea prototype prevăzută obiectelor Javascript, vom putea extinde şablonul iniţial Queens adăugând alte proprietăţi sau metode:

Queens.prototype.Dest = function(id_dom) {
          return "obiectul din document cu ID=id_dom"; 
                 // document.getElementById(id_dom);
}
alert(obj1.Dim + '\n' + obj1.Dest("diagrama1"));

Metoda randomizării

Putem obţine o soluţie a unei probleme combinatoriale oarecare folosind următoarea idee:

      REPETĂ {
               generează_aleatoriu componentele soluţiei
      }
      PÂNÂ CÂND vectorul generat satisface_condiţiile de a fi o soluţie a problemei

function Queens(n, odom) { // 'odom' referă un obiect existent în DOM-ul documentului
    this.n = n > 3 && n < 10 ?  n : 4; // n = 10 este deja prohibitiv ca timp (Firefox)
    this.row = new Array(n);
    this.odom = odom;
}

Queens.prototype.is_good = function() {
    var n = this.n, row = this.row;
    for(var i = 0; i < n - 1; i++)
        for(var j = i + 1; j < n; j++) 
            if(row[i] == row[j] || Math.abs(row[i] - row[j]) == j - i)
                return 0;
    return 1;
};

Queens.prototype.set_queen = function() { // implementare a randomizării
    var n = this.n, row = this.row;       // insuficient elaborată 
    do {                                  // (deja n = 10 ia prea mult timp)
        for(var i = 0; i < n; i++)
            row[i] = Math.round(1000 * Math.random()) % n;
    } while(!this.is_good());
};

Queens.prototype.show_table = function() {
    var n = this.n, row = this.row, diw = this.odom;
    var diag = document.createElement('table');
    diag.setAttribute('class', 'diag');

    var TR = document.createElement('tr'); // noduri care vor fi apoi clonate,
    var TH = document.createElement('th'); // evitând recrearea lor
    var TD = document.createElement('td');
    var SQ = document.createElement('img');
    SQ.setAttribute('src', "static/wqueen.png");
    var DIV = document.createElement('div');
    
    var drow, cell, dsq, i, j;
        
    var tbody = document.createElement('tbody'); // fără secţiuni THEAD, TFOOT 
    for(i = 0; i < n; i++) {
        drow = TR.cloneNode(true);
        for(j = 0; j < n; j++) {
            cell = TD.cloneNode(true);
            dsq = DIV.cloneNode(true);
            dsq.setAttribute('class', ((i + j) & 1 ? 'BlackField' : 'WhiteField'));
            if(row[j] == i)
                dsq.appendChild(SQ.cloneNode(true));
            cell.appendChild(dsq);
            drow.appendChild(cell);
        }
        tbody.appendChild(drow);
    }
    diag.appendChild(tbody);
    diw.appendChild(diag);
};

Queens.prototype.run = function() { // un shortcut pentru lansarea rezolvării
    this.set_queen();
    this.odom.innerHTML="";
    this.show_table();
}

Fişierul "js" redat mizează pe existenţa unor definiţii CSS pentru redarea unei diagrame de şah (fiind puţine la număr, ele pot fi incluse direct în secţiunea de <head> a fişierului HTML, sub tagul <style>) - de exemplu:

table.diag td { padding: 0em; text-align:center; }
.WhiteField { background: #f8f0ff; padding: 2px; width: 32px; height: 32px; }
.BlackField { background: #f8f0ff url("static/hash5.gif") 50% 50%; 
              padding: 2px; width: 32px; height: 32px; }

N.B. Dar stilarea elementelor poate avea şi alt scop decât acela de a prezenta frumos obiectele respective… În demonstraţia inclusă la început (v. "Arată diagrama"), am preferat să marcăm numai acele câmpuri negre pe care s-a aşezat câte o damă - sugerând astfel investigarea culorilor posibile pentru câmpurile ocupate de cele n dame care nu se atacă pe o tablă n×n: dacă 6 dame sunt plasate pe o tablă de şah 6×6 şi nu se atacă două câte două, atunci nu este posibil ca numai trei dintre cele şase câmpuri ocupate, să fie de o aceeaşi culoare (să se arate că patru dintre câmpurile astfel ocupate sunt de o aceeaşi culoare); este posibil ca pe tabla 8×8 cele 8 dame care nu se atacă reciproc să ocupe trei câmpuri negre şi cinci câmpuri albe?; ş.a.m.d.

Fişierul HTML va trebui să conţină în <body>:

n = <input id="en_ul" type="text" value="5" size="2" />  
<input type="button" value=" Show diagramm " 
       onclick="var n = document.getElementById('en_ul').value;
                var dame = new Queens(n,document.getElementById('diagrama1'));
                dame.run();" />

<div id="diagrama1"> </div>

permiţând astfel utilizatorului să introducă o valoare "n" şi să declanşeze prin click pe butonul "Show" seria de acţiuni specificată de onclick (în urma căreia se va prezenta o soluţie în diviziunea cu ID="diagrama1").

Metoda backtracking

Trebuie doar să extindem obiectul Queens definit mai sus, cu o nouă metodă "is_good" (fiindcă prima operează pe întregul vector ROW[], ori acum trebuie să testăm fiecare soluţie "parţială") şi cu o metodă care să asigure mecanismul backtracking:

Queens.prototype.is_good_back = function(col) {
    var row = this.row;
    if(col == 0) return 1;
    for(var i = 0; i < col; i++)
        if(row[i] == row[col] || Math.abs(row[i] - row[col]) == col - i)
            return 0;
    return 1;
};

Queens.prototype.back = function(col) {
    for(var to = 0; to < this.n; to++) {
        this.row[col] = to;
        if(this.is_good_back(col)) {
            if(col == this.n - 1) 
                this.show_table();
            else this.back(col + 1);
        }
    }
}

Desigur că trebuie să adaptăm şi fişierul HTML, iar aceasta se poate face în multe variante (depinzând de imaginaţia şi inspiraţia fiecăruia, dar... să ne gândim totdeauna şi la "bun gust"!). O modalitate didactică, vizând completarea faţă de HTML-ul anterior ar fi următoarea:

n = <input id="en_ul" type="text" value="5" size="2" />  
<input type="button" value=" Show diagramm " 
       onclick="var n = document.getElementById('en_ul').value;
                var dame = new Queens(n, document.getElementById('diagrama1'));
                dame.run();
                
                var dame_bk = new Queens(n, document.getElementById('diagrama_bk'));
                dame_bk.back(0);" />

<div id="diagrama1"> </div>
<div id="diagrama_bk"> </div>

De data aceasta, onclick va determina construcţia unui al doilea obiect "Queens", dame_bk şi pentru acesta este invocată apoi metoda "back" - ceea ce va duce la inserarea în diviziunea cu ID="diagram_bk" a diagramelor corespunzătoare soluţiilor (una sub cealaltă).