473,320 Members | 1,948 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

help me with the program

N-Queens :
You are given a N x N chessboard & you are required to place N queens
on it so that they can't attack each-other. You just need to find out
the valid positions of the queens and the total number of such valid
combinations. A sample I/p and o/p is given below (where N will be
input by the user).

Sample I/p :
Enter the no. of queens: 4
Sample o/p:
1,3,0,2
2,0,3,1
Total no. of possible combinations = 2

Explanation: In the aforesaid example 4 is the value of N input by the
user(4 x 4 chessboard & 4 queens). The o/p prints the position no.s of
the four queens on the chessboard on screen (position no.s can have
value from 0 to N-1, refer the figure below).

0 1 2 3
- Q - -
- - - Q
Q - - -
- - Q -

The second line shows next such valid combination. Finally it prints
the total no. of such valid combinations on screen.

Nov 15 '05 #1
7 1751
On 4 Sep 2005 11:02:20 -0700, "sahu" <sw********@gmail.com> wrote:
N-Queens :

snip

Your third posting in five minutes with absolutely no lines of code
whatsoever. You must have confused this with the
do.my.homework.for.me group.
<<Remove the del for email>>
Nov 15 '05 #2
sahu wrote:

N-Queens :
You are given a N x N chessboard & you are required to place N queens
on it so that they can't attack each-other. You just need to find out
the valid positions of the queens and the total number of such valid
combinations.

<snip>

start with the easy case n == 2
Nov 15 '05 #3

In article <43**************@retarus.de>, Wolfgang Riedel <wo*************@retarus.de> writes:
sahu wrote:

N-Queens :


start with the easy case n == 2


The *really* easy case is n == 0, and the solution for that one also
works for any multiple of 0.

--
Michael Wojcik mi************@microfocus.com
Nov 15 '05 #4
Michael Wojcik wrote:

In article <43**************@retarus.de>, Wolfgang Riedel <wo*************@retarus.de> writes:
sahu wrote:

N-Queens :


start with the easy case n == 2


The *really* easy case is n == 0, and the solution for that one also
works for any multiple of 0.


if n == 0 and n == 2 have the same number of solutions, it should be save to
assume
this holds for all (at least even) values of n.
Of course N-Janus is another story...
Nov 15 '05 #5
On Tue, 06 Sep 2005 10:09:50 +0200, Wolfgang Riedel wrote:
Michael Wojcik wrote:

In article <43**************@retarus.de>, Wolfgang Riedel <wo*************@retarus.de> writes:
> sahu wrote:
> >
> > N-Queens :
>
> start with the easy case n == 2


The *really* easy case is n == 0, and the solution for that one also
works for any multiple of 0.


if n == 0 and n == 2 have the same number of solutions, it should be save to
assume
this holds for all (at least even) values of n.


Not safe and in fact wrong.

Lawrence

Nov 15 '05 #6
Wolfgang Riedel wrote:
Michael Wojcik wrote:
In article <43**************@retarus.de>, Wolfgang Riedel <wo*************@retarus.de> writes:
sahu wrote:

N-Queens :

start with the easy case n == 2


The *really* easy case is n == 0, and the solution for that one also
works for any multiple of 0.


if n == 0 and n == 2 have the same number of solutions, it should be save to
assume
this holds for all (at least even) values of n.
Of course N-Janus is another story...


It seems to me that the case n==0 has one solution,
n==1 also has one, and n==2 has none. Fitting these three
observations with a quadratic gives this general formula
for the number of solutions as a function of n:

S(n) = 1 + n/2 - n*n/2

This useful formula is a great time-saver. For example,
we need not write a computer program to discover that the
number of solutions on the standard n==8 chessboard is
minus twenty-seven.

--
Eric Sosman
es*****@acm-dot-org.invalid
Nov 15 '05 #7
Eric Sosman wrote:

Wolfgang Riedel wrote:
Michael Wojcik wrote:
In article <43**************@retarus.de>, Wolfgang Riedel <wo*************@retarus.de> writes:

sahu wrote:

> N-Queens :

start with the easy case n == 2

The *really* easy case is n == 0, and the solution for that one also
works for any multiple of 0.


if n == 0 and n == 2 have the same number of solutions, it should be save to
assume
this holds for all (at least even) values of n.
Of course N-Janus is another story...


It seems to me that the case n==0 has one solution,
n==1 also has one, and n==2 has none. Fitting these three
observations with a quadratic gives this general formula
for the number of solutions as a function of n:

S(n) = 1 + n/2 - n*n/2

This useful formula is a great time-saver. For example,
we need not write a computer program to discover that the
number of solutions on the standard n==8 chessboard is
minus twenty-seven.


while I still think, you can place nothing on no chessboard, even no no queen -
for n == 3, there are as well 0 solutions.
So the formula should be:

S(n) = (n**4 - 13n**3 + 46n*2 -48n) / -14

and we see one of those 'off by one' features
(they just slip by and are so easy to miss,
not that I want to introduce TDD into this serious debate):

-27 is true for n == 9
for n == 8, there is simply no solution

Wolfgang
Nov 15 '05 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: PHPkemon | last post by:
Hi there, A few weeks ago I made a post and got an answer which seemed very logical. Here's part of the post: PHPkemon wrote: > I think I've figured out how to do the main things like...
6
by: wukexin | last post by:
Help me, good men. I find mang books that introduce bit "mang header files",they talk too bit,in fact it is my too fool, I don't learn it, I have do a test program, but I have no correct doing...
5
by: Bec | last post by:
I'm in desperate need of your help.. I need to build an access database and have NO idea how to do this.. Not even where to start.. It IS for school, and am not asking anyone to do my...
7
by: tyler_durden | last post by:
thanks a lot for all your help..I'm really appreciated... with all the help I've been getting in forums I've been able to continue my program and it's almost done, but I'm having a big problem that...
2
by: Erik | last post by:
Hi Everyone, I'm having real problems compiling some source for eVC4++. The errors I am getting are below: It all seems to be centred around winsock. If I move the afsock.h reference to before...
1
by: Willing 2 Learn | last post by:
Below is a program I did to recognize a Finite State Automata for ASCII (J+H)*. I got that one working but im having trouble getting the NFA program to work. I really desperately need help! My...
4
by: Bob Homes | last post by:
In VB6, I used a system, which I loved, whereby I assigned a "helpId" to each menu item; that way, you could rest the cursor on the item (without actually running it) and then press F1 to get...
2
by: Bsnpr8 | last post by:
I need help guys, i have to many stuff to do, because i am in my last 2 weeks of the university, my last assignment is to do a spell checker in C++, i have an idea but nothing is coming out. I really...
6
by: HelpME | last post by:
I wrote a program in Vb.Net that was running fine. However I am unable to install it on a couple of machines. When i run it I get a windows error message that says My Project.exe has...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.