Nqueens problem, n will be input, output count of all possibles

[otnaug]

Hi,

I'm writing a program for nqueens where inputs will be n and possibly a few existing queens already placed on the board. So far I've come up with one method, but got stuck on the second one.
(hoping second method is more efficient)

1st method:
- tabulate possible outcome of (n*n choose n)
- loop through all the outcomes and decide their legality.
- (if there are inputs of existing queens then that's great, i just narrow down from the possible outcome table)

2nd method (stuck):
- i want to do the brute force method on wikipedia -- going horizontal line by line on the board
- for nqueens i need to write n loops.
- so my program will have 20 different sections, 1 for each n up to 20 (with the 20 being a 20-level nested loop), once user input n i'll go to that loop.
- seems like a really bad idea.



any hint is welcome!
the assignment is to further parallelize it, i don't know how to parallelize recursive codes (not to mention i don't know how to write a recursive version of nqueens).



thanks!

 

[mfb]

- so my program will have 20 different sections, 1 for each n up to 20 (with the 20 being a 20-level nested loop), once user input n i'll go to that loop.

Looks like an application for a recursive function. Each function has a loop which can run in parallel.

 

[otnaug]

Looks like an application for a recursive function. Each function has a loop which can run in parallel.

can you provide some outlines for the recursive function? thanks!

 

[mfb]

FindPosition(LineToFill, board) {
..[/color]//look for possible position for queen
..[/color]//if position possible, call FindPosition(LineToFill+1,modifiedboard)
}

Like that?

 

[jtbell]

Which language are you using?

 

[jtbell]

Moved to the homework forum. Be mindful of the guidelines for helping with assignments: no complete solutions, etc.