经典 n个皇后问题 求递归代码

苍祭

n个皇后 问题 即一个方形棋盘 在上面放n个皇后  皇后所在的行列 以及对角都不能再放皇后  
看不明白可以百度

andalousie

现在看来，n皇后问题也不过如此了。。。我的是C++版本。
queens.h

1. // Queens.h
   
2. 
   
3. const int max_board = 30;
   
4. 
   
5. class Queens{
   
6. public:
   
7.         Queens(int size);
   
8.         bool is_solved() const;
   
9.         void print() const;
   
10.         bool unguarded(int col) const;
    
11.         void insert(int col);
    
12.         void remove(int col);
    
13.         int  board_size;  //Dimension of board = maximum number of queens
    
14. private:
    
15.         int  _count;    //Current number of queens = first unoccupied row
    
16.         bool col_free[max_board];
    
17.         bool up_free[2*max_board-1];
    
18.         bool down_free[2*max_board-1];
    
19.         int  queen_in_row[max_board]; // column number of queen in each row
    
20. };
    
21. 
    
22. Queens::Queens(int size)
    
23. : board_size(size), _count(0)
    
24. {
    
25.         for(int i = 0; i < board_size; ++i) col_free[i] = true;
    
26.         for(int j = 0; j < (2*max_board-1); ++j) up_free[j] = true;
    
27.         for(int k = 0; k < (2*max_board-1); ++k) down_free[k] = true;
    
28. }
    
29. 
    
30. bool Queens::is_solved() const
    
31. {
    
32.         return _count == board_size;
    
33. }
    
34. 
    
35. void Queens::insert(int col)
    
36. {
    
37.         queen_in_row[_count] = col;
    
38.         col_free[col] = false;
    
39.         up_free[_count+col] = false;
    
40.         down_free[_count-col+board_size-1] = false;
    
41.         _count++;
    
42. }
    
43. 
    
44. void Queens::remove(int col)
    
45. {
    
46.         _count--;
    
47.         queen_in_row[_count] = 0;
    
48.         col_free[col] = true;
    
49.         up_free[_count+col] = true;
    
50.         down_free[_count-col+board_size-1] = true;
    
51. }
    
52. 
    
53. void Queens::print() const
    
54. {
    
55.         for(int row = 0; row < board_size; ++row)
    
56.         {
    
57.                 std::cout << "|";
    
58.                 for(int col = 0; col < board_size; ++col)
    
59.                 {
    
60.                         if(queen_in_row[row] == col) std::cout << "Q|";
    
61.                         else std::cout << " |";
    
62.                 }
    
63.                 std::cout << "\n";
    
64.         }
    
65.         std::cout << "*******************************\n";
    
66. }
    
67. 
    
68. bool Queens::unguarded(int col) const
    
69. {
    
70.         return col_free[col]
    
71.             && up_free[_count+col]
    
72.             && down_free[_count-col+board_size-1];
    
73. }

复制代码

main.cpp

1. #include <iostream>
   
2. #include "queens.h"
   
3. 
   
4. void solve_from(Queens &config)
   
5. {
   
6.         if(config.is_solved()) config.print();
   
7.         else
   
8.                 for(int col = 0; col < config.board_size; ++col)
   
9.                         if(config.unguarded(col))
   
10.                         {
    
11.                                 config.insert(col);
    
12.                                 solve_from(config);  //Recursively continue to add queens
    
13.                                 config.remove(col);
    
14.                         }
    
15. }
    
16. 
    
17. int main()
    
18. {
    
19.         int board_size;
    
20. //        print_information();
    
21.         std::cout << "What is the size of the board?" << std::flush;
    
22.         std::cin  >> board_size;
    
23.         if(board_size < 0 || board_size > max_board)
    
24.                 std::cout << "The number must between 0 and " << max_board << std::endl;
    
25.         else{
    
26.                 Queens config(board_size);  //Initialize empty configuration
    
27.                 solve_from(config);  //Find all solutions extending configuration
    
28.         }
    
29. }

复制代码

苍祭

补充我的代码  这样得不到最短路径长度
#include "iostream"
using namespace std;

typedef struct node{
    int x;
    int y;
    struct node *next;
}node,*Node;

#define si 20

typedef struct stak{
    Node top,base;
}st,*ST;

int i , j ;
int n =0 ,m = 0,mark = 0;

bool judge (char a[si][si] , ST s ,int b , int c )
{
    Node p;
    if( mark )
        return false;
    if( a[b][c] != '#' && b < n && c < m && a[b][c] != 'T')
    {
        p=(Node)malloc(sizeof(node));
        p->x = b;
        p->y = c;
        p->next = s->top;
        s->top = p;
        judge(a , s , b+1 , c);
        judge(a , s , b , c+1);
    }
    else
        if( a[b][c] == 'T')
        {
            mark ++;
            return true;   
        }
        else
            return false;
        
}

