8 queens


Results 1 to 8 of 8

Thread: 8 queens

  1. #1
    Join Date
    Jul 2002
    Location
    New York
    Posts
    99

    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
    "We all wont be safe until nerd persecution ends"
    - Gilbert Love

  2. #2
    Join Date
    Aug 2001
    Posts
    114
    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.
    UM

  3. #3
    Join Date
    Apr 2001
    Location
    Omaha, NE.
    Posts
    587

    Re: 8 queens

    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.
    "I am the EPITOME of FRUGALITY, the KING OF CHEAPNESS, the TIGHTEST of the TIGHTWADS, the MASTER-BLASTER of PENNY PINCHING, the BISHOP of UNDER-BUDGETING, the CARDINAL of COST-CUTTING, I AM THE MASTER MISER!!!."

    -Jim Sears

    GAIM ID: cmmiller1973

  4. #4
    Join Date
    Feb 2003
    Posts
    44

    woo:)

    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";

  5. #5
    Join Date
    Feb 2003
    Posts
    44
    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.

  6. #6
    Join Date
    Jan 2000
    Location
    Houston, TX, USA
    Posts
    9,994
    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
    We love Sensei!!
    A 1:1 ratio of Arby's sauce to Horsey sauce must be maintained.
    Like Linux? Want to like it more? Try Debian
    Best. (Python.) IRC bot. ever.
    Geekology

  7. #7
    Join Date
    Jul 2002
    Location
    New York
    Posts
    99
    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;
    }
    "We all wont be safe until nerd persecution ends"
    - Gilbert Love

  8. #8
    Join Date
    Oct 2002
    Location
    NY
    Posts
    39
    please, use the [ code ] tag... It's so much easeyer to read that way.
    Madmen often turn out to be the prophets

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •