八皇后问题_c语言吧

218.22.28.*	1楼请大家帮忙给我写一个关于八皇后的问题的c语言程序设计,要实现动态操作
2004-9-16 15:33 回复

assiss	2楼这样的忙我不会帮.
2004-9-16 15:40 回复

61.235.139.*	3楼为什么
2004-9-18 08:00 回复

218.75.16.*

4楼

八皇后问题程序及注解
http://www.mydrs.org 2003-12-3 大榕树

大家一定见过这种办法吧 ,但是做为初学者理解起来特别困难 ,我就把我当时对它的理解简单说一下,不对的地方大家给个建议!
program eightqueens;
var
  x:array[1..8] of integer;
  a,b,c:array[-7..16] of boolean;
  i:integer;
procedure print;
  var k:integer;
  begin
   for k:=1 to 8 do write(x[k]:4);
   writeln;
  end;
procedure try(i:integer);
  var j:integer;
  begin
   for j:=1 to 8 do
    if a[j] and b[i+j] and c[i-j]
     then begin
   x:=j;
   a[j]:=false;
   b[i+j]:=false;
   c[i-j]:=false;
   if i<8 then try(i+1)
    else print;
   a[j]:=true;
   b[i+j]:=true;
   c[i-j]:=true
  end
end;
begin
  for i:=-7 to 16 do
   begin
    a:=true;
    b:=true;
    c:=true
   end;
  try(1);
end. 现在循环从 i=1 ,j:=1 to 8 do 开始此时计算机检测到 i=1 j=1 简化为(1,1)为空,占用该位置并令该位置对应的斜线和水平方向的位置为 false ,然后程序就开始去执行try(2),注意此时计算机在i=1 这层仅仅走拉一个循环(j=1)就跳到拉i=2 这层里此时计算机从j:=1 to 8 do 又开始循环,排除 j=1,j=2 得到 (2,3)注意计算机在层里也只是走拉3(j=3)个循环然后又跳到拉i=3 这层依次类推得到(3,5),(4,2)(5,4)而在i=6 这层里计算机从j:= 1 to 8 do 都没有找到合适的位置,此时注意在i=6 这层里计算机计算机将返回到i=5 这层里,(因为用拉递归)并且释放(5,4)该位置,为什么要释放呢?因为原因很简单如果不释放的话该位置对应的斜线和水平方向会对以后的几层造成影响,让计算机误认为为false.此时的在i=5这层里 j=4才是结束,然后计算机又会从j=5到 8 开始去找合适的位置 ,如果找不到又会返回到上一层依次类推直到计算机找到一组解输出,假设在(8,3)这个位置是计算机找到的一组解,此时计算机又会从j=4到8 开始循环,如果找不到计算机就会返回上一层的即i=7这层接着上一次的跳出位置走完以后的循环,依次类推不断的返回,跳出, 求解,(即令前几个位置不变,从第8个位置变换,没有空位置的.接会返回上一层)最后返回到i=1这层里,注意此时在这层里也只是走拉j=1个循环然后计算机就又开始从j= 2 去试着找....大家有没有算过求出所有的解要走过多少个循环?我想估计也不下1000个吧.其实整个过程就是一个重复的过程(即递归)倒着想在i=7 这层里的j=1 位置即(7,1) 计算机会去试从(8,1)到(8,8)这8 个位置,而在(7,2)也同样会去试这8 个位置等等在(6,1)会试(7,1)到(7,8) 等. 这是正着考虑(1,1)这里计算机会试着从(2,1)到(2,8)这8个位置而在这8 个位置里并没有试完就有空位置 (2,3)此时计算机会在这个位置对下一层里开始试(3,1)..(3,8)依次类推,试不通的返回,接着走完上一层直到试完所有的位置!

2004-9-22 17:29
回复

220.175.12.*	5楼用Ｃ语言呀你？？？
2004-12-7 09:38 回复

61.131.58.*	6楼 4楼的咋贴个PASCAL的。。
2004-12-7 09:52 回复

assiss	7楼 4楼的已经基本上把思路都给出来了，竟然还有这么多人JJWW。真TMD人心不足蛇吞象啊。
2004-12-7 10:01 回复

