Finding just one solution to N-queen problem by observing the pattern of solutions

Finding just one solution to N-queen problem by observing the pattern of solutions

Post by HKLN » Wed, 01 Jun 2005 00:46:51


Did anyone do this before? That is, just input the N and the solution
is constructed by just putting the queens on the board directly. This
takes linear time.

Recently, I found the pattern for all N except N = 9, 15, 21, ...,
9+6n.
Although I haven't proved the solution mathematically, I tested my
method for N below 1000.

To avoid reinventing the wheel, I would like to know if anyone did this
before.

Thank you for your time.
 
 
 

Finding just one solution to N-queen problem by observing the pattern of solutions

Post by Francis So » Wed, 01 Jun 2005 01:04:40


A few years ago, a friend told me it was published but I haven't the
reference.

 
 
 

Finding just one solution to N-queen problem by observing the pattern of solutions

Post by Francis So » Wed, 01 Jun 2005 01:33:19

I found this survey paper (via google scholar):
http://www.yqcomputer.com/
and a piece of code:
http://www.yqcomputer.com/
 
 
 

Finding just one solution to N-queen problem by observing the pattern of solutions

Post by HKLN » Wed, 01 Jun 2005 22:17:22

hank you for your reference, Francis. I've read the paper and found
that my method is similar to the Knight's walk.

Here are my observation on the solution pattern:

Pattern 1: For N=4,5,6,7, 10,11,12,13, 16,17,18,19, ....
Pattern 2: For N=8,20,32,...,8 + 12n
Pattern 3: For N=14,26,38,...,14 + 12n

I haven't found the pattern for N=9+6n, yet.

(The examples are at the bottom of this message.)

- Pattern 1: Knight's walk.
- Pattern 2: Upper half is the same. Lower half has lines in opposite
direction and each line has two queens.
- Pattern 3:
Bottle-left: the no. of lines are 1, 4, 7, ... 1 + 3n. One line for
N=14 and 26, 4 lines for N=38 and 50, and so on.
Middle: One queen at the bottom-most row.
Bottle-right: Knight's walk again.


Pattern 1:

N=4
-Q--
---Q
Q---
--Q-


N=5
-Q---
---Q-
Q----
--Q--
----Q


N=6
-Q----
---Q--
-----Q
Q-----
--Q---
----Q-


Pattern 2:

N=8
-Q------
---Q----
-----Q--
-------Q
--Q-----
Q-------
------Q-
----Q---


N=20
-Q------------------
---Q----------------
-----Q--------------
-------Q------------
---------Q----------
-----------Q--------
-------------Q------
---------------Q----
-----------------Q--
-------------------Q
--Q-----------------
Q-------------------
------Q-------------
----Q---------------
----------Q---------
--------Q-----------
--------------Q-----
------------Q-------
------------------Q-
----------------Q---


N=32
-Q------------------------------
---Q----------------------------
-----Q--------------------------
-------Q------------------------
---------Q----------------------
-----------Q--------------------
-------------Q------------------
---------------Q----------------
-----------------Q--------------
-------------------Q------------
---------------------Q----------
-----------------------Q--------
-------------------------Q------
---------------------------Q----
-----------------------------Q--
-------------------------------Q
--Q-----------------------------
Q-------------------------------
------Q-------------------------
----Q---------------------------
----------Q---------------------
--------Q-----------------------
--------------Q-----------------
------------Q-------------------
------------------Q-------------
----------------Q---------------
----------------------Q---------
--------------------Q-----------
--------------------------Q-----
------------------------Q-------
------------------------------Q-
----------------------------Q---


Pattern 3:

N=14


-Q------------
---Q----------
-----Q--------
-------Q------
---------Q----
-----------Q--
-------------Q
--Q-----------
Q-------------
------Q-------
--------Q-----
----------Q---
------------Q-
----Q---------


N=26

-Q------------------------
---Q----------------------
-----Q--------------------
-------Q------------------
---------Q----------------
-----------Q--------------
-------------Q------------
---------------Q----------
-----------------Q--------
-------------------Q------
---------------------Q----
-----------------------Q--
-------------------------Q
--Q-----------------------
Q-------------------------
------Q-------------------
--------Q-----------------
----------Q---------------
------------Q-------------
--------------Q-----------
----------------Q---------
------------------Q-------
--------------------Q-----
----------------------Q---
-
 
 
 

Finding just one solution to N-queen problem by observing the pattern of solutions

Post by djimene » Thu, 02 Jun 2005 05:51:42

In article < XXXX@XXXXX.COM >,


I did something like this about 12 years ago. Mine didn't work for about
1/4 of the cases. It was the same kind of thing. There were 3 cases and
each one had its own pattern. I wrote a little C program and tested it
up to about n=600. I'll post it if there's interest. I never bothered
to try publishing it.
--
Daniel Jimez XXXX@XXXXX.COM
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage