题解 | #59.N皇后问题#

递归+回溯

• 创建arr数组存储皇后的摆放情况，初始化为全0
• check函数表示当前放置位置是否合法

递归：对于每一行，逐列检查是否合法，合法则在arr数组对应的位置置为1，然后递归

function Nqueen( n ) {
  let count = 0;
  
  let arr = [];
  for(let i=0; i<n; i++){
    arr.push([]);
    for(let j=0; j<n; j++)
      arr[i][j] = 0;
  }
  
  function check(row,colomn){//arr[row][colomn]置为1是否合法
    for(let i=0; i<row; i++){
      let index = arr[i].indexOf(1);//index就是第i行的下标
      if (index == colomn)
        return false;
      if( Math.abs(i-row) == Math.abs(index-colomn) )
        return false;
    }
    return true;
  }
  
  function traceTrack(len){//len表示给第len行放置棋子
    if(len>=n){
      count++;
      return;
    }
      
    for(let i=0; i<n; i++){//i表示第i列
      if(check(len,i) == true){
        arr[len][i] = 1;
        traceTrack(len+1);
        arr[len][i] = 0;
      }
    }
  }
  
  
  traceTrack(0);
  return count;
}