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

苍祭

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

andalousie

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

// Queens.h

const int max_board = 30;

class Queens{
public:
        Queens(int size);
        bool is_solved() const;
        void print() const;
        bool unguarded(int col) const;
        void insert(int col);
        void remove(int col);
        int  board_size;  //Dimension of board = maximum number of queens
private:
        int  _count;    //Current number of queens = first unoccupied row
        bool col_free[max_board];
        bool up_free[2*max_board-1];
        bool down_free[2*max_board-1];
        int  queen_in_row[max_board]; // column number of queen in each row
};

Queens::Queens(int size)
: board_size(size), _count(0)
{
        for(int i = 0; i < board_size; ++i) col_free[i] = true;
        for(int j = 0; j < (2*max_board-1); ++j) up_free[j] = true;
        for(int k = 0; k < (2*max_board-1); ++k) down_free[k] = true;
}

bool Queens::is_solved() const
{
        return _count == board_size;
}

void Queens::insert(int col)
{
        queen_in_row[_count] = col;
        col_free[col] = false;
        up_free[_count+col] = false;
        down_free[_count-col+board_size-1] = false;
        _count++;
}

void Queens::remove(int col)
{
        _count--;
        queen_in_row[_count] = 0;
        col_free[col] = true;
        up_free[_count+col] = true;
        down_free[_count-col+board_size-1] = true;
}

void Queens::print() const
{
        for(int row = 0; row < board_size; ++row)
        {
                std::cout << "|";
                for(int col = 0; col < board_size; ++col)
                {
                        if(queen_in_row[row] == col) std::cout << "Q|";
                        else std::cout << " |";
                }
                std::cout << "\n";
        }
        std::cout << "*******************************\n";
}

bool Queens::unguarded(int col) const
{
        return col_free[col]
            && up_free[_count+col]
            && down_free[_count-col+board_size-1];
}

main.cpp

#include <iostream>
#include "queens.h"

void solve_from(Queens &config)
{
        if(config.is_solved()) config.print();
        else
                for(int col = 0; col < config.board_size; ++col)
                        if(config.unguarded(col))
                        {
                                config.insert(col);
                                solve_from(config);  //Recursively continue to add queens
                                config.remove(col);
                        }
}

int main()
{
        int board_size;
//        print_information();
        std::cout << "What is the size of the board?" << std::flush;
        std::cin  >> board_size;
        if(board_size < 0 || board_size > max_board)
                std::cout << "The number must between 0 and " << max_board << std::endl;
        else{
                Queens config(board_size);  //Initialize empty configuration
                solve_from(config);  //Find all solutions extending configuration
        }
}

苍祭

补充我的代码  这样得不到最短路径长度
#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:

刺客信条

代码长就犯晕

未闻丶花名

路过看看= =！