### Author Topic: -={ Challenge }=- Eight Queens Puzzle  (Read 10388 times)

0 Members and 1 Guest are viewing this topic. ##### -={ Challenge }=- Eight Queens Puzzle
« on: August 18, 2011, 09:29:56 AM »
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 ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #1 on: August 18, 2011, 11:52:47 AM »
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... ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #2 on: August 18, 2011, 12:51:26 PM »
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 ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #3 on: August 18, 2011, 12:53:58 PM »
in the job one has to show any solution. There are algorithms that provide solutions for any size of the field ... ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #4 on: August 18, 2011, 12:58:15 PM »
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 ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #5 on: August 18, 2011, 01:04:19 PM »
3*3
4*4
5*5
6*6
« Last Edit: August 18, 2011, 01:23:53 PM by ElpanovEvgeniy »

#### ElpanovEvgeniy ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #6 on: August 18, 2011, 01:05:06 PM »
7*7
8*8
20*20
50*50
« Last Edit: August 18, 2011, 01:22:03 PM by ElpanovEvgeniy »

#### ElpanovEvgeniy ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #7 on: August 18, 2011, 01:06:54 PM »
This simple solution can be easily scaled to any size chess board  ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #8 on: August 18, 2011, 01:13:23 PM »
This simple solution can be easily scaled to any size chess board But you have conflicts with many of the diagonals #### VovKa

• Swamp Rat
• Posts: 1463
• Ukraine ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #9 on: August 18, 2011, 01:21:39 PM »
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  ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #10 on: August 18, 2011, 01:22:42 PM »
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 ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #11 on: August 18, 2011, 01:26:56 PM »
Sorry.
Now replaced all the pictures.
The pictures can be seen a simple algorithm that does not require complex calculations. ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #12 on: August 18, 2011, 01:28:13 PM »
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 ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #13 on: August 18, 2011, 01:34:54 PM »
I tried to reproduce the solution for the memory, I need more time to think ...

#### VovKa

• Swamp Rat
• Posts: 1463
• Ukraine ##### Re: -={ Challenge }=- Eight Queens Puzzle
« Reply #14 on: August 18, 2011, 01:36:00 PM »
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 