Topic: -={ Challenge }=- Eight Queens Puzzle

[Lee Mac]

Introduction:

The eight queens puzzle is the problem of placing eight chess queens on an 8Ś8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an nŚn chessboard, where solutions exist for all natural numbers n with the exception of 2 and 3.

The Challenge:

To create a program that will return a solution to the n-queens puzzle for arbitrary 'n'. The program should take a single argument 'n' and return a list of 2D coordinates describing the positions of the queens on the nxn chessboard such that no two queens attack each other. For consistency of solutions in this thread, the first square can have coordinates (1, 1).

Examples:

Note that these examples illustrate one possible solution, of which there may be many unique solutions.

Code: [Select]

_$ (nQueens 4)
((4 3) (3 1) (2 4) (1 2))

Code: [Select]

_$ (nQueens 8)
((8 4) (7 2) (6 7) (5 3) (4 6) (3 8) (2 5) (1 1))

[ElpanovEvgeniy]

I solved this problem long ago, I turned a simple fractals.
My solution is short and not interesting, I'll write and lay out when you say...

[Lee Mac]

I solved this problem long ago, I turned a simple fractals.
My solution is short and not interesting, I'll write and lay out when you say...

It is quite a famous problem, so I thought it would be a good challenge. A solution using fractals sounds interesting!

Would you like me to post my solution?

[ElpanovEvgeniy]

in the job one has to show any solution. There are algorithms that provide solutions for any size of the field ...

[Lee Mac]

This was my solution, I'm sure it could be optimised further:

Code: [Select]

(defun nQueens ( n / _inRow _inColumn _inDiagonal _Conflict _nQueens )

    (defun _inRow ( i l )
        (member i (mapcar 'car  l))
    )
    (defun _inColumn ( j l )
        (member j (mapcar 'cadr l))
    )
    (defun _inDiagonal ( i j l )
        (and l
            (or
                (= (- i j) (- (caar l) (cadar l)))
                (= (+ i j) (+ (caar l) (cadar l)))
                (_inDiagonal i j (cdr l))
            )
        )
    )
    (defun _Conflict ( i j l )
        (or
            (_inRow i l)
            (_inColumn j l)
            (_inDiagonal i j l)
        )
    )
   
    (defun _nQueens ( m i j l / r )
        (cond
            (   (zerop m)
                l
            )
            (   t
                (while (and (<= (setq i (1+ i)) n) (not r))
                    (while
                        (and (<= (setq j (1+ j)) n)
                            (or (_Conflict i j l)
                                (not (setq r (_nQueens (1- m) i 0 (cons (list i j) l))))
                            )
                        )
                    )
                )
                r
            )
        )
    )
   
    (_nQueens n 0 0 nil)
)

[ElpanovEvgeniy]

3*3
4*4
5*5
6*6

[ElpanovEvgeniy]

7*7
8*8
20*20
50*50

[ElpanovEvgeniy]

This simple solution can be easily scaled to any size chess board 

[Lee Mac]

This simple solution can be easily scaled to any size chess board 

But you have conflicts with many of the diagonals 

[VovKa]

This simple solution can be easily scaled to any size chess board 

But you have conflicts with many of the diagonals 

why many? i see only main diagonal problem. but that's enough

[Lee Mac]

This simple solution can be easily scaled to any size chess board 

But you have conflicts with many of the diagonals 

why many? i see only main diagonal problem. but that's enough

Sorry, I meant that diagonal in many of the solutions, but yes, one is enough 

EDIT: But now that Evgeniy has updated the images, there are many more...

[ElpanovEvgeniy]

Sorry.
Now replaced all the pictures.
The pictures can be seen a simple algorithm that does not require complex calculations.

[Lee Mac]

Sorry.
Now replaced all the pictures.
The pictures can be seen a simple algorithm that does not require complex calculations.

That may work up to 7, but I believe you will have a problem with every even number onwards...

[ElpanovEvgeniy]

I tried to reproduce the solution for the memory, I need more time to think ...

[VovKa]

Sorry.
Now replaced all the pictures.
The pictures can be seen a simple algorithm that does not require complex calculations.

the wikipedia article is too long for this problem to be so simple