int main()
{
   
    while(scanf("%d%d",&n,&m) != EOF)
    {
        getchar();
        mark = 0;
        char data[si][si] = {'\0'};
        int x = 0, y = 0, rout = 0;
        ST s;
        s = (ST)malloc( sizeof(st) );
        s->base = s->top = (Node)malloc(sizeof(node));
        s->base->next = s->top->next = NULL;
        for(i = 0;i < n;i++)
        {
            for(j = 0;j < m;j++)
            {
                scanf("%c",&data[i][j]);
            }
            getchar();
        }
        judge(data , s , x , y );
        if(mark)
        {
            while(s->base != s->top)
            {
                rout ++;
                s->top = s->top->next;
            }
            printf("%d\n",rout);
        }
        else
            printf("impossible\n");
    }
    return 0;
}

仰望天上的光

...让人看不明白去baidu，你自己为什么就不baidu下？这么经典的问题不是能baidu出一堆C的代码吗？

S4C

using System;
using System.Collections.Generic;
using System.Text;

namespace N皇后问题
{
    class Recursion
    {
        static int queen_count ;
        static int[] rows;
        static int[] cross_left;
        static int[] cross_right;
        static int[] result;

        static void Main(string[] args)
        {
            //使用递归的方式求解N皇后问题
            while (true)
            {
                while (!get_input())
                {
                    get_input();
                }

                rows = new int[queen_count];
                cross_left = new int[2 * queen_count - 1];
                cross_right = new int[2 * queen_count - 1];
                result = new int[queen_count];
                DateTime start = DateTime.Now;
                put_queen(0);
                TimeSpan used_time = (TimeSpan)(DateTime.Now - start);
                Console.WriteLine();
                Console.WriteLine(queen_count.ToString() + " 皇后的解为 :");
                for (int queen = 0; queen < result.Length; queen++)
                {
                    Console.Write(result[queen].ToString());//结果产生
                    Console.Write(" ");
                }
                Console.WriteLine();
                Console.WriteLine("消耗时间: " + used_time.TotalSeconds.ToString() + " 秒");
                Console.ReadLine();
            }
        }

        static bool get_input()
        {
            Console.Clear();
            Console.WriteLine("使用递归方法求解N皇后问题的一组解, 请输入皇后个数( 4< N <= 50 ) : ");
            string str_n = Console.ReadLine();

            if (string.IsNullOrEmpty(str_n))
            {
                error();
                return false;
            }

            if (!int.TryParse(str_n, out queen_count))
            {
                error();
                return false;
            }

            if (queen_count < 4 || queen_count > 50)
            {
                error();
                return false;
            }
            return true;
        }
        static void error()
        {
            Console.WriteLine("请输入正确的数字!");
            System.Threading.Thread.Sleep(1000);
        }
        static bool put_queen(int q_x)//列位置
        {
            if (q_x == (queen_count -1))
            {
                for (int k = 0; k < queen_count; k++)
                {
                    if (canput((queen_count - 1), k))
                    {
                        result[(queen_count - 1)] = k;
                        return true;
                    }
                }
                return false;
            }

            for (int des_y = 0; des_y < queen_count; des_y++)//当前行位置
            {
                if (canput(q_x, des_y))
                {
                    rows[des_y] = 1;
                    cross_left[des_y - q_x + queen_count -1] = 1;
                    cross_right[des_y + q_x] = 1;
                    result[q_x] = des_y;

                    if (put_queen(q_x + 1))
                        return true;
                    else
                    {
                        rows[des_y] = 0;
                        cross_left[des_y - q_x + queen_count -1] = 0;
                        cross_right[des_y + q_x] = 0;
                    }
                }
                else
                    continue;
            }

            return false;

        }
        static bool canput(int x, int y)
        {
            if (rows[y] == 1)
                return false;

            if (cross_left[y - x + queen_count -1] == 1)
                return false;

            if (cross_right[y + x] == 1)
                return false;

            return true;
        }
    }
}

苍祭

S4C 发表于 2012-3-25 13:19

                               
登录/注册后可看大图

using System;
using System.Collections.Generic;
using System.Text;

雷····能请问您用的是c语言吗？   我新手  还真看不太懂这个····

苍祭

仰望天上的光 发表于 2012-3-25 12:52

                               
登录/注册后可看大图

...让人看不明白去baidu，你自己为什么就不baidu下？这么经典的问题不是能baidu出一堆C的代码吗？

其实 不是想着这边的高手回答会更清楚些的嘛，我百度过了·····可是好像我高估我自己了····

丿夏夜灬彬刂

0.0
:dizzy:

霸王龙

代码去百度

旭日东升

苍祭 发表于 2012-3-26 23:13

                               
登录/注册后可看大图

其实 不是想着这边的高手回答会更清楚些的嘛，我百度过了·····可是好像我高估我自己了····

不是高估自己了，看到别人写的代码头晕很正常。、
学习C语言得多看别人代码，看懂后自己就可以融会贯通了。
试着一行一行的慢慢看把。

bingghost

苍祭 发表于 2012-3-26 23:12

                               
登录/注册后可看大图

雷····能请问您用的是c语言吗？   我新手  还真看不太懂这个····

显然是C#的

笑着流泪

代码长就犯晕，不知道如何看下去了:dizzy:

刺客信条

代码长就犯晕

未闻丶花名

路过看看= =！