مسئله n وزیر

سلام دوستان.
من دنبال الگریتم مسئله n وزیر میگردم. چون به نظر من پیچیده میاد دنبال یه توضیح ویه کدساده از این برنامه میگردم تا بتونم خودم بنویسمش.
در ضمن باید به روش عقبگرد هم باشه.

سلام
این کد برای 8وزیره
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
و این:

کد:

---

// eight queens puzzle in C++
// written by Tim  Budd, Oregon State University, 1996
//
# include <iostream.h>
# define bool int // not all compilers yet support booleans
class queen {
public:
  // constructor
 queen (int, queen *);
 
  // find and print solutions
 bool findSolution();
 bool advance();
 void print();
private:
  // data fields
 int row;
 const int column;
 queen * neighbor;
 
  // internal method
 bool canAttack (int, int);
};
queen::queen(int col, queen * ngh)
 : column(col), neighbor(ngh)
{
 row = 1;
}
bool queen::canAttack (int testRow, int testColumn)
{
  // test rows
 if (row == testRow)
  return true;
 
  // test diagonals
 int columnDifference = testColumn - column;
 if ((row + columnDifference == testRow) ||
  (row - columnDifference == testRow))
  return true;
 
  // try neighbor
 return neighbor && neighbor->canAttack(testRow, testColumn);
}
bool queen::findSolution()
{
 // test position against neighbors
        // The while loop is not necessary since advance() always
        // moves the queen to the next "safe" position.
        // [Jerry Roth, Gonzaga University, Feb. 2000]
 //while (neighbor && neighbor->canAttack (row, column))
 if (neighbor && neighbor->canAttack (row, column))
  if (! advance())
  return false;
 
  // found a solution
 return true;
}
bool queen::advance()
{
 if (row < 8) {
  row++;
  return findSolution();
  }
 
 if (neighbor && ! neighbor->advance())
  return false;
 
 row = 1;
 return findSolution();
}
void queen::print()
{
 if (neighbor)
  neighbor->print();
 cout << "column " << column << " row " << row << '\n';
}
int main() {
 queen * lastQueen = 0;
 
 for (int i = 1; i <= 8; i++) {
  lastQueen = new queen(i, lastQueen);
  if (! lastQueen->findSolution())
  cout << "no solution\n";
  }
 
 lastQueen->print();
}

---

این سایتم جالبه:
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

از کمکتون ممنون.
ولی میشه این کد رو با vcpp هم قرار بدین.

سلام
این کد وزیر ها رو سطر به سطر جا به جا میکنه
واسه اینکه بخوایم ستون به ستون تست کنه چی کار باد کنیم؟؟؟

نقل قول:

---

