#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    32
    Rep Power
    2

    N-Queens problem


    This is more than just frustrating!
    I think most of you super PRO's are quite familiar with this problem. I am being asked to a build a function "def Queens(N)" which receives as a parameter an integer N which represents the size of an NxN chessboard where I will have to place N queens and count the amount of possibilities there is of positioning N queens on the board without having one threaten the other.

    In other words, no two queens can be in the same row, column or diagonal. I have the idea of how the algorithm works, I wrote it down on paper millions of times but then I get to blank when I start the code!

    Could anyone please post the way to start the function? - I thought about using a recursion but still i'm not yet into PRO programming and im just into doing simple and understandable pieces of code...

    Thanks in advance.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2012
    Posts
    39
    Rep Power
    3
    Have you looked up the eight queens problem on wikipedia?
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    32
    Rep Power
    2
    Originally Posted by Quackajack
    Have you looked up the eight queens problem on wikipedia?
    Yes, I did my research but I repeat, I am still a newbie and I don't understand all the complicated codes that are used in the given examples...
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    Code:
    $ python -c 'import q;q.queens(4)'
    depth += 1
    # Trying to place a queen on rank 1.  Open files on [1, 2, 3, 4].
    # Accept square a1.
    depth += 1
    # Trying to place a queen on rank 2.  Open files on [2, 3, 4].
    # a1 attacks b2
    # Accept square c2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [2, 4].
    # c2 attacks b3
    # c2 attacks d3
    depth -= 1
    # Accept square d2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [2, 3].
    # Accept square b3.
    depth += 1
    # Trying to place a queen on rank 4.  Open files on [3].
    # b3 attacks c4
    depth -= 1
    # a1 attacks c3
    depth -= 1
    depth -= 1
    # Accept square b1.
    depth += 1
    # Trying to place a queen on rank 2.  Open files on [1, 3, 4].
    # b1 attacks a2
    # b1 attacks c2
    # Accept square d2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [1, 3].
    # Accept square a3.
    depth += 1
    # Trying to place a queen on rank 4.  Open files on [3].
    # Accept square c4.
    depth += 1
    # Solved.  We've placed all 4 queens.
    [2, 4, 1, 3]
    depth -= 1
    depth -= 1
    # d2 attacks c3
    depth -= 1
    depth -= 1
    # Accept square c1.
    depth += 1
    # Trying to place a queen on rank 2.  Open files on [1, 2, 4].
    # Accept square a2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [2, 4].
    # a2 attacks b3
    # Accept square d3.
    depth += 1
    # Trying to place a queen on rank 4.  Open files on [2].
    # Accept square b4.
    depth += 1
    # Solved.  We've placed all 4 queens.
    [3, 1, 4, 2]
    depth -= 1
    depth -= 1
    depth -= 1
    # c1 attacks b2
    # c1 attacks d2
    depth -= 1
    # Accept square d1.
    depth += 1
    # Trying to place a queen on rank 2.  Open files on [1, 2, 3].
    # Accept square a2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [2, 3].
    # d1 attacks b3
    # Accept square c3.
    depth += 1
    # Trying to place a queen on rank 4.  Open files on [2].
    # c3 attacks b4
    depth -= 1
    depth -= 1
    # Accept square b2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [1, 3].
    # b2 attacks a3
    # b2 attacks c3
    depth -= 1
    # d1 attacks c2
    depth -= 1
    depth -= 1
    file q.py
    Code:
    # n queens
    # recursion looks like a good choice because
    # python saves the backtracking state and the
    # stack depth won't be excessive.
    # How do you handle solutions that are symmetrically or by rotation the same?
    
    import string
    
    def algebraic(f,r):
        return string.ascii_lowercase[f]+string.digits[r+1]
    
    def adjust(a):
        try:
            return [1+A for A in a]
        except:
            return 1+a
    
    def queens(N,FILES=[]):
        print('depth += 1')
        RANK = len(FILES)
        if N == RANK:
            print("# Solved.  We've placed all %d queens."%N)
            print(adjust(FILES))
        else:
            print('# Trying to place a queen on rank %d.  Open files on %s.'%(adjust(RANK),adjust(set(range(N))-set(FILES))))
            for FILE in set(range(N))-set(FILES):
                for (R,F) in enumerate(FILES):
                    if (F==FILE+RANK-R) or (F==FILE-RANK+R):
                        print('# %s attacks %s'%(algebraic(F,R),algebraic(FILE,RANK)))
                        break
                else:
                    print('# Accept square %s.'%(algebraic(FILE,RANK)))
                    queens(N,FILES+[FILE])
        print('depth -= 1')
    Last edited by b49P23TIvg; November 22nd, 2012 at 11:59 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    32
    Rep Power
    2
    Originally Posted by b49P23TIvg
    Code:
    $ python -c 'import q;q.queens(4)'
    depth += 1
    # Trying to place a queen on rank 1.  Open files on [1, 2, 3, 4].
    # Accept square a1.
    depth += 1
    # Trying to place a queen on rank 2.  Open files on [2, 3, 4].
    # a1 attacks b2
    # Accept square c2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [2, 4].
    # c2 attacks b3
    # c2 attacks d3
    depth -= 1
    # Accept square d2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [2, 3].
    # Accept square b3.
    depth += 1
    # Trying to place a queen on rank 4.  Open files on [3].
    # b3 attacks c4
    depth -= 1
    # a1 attacks c3
    depth -= 1
    depth -= 1
    # Accept square b1.
    depth += 1
    # Trying to place a queen on rank 2.  Open files on [1, 3, 4].
    # b1 attacks a2
    # b1 attacks c2
    # Accept square d2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [1, 3].
    # Accept square a3.
    depth += 1
    # Trying to place a queen on rank 4.  Open files on [3].
    # Accept square c4.
    depth += 1
    # Solved.  We've placed all 4 queens.
    [2, 4, 1, 3]
    depth -= 1
    depth -= 1
    # d2 attacks c3
    depth -= 1
    depth -= 1
    # Accept square c1.
    depth += 1
    # Trying to place a queen on rank 2.  Open files on [1, 2, 4].
    # Accept square a2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [2, 4].
    # a2 attacks b3
    # Accept square d3.
    depth += 1
    # Trying to place a queen on rank 4.  Open files on [2].
    # Accept square b4.
    depth += 1
    # Solved.  We've placed all 4 queens.
    [3, 1, 4, 2]
    depth -= 1
    depth -= 1
    depth -= 1
    # c1 attacks b2
    # c1 attacks d2
    depth -= 1
    # Accept square d1.
    depth += 1
    # Trying to place a queen on rank 2.  Open files on [1, 2, 3].
    # Accept square a2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [2, 3].
    # d1 attacks b3
    # Accept square c3.
    depth += 1
    # Trying to place a queen on rank 4.  Open files on [2].
    # c3 attacks b4
    depth -= 1
    depth -= 1
    # Accept square b2.
    depth += 1
    # Trying to place a queen on rank 3.  Open files on [1, 3].
    # b2 attacks a3
    # b2 attacks c3
    depth -= 1
    # d1 attacks c2
    depth -= 1
    depth -= 1
    file q.py
    Code:
    # n queens
    # recursion looks like a good choice because
    # python saves the backtracking state and the
    # stack depth won't be excessive.
    # How do you handle solutions that are symmetrically or by rotation the same?
    
    import string
    
    def algebraic(f,r):
        return string.ascii_lowercase[f]+string.digits[r+1]
    
    def adjust(a):
        try:
            return [1+A for A in a]
        except:
            return 1+a
    
    def queens(N,FILES=[]):
        print('depth += 1')
        RANK = len(FILES)
        if N == RANK:
            print("# Solved.  We've placed all %d queens."%N)
            print(adjust(FILES))
        else:
            print('# Trying to place a queen on rank %d.  Open files on %s.'%(adjust(RANK),adjust(set(range(N))-set(FILES))))
            for FILE in set(range(N))-set(FILES):
                for (R,F) in enumerate(FILES):
                    if (F==FILE+RANK-R) or (F==FILE-RANK+R):
                        print('# %s attacks %s'%(algebraic(F,R),algebraic(FILE,RANK)))
                        break
                else:
                    print('# Accept square %s.'%(algebraic(FILE,RANK)))
                    queens(N,FILES+[FILE])
        print('depth -= 1')

    That's one hella big piece of code...
    The thing is that i'm trying so hard to work this out using a single List. For example, I am working on a 8x8 chessboard, thus i'm using an 8 elements list where each index points at a column and the value inside of a certain index (column) points at the row that the queen is at.

    I am so lost in the recursion and I could really use some help here :-(

    I am not allowed to use "enumeration"; in fact I don't even know what it is XD please consider :] i'm just 3 weeks into college and it is a nightmare when it gets to crazy codes!
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    The program is 28 lines long, much of which is just to explain what it is doing. The first block is output from a 4x4 chessboard. I see now that I inconsistently named files with algebraic notation (letters) and numbers. I suppose I could try again showing diagrams.

    Post your effort, we'll try to explain or fix it.
    [code]Code tags[/code] are essential for python code and Makefiles!
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    32
    Rep Power
    2
    Originally Posted by b49P23TIvg
    The program is 28 lines long, much of which is just to explain what it is doing. The first block is output from a 4x4 chessboard. I see now that I inconsistently named files with algebraic notation (letters) and numbers. I suppose I could try again showing diagrams.

    Post your effort, we'll try to explain or fix it.


    Alright! I managed to get out of this question! but for checking purposes; is the answer 92 possibilities in a 8x8 chessboard?
  14. #8
  15. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    Well, Mr/Ms "Yes, I did my research", I got 92 solutions for an 8x8 board, as did the wikipedia article, of which they draw the unique solutions after accounting for translation and rotation.

    Now, did you learn anything about recursion?
    [code]Code tags[/code] are essential for python code and Makefiles!
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    32
    Rep Power
    2
    Originally Posted by b49P23TIvg
    Well, Mr/Ms "Yes, I did my research", I got 92 solutions for an 8x8 board, as did the wikipedia article, of which they draw the unique solutions after accounting for translation and rotation.

    Now, did you learn anything about recursion?

    Absolutely!

IMN logo majestic logo threadwatch logo seochat tools logo