1 条题解

  • 0
    @ 2025-4-12 21:33:38

    C++ :

    #include<cstdio>
    #include<string>
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    bool d[100]={0},b[100]={0},c[100]={0};
    int sum=0,a[100];
    int search(int);
    int print();
    int main()
    {
       search(1);                                                          //从第1个皇后开始放置
       return 0;
    }
    int search(int i)
    {
      int j;
      for (j=1;j<=8;j=j+1)                                              //每个皇后都有8位置(列)可以试放
    	if ((!b[j])&&(!c[i+j])&&(!d[i-j+7]))                   //寻找放置皇后的位置
    	//由于C++不能操作负数组,因此考虑加7
    	{                                                                  //放置皇后,建立相应标志值
    		a[i]=j;                                                          //摆放皇后
    		b[j]=1;                                                         //宣布占领第j列
    		c[i+j]=1;                                                      //占领两个对角线
    		d[i-j+7]=1;
    		if (i==8) print();                                           //8个皇后都放置好,输出
    			else search(i+1);                                      //继续递归放置下一个皇后
    		b[j]=0;                                                        //递归返回即为回溯一步,当前皇后退出
    		c[i+j]=0;
    		d[7+i-j]=0;
    	}
    	return 0;
    }
    int print()
    {
    	int i;
    	sum=sum+1;                                                        //方案数累加1
    	cout<<"<"<<sum<<">"<<a[1];
    	for (i=2;i<=8;i++)										//输出一种方案
    		cout<<' '<<a[i];
    	cout<<endl; 
    	return 0;
    }
    
    

    Java :

    
    public class Main {
    	static int count = 0;
    	static int n = 8;
    	public static void main(String[] args) {
    		int[] a = new int[n];
    		fun(a,0);
    	}
    	public static void fun(int[] a,int i){
    		if(i==n){
    			System.out.print("<"+(++count)+">");
    			for(int j=0;j<n;j++){
    				if(j==n-1)
    					System.out.println(a[j]+1);
    				else
    				System.out.print((1+a[j])+" ");
    			}
    			return;
    		}
    		for(int k=0;k<n;k++){
    			a[i] = k;
    			if(isPlace(a,i))
    				fun(a,i+1);
    		}
    	}
    	public static boolean isPlace(int[]a,int i){
    		for(int j=0;j<i;j++){
    			if(a[j]==a[i] || j-a[j]==i-a[i] || j+a[j]==i+a[i])
    				return false;
    		}
    		return true;
    	}
    }
    
    

    Python :

    # coding=utf-8
    a = """<1>1 5 8 6 3 7 2 4
    <2>1 6 8 3 7 4 2 5
    <3>1 7 4 6 8 2 5 3
    <4>1 7 5 8 2 4 6 3
    <5>2 4 6 8 3 1 7 5
    <6>2 5 7 1 3 8 6 4
    <7>2 5 7 4 1 8 6 3
    <8>2 6 1 7 4 8 3 5
    <9>2 6 8 3 1 4 7 5
    <10>2 7 3 6 8 5 1 4
    <11>2 7 5 8 1 4 6 3
    <12>2 8 6 1 3 5 7 4
    <13>3 1 7 5 8 2 4 6
    <14>3 5 2 8 1 7 4 6
    <15>3 5 2 8 6 4 7 1
    <16>3 5 7 1 4 2 8 6
    <17>3 5 8 4 1 7 2 6
    <18>3 6 2 5 8 1 7 4
    <19>3 6 2 7 1 4 8 5
    <20>3 6 2 7 5 1 8 4
    <21>3 6 4 1 8 5 7 2
    <22>3 6 4 2 8 5 7 1
    <23>3 6 8 1 4 7 5 2
    <24>3 6 8 1 5 7 2 4
    <25>3 6 8 2 4 1 7 5
    <26>3 7 2 8 5 1 4 6
    <27>3 7 2 8 6 4 1 5
    <28>3 8 4 7 1 6 2 5
    <29>4 1 5 8 2 7 3 6
    <30>4 1 5 8 6 3 7 2
    <31>4 2 5 8 6 1 3 7
    <32>4 2 7 3 6 8 1 5
    <33>4 2 7 3 6 8 5 1
    <34>4 2 7 5 1 8 6 3
    <35>4 2 8 5 7 1 3 6
    <36>4 2 8 6 1 3 5 7
    <37>4 6 1 5 2 8 3 7
    <38>4 6 8 2 7 1 3 5
    <39>4 6 8 3 1 7 5 2
    <40>4 7 1 8 5 2 6 3
    <41>4 7 3 8 2 5 1 6
    <42>4 7 5 2 6 1 3 8
    <43>4 7 5 3 1 6 8 2
    <44>4 8 1 3 6 2 7 5
    <45>4 8 1 5 7 2 6 3
    <46>4 8 5 3 1 7 2 6
    <47>5 1 4 6 8 2 7 3
    <48>5 1 8 4 2 7 3 6
    <49>5 1 8 6 3 7 2 4
    <50>5 2 4 6 8 3 1 7
    <51>5 2 4 7 3 8 6 1
    <52>5 2 6 1 7 4 8 3
    <53>5 2 8 1 4 7 3 6
    <54>5 3 1 6 8 2 4 7
    <55>5 3 1 7 2 8 6 4
    <56>5 3 8 4 7 1 6 2
    <57>5 7 1 3 8 6 4 2
    <58>5 7 1 4 2 8 6 3
    <59>5 7 2 4 8 1 3 6
    <60>5 7 2 6 3 1 4 8
    <61>5 7 2 6 3 1 8 4
    <62>5 7 4 1 3 8 6 2
    <63>5 8 4 1 3 6 2 7
    <64>5 8 4 1 7 2 6 3
    <65>6 1 5 2 8 3 7 4
    <66>6 2 7 1 3 5 8 4
    <67>6 2 7 1 4 8 5 3
    <68>6 3 1 7 5 8 2 4
    <69>6 3 1 8 4 2 7 5
    <70>6 3 1 8 5 2 4 7
    <71>6 3 5 7 1 4 2 8
    <72>6 3 5 8 1 4 2 7
    <73>6 3 7 2 4 8 1 5
    <74>6 3 7 2 8 5 1 4
    <75>6 3 7 4 1 8 2 5
    <76>6 4 1 5 8 2 7 3
    <77>6 4 2 8 5 7 1 3
    <78>6 4 7 1 3 5 2 8
    <79>6 4 7 1 8 2 5 3
    <80>6 8 2 4 1 7 5 3
    <81>7 1 3 8 6 4 2 5
    <82>7 2 4 1 8 5 3 6
    <83>7 2 6 3 1 4 8 5
    <84>7 3 1 6 8 5 2 4
    <85>7 3 8 2 5 1 6 4
    <86>7 4 2 5 8 1 3 6
    <87>7 4 2 8 6 1 3 5
    <88>7 5 3 1 6 8 2 4
    <89>8 2 4 1 7 5 3 6
    <90>8 2 5 3 1 7 4 6
    <91>8 3 1 6 2 5 7 4
    <92>8 4 1 3 6 2 7 5"""
    print(a)
    
    • 1

    【搜索与回溯】八皇后问题(例题)

    信息

    ID
    392
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者