js版本的八皇后回溯算法结果有误？

Question

使用js实现的八皇后回溯算法，但是得到的结果，是有错的。若是有结果的话，理应都是长度为8的数组，但是结果不是。如效果图。请帮忙修改一下代码，至可以正常显示结果。<code>let coloum = 8; //棋盘的列let row = 8; //棋盘的行// 先创建一个二维数组let arrInner = new Array();for(var i=0;i<coloum;i++){ arrInner[i] = new Array();}let arrNew = arrInner.slice(0); //复制二维数组row_add = 0;var tmp = [];var total = 0;function dfs(row_add){ if(row_add==8){ total++; console.log('打印出结果：',tmp); tmp = []; return }else{ for(var i=0;i<8;i++){ if(check(i,row_add)==1){ arrNew[i][row_add] = 1; //如果通过验证,说明可以放皇后 tmp.push([i,row_add]) dfs(row_add+1); //然后继续调用 arrNew[i][row_add] = 0; //说明后面那一行都放不了皇后，所以上一行的皇后要清零，以免回溯的时候出现脏数据 tmp.pop([i,row_add]) } } }}function check(x,y){ //以该位置为基准，判断在同一列上有无已经放置了的皇后 for(var k=0;k<=7;k++){ // console.log('1:',x,k); if((k>=0)&&arrNew[x][k]==1){ return 0; } } //以该位置为基准，判断其右对角线上有没有已经放置了的皇后 for(var i=x,j=y;i>=0,j>=0;i--,j--){ // console.log('2:',i,j); if((i>=0&&j>=0)&&arrNew[i][j]==1){ return 0; } } //以该位置为基准，判断其左对角线上有没有已经放置了的皇后 for(var l=x,m=y;l<=7,m>=0;l++,m--){ // console.log('3:',l,m); if((l<=7&&m>=0)&&arrNew[l][m]==1){ return 0; } } return 1;}dfs(0);</code>

Answer 1

八皇后问题
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

工作原理
首先从定义知道，两个皇后都不能处于同一行，所以第0个皇后放在第0行，第一个皇后放在第1行，以此类推。

先在第0行第0个格子（0,0）放一个皇后0，接着把处于同一行、同一列或同一斜线上的格子都标记为皇后0；

然后把皇后1放到第1行标记为-1的格子中，以此类推直到放下皇后7（即最后一个皇后）。

若中途出现放皇后 iQueen时，第 iQueen行所有格子已经被全部标记，即if( arr[ iQueen*n + i ].index == -1 )的判断，则回溯到上一层函数（其实就是没有进入到if分支，所有没有进行递归了，代码执行完自然会跳回上一层函数继续执行）。

注意此时的执行环境（exection context）已经变了，所有setQueen函数内定义的变量全部回溯到上一层函数递归到下一层函数前的状态，即执行setQueen( iQueen + 1 );这行代码前的状态，例如递归前i=2，iQueen=1，无论下一层函数里的i和iQueen怎样变化，回溯后还是i=2，iQueen=1，然后紧接着执行未执行完的代码。