论坛 › 数据结构与算法 › 八皇后问题与回溯法

溯月0503 发表于 2015-6-24 09:58:12

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

运行有错

June_SR 发表于 2015-6-25 09:49:28

学习学习

565335545 发表于 2015-6-28 15:14:06

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

嗷嗷这样握

565335545 发表于 2015-6-28 15:14:45

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

高级回复

misys 发表于 2015-12-23 13:50:19

感谢分享

苦哈哈哈 发表于 2015-12-23 19:39:29

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

lewisyixin 发表于 2015-12-24 22:49:15

感谢分享

我叫淳子 发表于 2015-12-29 17:23:38

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

ELI_ 发表于 2016-7-1 15:21:02

谢谢分享

DAY 发表于 2016-7-6 14:53:04

#include <iostream>
#include<cmath>
using namespace std;

#define N 8
static int count = 1;

int matrix = {0};
//matrix为空，matrix中放第i行的皇后的列坐标（从1开始记）

bool IsLegal(const int &i, const int &j)
{
    //判断前面的i-1个棋子（坐标是matrix）与matrix是否冲突，i为1时合法
    for (int m = 1; m <= i - 1; ++m) {
      int n = matrix;
      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 == 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 = 1;
            if ( IsLegal(i, j) ) {
                matrix = j;
                Trial(i + 1);
            }
            matrix = 0;
      }
}

int main(void)
{
    Trial(1);

    return 0;
}

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

lb971216008 发表于 2016-8-23 22:23:43

厉害

子煜从嘉 发表于 2016-8-24 20:51:57

#include<stdio.h>
#include<iostream>
#define N 8
typedef struct _pos_flag
{
        int xpo;
        int ypo;
}Pos;
static char code;
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 = '#';
                code = '#';
                code = '#';
                code = '#';
        }
        for (i = 1; i <= N; i++)
        {
                for (j = 1; j <= N; j++)
                        code = ' ';
        }
       
}
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);

                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 = ni + pos.xpo;
                        nj = nj + pos.ypo;
                        ret = ret&&code != '*';
                }
        }
        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 = '*';
                                find(i + 1);
                                code = ' ';
                        }

                }
        }

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

查看完整版本: 八皇后问题与回溯法