八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。
以下求出一个解:
var map = []; var n = 8; for(var i = 0; i < n; i++){ map[i] = []; for(var j = 0; j < n; j++) { map[i][j] = 0; } } function isSafe(i0, j0) { //console.log('isSafe:', i0, j0); if(map[i0][j0]) { return false; } for(var i = 0; i < n; i++) { if(map[i0][i] || map[i][j0]) { return false; } } var i = i0; var j = j0; while(i >= 0 && j >= 0) { if(map[i][j]) { return false; } i--; j--; } var i = i0; var j = j0; while(i < n && j < n) { if(map[i][j]) { return false; } i++; j++; } var i = i0; var j = j0; while(i >= 0 && j < n) { if(map[i][j]) { return false; } i--; j++; } var i = i0; var j = j0; while(i < n && j >= 0) { if(map[i][j]) { return false; } i++; j--; } //console.log(' safe:', i0, j0); return true; } function mark(i, j){ map[i][j] = 1; } function unmark(i, j){ map[i][j] = 0; }; function nqueen(k){ if(k == 0) { return true; } for(var i = 0; i < n; i++) { for(var j = 0; j < n; j++) { if(isSafe(i, j)) { mark(i, j); //console.log('mark', i, j); if(nqueen(k - 1)) { return true; } else { unmark(i, j); //console.log('unmark', i, j); } } } } return false; } console.log(nqueen(n)); console.log(map);
判断位置是否合法那里写的太复杂了。
求出全部92个解。
参考:八皇后问题(C语言版本)
由于8个皇后的任意两个不能处在同一行,那么肯定是每一个皇后占据一行。于是我们可以定义一个数组queens[8],数组中第i个数字表示位于第i行的皇后的列号。先把数组queens的8个数字分别用0~7初始化,接下来就是对数组queens做全排列。因为我们是用不同的数字初始化数组,所以任意两个皇后肯定不同列。我们只需要判断每一个排列对应的8个皇后是不是在同一对角线上,也就是对于数组的两个下标i和j,是不是 i-j==queens[i]-queens[j]或者 j-i==queens[i]-queens[j]。
代码如下:
var queens = []; var n = 8; var result = []; for(var i = 0; i < n; i++) { queens[i] = i + 1; } while(true){ if(isvalid()){ result.push(queens.concat()); } if(!next()) { break; } } console.log(result); function next() { // var j = n-2; while(j >= 0 && queens[j] > queens[j + 1]){ j--; } if(j < 0) { return false; } // var k = j + 1; var min = queens[k]; for(var i = k + 1; i < n; i++) { if(queens[i] < queens[j]) { break; } if(queens[i] < min) { min = queens[i]; k = i; } } // var temp = queens[j]; queens[j] = queens[k]; queens[k] = temp; // var a = j + 1; var b = n - 1; while(a < b) { var temp = queens[a]; queens[a] = queens[b]; queens[b] = temp; a++; b--; } // return true; } function isvalid(){ for(var i = 0; i < n - 1; i++){ for(var j = i + 1; j < n; j++) { if(i - j == queens[i] - queens[j] || j - i == queens[i] - queens[j]){ return false; } } } return true; }
其中生成全排列使用的是“字典序法”。
发表评论:
◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。