算法-n皇后问题

比眉伴天荒 2022-07-24 08:24 141阅读 0赞

> **题目描述：**一个 n\*n 的棋盘，要在上面放 n 个皇后。规则：两个皇后之间如果是同列、同行、同对角线它们会互相攻击。也就
> 
> 是说：棋盘上的任意两个皇后不能为同列、同行、同对角线。
> 
>   
> 
> 
> **算法思想：**q(j)表示一个解的空间即存储一组可行解的数组，j表示行数，q(j)的值表示j行可以放置皇后的所在列数，根据任意
> 
> 两个皇后不能在同列、同对角线可得放置皇后的条件是

> > (1) q( i ) != q( k );
> 
> > (2) abs( q( i ) - q( k ) ) != abs( i - k )。

> 当可以放置皇后时就继续到下一行，不能放置则尝试该行的下一列位置，重新检测，如此反复，直到将所有解解出。
> 
>     #include <stdio.h>
>     #include <math.h>
>     #define N 15    //规定皇后最多为15个 
>     int q[N];         //记录各皇后所在的列号
>     int count = 0;
>     int check(int i,int k){//检验第i行的k列上是否可以摆放皇后
>     	int j=1;
>     	while(j<i){  //j=1~i-1是已经放置了皇后的行	
>     		//第j行的皇后是否在k列或(j,q[j])与(i,k)是否在斜线上
>     		if(q[j]==k || abs(j-i)==abs(q[j]-k)) 
>     			return 0;
>     		j++;
>     	}
>     	return 1;
>     }
>     void print(int n){
>     	int i,j;
>     	printf("第%d个解：",count);
>     	for(i=1;i<=n;i++)
>     		printf("(%d,%d) ",i,q[i]);
>     	printf("\n");
>     }
>     void place(int i,int n) {//放置皇后到棋盘上 
>     	int j;
>     	if(i>n){
>     		++count;
>     		print(n);	
>     	} else {
>     		for(j=1;j<=n;j++){   //试探第i行的每一个列
>     		
>     			if(check(i,j)){
>     				q[i] = j;
>     				place(i+1,n);  //上一任务完成时才进行下一个任务
>     			}
>     		}
>     	}
>     }
>     int main(void){
>     	int n;
>     	scanf("%d",&n);
>     	if(n<=15)
>     		place(1,n);
>     	printf("%d\n",count);
>     	return 0;
>     }
> 
>   
>   
>

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关【经典算法】N皇后问题

经典N皇后问题的算法。做一道经典题目，来一场思维旅行。

本是古典何须时尚/ 2024年05月25日 17:33/ 0 赞/ 44 阅读

相关算法分析---8皇后问题---N皇后问题

![在这里插入图片描述][20210406171121133.png] package demo1; public class NkingsSort

一时失言乱红尘/ 2022年11月16日 05:51/ 0 赞/ 138 阅读

相关 n皇后问题

目前会的一种解决n皇后的方法，在笔记本上大概能解除10以内的问题，更大规模的还要再去学习其他的人的好方法 include<iostream> usi

曾经终败给现在/ 2022年08月20日 06:24/ 0 赞/ 153 阅读

相关 n皇后问题

n皇后问题 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述在n×n 格的棋盘上放置

小鱼儿/ 2022年08月18日 02:30/ 0 赞/ 136 阅读

相关 N皇后问题

在n\n的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n\n格的棋盘上放置n个皇后，任何2个皇后

本是古典何须时尚/ 2022年08月08日 14:38/ 0 赞/ 134 阅读

相关算法-n皇后问题

> 题目描述：一个 n\n 的棋盘，要在上面放 n 个皇后。规则：两个皇后之间如果是同列、同行、同对角线它们会互相攻击。也就 > > 是说：棋盘上的任意两个皇后不能为同列、同

比眉伴天荒/ 2022年07月24日 08:24/ 0 赞/ 142 阅读

相关 N皇后问题

转自：http://www.cnblogs.com/chuanlong/archive/2013/04/21/3033471.html <table sty

╰+哭是因爲堅強的太久メ/ 2022年07月14日 20:42/ 0 赞/ 173 阅读

相关 N皇后问题

题目: 请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个nxn的棋盘上放置n个棋子，使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。给定一个int

- 日理万妓/ 2022年06月16日 12:41/ 0 赞/ 198 阅读

相关 N 皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包

喜欢ヅ旅行/ 2022年05月17日 04:52/ 0 赞/ 183 阅读

相关 n皇后问题

package test; public class Main{ static final int n=4; static int

客官°小女子只卖身不卖艺/ 2022年03月25日 06:22/ 0 赞/ 202 阅读