N皇后

说明:

N皇后问题是一个以国际象棋为背景的问题:如何能够在N×N的国际象棋棋盘上放置N个皇后,使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。

解法:

N个皇后中任意两个不能处在同一行,所以每个皇后必须占据一行,及一列。我们采用回溯法的思想去解。首先摆放好第0行皇后的位置,然后在不冲突的情况下摆放第1行皇后的位置。到第j行时,如果没有一个位置可以无冲突的摆放皇后,则回溯到第j-1行,寻找第j-1行皇后的下一个可以摆放的位置。

总结一下,用回溯法解决N皇后问题的步骤:

(1)从第0列开始,为皇后找到安全位置,然后跳到下一列.

(2)如果在第n列出现死胡同,如果该列为第0列,棋局失败,否则后退到上一列,再进行回溯.

(3)如果在第8列上找到了安全位置,则棋局成功.

C:

#include <bits/stdc++.h>
using namespace std;
int N,sum = 0;
int queen[100];//queen[i]的值表示第i行放第queen[i]列 
void nqueen(int k)
{
	int j;
	if(k == N)//如果所有的皇后都放好了就输出 
	{
		for(int i = 0;i < N;i++)
			cout<<queen[i] + 1<<" ";//我是从第0行开始放,所以输出就要+1 
		cout<<endl;
		sum++;//每放置一种,就加一种方法 
		return;
	}
	for(int i = 0;i < N;i++)//枚举N列 
	{
		for(j = 0;j < k;j++)//前k行的皇后 
		{//第j行的皇后的列是queen[j],不能和我当前的列相同 
			if(queen[j] == i || abs(j - k) == abs(queen[j] - i))
			//也不能是对角线 
				break;
		}
		if(k == j)
		{//如果情况都满足,j就会等于k,这时就保存列号,并且进入下一行枚举
			queen[j] = i;
			nqueen(k+1);
		}//如果下一行的皇后没有正确的位置放,就会回溯,继续循环上一行的皇后位置 
	} 
} 
int main()
{
	cin>>N;
	nqueen(0);//从第0行开始放皇后 
	cout<<sum;//输出一共有多少种放法 
	return 0;
}

Java:

public class Nqueen{
     static int[] queen = new int[100];
     static int N,sum = 0;
     public static void nqueen(int k){
         int j;
         if(k == N){
             for(int i = 0;i < N;i++)
                System.out.print(queen[i] + 1 + " ");
             System.out.println();
             sum++;
             return;
         }
         for(int i = 0;i < N;i++){
             for(j = 0; j < k;j++){
                if(queen[j] == i || abs(queen[j],i) == abs(k,j))
                    break;
             }
             if(j == k){
                queen[j] = i;
                nqueen(k+1);
             }
         }
     }
     public static int abs(int i,int j){
         if(i > j)
             return i - j;
         else
             return j - i;
     }
     public static void main(String[] args){
         N = Integer.parseInt(args[0]);
         nqueen(0);
         System.out.println(sum);
     }
 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏hbbliyong

WPF Trigger for IsSelected in a DataTemplate for ListBox items

<DataTemplate DataType="{x:Type vm:HeaderSlugViewModel}"> <vw:HeaderSlug...

4064
来自专栏落花落雨不落叶

canvas画简单电路图

63111
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5556
来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2192
来自专栏C#

DotNet加密方式解析--非对称加密

    新年新气象,也希望新年可以挣大钱。不管今年年底会不会跟去年一样,满怀抱负却又壮志未酬。(不过没事,我已为各位卜上一卦,卦象显示各位都能挣钱...)...

4928
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2665
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

4045
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3185
来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2576
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2070

扫码关注云+社区