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,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[i] = 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[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 9 4773
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,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[i] = 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[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;
}
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 kb******@gascad.at
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
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
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 kb******@gascad.at
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 kb******@gascad.at
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
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 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 kb******@gascad.at This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Andreas |
last post by:
Hi!
does anybody know an algorithm to solve the 8-queens-problem in PHP?
|
by: cfanatic |
last post by:
Hey all, I been reading through these forums for a long time but have
never posted. Well, I got a dillema. I have a program of the Eight
Queen's program and I have to make it work without...
|
by: Matt |
last post by:
I will be grateful if someone explians this part
colfree = FALSE;
upfree = FALSE;
downfree = FALSE;
of the code below. I don't understand how this marks the downward and
upward diagonals....
|
by: totalgeekdom |
last post by:
Background:
The problem I'm trying to solve is.
There is a 5x5 grid.
You need to fit 5 queens on the board such that when placed there are
three spots left that are not threatened by the queen.
...
|
by: windandwaves |
last post by:
Hi Folk
I have to store up to eight boolean bits of information about an item
in my database.
e.g.
with restaurant
drive-through facility
yellow windows
|
by: angel120 |
last post by:
Since this is my first post, allow me to introduce myself. My name is Angel, and I'm a 3rd year student at Queens College. I currently am taking CS211, which is the second level of C++, CS212 which...
|
by: angel120 |
last post by:
So my second hw is to solve the 8 queens problem using a 1D array. The professor gave us a code that outputs the following (labeled as q):
0 2 5 7 6 3 1 4
The spaces 0-7 refer to the column #,...
|
by: cf29 |
last post by:
Greetings,
I designed in JavaScript a small program on my website called 5
queens.
(http://www.cf29.com/design/dame5_eng.php)
The goal is to control all the chess board with five queens that...
|
by: AZRebelCowgirl73 |
last post by:
I am trying to develop an 8 queens program, and currently it is working however it is printing 87222211 which is obviously wrong, I am trying to print the row of the queen in order from...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
| |