61.180.237.*	8楼谁能用C语言告诉我，谢谢
2005-5-9 09:53 回复

木树树
0位粉丝

9楼

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int Judge(int *p, int j)
　　　　　　　　　　　　//判断当前棋子位置是否符合规则，是则返回1，否则返回0；
{
　　int i;
　　for(i=0;i<j;i++)
　　{
　　　 if(p[j]==p[i])　return 0;
　　　 if(abs(p[j]-p[i])==j-i)　return 0;
　　}
　　return 1;
}

int main()
{
　　　int a[8];　//a[i]表示第i行的后所在位置（a[3]=0表示第3行的后在第0列）
　　　int i=0,j=0,k=0;

　　　for(a[0]=0;a[0]<8;j=0,a[j]++)
　　　　 for(a[++j]=0;a[j]<8;j=1,a[j]++)
　　　　　 if(Judge(a,j))
　　　　　　 for(a[++j]=0;a[j]<8;j=2,a[j]++)
　　　　　　　 if(Judge(a,j))
　　　　　　　　 for(a[++j]=0;a[j]<8;j=3,a[j]++)
　　　　　　　　　 if(Judge(a,j))
　　　　　　　　　　 for(a[++j]=0;a[j]<8;j=4,a[j]++)
　　　　　　　　　　　 if(Judge(a,j))
　　　　　　　　　　　　 for(a[++j]=0;a[j]<8;j=5,a[j]++)
　　　　　　　　　　　　　 if(Judge(a,j))
　　　　　　　　　　　　　　 for(a[++j]=0;a[j]<8;j=6,a[j]++)
　　　　　　　　　　　　　　　 if(Judge(a,j))
　　　　　　　　　　　　　　　　 for(a[++j]=0;a[j]<8;a[j]++)
　　　　　　　　　　　　　　　　　 if(Judge(a,j))
　　　　　　　　　　　　　　　　　 {　for(i=0;i<8;i++) printf("%d",a[i]);
　　　　　　　　　　　　　　　　　　　printf("%3s"," ");
　　　　　　　　　　　　　　　　　　　if(!(++k%7)) printf("\n");
　　　　　　　　　　　　　　　　　 }
　　　printf("\n\n%d\n\n",k);
　　　printf("\n请按任意键结束...");
　　　getch();
　　　return 0;
}

2005-6-10 15:07
回复

203.118.142.*	10楼关键是思路!!!楼主别在JJWW的啦,是不是作业来不急交了啊...
2005-6-11 10:48 回复

59.64.38.*

11楼

#include<stdio.h>
int check(int x,int y,int a,int b) /*判断任两行的皇后是否在一斜线上*/
{
if((a-x==y-b)||(a-x==b-y))
return(0);
else return(1);
}
main()
{
int q,Q,w,W,e,E,r,R,t,T,y,Y,u,U,i,I,k;
q=1;w=2;e=3;r=4;t=5;y=6;u=7;i=8;k=0;

printf("-----------------------\n\n");
for(Q=1;Q<=8;Q++)
for(W=1;W<=8;W++)
for(E=1;E<=8;E++)
for(R=1;R<=8;R++)
for(T=1;T<=8;T++)
for(Y=1;Y<=8;Y++)
for(U=1;U<=8;U++)
for(I=1;I<=8;I++)
if(check(q,Q,w,W)&&check(q,Q,e,E)&&check(q,Q,r,R)&&check(q,Q,t,T)&&check(q,Q,y,Y)&&
check(q,Q,u,U)&&check(q,Q,i,I)&&check(w,W,e,E)&&check(w,W,r,R)&&check(w,W,t,T)&&
check(w,W,y,Y)&&check(w,W,u,U)&&check(w,W,i,I)&&check(e,E,r,R)&&check(e,E,t,T)&&
check(e,E,y,Y)&&check(e,E,u,U)&&check(e,E,i,I)&&check(r,R,t,T)&&check(r,R,y,Y)&&
check(r,R,u,U)&&check(r,R,i,I)&&check(t,T,y,Y)&&check(t,T,u,U)&&check(t,T,i,I)&&
check(y,Y,u,U)&&check(y,Y,i,I)&&check(u,U,i,I)&& /*判断任两行的皇后是否在一斜线上*/
Q!=W&&Q!=E&&Q!=R&&Q!=T&&Q!=Y&&Q!=U&&Q!=I&&W!=E&&W!=R&&W!=T&&W!=Y&&W!=U&&W!=I&&
E!=R&&E!=T&&E!=Y&&E!=U&&E!=I&&R!=T&&R!=Y&&R!=U&&R!=I&&T!=Y&&T!=U&&T!=I&&Y!=U&&
Y!=I&&U!=I) /*排除任两行的皇后在同一列上*/
{ printf("%d%d%d%d%d%d%d%d\t",Q,W,E,R,T,Y,U,I); k++;}

printf("\n\nba huang hou de jie you %d ge",k);
printf("\n-------------------------\n\n");

}

