16
\$\begingroup\$

(Despite 60+ questions tagged , 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.

8-queens example solution 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 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
\$\endgroup\$
10
  • 1
    \$\begingroup\$ Related. \$\endgroup\$ Jul 21, 2017 at 14:07
  • 1
    \$\begingroup\$ Could you give testcases for odd inputs? \$\endgroup\$
    – user41805
    Jul 21, 2017 at 14:13
  • \$\begingroup\$ @Cowsquack Added n=7 example \$\endgroup\$ Jul 21, 2017 at 14:32
  • 1
    \$\begingroup\$ @KeyuGan Something like the MATL answer? Yeah, that's fine. \$\endgroup\$ Jul 21, 2017 at 16:02
  • 2
    \$\begingroup\$ @JonathanAllan No such exclusion was intended, so long as the program finishes in finite time with probability one (as standard for all submissions). \$\endgroup\$ Jul 21, 2017 at 18:45

12 Answers 12

6
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ It's not clear to me how it can be O(1) with a loop repeating n times. How can all of those calculations always be done in constant time? \$\endgroup\$
    – poi830
    Jul 22, 2017 at 3:10
  • 1
    \$\begingroup\$ @poi830 I mean O(1) computation time per row to determine the position of the queen. \$\endgroup\$
    – orlp
    Jul 22, 2017 at 3:18
  • \$\begingroup\$ couldn't you save a few by making a new variable for n/2? \$\endgroup\$
    – Jeffmagma
    Dec 26, 2017 at 2:44
  • \$\begingroup\$ Suggest n-=o=n%2;for(y=n+o;y--;) instead of o=n%2;n-=o;for(y=0;y<n+o;++y) \$\endgroup\$
    – ceilingcat
    Jan 24, 2019 at 7:18
5
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ I'm not sure this counts as a solution, given that it doesn't always give the correct answer. \$\endgroup\$
    – junkmail
    Jul 21, 2017 at 15:23
  • 1
    \$\begingroup\$ @junkmail Huh? There is no such thing as the correct answer, as there a several solutions (as stated by the challenge). The code always gives a correct answer, just not the same every time \$\endgroup\$
    – Luis Mendo
    Jul 21, 2017 at 15:24
  • \$\begingroup\$ It's theoretically possible for the program to run arbitrarily many times and still fail to give an answer. \$\endgroup\$
    – junkmail
    Jul 21, 2017 at 15:28
  • 1
    \$\begingroup\$ @junkmail But it finishes in finite time with probability one \$\endgroup\$
    – Luis Mendo
    Jul 21, 2017 at 15:28
  • 1
    \$\begingroup\$ @JamesHollis I disagree. That could make some permutations more likely than others, but it wouldn't prevent any permutation from appearing. So the solution would eventually be reached. And in addition, assuming the random generator is ideal is usually accepted \$\endgroup\$
    – Luis Mendo
    Jul 22, 2017 at 10:33
2
\$\begingroup\$

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.

output

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ As this code isn't yours, could you convert it into a Community Wiki? (just click the button below the editing window that says "Community Wiki") \$\endgroup\$ Jul 21, 2017 at 18:26
  • \$\begingroup\$ Hi QuaerendoInvenietis and welcome to PPCG. As it's currently written, this doesn't seem to take a particular number as input and output only that solution. \$\endgroup\$ Jul 21, 2017 at 18:47
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Can't you use Œc€ instead of œc€2 for -1? \$\endgroup\$ Jul 22, 2017 at 13:36
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

Source code with execution paths highlighted

* 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.

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 18 bytesSBCS

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

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

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!

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

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.

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

Charcoal, 44 bytes

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

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

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

J, 49 bytes

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

Try it online!

Brute force by testing all permutations of length n.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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