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

0 Members and 1 Guest are viewing this topic.

Lee Mac

  • Seagull
  • Posts: 12605
  • London, England
-={ 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

  • Water Moccasin
  • Posts: 1566
  • Moscow (Russia)
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...

Lee Mac

  • Seagull
  • Posts: 12605
  • London, England
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

  • Water Moccasin
  • Posts: 1566
  • Moscow (Russia)
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 ...

Lee Mac

  • Seagull
  • Posts: 12605
  • London, England
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

  • Water Moccasin
  • Posts: 1566
  • Moscow (Russia)
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

  • Water Moccasin
  • Posts: 1566
  • Moscow (Russia)
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

  • Water Moccasin
  • Posts: 1566
  • Moscow (Russia)
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  :?

Lee Mac

  • Seagull
  • Posts: 12605
  • London, England
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: 1417
  • 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 :)

Lee Mac

  • Seagull
  • Posts: 12605
  • London, England
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... :o

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1566
  • Moscow (Russia)
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.

Lee Mac

  • Seagull
  • Posts: 12605
  • London, England
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

  • Water Moccasin
  • Posts: 1566
  • Moscow (Russia)
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: 1417
  • 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 :)