نوشته شده توسط farshidshd [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

سلام
این کد وزیر ها رو سطر به سطر جا به جا میکنه
واسه اینکه بخوایم ستون به ستون تست کنه چی کار باد کنیم؟؟؟

---

سلام
منظورتون چیه؟
ما تو مسئله nوزیر توی هر سطر تنها می تونیم یه وزیر داشته باشیم
پس فقط اونا رو تو ستونا جابه جا می کنیم:20:

کدی که شما نوشتین توش با کلاس ها کار شده ولی من دنبال یه کد با روش عقب گرد میگردم که هم ساده تر باشه و هم منم بتونم یه چیزلیی لزش بفهمم.
ممنون.

نقل قول:

---

نوشته شده توسط فاطـمه [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

سلام
منظورتون چیه؟
ما تو مسئله nوزیر توی هر سطر تنها می تونیم یه وزیر داشته باشیم
پس فقط اونا رو تو ستونا جابه جا می کنیم:20:

---

وزیر ها سطر به سطر جا به جا میشن
من میخوام ستون به ستون تست کنه و جابه جا کنه
یعنی به جای اینکه توی سطر یه وزیر داشته باشیم
توی ستون یه وزیر باشه فقط

سلام اینم یکم ساده تر

کد:

---

#include <stdio.h> intis_safe(int rows[8], int x, int y)  {    int i;    for (i=1; i <= y; ++i) {      if (rows[y-i] == x || rows[y-i] == x-i || rows[y-i] == x+i)            return 0;    }    return 1;} voidputboard(int rows[8])  {    static int s = 0;    int x, y;    printf("\nSolution #%d:\n---------------------------------\n", ++s);    for (y=0; y < 8; ++y) {        for (x=0; x < 8; ++x)            printf(x == rows[y] ? "| Q " : "|  ");        printf("|\n---------------------------------\n");    }} voideight_queens_helper(int rows[8], int y){    int x;    for (x=0; x < 8; ++x) {        if (is_safe(rows, x, y)) {            rows[y] = x;            if (y == 7)              putboard(rows);            else              eight_queens_helper(rows, y+1);        }    }} intmain(){    int rows[8];    eight_queens_helper(rows, 0);    return 0;}

---

[PHP]#include <stdio.h> intis_safe(int rows[8], int x, int y) { int i; for (i=1; i <= y; ++i) { if (rows[y-i] == x || rows[y-i] == x-i || rows[y-i] == x+i) return 0; } return 1;} voidputboard(int rows[8]) { static int s = 0; int x, y; printf("\nSolution #%d:\n---------------------------------\n", ++s); for (y=0; y < 8; ++y) { for (x=0; x < 8; ++x) printf(x == rows[y] ? "| Q " : "| "); printf("|\n---------------------------------\n"); }} voideight_queens_helper(int rows[8], int y){ int x; for (x=0; x < 8; ++x) { if (is_safe(rows, x, y)) { rows[y] = x; if (y == 7) putboard(rows); else eight_queens_helper(rows, y+1); } }} intmain(){ int rows[8]; eight_queens_helper(rows, 0); return 0;}[/PHP]


این چیه فاطمه؟؟×!!

چرا این جوری شده؟!

کد:

---

#include <stdio.h>
 
int
is_safe(int rows[8], int x, int y) 
{
    int i;
 
    for (i=1; i <= y; ++i) {
      if (rows[y-i] == x || rows[y-i] == x-i || rows[y-i] == x+i)
            return 0;
    }
 
    return 1;
}
 
void
putboard(int rows[8]) 
{
    static int s = 0;
    int x, y;
 
    printf("\nSolution #%d:\n---------------------------------\n", ++s);
    for (y=0; y < 8; ++y) {
        for (x=0; x < 8; ++x)
            printf(x == rows[y] ? "| Q " : "|  ");
        printf("|\n---------------------------------\n");
    }
}
 
void
eight_queens_helper(int rows[8], int y)
{
    int x;
 
    for (x=0; x < 8; ++x) {
        if (is_safe(rows, x, y)) {
            rows[y] = x;
            if (y == 7)
              putboard(rows);
            else
              eight_queens_helper(rows, y+1);
        }
    }
}
 
int
main()
{
    int rows[8];
 
    eight_queens_helper(rows, 0);
 
    return 0;
}

---

این الان ستونی جا به جا میکنه؟؟؟
این کد رو خودت دادی بهم اجراش کن
متوجه میشی که سطری جا به جا میکنه
من میخوام همین ستونی جابه جا بشه
یعنی تو هر ستون یه وزیر که همدیگر رو گارد نکنه...

کد:

---

#include<iostream.h>
#include<conio.h>


void place(int,int,int [][8],int [][8]);
void print(int,int,int [][8],int [][8]);


int main( )
{
clrscr();
int const k=8;
int p[k][k];
int placed[k][k];

int a,b;
for(a=1;a<=8;a++)
  {for(b=1;b<=8;b++)
      {p[a][b]=1;
        placed[a][b]=0;
      }
  }

for(a=1;a<=8;a++)
  { for(b=1;b<=8;b++)
        {
        place(a,b,p,placed);
        print(a,b,p,placed);
        }
  }

getch( );
return(0);

}


void place(int i,int j,int p[][8],int placed[][8])
{
placed[i][j]=1;
int a,b,k;

for(k=1;k<=8;k++)
    {  p[i][k]=0;
      p[k][j]=0;
      if(k+i<=8 && k+j<=8) {p[k+i][k+j]=0;}
      if(k+i<=8 && j-k>=1) {p[k+i][j-k]=0;}
      if(i-k>=1 && k+j<=8) {p[i-k][k+j]=0;}
      if(i-k>=1 && j-k>=1) {p[i-k][j-k]=0;}
    }
for(a=1;a<=8;a++)
  { for(b=1;b<=8;b++)
        { if(p[a][b]==1) place(a,b,p,placed);
        }
  }

}



void print(int i,int j,int p[][8],int placed[][8])
{
int a,b;
int c=0;

for(a=1;a<=8;a++)
    {for(b=1;b<=8;b++)
        {if(placed[a][b]==0) cout<<"=";
          if(placed[a][b]==1)
            { c++;          cout<<"";
            }
        }cout<<"\n";
    }

if(c!=8)cout<<"could not place all 8 vazir"
            <<"for the start home("<<i<<","<<j
            <<")!press any key to continue:\n\n\n";
if(c==8)
  {cout<<"****all 8 vazir placed with starthome("<<i<<","
        <<j<<")!!\n\n\n";
  }


for(a=1;a<=8;a++)
  { for(b=1;b<=8;b++)
        { p[a][b]=1;
          placed[a][b]=0;
        }
  }

getch( );
return;
}

---

خب نهایتا جای I, j عوض می شه تو آرایه
چه لزومی داره این کار رو بکنید؟

نقل قول:

---

نوشته شده توسط فاطـمه [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

خب نهایتا جای I, j عوض می شه تو آرایه
چه لزومی داره این کار رو بکنید؟

---

استاد خواسته بود
ممنونم
درستش کردم

in proje 8 vazer baray fatemeh and farshid
//gives a start home adress & cheks if 8 vazir could be placed by that start home.
#include<iostream.h>
#include<conio.h>

void place(int,int,int [][8],int [][8]);
void print(int,int,int [][8],int [][8]);

int main( )
{
clrscr( );
int const k=8;
int p[k][k];
int placed[k][k];
int a,b;
for(a=1;a<=8;a++)
{for(b=1;b<=8;b++)
{p[a][b]=1;
placed[a][b]=0;
}
}
for(a=1;a<=8;a++)
{ for(b=1;b<=8;b++)
{
place(a,b,p,placed);
print(a,b,p,placed);
}
}
getch( );
return(0);
}

void place(int i,int j,int p[][8],int placed[][8])
{
placed[i][j]=1;
int a,b,k;
for(k=1;k<=8;k++)
{ p[i][k]=0;
p[k][j]=0;
if(k+i<=8 && k+j<=8) {p[k+i][k+j]=0;}
if(k+i<=8 && j-k>=1) {p[k+i][j-k]=0;}
if(i-k>=1 && k+j<=8) {p[i-k][k+j]=0;}
if(i-k>=1 && j-k>=1) {p[i-k][j-k]=0;}
}
for(a=1;a<=8;a++)
{ for(b=1;b<=8;b++)
{ if(p[a][b]==1) place(a,b,p,placed);
}
}
}

void print(int i,int j,int p[][8],int placed[][8])
{
int a,b;
int c=0;
for(a=1;a<=8;a++)
{for(b=1;b<=8;b++)
{if(placed[a][b]==0) cout<<"_";
if(placed[a][b]==1)
{ c++; cout<<"v";
}
}cout<<"\n";
}
if(c!=8)cout<<"could not place all 8 vazir"
<<"for the start home("<<i<<","<<j
<<")!press any key to continue:\n\n\n";
if(c==8)
{cout<<"****all 8 vazir placed with starthome("<<i<<","
<<j<<")!****\n\n\n";
}

for(a=1;a<=8;a++)
{ for(b=1;b<=8;b++)
{ p[a][b]=1;
placed[a][b]=0;
}
}
getch( );
}

age on moshkel dareh pas az in poroje estefadeh koned
#include <iostream.h>
#include <conio.h>
#include <_defs.h>
int board[8][8]={0};
int value[8][8]={
{2,3,4,4,4,4,3,2},
{3,4,6,6,6,6,4,3},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{3,4,6,6,6,6,4,3},
{2,3,4,4,4,4,3,2}};
int row[8]= {-2,-2,-1,1,2,2,1,-1};
int col[]={-1 , 1 , 2 , 2 , 1 , -1 , -2 , -2 };
int satr,soton,count=0,min=8;
//************************************************** ***
void getfirstvalue();
void print();
void changevalue();
int move();
//************************************************** ***
int main()
{
getfirstvalue();
++count;
print();
while(move())
{
getch();
++count;
print();
}
getch();
return 0;
}
//************************************************** ***
void getfirstvalue()
{
cout<<"enter the satr and soton for start :\n";
do{
cout<<"enter satr : ";
cin>>satr;
}while(satr > 8 || satr < 1);
do{
cout<<"enter soton : ";
cin>>soton;
}while(soton > 8 || soton < 1);
board[(satr-1)][(soton-1)]=1;
value[satr-1][soton-1]=0;
changevalue();
}
//************************************************** ***
void print()
{
int i,j;
cout<<"satr : "<<satr<<"\t\tsoton"<<soton<<"\n";
for(i=0;i<8;i++){
for(j=0;j<8;j++){
cout<<" "<<board[i][j]<<" ";
}
cout<<"\n";
}
cout<<"-------------------------------------------------\n";
for(i=0;i<8;i++){
for(j=0;j<8;j++)
cout<<" "<<value[i][j]<<" ";
cout<<"\n";
}
}
//************************************************** ***
void changevalue()
{
int number,x[8],y[8];
for(number = 0; number < 8 ; number++){
x[number] = satr + row[number];
y[number] = soton + col[number];
if(x[number] > 0 && x[number] <= 8 && y[number] > 0 &&
y[number] <= 8 && board[(x[number]-1)][(y[number]-1)] != 1 )
value[x[number]-1][y[number]-1]--;
}
}
//************************************************** ***
int move()
{
int i,x[8],y[8],z,t;
min=8;
for(i=0;i<8;i++){
if(row[i]<-2)
row[i]+=1;
x[i]=satr+row[i];
y[i]=soton+col[i];
if( x[i] > 0 && x[i] <= 8 && y[i] > 0 && y[i] <= 8 &&
board[x[i]-1][y[i]-1] != 1)
if(value[x[i]-1][y[i]-1] <=min){
min=value[x[i]-1][y[i]-1];
z=x[i],t=y[i];
}
}
if(min > 7 || min < -1)
return 0;
if(z > 8 || z <= 0 || t > 8 || t <= 0 || board[z-1][t-1])
return 0;
satr=z;
soton=t;
board[z-1][t-1]=1;
value[z-1][t-1]=0;
changevalue();
return 1;
}

سلام
من تابع اون رو توی c# نوشتم
ب

کد:

---

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

namespace nVazir
{
    class Class1
    {
        private int n, i;
        private int []col = new int[11];
        public int[] a = new int[11];
        //---------------------------------------
        public Class1(int temp)
        {
            n = temp;
        }
        //---------------------------------------
        public void perform()
        {
            for (i = 0; i < n; i++)
            {
                queens();
            }
        }
        //---------------------------------------
        public bool promising()
        {
            int k;
            bool flag = true;
            k = 1;
            while ( (k < i) && flag )
            {
                if ( (col[i] == col[k]) || (Math.Abs(col[i] - col[k]) == (i - k)) )
                    flag = false;
                k++;
            }
            return flag;
        }
        public void queens()
        {
            int j;
            if (promising())
            {
                if (i == n)
                {

                    for (int m = 1; m <= n; m++)
                    {
                        a[i] = col[i];
                    }
                }
                else
                {

                    for (j = 1; j <= n; j++)
                    {
                        col[i + 1] = j;
                        //queens(i + 1);
                        i++;
                        queens();
                    }
                }
            }
        }
        //---------------------------------------
    }
}

---

کدوم یکی ابتدایی تره و میشه به Nوزیر تبدیلش کرد