八皇后问题与回溯法

溯月0503

565335545 发表于 2015-6-24 09:45
啥东西

运行有错

June_SR

学习学习

565335545

溯月0503 发表于 2015-6-24 09:58
运行有错

嗷嗷这样握

565335545

565335545 发表于 2015-6-28 15:14
嗷嗷这样握

高级回复

misys

感谢分享

苦哈哈哈

这一直是一个老大难问题，每次看到都头疼

lewisyixin

感谢分享

我叫淳子

谢谢楼主。。。这个很好。

ELI_

谢谢分享

DAY

1. #include <iostream>  
   
2. #include<cmath>
   
3. using namespace std;  
   
4.   
   
5. #define N 8  
   
6. static int count = 1;
   
7.   
   
8. int matrix[N + 1][N + 1] = {0};  
   
9. //  matrix[0][j]为空，matrix[i][0]中放第i行的皇后的列坐标（从1开始记）  
   
10.   
    
11. bool IsLegal(const int &i, const int &j)  
    
12. {  
    
13.     //  判断前面的i-1个棋子（坐标是matrix[m][n]）与matrix[i][j]是否冲突，i为1时合法  
    
14.     for (int m = 1; m <= i - 1; ++m) {  
    
15.         int n = matrix[m][0];  
    
16.         if (  n == j || abs(i - m) == abs(j - n) )  //abs(i-m)==abs(j-n)设计的很巧妙
    
17.             return false;  
    
18.     }  
    
19.     return true;  
    
20. }  
    
21.   
    
22. void Print(void)  //打印函数，都明白，不用过多的解释
    
23. {  
    
24. 
    
25.     printf("Case %d:\n", count++);  
    
26.     for (int i = 1; i <= N; i++) {  
    
27.         for (int j = 1; j <= N; j++) {  
    
28.             matrix[i][j] == 1 ? printf("%c ", 5) : printf(". ");  
    
29.         }  
    
30.         cout << endl;  
    
31.     }  
    
32.     cout << endl;  
    
33. }  
    
34.   
    
35. void Trial(const int &i)  //最主要的函数，明白此函数就明白了八皇后问题的解法。
    
36. {  
    
37.     //  进入本函数时，在N*N的棋盘前i-1行已放置了互不攻击的i-1个棋子  
    
38.     //  现从第i行起继续为后续棋子选择合适位置  
    
39.   
    
40.     if (i > N)   //  输出当前的合法布局  
    
41.         Print();  
    
42.     else  
    
43.         for (int j = 1; j <= N; ++j) {  
    
44.             matrix[i][j] = 1;  
    
45.             if ( IsLegal(i, j) ) {  
    
46.                 matrix[i][0] = j;  
    
47.                 Trial(i + 1);  
    
48.             }  
    
49.             matrix[i][j] = 0;  
    
50.         }  
    
51. }  
    
52.   
    
53. int main(void)  
    
54. {  
    
55.     Trial(1);  
    
56.   
    
57.     return 0;  
    
58. }  
    
59. 
    
60. //个人认为这个代码更好理解一点

复制代码

lb971216008

厉害

子煜从嘉

#include<stdio.h>
#include<iostream>
#define N 8
typedef struct _pos_flag
{
        int xpo;
        int ypo;
}Pos;
static char code[N + 2][N + 2];
static Pos pos[] = { { -1, -1 }, { -1, 0 }, { -1, 1 } };

static int count = 0;


void init()
{
        int i = 0;
        int j = 0;
        for (i = 0; i < N + 2; i++)
        {
                code[0][i] = '#';
                code[N + 1][i] = '#';
                code[i][0] = '#';
                code[i][N + 1] = '#';
        }
        for (i = 1; i <= N; i++)
        {
                for (j = 1; j <= N; j++)
                        code[i][j] = ' ';
        }
       
}
void display()
{
        int i = 0;
        int j = 0;
        for (i = 0; i <N + 2; i++)
        {
                for (j = 0; j < N + 2; j++)
                        printf("%c", code[i][j]);

                printf("\n");

        }
}

int check(int i, int j)
{
        int ret = 1;
        int p= 0;
       
        for (p = 0; p < 3; p++)
        {
                int ni = i;
                int nj = j;
                while (ret&&code[ni][nj] != '#')
                {
                        ni = ni + pos[p].xpo;
                        nj = nj + pos[p].ypo;
                        ret = ret&&code[ni][nj] != '*';
                }
        }
        return ret;

}

void find(int i)
{
        int j = 0;
        if (i > N)
        {
                count++;
                printf("Solution: %d\n", count);

                display();

                getchar();
        }
        else
        {
                for (j = 1; j <= N; j++)
                {
                        if (check(i, j))
                        {
                                code[i][j] = '*';
                                find(i + 1);
                                code[i][j] = ' ';
                        }

                }
        }

}
int main()
{
        init();
        //display();
        find(1);
        system("pause");
        return 0;
}