Source JS
Même si le code source du programme JavaScript est facile à écrire, je l'ai obfusqué.
Dans ce programme nous trouvons notamment :
Création du tableau : selon la taille voulue (ici 10 par défaut), cette fonction
place les 10 zones sur la grille. Elle est appelée jusqu'à ce que chaque zone
respecte un ensemble de contraintes et que la grille ait effectivement une solution.
Création d’une zone : on tire au hasard une des 100 cellules, que l’on retire
des cellules disponibles, et on place les cellules en contact avec cette cellule
dans une file.
On mélange cette file et on tire au hasard une cellule, que l’on retire
également des cellules disponibles.
On répète ce processus jusqu’à ce que la zone atteigne le nombre maximum de 10
cellules, ou si la disposition des zones précédentes fait qu’il n’y a plus de
cellule à traiter alors que la zone n’a pas encore atteint le nombre maximum
de cellules. On passe ensuite à la zone suivante, et ce, jusqu’à ce que toutes
les zones soient traitées.
Complétion des zones restantes : on regarde s’il reste des cellules disponibles
et, si oui, pour chacune de ces cellules, on examine les cellules à proximité.
On choisit au hasard une cellule et donc une zone, puis on affecte cette cellule
à cette zone et on la retire des cellules disponibles.
Les contraintes sont les suivantes : générer un nombre limité de petites zones,
et il ne peut pas y avoir une zone d’une cellule sur une même ligne ou colonne
qu’une autre zone constituée d’une seule cellule.
Le programme peut générer deux zones séparées ayant le même numéro, ce qui est
un bug, et a priori des zones d’une largeur maximale d’une cellule peuvent se
retrouver sur la même ligne ou la même colonne, ce qui est également un bug.
Au moment de la constitution d’une zone, on vérifie qu’elle ne soit pas trop
épaisse (voir Chevallier et Laspalès).
Le placement d'une reine supprime la reine qui est déjà sur la même ligne ou
colonne. Cliquer sur une reine l'efface. on ne peut placer une reine au contact
d'une autre reine.
On peut checker la solution : dans ce cas on vérifie que toutes les zones ont
bien une seule reine et qu'il y a bien une seule reine par ligne et par colonne
sur toutes les lignes et toutes les colonnes.
Quand on a créé toutes les zones, on vérifie qu'une solution existe.
Cela se fait par l'appel d'une fonction récursive qui traite
chaque ligne du haut vers le bas de la grille. On essaie de placer une reine
sur la ligne courante en respectant les contraintes. Donc on va essayer pour
chaque colonne de la ligne en partant de la gauche vers la droite. Si on a
placé une reine on passe à la ligne suivante sur laquelle on teste de la gauche
vers la droite. si une reine est placée on passe à la ligne suivante.
Si une reine est placée sur chaque ligne en respectant les contraintes on a
trouvé une solution. Dans le cheminement on peut être sur le traitement
d'une ligne et ne pas arriver à placer une reine. on revient dans ce cas
grace à la récursivité sur la dernière reine placée sur la ligne précédente
que l'on retire et que l'on essaie de placer plus à droite.
Donc le principe de récursivité est ici de traiter une ligne.
Si une ligne est traitée on traite la ligne suivante et ainsi de suite.
Si on ne peut pas traiter une ligne on retourne sur la ligne précédente et on
essaie de placer la reine sur une colonne plus à droite. Si on n'y arrive pas,
on revient sur la ligne précédente et on essaie de placer la reine plus à
droite.
Donc reine placée entraine traitement de la ligne suivante et reine non placée
entraine retour à la ligne précédente et tentative de trouver une position plus
à droite.
Ce traitement a permis d'utiliser des maps, des sets, de la destructuration
de tableau, de la récursivité et le maniement des objets du DOM afin de modifier
les caractéristiques d'affichage de chaque cellule. Egalement le traitement
d'évènements comme le clic sur un bouton. Les fonctions de manipulation de
tableau pop, push, shift, slice et splice.
Ci-dessous quelques extraits du source :
board = Array.from({length: N}, () => Array(N).fill(0));
const template = `repeat(${N}, var(--cell-size))`;
boardContainer.style.gridTemplateColumns = template;
boardContainer.style.gridTemplateRows = template;
boardContainer.innerHTML = '';
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
const cell = document.createElement('div');
cell.classList.add('cell');
cell.dataset.row = i;
cell.dataset.col = j;
cell.style.backgroundColor = colors[zones[i][j]];
if (i === 0 || zones[i-1][j] !== zones[i][j]) cell.style.borderTopColor = "black";
if (j === 0 || zones[i][j-1] !== zones[i][j]) cell.style.borderLeftColor = "black";
if (i === N-1) cell.style.borderBottomColor = "black";
if (j === N-1) cell.style.borderRightColor = "black";
cell.addEventListener('click', () => toggleQueen(i, j, cell));
boardContainer.appendChild(cell);
}
}
}
if (board[row][col] === 1) {
board[row][col] = 0;
cell.textContent = '';
return;
}
for (let c=0;c<N;c++) {
if (board[row][c]===1) {
board[row][c]=0;
boardContainer.querySelector(`.cell[data-row="${row}"][data-col="${c}"]`).textContent='';
}
}
for (let r=0;r<N;r++) {
if (board[r][col]===1) {
board[r][col]=0;
boardContainer.querySelector(`.cell[data-row="${r}"][data-col="${col}"]`).textContent='';
}
}
const zoneId=zones[row][col];
for (let i=0;i<N;i++){
for (let j=0;j<N;j++){
if (zones[i][j]===zoneId && board[i][j]===1){
board[i][j]=0;
boardContainer.querySelector(`.cell[data-row="${i}"][data-col="${j}"]`).textContent='';
}
}
}
board[row][col]=1;
cell.textContent='♛';
}
const idx=Math.floor(Math.random()*available.length);
const [si,sj]=available.splice(idx,1)[0];
const neigh=[[i-1,j],[i+1,j],[i,j-1],[i,j+1]].filter(
([ni,nj])=>ni>=0 && ni<N && nj>=0 && nj<N && zones[ni][nj]===-1
);
zones[i][j]=zones[ni][nj];
const a=arr.slice();
for (let i=a.length-1;i>0;i--){
const j=Math.floor(Math.random()*(i+1));
[a[i],a[j]]=[a[j],a[i]];
const usedCols=new Set();
const usedZones=new Set();
function isSafe(r,c,queens){
if (usedCols.has(c)) return false;
if (usedZones.has(zones[r][c])) return false;
for (const [qr,qc] of queens){
if (Math.abs(qr-r)<=1 && Math.abs(qc-c)<=1) return false;
}
return true;
}
function backtrack(r,queens){
if (r===N) return true;
for (let c=0;c<N;c++){
if (isSafe(r,c,queens)){
queens.push([r,c]);
usedCols.add(c);
usedZones.add(zones[r][c]);
if (backtrack(r+1,queens)) return true;
queens.pop();
usedCols.delete(c);
usedZones.delete(zones[r][c]);
}
}
return false;
}
return backtrack(0,[]);
if (rowSum!==1 || colSum!==1){
alert("Solution incorrecte : chaque ligne et chaque colonne doit contenir une reine.");
for (let i=0;i<N;i++) for (let j=0;j<N;j++) if (zones[i][j]===z && board[i][j]===1) count++;
if (count!==1){
alert("Solution incorrecte : chaque zone doit contenir une reine.");
|