The eight queens problem

Discussion in 'C++' started by jblazi, Aug 30, 2004.

  1. jblazi

    jblazi Guest

    In the book "Algortims and Data Structures" by Wirth there is a program in
    Pascal to compute all 92 solutions of the above mentioned problem. I tried
    to translate his program into C++, the only small problem being that he
    uses array with a starting index other than zero. Here is my solution:


    // Pascal like array with arbitrary indeces
    class Array {
    int *datum,start_index,end_index;

    public:
    Array(int s_index,int e_index) {start_index = s_index; end_index = e_index;datum = new int(end_index-start_index+1);}
    #include "stdafx.h"
    int& operator [](int i) {return *(datum-start_index+i);}
    };

    // x : row of queen in the i-th coloumn
    // a : no queen is in the the i-th row
    // b : no queen is in the the i-th diagonal
    // which has positive slope
    // c : no queen is in the the i-th diagonal
    // which has negative slope


    Array a(1,8),x(1,8),b(2,16),c(-7,7);

    void print_queens()
    {
    static int cnt = 0;

    printf("%2d: ",++cnt);
    for(int k=1;k<=8;k++)
    printf("%4d",x[k]);
    printf("\n");
    }

    void set_queen(int i)
    {
    int j;
    for(j=1;j<=8;j++)
    if (a[j] && b[i+j] && c[i-j]) {
    x = j;
    a[j] = b[i+j] = c[i-j] = 0;
    if (i < 8) set_queen(i+1); else print_queens();
    a[j] = b[i+j] = c[i-j] = 1;
    }
    }

    int _tmain(int argc, _TCHAR* argv[])
    {
    for(int i=1;i<=8;i++) a=1;
    for(int i=2;i<=16;i++) b=1;
    for(int i=-7;i<=7;i++) c=1;

    set_queen(1);
    return 0;
    }

    Now This only prints 82 solutions, so 10 solutions are missing. In the
    book the first 12 solutions a printed and they are the same as my first 12
    solutions, so something else goes wrong. I also did the same program in
    Common Lisp which works fine (and prints all 92 solutions). (This is
    strange as Cl is much more different from Pascal than C++.)

    Does, by any chance, anybody sees something which could go wrong (maybe
    when the indeces become higher)?

    Obviously, you can invest a lot of time here, so eveything I am asking for
    is to look at the implementation of the Pascal array class and to have a
    glance at the program.

    TIA,

    jb
    jblazi, Aug 30, 2004
    #1
    1. Advertising

  2. jblazi

    jblazi Guest

    On Mon, 30 Aug 2004 16:50:34 +0200, jblazi wrote:

    Sorry, but something went wrong with the copying. Here is the program:

    #include "stdafx.h"

    // Pascal like array with arbitrary indeces
    class Array {
    int *datum,start_index,end_index;

    public:
    Array(int s_index,int e_index) {start_index = s_index; end_index = e_index;datum = new int(end_index-start_index+1);}
    int& operator [](int i) {return *(datum-start_index+i);}
    };

    // x : row of queen in the i-th coloumn
    // a : no queen is in the the i-th row
    // b : no queen is in the the i-th diagonal
    // which has positive slope
    // c : no queen is in the the i-th diagonal
    // which has negative slope


    Array a(1,8),x(1,8),b(2,16),c(-7,7);

    void print_queens()
    {
    static int cnt = 0;

    printf("%2d: ",++cnt);
    for(int k=1;k<=8;k++)
    printf("%4d",x[k]);
    printf("\n");
    }

    void set_queen(int i)
    {
    int j;
    for(j=1;j<=8;j++)
    if (a[j] && b[i+j] && c[i-j]) {
    x = j;
    a[j] = b[i+j] = c[i-j] = 0;
    if (i < 8) set_queen(i+1); else print_queens();
    a[j] = b[i+j] = c[i-j] = 1;
    }
    }

    int _tmain(int argc, _TCHAR* argv[])
    {
    for(int i=1;i<=8;i++) a=1;
    for(int i=2;i<=16;i++) b=1;
    for(int i=-7;i<=7;i++) c=1;

    set_queen(1);
    return 0;
    }
    jblazi, Aug 30, 2004
    #2
    1. Advertising

  3. jblazi wrote:
    >


    > Now This only prints 82 solutions, so 10 solutions are missing. In the
    > book the first 12 solutions a printed and they are the same as my first 12
    > solutions, so something else goes wrong.


    So fire up your debugger, figure out how you can manage to break the
    program after the 12 solution has been generated and continue
    single stepping your program until you can see how and why the
    13-th solution comes up. Compare that with the posted 13-th solution
    in the book, note the differences and deduce why there are differences.
    (You might want to repeat this breaking in and single stepping to verify
    your deductions, etc)

    Welcome to the wonderful world of debugging. You will spend lots of time
    with your debugger. So get familiar with it.

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Aug 30, 2004
    #3
  4. jblazi wrote:
    > In the book "Algortims and Data Structures" by Wirth there is a program in
    > Pascal to compute all 92 solutions of the above mentioned problem. I tried
    > to translate his program into C++, the only small problem being that he
    > uses array with a starting index other than zero. Here is my solution:
    > [...]
    >
    > // Pascal like array with arbitrary indeces
    > class Array {
    > int *datum,start_index,end_index;
    >
    > public:
    > Array(int s_index,int e_index) {start_index = s_index; end_index = e_index;datum = new int(end_index-start_index+1);}


    new int(blah);

    allocates a _single_ int and initialises it to 'blah'. To allocate
    an array of blah ints you need to do

    new int[blah];

    > [...]


    Victor
    Victor Bazarov, Aug 30, 2004
    #4
  5. jblazi wrote:
    > On Mon, 30 Aug 2004 16:50:34 +0200, jblazi wrote:
    >
    > Sorry, but something went wrong with the copying. Here is the program:
    >
    > #include "stdafx.h"
    >
    > // Pascal like array with arbitrary indeces
    > class Array {
    > int *datum,start_index,end_index;
    >
    > public:
    > Array(int s_index,int e_index) {start_index = s_index; end_index = e_index;datum = new int(end_index-start_index+1);}


    You have the same problem here. 'datum' is a pointer to a single int, not
    an array of ints.

    > [...]


    Victor
    Victor Bazarov, Aug 30, 2004
    #5
  6. jblazi wrote:
    >
    > On Mon, 30 Aug 2004 16:50:34 +0200, jblazi wrote:
    >
    > Sorry, but something went wrong with the copying. Here is the program:


    This prints 92 solutions on VC++
    (after some modifications such as replacing stdafx.h
    with stdio.h, _tmain with main)

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Aug 30, 2004
    #6
  7. Karl Heinz Buchegger wrote:
    >
    > jblazi wrote:
    > >

    >
    > > Now This only prints 82 solutions, so 10 solutions are missing. In the
    > > book the first 12 solutions a printed and they are the same as my first 12
    > > solutions, so something else goes wrong.

    >
    > So fire up your debugger, figure out how you can manage to break the
    > program after the 12 solution has been generated and continue
    > single stepping your program until you can see how and why the
    > 13-th solution comes up. Compare that with the posted 13-th solution
    > in the book,


    Sorry. I missed that you said: *only* 12 solutions are printed

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Aug 30, 2004
    #7
  8. Karl Heinz Buchegger wrote:
    > jblazi wrote:
    >
    >>On Mon, 30 Aug 2004 16:50:34 +0200, jblazi wrote:
    >>
    >>Sorry, but something went wrong with the copying. Here is the program:

    >
    >
    > This prints 92 solutions on VC++
    > (after some modifications such as replacing stdafx.h
    > with stdio.h, _tmain with main)


    Wow. Undefined behaviour will never cease to amaze me...
    Victor Bazarov, Aug 30, 2004
    #8
  9. jblazi

    jblazi Guest

    On Mon, 30 Aug 2004 11:09:46 -0400, Victor Bazarov wrote:

    > You have the same problem here. 'datum' is a pointer to a single int, not
    > an array of ints.
    > Victor


    Thx. What a silly mistake! And it is then completely understandable that
    it *may* run on some compilers *by* *chance*, as somebody pointed out in
    the thread.

    jb
    jblazi, Aug 30, 2004
    #9
  10. Victor Bazarov wrote:
    >
    > Karl Heinz Buchegger wrote:
    > > jblazi wrote:
    > >
    > >>On Mon, 30 Aug 2004 16:50:34 +0200, jblazi wrote:
    > >>
    > >>Sorry, but something went wrong with the copying. Here is the program:

    > >
    > >
    > > This prints 92 solutions on VC++
    > > (after some modifications such as replacing stdafx.h
    > > with stdio.h, _tmain with main)

    >
    > Wow. Undefined behaviour will never cease to amaze me...


    Me too.
    I totally missed the 'non-allocation', yet the thing run
    as expected. I even stepped through with the debugger and
    noticed nothing. Well. Not exactly. There were access violations
    deep inside the printf code. After some examination I decided
    to drop that problem for later (I always use the same VC
    project for compiling newsgroup code, so it could be that there
    were some strange project settings left from a previous program).

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Aug 30, 2004
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. cfanatic
    Replies:
    3
    Views:
    545
    cfanatic
    Oct 16, 2003
  2. Jeff Epler
    Replies:
    10
    Views:
    654
    Anton Vredegoor
    Aug 20, 2003
  3. Matt

    "Eight Queens" program

    Matt, Aug 18, 2004, in forum: C Programming
    Replies:
    5
    Views:
    449
    -berlin.de
    Aug 21, 2004
  4. sathya_me

    Is this OT(was:Re: "Eight Queens" program)

    sathya_me, Aug 20, 2004, in forum: C Programming
    Replies:
    5
    Views:
    304
    sathya_me
    Aug 20, 2004
  5. SM Ryan

    Re: "Eight Queens" program

    SM Ryan, Aug 21, 2004, in forum: C Programming
    Replies:
    0
    Views:
    361
    SM Ryan
    Aug 21, 2004
Loading...

Share This Page