8皇后问题的回溯解法 - webdancer's Blog

8皇后问题的回溯解法

webdancer posted @ 2011年4月07日 02:11 in 算法 with tags 算法 , 1521 阅读

 

问题:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线(2条)上,问有多少种摆法。 

解法:采用回溯算法。

 

#include<stdio.h>
#include<stdlib.h>

#define N 9 
int x[N];
void vswap(int *pi,int *pj){
    int tmp=*pi;
    *pi=*pj;
    *pj=tmp;
}

void out(int * x,int n){
    int i;
    for(i=1;i<n;i++)
        printf("%d ",x[i]);
    printf("\n");
}

void init(int *x,int n){
    int i;

    for(i=1;i<n;i++)
        x[i]=i;
}

int bound(int t){
   int i;
   for(i=1;i<t;i++)
       if(abs(x[i]-x[t])==abs(i-t)||x[t]==x[i])
           return 0;
   return 1;

}

void traceback(int t){
    if(t>=N){
        out(x,N);
    }
    else{
        int i;
        for(i=t;i<N;i++){
            vswap(&x[t],&x[i]);
            if(bound(t))
                traceback(t+1);
            vswap(&x[t],&x[i]);
        }
    }
}

int main(){
    init(x,N);
    traceback(1);
    return 0;
}

运行:

 

gcc -o 8q 8q.c 

结果:

 

./8q|wc -l

为:92.

Rajasthan 4th Class 说:
2023年7月11日 19:39

Rajasthan State Class Book Board Every Year Published and Distribution in Elementary School 4th Class Book 2024 Various Gujarati, Hindi, English, Maths, EVS Subject Book, Every Year Rajasthan State Wise Primary Rajasthan 4th Class Book 2024 School newly Join More Than 5 Laks of Students, Rajasthan Board 4th Class Students Strength in More Then 50 laks of Students Attended in Elementary School Level Education.Rajasthan Elementary School Little Students can Download the Class Book for Academic Education Study Further uses, we have given more information about the Rajasthan Board.

seo service london 说:
2024年1月14日 00:14

I read your post and I found it amazing! thank


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee