八皇后问题与回溯法

溯月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

#include <iostream>  
#include<cmath>
using namespace std;  
  
#define N 8  
static int count = 1; 
  
int matrix[N + 1][N + 1] = {0};  
//  matrix[0][j]为空，matrix[i][0]中放第i行的皇后的列坐标（从1开始记）  
  
bool IsLegal(const int &i, const int &j)  
{  
    //  判断前面的i-1个棋子（坐标是matrix[m][n]）与matrix[i][j]是否冲突，i为1时合法  
    for (int m = 1; m <= i - 1; ++m) {  
        int n = matrix[m][0];  
        if (  n == j || abs(i - m) == abs(j - n) )  //abs(i-m)==abs(j-n)设计的很巧妙 
            return false;  
    }  
    return true;  
}  
  
void Print(void)  //打印函数，都明白，不用过多的解释 
{  
 
    printf("Case %d:\n", count++);  
    for (int i = 1; i <= N; i++) {  
        for (int j = 1; j <= N; j++) {  
            matrix[i][j] == 1 ? printf("%c ", 5) : printf(". ");  
        }  
        cout << endl;  
    }  
    cout << endl;  
}  
  
void Trial(const int &i)  //最主要的函数，明白此函数就明白了八皇后问题的解法。 
{  
    //  进入本函数时，在N*N的棋盘前i-1行已放置了互不攻击的i-1个棋子  
    //  现从第i行起继续为后续棋子选择合适位置  
  
    if (i > N)   //  输出当前的合法布局  
        Print();  
    else  
        for (int j = 1; j <= N; ++j) {  
            matrix[i][j] = 1;  
            if ( IsLegal(i, j) ) {  
                matrix[i][0] = j;  
                Trial(i + 1);  
            }  
            matrix[i][j] = 0;  
        }  
}  
  
int main(void)  
{  
    Trial(1);  
  
    return 0;  
}  

//个人认为这个代码更好理解一点

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;
}