9
votes
\$\begingroup\$

In chess, a queen can move as far as as the board extends horizontally, vertically, or diagonally.

Given a NxN sized chessboard, print out how many possible positions N queens can be placed on the board and not be able to hit each other in 1 move.

\$\endgroup\$

closed as off-topic by Martin Ender, Optimizer, ProgramFOX, NinjaBearMonkey, jimmy23013 Dec 20 '14 at 5:29

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Martin Ender, Optimizer, ProgramFOX, NinjaBearMonkey, jimmy23013
If this question can be reworded to fit the rules in the help center, please edit the question.

locked by Alex A. Feb 4 '16 at 22:16

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. See the help center for guidance on writing a good question.

Read more about locked posts here.

  • \$\begingroup\$ Do we need to handle 2 <= N <= 4 cases? If so how? \$\endgroup\$ – st0le Feb 2 '11 at 12:09
  • \$\begingroup\$ There is no solution for case: N = 2,3. The wikipedia has a excellent write up about this classic problem. It documents ver well about the solution number from N = 1 to N = 14. (I am still new to Code Golf. Not sure what is the best way to participate yet. :)) \$\endgroup\$ – Dongshengcn Jul 4 '11 at 0:01
  • \$\begingroup\$ A000170 \$\endgroup\$ – Peter Taylor Apr 12 '13 at 15:52
4
votes
\$\begingroup\$

Here's a solution (originally from this blog entry) where I construct a logical description of the solution in conjunctive normal form which is then solved by Mathematica:

(* Define the variables: Q[i,j] indicates whether there is a 
   Queen in row i, column j *)
Qs = Array[Q, {8, 8}];

(* Define the logical constraints. *)
problem =
  And[
   (* Each row must have a queen. *)
   And @@ Map[(Or @@ #) &, Qs],
   (* for all i,j: Q[i,j] implies Not[...] *)
   And @@ Flatten[
     Qs /. Q[i_, j_] :>
       And @@ Map[Implies[Q[i, j], Not[#]] &, 
         Cases[Qs, 
          Q[k_, l_] /;
           Not[(i == k) && (j == l)] && (
             (i == k) ||          (* same row *)
                 (j == l) ||          (* same column *)
             (i + j == k + l) ||  (* same / diagonal *)
             (i - j == k - l)),   (* same \ diagonal *)
          2]]]];

(* Find the solution *)
solution = FindInstance[problem, Flatten[Qs], Booleans] ;

(* Display the solution *)
Qs /. First[solution] /. {True -> Q, False -> x} // MatrixForm

Here's the output:

x   x   x   x   Q   x   x   x
x   Q   x   x   x   x   x   x
x   x   x   Q   x   x   x   x
x   x   x   x   x   x   Q   x
x   x   Q   x   x   x   x   x
x   x   x   x   x   x   x   Q
x   x   x   x   x   Q   x   x
Q   x   x   x   x   x   x   x
\$\endgroup\$
0
votes
\$\begingroup\$

Ruby

I don't see a golf tag, so i'm assuming it's just a challenge.

Here's an implementation of the Algorithm mentioned on Wikipedia. It's not by me, it's at Rosetta Stone and can be found here

CommWikied this Answer.

\$\endgroup\$
0
votes
\$\begingroup\$

Python 2, 190 185 chars

from itertools import*
n=input()
print len(filter(lambda x:all(1^(y in(z,z+i-j,z-i+j))for i,y in enumerate(x)for j,z in enumerate(x[:i]+(1e9,)+x[i+1:])),permutations(range(1,n+1),n)))

I just assumed the code golf tag even though it wasn't there. N is read from stdin, the program calculates solutions up to n=10 in acceptable time.

\$\endgroup\$
0
votes
\$\begingroup\$

Groovy

n=8
s=(1..n).permutations().findAll{ 
  def x=0,y=0
  Set a=it.collect{it-x++} 
  Set b=it.collect{it+y++} 
  a.size()==it.size()&&b.size()==it.size() 
}

Delivers a list of all queen solutions like this:

[ [4, 7, 3, 0, 6, 1, 5, 2], 
  [6, 2, 7, 1, 4, 0, 5, 3], 
  ... ]

For graphical representation add:

s.each { def size = it.size()
         it.each { (it-1).times { print "|_" }
                   print "|Q"
                   (size-it).times { print "|_" }
                   println "|"
                 }
         println ""
         }      

which looks like this:

|_|Q|_|_|_|_|_|_|
|_|_|_|Q|_|_|_|_|
|_|_|_|_|_|Q|_|_|
|_|_|_|_|_|_|_|Q|
|_|_|Q|_|_|_|_|_|
|Q|_|_|_|_|_|_|_|
|_|_|_|_|_|_|Q|_|
|_|_|_|_|Q|_|_|_|
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.