N王后问题，是一个科学谜题，指的是在把N个王后放到N*N的棋盘上，结果是任何王后之间都不会彼此威胁。换句话说，每个后继的王后既不能与前面的王后在同一行、同一列，也不能位于同一对角线上。N王后问题给出了Python代码。下面是JavaScript代码，但结果有些误差，不知何故。

function conflict(state,posX)	{
	var posY = state.length;
	for (var i=0;i<posY ;i++ )
	{
		var differ = Math.abs(state[i]-posX);
		if (differ == 0 || differ == (posY - i))
		{
			return true;
		}
	}
	return false;
}

function queens(num,state,solutions){
	for (var x=0;x<num ;x++ )
	{
		if (!conflict(state,x))
		{
			if (state.length == (num-1))
			{
				solutions.unshift(x);
				return true;
			}
			var result = queens(num,state.concat(x),solutions);
			if (result)
			{
				if (state.length==0)
				{
					solutions.unshift(x);
					continue;
				}
				solutions.unshift(x);
				return true;
			}

		}

	}
}

用法如下：

var result = [];
queens(4,[],result);
console.log(result);// [3, 1, 0, 2, 2, 0, 3, 1, 1, 3, 0, 2, 0, 3, 1, 2]

关于N王后问题
模块代码：

#nqueens.py
#coding=UTF-8

# n王后问题解决方案
# 检查当前王后位置（可能是多个）与下一个王后位置是否冲突
def conflict(state,posX):
	posY = len(state)
	for i in range(posY):
		if abs(state[i]-posX) in (0,posY-i):
			return True
		return False

# 采用回溯递归算法，结合生成器特性，计算可能的解决方案
def find(num=4,state=()):
	for pos in range(num):
		if not conflict(state,pos):
			if len(state)==num-1:
				yield (pos,)
		else:
			for result in find(num,state+(pos,)):
				yield (pos,)+result

# 形象地表示每个解决方案
def show(solutions):
	def printSolution(index,solution):
		print "\n方案"+str(index)+" "+str(solution)+"\n"
		for pos in solution:
			length=len(solution)
			print ". "*(pos)+"Q "+". "*(length-pos-1)+"("+str(pos)+")"
			list_solutions = list(solutions)
		if not len(list_solutions)==0:
			enum_solutions = enumerate(list_solutions)
			n_solutions = len(list_solutions)
			n_queens = len(list_solutions[0])
			print str(n_queens)+"王后问题有"+str(n_solutions)+"种方案："
		for index,solution in enum_solutions:
			printSolution(index+1,solution)

# 调用方法：
# nqueens.show(nqueens.find())
# 或
# nqueens.show(nqueens.find(5))

将以上代码复制到nqueens.py中，把nqueens.py保存在“你的路径”下。
查看全文 »