C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  The eight queens problem          C++Talk.NET Forum Index -> C++ language (comp.lang.c++) View previous topic :: View next topic   Author Message jblazi Guest Posted: Mon Aug 30, 2004 2:50 pm    Post subject: The eight queens problem 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[i] : row of queen in the i-th coloumn // a[i] : no queen is in the the i-th row // b[i] : no queen is in the the i-th diagonal // which has positive slope // c[i] : no queen is in the the i-th diagonal // which has negative slope Array a(1,,x(1,,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[i] = j; a[j] = b[i+j] = c[i-j] = 0; if (i < 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[i]=1; for(int i=2;i<=16;i++) b[i]=1; for(int i=-7;i<=7;i++) c[i]=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 Back to top jblazi Guest Posted: Mon Aug 30, 2004 2:58 pm    Post subject: Re: The eight queens problem 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[i] : row of queen in the i-th coloumn // a[i] : no queen is in the the i-th row // b[i] : no queen is in the the i-th diagonal // which has positive slope // c[i] : no queen is in the the i-th diagonal // which has negative slope Array a(1,,x(1,,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[i] = j; a[j] = b[i+j] = c[i-j] = 0; if (i < 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[i]=1; for(int i=2;i<=16;i++) b[i]=1; for(int i=-7;i<=7;i++) c[i]=1; set_queen(1); return 0; } Back to top Karl Heinz Buchegger Guest Posted: Mon Aug 30, 2004 2:59 pm    Post subject: Re: The eight queens problem jblazi wrote: Quote: 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 [email]kbuchegg (AT) gascad (DOT) at[/email] Back to top Victor Bazarov Guest Posted: Mon Aug 30, 2004 3:01 pm    Post subject: Re: The eight queens problem jblazi wrote: Quote: 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]; Quote: [...] Victor Back to top Victor Bazarov Guest Posted: Mon Aug 30, 2004 3:09 pm    Post subject: Re: The eight queens problem jblazi wrote: Quote: 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. Quote: [...] Victor Back to top Karl Heinz Buchegger Guest Posted: Mon Aug 30, 2004 3:20 pm    Post subject: Re: The eight queens problem jblazi wrote: Quote: 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 [email]kbuchegg (AT) gascad (DOT) at[/email] Back to top Karl Heinz Buchegger Guest Posted: Mon Aug 30, 2004 3:21 pm    Post subject: Re: The eight queens problem Karl Heinz Buchegger wrote: Quote: 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 [email]kbuchegg (AT) gascad (DOT) at[/email] Back to top Victor Bazarov Guest Posted: Mon Aug 30, 2004 3:53 pm    Post subject: Re: The eight queens problem Karl Heinz Buchegger wrote: Quote: 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... Back to top jblazi Guest Posted: Mon Aug 30, 2004 3:54 pm    Post subject: Re: The eight queens problem On Mon, 30 Aug 2004 11:09:46 -0400, Victor Bazarov wrote: Quote: 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 Back to top Karl Heinz Buchegger Guest Posted: Mon Aug 30, 2004 5:01 pm    Post subject: Re: The eight queens problem Victor Bazarov wrote: Quote: 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 [email]kbuchegg (AT) gascad (DOT) at[/email] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ language (comp.lang.c++) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.