2005-6-22 14:18
回复

59.41.45.*	12楼能不能在界面上用图形形式显示它的各种布局的，我也想要一个。。。。
2005-6-30 13:41 回复

210.31.69.*	13楼恩！我也想要！用递归实现，用图形形式来显示结果！帮帮忙哈！谢了！
2005-7-4 20:19 回复

222.28.136.*	14楼 hao
2005-7-5 10:25 回复

61.173.92.*	15楼有没有人能讲得详细点啊！看不懂啊！
2005-8-23 15:23 回复

219.131.172.*	16楼我的邮箱是：zshzpk@163.com
2005-11-16 11:38 回复

zgr0629
0位粉丝

17楼

这里我是用的递归
应该看的懂吧？

/*Program Queen*/
/*Made by ZGR*/

int pp=0;
int way[100];

print(n){
int i;
pp++;
for (i=0;i<=n;i++) printf("%d",way[i]+1);
printf("---%d\n",pp);
}

ifput(int x,int y){
int i,put;
put=1;
for (i=0;i<=y;i++) if(((abs(way[i]-x)==abs(i-y))&&(i!=y))||((way[i]==x)&&(y!=i))) put=0;
return(put);
}

queen(int y,int n){
int x,put;
for(x=0;x<=n;x++){
put=ifput(x,y);
if(put==1){
way[y]=x;
if(y==n) print(n);
else queen(y+1,n);
}
}
}

main(){
int n;
clrscr();
printf("Queen=");
scanf("%d",&n);
queen(0,n-1);
}

2005-11-16 14:01
回复

zgr0629 0位粉丝	18楼 Queen=8的时候好像是有92组解的吧我记不太清楚了
2005-11-16 14:03 回复

219.229.123.*	19楼把 clrscr(); 删除掉即为正确解
2005-12-12 13:15 回复

219.229.123.*

20楼

#include <stdio.h>
#include <math.h>
int pp=0;
int way[100];

print(n){
int i;
pp++;
for (i=0;i<=n;i++) printf("%d",way[i]+1);
printf("---%d\n",pp);
}

ifput(int x,int y){
int i,put;
put=1;
for (i=0;i<=y;i++) if(((abs(way[i]-x)==abs(i-y))&&(i!=y))||((way[i]==x)&&(y!=i))) put=0;
return(put);
}

queen(int y,int n){
int x,put;
for(x=0;x<=n;x++){
put=ifput(x,y);
if(put==1){
way[y]=x;
if(y==n) print(n);
else queen(y+1,n);
}
}
}

main(){
int n;

printf("Queen=");
scanf("%d",&n);
queen(0,n-1);
}

2005-12-12 13:19
回复

220.175.119.*	21楼有没有人会N皇后的C语言编程啊<好象和8皇后不一样
2005-12-18 10:29 回复

220.175.119.*	22楼知道的话可不可以发到我的邮箱LIUSHIMIN_163@163.COM
2005-12-18 10:31 回复

218.75.236.*	23楼我要的是思路。。。谁有什么好思路的吗？能不能说下
2005-12-20 13:14 回复

