八皇后问题-检查皇后位置一个小坑解决

为什么检查皇后位置是否合法是否可以用的时候只检查了上半部分???

由于本人脑袋不好使(可能是短路了)硬是想了半个小时才明白。。。先看看代码:

//这是百度百科上面对皇后位置检测的代码
bool isPlaceOK(int *a, int n, int c) {
    for (int i = 1; i <= n - 1; ++i) {
        if (a[i] == c || a[i] - i == c - n || a[i] + i == c + n)
            return false;
        //检查位置是否可以放
        //c是将要放置的位置
        //a[i] == c如果放在同一列,false
        //a[i] -+ i = c -+ n 如果在对角线上,false
    }
    return true;
}
//博客-八皇后问题(递归回溯算法详解+C代码)
int notDanger( int row, int col )
{
	int i,k;
	// 判断列方向
	for( i=0; i < 8; i++ )
	{
		if( chess[i][col]==1 )
		{
			return 0;
		}
	}
	// 判断左对角线 
	for( i=row, k=col; i>=0 && k>=0; i--, k-- )
	{
		if(chess[i][k]==1  )
		{
			return 0;
		}
	}
	// 判断右对角线 
	for( i=row, k=col; i>=0 && k<8; i--, k++ )
	{
		if(chess[i][k]==1  )
		{
			return 0;
		}
	}
	return 1;
}
//博客-八皇后问题(递归回溯)
  public boolean check(int x,int y){
        for (int i = 0; i < y; i++) {
            //纵向检查
            if (chessBoard[x][i]==1) {
                return false;
            }
            //检查左横向
            if (x-1-i>=0&&chessBoard[x-1-i][y-1-i]==1) {
                return false;
            }
            //检查右横向
            if (x+1+i<size &&chessBoard[x+1+i][y-1-i]==1) {
                return false;
            }
        }

        return true;
    }

各种的写法殊途同归,但是不难发现都只检查了上半部分是否合法。。。对于这个问题我们可以回想一下这个递归回溯()是怎么进行的:

//摘录自:八皇后问题(递归回溯)
 eck_燃
void EightQueen( int row )
{
	int col;

        //如果遍历完八行都找到放置皇后的位置则打印
	if( row>7 )
	{
		Print();
                 //打印八皇后的解                       
		count++;
		return ;
		
	}

	for( col=0; col < 8; col++ )//回溯,递归
	{
		if( notDanger( row, col ) )// 判断是否危险
		{
			chess[row][col]=1;
			EightQueen(row+1);
			
			chess[row][col]=0;//清零,以免回溯时出现脏数据
		}
	}
}

在每一次递归中,对棋盘的操作是按照顺序的从上到下,row也从0号索引增加到7号索引,因此在判断的时候应该只需要判断上半部分即可因为下半部分压根就没有放皇后。。。。。。

本篇文章由Rex创建并发布,若有转载文章的需求或发现内容错误、图片侵权等请发送邮件到:[email protected],本人高中生有可能回复没有那么及时,但是看到一定会第一时间处理回复的qwq。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