8 queens

Hello,

For all of you who havent heard of the 8 queens problem, it is when you place 8 queens on the board where none of them are threating each other.

I am just wondering if you guys think this is a difficult problem to resolve in a C/C++ program. I know there are answers all over the net, but im trying to figure it out on my own. I have come up with a recursive solution and it seems ok. I am having diffuculty implementing it though. I have spent about an hour and a half.

My experience is as follows....
Did nothing in college, got some fundamentals, but nothing real. In the last year and a half I have been working real hard to componsate. I
So I say I have 2 years of educational experience. I guess this is more a problem solving than a programming question, In which I have more than 2 years experience. Just want to know what you guys think of the difficuly of this problem and others like it. Also where to find others like it.

spacedog

Without much thought, there seems to be a fairly straightforward solution.

I definitely think it would take me more than a couple of hours to implement though.

Good luck with it. I'd be interested in seeing your recursive solution.

Quote:

---

Originally posted by spacedog
My experience is as follows....
Did nothing in college, got some fundamentals, but nothing real. In the last year and a half I have been working real hard to componsate. I
So I say I have 2 years of educational experience. I guess this is more a problem solving than a programming question, In which I have more than 2 years experience. Just want to know what you guys think of the difficuly of this problem and others like it. Also where to find others like it.

spacedog

---

My problem too...I'm finishing a degree in programming later this year, and I haven't felt like I used it, and when I try to get a programming job, no luck.

So, I'm trying to program everyday for at least a few hours so it can become 2nd nature.

Thank god for Linux, cause I really like programming on it.

Also, I like throwing out ideas on here as well.

that was fun:)
This isn't the optimal way. Just the quickest (to code) brute force way. Given that the problem is pretty small (and that I forget a @(#*@ perl command :P ) it really isn't a concern.

I have some hard ones...lemme see if i can hunt them down for you. They came from some consulting company. You had to code a solution to one of their problems and turn it in with your resume.



#!/usr/bin/perl
use strict;
my @board;
my ($h,$i,$j,$k);
my $queen;
my $list;

# ** remember, arrays start with 0..so bottom left is 0,0 and top right is 7,7 **


sub check{ #returns 1 if found
my ($x,$y) = @_;
my $i;
my $spacer;
my $found=0;

for($i=0;$i<8;$i++){ # check the XY planes at the same time
$found = ($board[$x][$i])?1:$found;
$found = ($board[$i][$y])?1:$found;
last if $found;
}


if( ($y <7) && ($found == 0) ){ # check upper diag's if its a possibility
$spacer=1;
for($i=$y+1;$i<=8;$i++){
$found = ($board[$x+$spacer][$i])?1:$found;
$found = ($board[$x-$spacer][$i])?1:$found;
$spacer++;
last if $found;
} # end upper diag for

} # end of y<7




if( ($y >0) && ($found ==0) ){ # check lower diag's if its a possibility
$spacer =1;
for($i=$y-1;$i>=0;$i--){
$found = ($board[$x+$spacer][$i])?1:$found;
$found = ($board[$x-$spacer][$i])?1:$found;
$spacer++;
last if $found;
} # end lower diag for
} # end y > 0


return($found);
} # end check


sub init{
my ($x,$y)=0;
# initialize the board
for($x=0;$x<8;$x++){
for($y=0;$y<8;$y++){
$board[$x][$y] =0;
} #end of y
}#end of x
} # end init


#run through the board starting at the lower left
# h and i control the initial move.
for($h=0;$h<8;$h++){
for($i=0;$i<8;$i++){
print "init $h $i: ";
&init;
$board[$h][$i]=1;
$queen=1;
$list ="$h $i\n";
for($j=0;$j<8;$j++){
for($k=0;$k<8;$k++){
next if &check($j,$k);
$board[$j][$k]=1;
$queen+=1;
$list .="$j $k\n";
print "$queen ";
if ($queen == 8){
die "$list";
} # end queen

} # end k
} # end j
print "\n";
}#end i
}# end h
print "whoops...didn't find jack.\n";

ok...
I found the problems, and I also found you can ramp up the difficulty on the chess program.

Here are a couple problems:
http://www.itasoftware.com/careers/programmers.php


Also, I noticed you decided to use recursion in your program, but the problem you described said find 'a' solution.


I took the easy way out:P Brute forcing one solution is easier then finding ALL solutions.

But if you can find all solutions,
why not try to do the same thing with "knights and queens" on the itasoftware page.

http://codeexamples.org/cgi-bin/c2h/...pe=HTML-detail

All n-queens solutions (not just 8), in Scheme. And way shorter (and more legible) than the Perl version :)

