hanyeah

八皇后问题是一个以国际象棋为背景的问题：如何能够在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;
}

其中生成全排列使用的是“字典序法”。