1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 29, 2013 #1
    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 dunno how to parallelize recursive codes (not to mention i dunno how to write a recursive version of nqueens).



    thanks!
     
  2. jcsd
  3. Mar 29, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Looks like an application for a recursive function. Each function has a loop which can run in parallel.
     
  4. Mar 29, 2013 #3
    can you provide some outlines for the recursive function? thanks!
     
  5. Mar 29, 2013 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

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

    Like that?
     
  6. Mar 29, 2013 #5

    jtbell

    User Avatar

    Staff: Mentor

    Which language are you using?
     
  7. Mar 29, 2013 #6

    jtbell

    User Avatar

    Staff: Mentor

    Moved to the homework forum. Be mindful of the guidelines for helping with assignments: no complete solutions, etc.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Nqueens problem, n will be input, output count of all possibles
  1. Input/Output Impedance (Replies: 15)

Loading...