ok it wasent to bad, the night I posted this i went to a bar and walked through the algorithm with a few pints and friends and a chess board. The algorithm is simple... I hope my explanation is ok.

given queen 0,0
go column by column starting from row zero of each column and attempt to place the queen.
when you reach the last row of the column and cannot successfully place the queen, remove that queen go to the previos column and move that queen up to the next safe row. if you keep doing this you will come with a solution. My program came up with 92 solutions

here is the code, it is sloppy, but if you cut and past it will work fine. Also the recursion is pretty straight forward.

#include <stdio.h>

class Queen{
public:
void setColumn(int col) {column = col;};
void setRow(int r){row = r;};
int getRow(){return row;};
int getColumn(){return column;};

int isSafe(Queen queens[]);
private:
int column;
int row;
};


int Queen::isSafe(Queen queens[]){
//dont look at the whole board. Just look at al columns left
int q_placed = column;
int i;
int q_R, q_C;
int x, y;

// printf("Try to place queen at column and row: %i, %i\n", column, row);

if(q_placed==0) //only on case of first queen
return 1;//return true

//three cases return false
if(column < 0 || column >7)
return -1; //error case

//check if anyone is in the same row oinly check untill self
for(i=0;i<column;i++){
//&& dont compare to self
if(row == queens[i].getRow() && column != queens[i].getColumn()){
// printf("%i,%i is in the row of %i,%i\n", column, row, queens[i].getColumn(), queens[i].getRow());
return 0;
}
}


//check if we are in the same diagnol
for(i=0;i<column;i++){
//walk up the right diagnol stop when q_c=8
for(q_R = queens[i].getRow(),q_C = queens[i].getColumn();q_R < 8 && q_C < 8;q_C++, q_R++){
if(row == q_R && column == q_C){
// printf("%i,%i is in the ++ diagnol of %i,%i\n", column, row, queens[i].getColumn(), queens[i].getRow());
return 0;
}
}
//walk down right diagnol
for(q_R = queens[i].getRow(),q_C = queens[i].getColumn();q_C >=0 && q_R >=0;q_C--, q_R--){
if(row == q_R && column == q_C){
//printf("%i,%i is in the -- diagnol of %i,%i\n", column, row, queens[i].getColumn(), queens[i].getRow());
return 0;
}
}
//walk up left diagnol
for(q_R = queens[i].getRow(),q_C = queens[i].getColumn();q_C >=0 && q_R <8;q_C--, q_R++){
if(row == q_R && column == q_C){
// printf("%i,%i is in the -+ diagnol of %i,%i\n", column, row, queens[i].getColumn(), queens[i].getRow());
return 0;
}
}
//walk up left diagnol
for(q_R = queens[i].getRow(),q_C = queens[i].getColumn(); q_R >=0 && q_C <8;q_C++, q_R--){
if(row == q_R && column == q_C){
// printf("%i,%i is in the +- diagnol of %i,%i\n", column, row, queens[i].getColumn(), queens[i].getRow());
return 0;
}
}
}
return 1;
}

int placeQueen(Queen queens[], int c, int r);


static int count=0;

int main(){

Queen queens[8];

//Initialize queens
for(int c=0;c<8;c++){
queens[c].setColumn(c);
queens[c].setRow(0);
}

if(placeQueen(queens, 0, 0)) //call function
printf("Count: %i\n", count);

}


int placeQueen(Queen queens[], int c, int r){
//each queen is in possesion of their own column "c", so "c" refers to the actual queen
//and its column
//printf("column - %d and row %d\n", c, r);

while(1){
while(queens[c].getRow()<8){
if(queens[c].isSafe(queens)){
if(c==7){//if the 7th and last queen is safe print results
for(int i=0;i<8;i++)
printf("Finished: %d,%d\n", queens[i].getColumn(), queens[i].getRow());
printf("-----------------------\n");
////////////////////////////////////////////////////////////////////////
//ok. we got a solution to 8 queens now move last queen to the next peice and continue
queens[c].setRow(queens[c].getRow()+1);
count++;//counting purposes
c=6;//since we are passing (placeQueen(queens, c+1, 0)) I have to make sure c <8

}//end if(c==7) move to the next cloumn
return (placeQueen(queens, c+1, 0)); //recursion
}//cant safely place the queen in that row, try the next
else
queens[c].setRow(queens[c].getRow()+1);
}//end while

if(queens[0].getRow() > 7)
return 1;//return from function here
//OK the while(queens[c].getRow()<8) failed, now set the row to zero and
//work on the previos column
queens[c].setRow(0);
c--;
queens[c].setRow(queens[c].getRow()+1);

}
return 0;
}

please, use the [ code ] tag... It's so much easeyer to read that way.