221.217.172.*	24楼强！！！！！！！！！！！
2005-12-20 23:28 回复

222.39.116.*

25楼

#include <stdio.h>
#include <stdlib.h>

int xie(int a,int b,int c,int d,int e,int f,int g,int h
{
if(b==a+1||b==a-1||c==a+2||c==a-2||d==a+3||d==a-3||e==a+4||e==a-4
||f==a+5||f==a-5||g==a+6||g==a-6||h==a+7||h==a-7
||c==b+1||c==b-1||d==b+2||d==b-2||e==b+3||e==b-3
||f==b+4||f==b-4||g==b+5||g==b-5||h==b+6||h==b-6
||d==c+1||d==c-1||e==c+2||e==c-2
||f==c+3||f==c-3||g==c+4||g==c-4||h==c+5||h==c-5
||e==d+1||e==d-1
||f==d+2||f==d-2||g==d+3||g==d-3||h==d+4||h==d-4
||f==e+1||f==e-1||g==e+2||g==e-2||h==e+3||h==e-3
||g==f+1||g==f-1||h==f+2||h==f-2
||h==g+1||h==g-1)

return(0);
else
return(1);
}
int main(void)
{
int A,B,C,D,E,F,G,H,s=0;

printf("-------------------------\n");
for(A=1;A<=8;A++)
for(B=1;B<=8;B++)
for(C=1;C<=8;C++)
for(D=1;D<=8;D++)
for(E=1;E<=8;E++)
for(F=1;F<=8;F++)
for(G=1;G<=8;G++)
for(H=1;H<=8;H++)
{
if(A!=B&&A!=C&&A!=D&&A!=E&&A!=F&&A!=G&&A!=H
&&B!=C&&B!=D&&B!=E&&B!=F&&B!=G&&B!=H
&&C!=D&&C!=E&&C!=F&&C!=G&&C!=H
&&D!=E&&D!=F&&D!=G&&D!=H
&&E!=F&&E!=G&&E!=H
&&F!=G&&F!=H
&&G!=H
&&A+B+C+D+E+F+G+H==36
&&xie(A,B,C,D,E,F,G,H))
{
printf("%d%d%d%d%d%d%d%d\t",A,B,C,D,E,F,G,H);
s++;
}
}
printf("\n-------------------------");
printf("\nyou %d zhong pai lie fang fa\n",s);

system("PAUSE");
}

2005-12-22 13:13
回复

222.240.144.*	26楼我也是学计算机的，真的太佩服你们了以后我经常来看看吧
2005-12-27 15:53 回复

61.178.57.*	27楼告诉你们要把程序写的象拉屎一样，那是艺术！！！！
2005-12-28 16:12 回复

221.123.71.*	28楼有这么多呀!大开眼界呀！
2005-12-28 18:39 回复

218.104.97.*

29楼

#ifndef _QUEENBOARD_H_
#define _QUEENBOARD_H_

const int BOARDSIZE = 8;

using namespace std;

class Queenboard {

private:
bool board[BOARDSIZE][BOARDSIZE];

public:
Queenboard();
bool is_space_under_attack(int, int) const;
void occupy_space(int, int);
void clear_column(int);

friend ostream& operator<<(ostream& out, const Queenboard& cb);
};

Queenboard::Queenboard() {
// Initialize the board to contain zero queens.
for (int row = 0; row < BOARDSIZE; row++) {
for (int col = 0; col < BOARDSIZE; col++) {
board[row][col] = false;
}
}
}

ostream& operator<<(ostream& out, const Queenboard& cb) {

// output the board
for (int row = 0; row < BOARDSIZE; row++) {

out << "---------------------------------" << endl;
for (int col = 0; col < BOARDSIZE; col++) {
out << "|";
if ( cb.board[row][col]) {
out << " Q ";
}
else {
out << " ";
}
}
out << "|" << endl;
}
out << "---------------------------------" << endl;
return out;
}

void Queenboard::clear_column(int col) {

if (col >= BOARDSIZE || col < 0) {
throw out_of_range("Queenboard::clear_column()");
}

for (int row = 0; row < BOARDSIZE; row++) {
board[row][col] = false;
}
}

void Queenboard::occupy_space(int row, int col) {

if (col >= BOARDSIZE || col < 0 ||
row >= BOARDSIZE || row < 0) {
throw out_of_range("Queenboard::occupy_space()");
}

// places a queen on the board
board[row][col] = true;
}

bool Queenboard::is_space_under_attack(int row, int col) const {

if (col >= BOARDSIZE || col < 0 ||
row >= BOARDSIZE || row < 0) {
throw out_of_range("Queenboard::is_space_under_attack()");
}

// check to the left
int i = col - 1;
while (i >= 0) {
if (board[row][i]) return true;
i--;
}

// check diagonal up and left
int j = row - 1;
int k = col - 1;
while (j >= 0 && k >= 0) {
if (board[j][k]) return true;
j--; k--;
}

// check diagonal down and left
j = row + 1;
k = col - 1;
while (j < BOARDSIZE && k >= 0) {
if (board[j][k]) return true;
j++; k--;
}

return false;
}

#endif

#include <iostream>
#include <cstdlib>
#include <stdexcept>

#include "Queenboard.h"

using namespace std;

bool place_queens(Queenboard& qb, int col);

int main(int argc, char* argv[]) {

try {

Queenboard qb;
if (! place_queens(qb, 0)) {
cout << "No solution found.\n";
}
return EXIT_SUCCESS;
}
catch (exception& e) {
cerr << e.what() << "\n";
}
catch (...) {
cerr << "Unknown exception caught.\n";
}

return EXIT_FAILURE;
}

bool place_queens(Queenboard& qb, int col) {

bool inserted = false;
for (int row = 0; row < BOARDSIZE; row++) {

if (! qb.is_space_under_attack(row, col)) {

// insert a queen
qb.occupy_space(row, col);
inserted = true;

if (col == BOARDSIZE - 1) {
// solution found!
cout << qb << "\n";
return true;

}
else {
// place a queen in the next column
if (place_queens(qb, col + 1)) {
return true;
}
else {
inserted = false;
}
}
}
}

if (! inserted) {
// backtrack to previous column
qb.clear_column(col - 1);
return false;
}
}

2005-12-29 23:22
回复

61.143.143.*

30楼

刚刚看了9楼的程序,和我的思路一模一样.我用的是Turbo C

#include "stdio.h"
#include "math.h"

int y[9],x[9]={0,1,2,3,4,5,6,7,8};

void EightQueens();
void output();

void main()
{
EightQueens();
getch();
}

void output()
{
int i;
for (i=1;i<=8 ;i++ )
printf("x[%d]=%d,y[%d]=%d \n",i,i,i,y[i]);
printf("\n");
}

int Judge(int i)/*判断棋子的位置是否适当*/
{
int r;float k;
for (r=1;r<i;r++)
{
if (y[r]==y[i]) return(0);/*不能在同一竖行*/
if (abs(y[i]-y[r])==(i-r)) return(0);/*不能在同一斜行(斜率不能为正负1)*/
}
return(1);
}

void EightQueens()
{
for (y[1]=1;y[1]<=8 ;y[1]++ )
{
for (y[2]=1;y[2]<=8 ;y[2]++ )
{if (Judge(2)==0) continue;
for (y[3]=1;y[3]<=8 ;y[3]++ )
{if (Judge(3)==0) continue;
for (y[4]=1;y[4]<=8 ;y[4]++ )
{if (Judge(4)==0) continue;
for (y[5]=1;y[5]<=8 ;y[5]++ )
{if (Judge(5)==0) continue;
for (y[6]=1;y[6]<=8 ;y[6]++ )
{if (Judge(6)==0) continue;
for (y[7]=1;y[7]<=8 ;y[7]++ )
{if (Judge(7)==0) continue;
for (y[8]=1;y[8]<=8 ;y[8]++ )
{if (Judge(8)==0) continue;
output();
}
}
}
}
}
}
}
}
}

2005-12-31 22:20
回复



内　容:
用户名:
验证码:	请点击后输入验证码，加入会员后本吧发贴免验证码。

八皇后问题

发表回复