N-Queens Puzzle

Question

(Despite 60+ questions tagged chess, we don't have a simple n-queens challenge.)

In chess, the N-Queens Puzzle is described as follows: Given an n x n chessboard and n queens, arrange the queens onto the chessboard so that no two queens are threatening each other. Below is an example solution for n = 8, borrowed from Wikipedia.

Or, in ASCII rendering:

xxxQxxxx
xxxxxxQx
xxQxxxxx
xxxxxxxQ
xQxxxxxx
xxxxQxxx
Qxxxxxxx
xxxxxQxx

The challenge here will be to take input n and output an ASCII representation of a solution to the n-Queens puzzle. Since there are more than one possible solution (e.g., at the least, a rotation or reflection), your code only needs to output any valid solution.

Input

A single positive integer n with n >= 4 in any convenient format. (n=2 and n=3 have no solutions, and n=1 is trivial, so those are excluded)

Output

The resulting ASCII representation of a solution to the N-queens puzzle, as outlined above. You may choose any two distinct ASCII values to represent blank spaces and queens. Again, this can be output in any suitable format (single string, a list of strings, a character array, etc.).

Rules

• Leading or trailing newlines or whitespace are all optional, as well as whitespace between characters, so long as the characters themselves line up correctly.
• You can either use an algorithm to calculate the possible positions, or use the explicit "stair-step" style of solution, whichever is golfier for your code.
• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• If possible, please include a link to an online testing environment so other people can try out your code!
• Standard loopholes are forbidden.
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

n=4
xQxx
xxxQ
Qxxx
xxQx

n=7
xxQxxxx
xxxxxxQ
xQxxxxx
xxxQxxx
xxxxxQx
Qxxxxxx
xxxxQxx

n=10
xxxxQxxxxx
xxxxxxxxxQ
xxxQxxxxxx
xxxxxxxxQx
xxQxxxxxxx
xxxxxxxQxx
xQxxxxxxxx
xxxxxxQxxx
Qxxxxxxxxx
xxxxxQxxxx

Answer 1

C, 114 bytes

Q(n,o,y){o=n%2;n-=o;for(y=0;y<n+o;++y)printf("%*c\n",y<n?o+n-(n+y%(n/2)*2+(n%6?y<n/2?n/2-1:2-n/2:y<n/2))%n:0,81);}

Directly prints a solution in O(1) time.

Answer 2

MATL, 33 32 27 bytes

`x,GZ@]1Z?tt!P!,w&TXds]h1>a

Try it online!

Semi-brute force, non-determistic approach:

1. Generate a random permutation of row positions
2. Generate a random permutation of column positions
3. Check that no queens share a diagonal or anti-diagonal
4. Repeat if necessary.

The obtained solution is random. If you run the code again you may get a different valid configuration. Running time is also random, but the longest test case (n = 10) finishes in about 30 seconds in TIO most of the time.

Answer 3

Mathematica, 103 108 110 117 bytes

-5 bytes for DuplicateFreeQ -> E!=##&@@@

-7 bytes for ReplacePart[Array[],] -> SparseArray[]

SparseArray[Thread@#&@@Select[Permutations@Range@#~Tuples~2,And@@(E!=##&@@@{#-#2,+##})&@@#&]->1,{#,#}]&

Return a 2D-array. It takes 2.76s to calculate f[6] and 135s for f[7]. (In the current version, - becomes 0 and Q to 1.

The algorithm is similar to MATL answer but here the code is completely brute-force.

Answer 4

C - 222 bytes

v,i,j,k,l,s,a[99];main(){for(scanf("%d",&s);*a-s;v=a[j*=v]-a[i],k=i<s,j+=(v=j<s&&(!k&&!!printf(2+"\n\n%c"-(!l<<!j)," #Q"[l^v?(l^j)&1:2])&&++l||a[i]<s&&v&&v-i+j&&v+i-j))&&!(l%=s),v||(i==j?a[i+=k]=0:++a[i])>=s*k&&++a[--i]);}

The code is not mine, but from the IOCCC. I hope I'm not breaking any rules. Also, this displays all solutions for N between 4 and 99. I'll try to get a TIO link later.

Answer 5

Jelly, 24 21 bytes

,JŒc€IF€An/PC
ẊÇ¿=þRG

Try it online!

Assuming each queen are placed on separate rows, we only need to find the column indices to place each queen at to avoid conflicts, which can be found by generating a random permutation of [1, 2, ..., n] and testing it.

Explanation

,JŒc€IF€An/PC  Helper. Input: permutation of [1, 2, ..., n]
 J             Enumerate indices, obtains [1, 2, ..., n]
,              Join
  Œc€          Find all pairs in each
     I         Calculate the difference of each pair
      F€       Flatten each
        A      Absolute value
               (We now have the distance in column between each queen and
                the distance in rows between each queen. If they are unequal,
                the queens do not conflict with each other)
         n/    Reduce using not-equals
           P   Product, returns 1 only if they are all unequal
            C  Complement
               Returns 1 when there is a conflict, else 0

ẊÇ¿=þRG  Main.  Input: n
Ẋ        Shuffle (When given an integer, it will shuffle [1, 2, ..., n])
 Ç¿      While the helper returns 1, continue shuffling
     R   Range, gets [1, 2, ..., n]
   =þ    Equality table (Generates the board as a matrix)
      G  Pretty-print the matrix

Answer 6

Python 3, 204 189 bytes

import itertools as p
n=int(input())
r=range(n)
b='.'*(n-1)+'Q'
for c in p.permutations(r):
 if len(set((x*z+c[x],z)for x in r for z in[1,-1]))==n+n:[print(*(b[x:]+b[:x]))for x in c];break

Brute force search through all permutations. I could remove the * and print the list comprehensions, but they look awful.

Output:

10
Q . . . . . . . . .
. . Q . . . . . . .
. . . . . Q . . . .
. . . . . . . Q . .
. . . . . . . . . Q
. . . . Q . . . . .
. . . . . . . . Q .
. Q . . . . . . . .
. . . Q . . . . . .
. . . . . . Q . . .

Slightly ungolfed:

import itertools as p
n=int(input())
r=range(n)
b='.'*(n-1)+'Q'
for c in p.permutations(r):
    if len(set( (x*z+c[x],z) for x in r for z in[1,-1] )) == n+n:
        [print(*(b[x:] + b[:x])) for x in c]
        break

Answer 7

Befunge, 122 bytes

&::2%-v>2*00g++00g%00g\-\00g\`*4>8#4*#<,#-:#1_$55+"Q",,:#v_@
/2p00:<^%g01\+*+1*!!%6g00-2g01\**!!%6g00-g012!:`\g01:::-1<p01

Try it online!

This is more or less based on the C solution by orlp.

Explanation

Read the number of queens, q, from stdin and calculate two variables for later use: n = q - q%2, and hn = n/2
Start the main loop, iterating r, the row number, from q down to 0, decrementing at the start of the loop, so the first r is q minus 1.
Calculate the offset of the queen in each row with the following formula:

offset = (n - (
  (hn <= r) * (2 - hn) * !!(n % 6) + 
  (hn > r) * ((hn - 2) * !!(n % 6) + 1) + 
  (y % hn * 2) + n
) % n) * (n > r)

Output offset space characters to indent the queen's position for the current row, plus one additional space just because it makes the output loop easier.
Output the Q for the queen, followed by a newline to move to the next row.
Test if r is zero, in which case we've reached the end of the board and can exit, otherwise we repeat the main loop again.

Answer 8

APL (Dyalog Unicode), 18 bytes^SBCS

Full program prompting for n from stdin. Prints space-separated solution to stdout using · for empty squares and ⍟ for Queens.

⎕CY'dfns'
⊃queens⎕

Try it online!

⎕CY'dfns' Copy the "dfns" library

⎕ get input from stdin

queens find all truly unique Queens' solutions (no reflections or rotations)

⊃ pick the first solution

Answer 9

Haskell, 145 bytes

The obvious brute force approach:

b=1>0
t[]=b
t(q:r)=all(/=q)r&&foldr(\(a,b)->(abs(q-b)/=a&&))b(zip[1..]r)&&t r
q n|y<-[1..n]=(\q->(' '<$[1..q])++"Q")<$>[x|x<-mapM(\_->y)y,t x]!!0

Try it online!

Answer 10

Retina, 136 bytes

.+
$* 
 
$_;$`Q¶
( +)\1( ?);
:$1;
:( +);\1\1
$1$1
:((   )+);( *)
 $1$1% $3$3
: ( +);( \1)?( *)
 $1 $1%$#2$* $#2$* $#2$* $1$3$3
( +)%\1?

Try it online! Port of @orlp's excellent C answer. Explanation:

.+
$* 

Convert to unary, using spaces (there is a space after the *).

$_;$`Q¶

Create N rows with N spaces, a ;, then 0..N-1 spaces, then a Q. The remaining stages apply to all rows.

( +)\1( ?);
:$1;

Integer divide N by 2. (Also wrap the result in :; to make it easier to anchor patterns.)

:( +);\1\1
$1$1

If the loop index equals N/2*2, then just leave that many spaces.

:((   )+);( *)
 $1$1% $3$3

If N/2 is a multiple of 3, then take double the loop index plus one, modulo N/2*2+1.

: ( +);( \1)?( *)
 $1 $1%$#2$* $#2$* $#2$* $1$3$3

Otherwise, take double the loop index plus (N/2-1) plus an extra 3 in the bottom half of the board, modulo N/2*2.

( +)%\1?

Actually perform the modulo operation.

Answer 11

Charcoal, 44 bytes

Ｎθ≔÷θ²ηＥθ◧Q⊕⎇⁼ι⊗ηι⎇﹪η³﹪⁺⁺⊗ι⊖η׳¬‹ιη⊗η﹪⊕⊗ι⊕⊗η

Try it online! Link is to verbose version of code. Another port of @orlp's excellent C answer.

Answer 12

J, 49 bytes

i.=/0({(1-.@e.,)@(([:(=#\){.|@-}.)\."1)#])!A.&i.]

Try it online!

Brute force by testing all permutations of length n.