经典 n个皇后问题 求递归代码
n个皇后 问题 即一个方形棋盘 在上面放n个皇后皇后所在的行列 以及对角都不能再放皇后看不明白可以百度
现在看来，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);
intboard_size;//Dimension of board = maximum number of queens
private:
int_count; //Current number of queens = first unoccupied row
bool col_free;
bool up_free;
bool down_free;
intqueen_in_row; // 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 = true;
for(int j = 0; j < (2*max_board-1); ++j) up_free = true;
for(int k = 0; k < (2*max_board-1); ++k) down_free = true;
}
bool Queens::is_solved() const
{
return _count == board_size;
}
void Queens::insert(int col)
{
queen_in_row = col;
col_free = false;
up_free = false;
down_free = false;
_count++;
}
void Queens::remove(int col)
{
_count--;
queen_in_row = 0;
col_free = true;
up_free = true;
down_free = 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 == col) std::cout << "Q|";
else std::cout << " |";
}
std::cout << "\n";
}
std::cout << "*******************************\n";
}
bool Queens::unguarded(int col) const
{
return col_free
&& up_free
&& down_free;
}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 , ST s ,int b , int c )
{
Node p;
if( mark )
return false;
if( a != '#' && b < n && c < m && a != '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 == 'T')
{
mark ++;
return true;
}
else
return false;
}
int main()
{
while(scanf("%d%d",&n,&m) != EOF)
{
getchar();
mark = 0;
char data = {'\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);
}
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的代码吗？ 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;
cross_left = new int;
cross_right = new int;
result = new int;
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.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 = 1;
cross_left = 1;
cross_right = 1;
result = des_y;
if (put_queen(q_x + 1))
return true;
else
{
rows = 0;
cross_left = 0;
cross_right = 0;
}
}
else
continue;
}
return false;
}
static bool canput(int x, int y)
{
if (rows == 1)
return false;
if (cross_left == 1)
return false;
if (cross_right == 1)
return false;
return true;
}
}
}
S4C 发表于 2012-3-25 13:19 static/image/common/back.gif
using System;
using System.Collections.Generic;
using System.Text;
雷····能请问您用的是c语言吗？ 我新手还真看不太懂这个···· 仰望天上的光 发表于 2012-3-25 12:52 static/image/common/back.gif
...让人看不明白去baidu，你自己为什么就不baidu下？这么经典的问题不是能baidu出一堆C的代码吗？
其实 不是想着这边的高手回答会更清楚些的嘛，我百度过了·····可是好像我高估我自己了···· 0.0
:dizzy: 代码去百度{:5_90:} 苍祭 发表于 2012-3-26 23:13 static/image/common/back.gif
其实 不是想着这边的高手回答会更清楚些的嘛，我百度过了·····可是好像我高估我自己了····
不是高估自己了，看到别人写的代码头晕很正常。、
学习C语言得多看别人代码，看懂后自己就可以融会贯通了。
试着一行一行的慢慢看把。 苍祭 发表于 2012-3-26 23:12 static/image/common/back.gif
雷····能请问您用的是c语言吗？ 我新手还真看不太懂这个····
显然是C#的 代码长就犯晕，不知道如何看下去了:dizzy: 代码长就犯晕 路过看看= =！
页:
[1]