Implement the N-Queens Problem - Implement the N-Queens Algorithm

Curriculum Help
1

Tell us what’s happening:

Hi,
I think the solutions are correct, but I’m not passing tests 8 and 11.

Your code so far

function dfsNQueens(n){
  if (n<1 || n==2 || n==3) return [];
  if (n==1)return [[0]];
  let soluciones=[]
 
  let tabVacio= Array(n).fill(-1)
let pila=[tabVacio];
while(pila.length>0){
  
  let nuevoTablero=pila.pop()
  let longitud=Math.max(...nuevoTablero);
  if (longitud==n-1){
    soluciones.push(nuevoTablero);
    continue;
  }
  for(let i=0; i<nuevoTablero.length;i++){
    let actual=[...nuevoTablero];
    if (actual[i]==-1){
      actual[i]=longitud+1;
      if (esValido(actual)==true){        
      pila.push(actual);
      
    }
    }
}
}
return soluciones;

}
function esValido(tablero){
  
  for (let i=0;i<tablero.length;i++){
    if (tablero[i]==-1) continue;
    for (let j=i+1; j<tablero.length;j++){
      if (tablero[j]==-1) continue;
      if (Math.abs(tablero[i] - tablero[j]) == Math.abs(i - j)) {return false;}

    }
  }
  
  return true;}

  console.log(dfsNQueens(5))

Your browser information:

User Agent is: Mozilla/5.0 (X11; Linux x86_64; rv:151.0) Gecko/20100101 Firefox/151.0

Challenge Information:

Implement the N-Queens Problem - Implement the N-Queens Algorithm

GitHub Link: freeCodeCamp/curriculum/challenges/english/blocks/lab-n-queens-problem-js/69860157f7fce39f9df399a3.md at main · freeCodeCamp/freeCodeCamp · GitHub

2

it looks like the tests are expecing the array members to be in the same order as written in the hint, which is what should come out if you use DFS algorithm

3

I think the algorithm is designed for recursion; I tried to implement it iteratively, which explains the different order of the solutions.

4

I don’t think that explains it. Unless you can explain exactly how?

Look at the order of the desired solution:

[
[0, 2, 4, 1, 3], 
[0, 3, 1, 4, 2], 
[1, 3, 0, 2, 4], 
[1, 4, 2, 0, 3], 
[2, 0, 3, 1, 4], 
[2, 4, 1, 3, 0], 
[3, 0, 2, 4, 1], 
[3, 1, 4, 2, 0], 
[4, 1, 3, 0, 2], 
[4, 2, 0, 3, 1]]

It’s in a very logical order, always starting with the lowest numbers first. This should give you a good clue about how to move through the array.

Your output:

[ [ 2, 4, 1, 3, 0 ],
  [ 3, 1, 4, 2, 0 ],
  [ 4, 1, 3, 0, 2 ],
  [ 1, 4, 2, 0, 3 ],
  [ 4, 2, 0, 3, 1 ],
  [ 1, 3, 0, 2, 4 ],
  [ 3, 0, 2, 4, 1 ],
  [ 2, 0, 3, 1, 4 ],
  [ 0, 2, 4, 1, 3 ],
  [ 0, 3, 1, 4, 2 ] ]

It’s harder to see a reasonable pattern here.

5

Certainly not is a backtracking, thanks

6

Hi, I changed the approach and used a recursive strategy: I start with an array of [-1, …, -1], and at each child node, I add 0, 1, 2, and 3 in that order. The solutions are correct again, but they appear in a different order.

function dfsNQueens(n) {
  if (n < 1 || n == 2 || n == 3) return [];
  if (n == 1) return [[0]];
  let soluciones = [];

  let tabVacio = Array(n).fill(-1);

  function recursiva(tablero) {
    let longitud = Math.max(...tablero);
    if (longitud == n - 1) {
      soluciones.push(tablero);
      return;
    }
    for (let i = 0; i < n; i++) {
      let tabula = [...tablero];
      if (tabula[i] == -1) {
        tabula[i] = longitud + 1;
        if (esValido(tabula)) {
          recursiva(tabula);
        }
      }
    }
  }
  recursiva(tabVacio);
  return soluciones;
}
function esValido(tablero) {
  for (let i = 0; i < tablero.length; i++) {
    if (tablero[i] == -1) continue;
    for (let j = i + 1; j < tablero.length; j++) {
      if (tablero[j] == -1) continue;
      if (Math.abs(tablero[i] - tablero[j]) == Math.abs(i - j)) {
        return false;
      }
    }
  }

  return true;
}

console.log(dfsNQueens(5));
7

Now I am going to work through the exercise using a dynamic matrix