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 条评论
登录 后参与评论

相关文章

来自专栏Hongten

让你一看就明白什么是代理模式--java版本_源码下载

======================================================

913
来自专栏racaljk

Julia体验 语言特性 元编程,宏

上接语言基础,就release-1.1来看,个人感觉这门语言和自己心中的理想国相距较远。这门语言因为受众不仅仅是程序员有很多让人迷惑的设计,但是奇怪的是它的语法...

972
来自专栏曾大稳的博客

Android ClassLoader流程解读并简单方式实现热更新

ClassLoader在启动Activity的时候会调用loadClass方法,我们就从这里入手:

1072
来自专栏后端之路

Dubbo优雅服务降级之mock

Dubbo优雅服务降级之Stub dubbo作为国内互联网最常用的Java开源服务治理框架,在提供了远程调用的同时也提供了服务降级功能。 首先可以考虑一下服务降...

1.1K5
来自专栏IT笔记

传说中的并发编程ABA问题

什么是ABA问题 ABA并不是一个缩写,更像是一个形象的描述。ABA问题出现在多线程或多进程计算环境中。 首先描述ABA。假设两个线程T1和T2访问同一个变量V...

4007
来自专栏ACM算法日常

UVA10129:Play on Words(欧拉回路)

Some of the secret doors contain a very interesting word puzzle. The team of arc...

781
来自专栏Flutter入门到实战

老司机带你重构Android的v4包的部分源码

版权声明:本文为博主原创文章,未经博主允许不得转载。https://www.jianshu.com/p/a08d754944c4

981
来自专栏Android源码框架分析

Android面试官装逼失败之:Activity的启动模式总结

1433
来自专栏数据结构与算法

P2605 [ZJOI2010]基站选址

题目描述 有N个村庄坐落在一条直线上,第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站,在第i个村庄建立基站的费用为Ci。...

3758
来自专栏王小雷

SAS学习笔记之《SAS编程与数据挖掘商业案例》(3)变量操作、观测值操作、SAS数据集管理

SAS学习笔记之《SAS编程与数据挖掘商业案例》(3)变量操作、观测值操作、SAS数据集管理 1. SAS变量操作的常用语句 ASSIGNMENT 创建或修改...

18410

扫码关注云+社区