20
\$\begingroup\$

Given a number N from 2 to 8, place any nonzero number of queens on a grid of any size so that every queen has exactly N queens (counting itself) in each of its row, column, and each diagonal.

This challenge has a significant runtime limit. Your code must finish all N from 2 to 8 (combined) within the 60-second timeout on TIO. This makes brute force unlikely to work.

Some example outputs are below. You can use this verification script to confirm your outputs.

N=2

.OO.
O..O
O..O
.OO.

N=3 (by Christian Sievers)

..OOO......
.O.O...O...
OO...O.....
O...O....O.
O......O..O
..O...O..O.
..O..O....O
.O...O..O..
.......OO.O
...O..O..O.
....O.O.O..

N=4 (by Christian Sievers)

...OO..OO...
..OO....OO..
.O...OO...O.
OO........OO
O....OO....O
..O.O..O.O..
..O.O..O.O..
O....OO....O
OO........OO
.O...OO...O.
..OO....OO..
...OO..OO...

Your output grid can be square or rectangular. It may have empty rows and/or columns, even ones on the outside as a "margin" that makes the array bigger than necessary.

You can output as a 2D array of two distinct values of your choice, or as a string that displays as such.

For the 60-second time limit, running verification code doesn't have to happen within this time. If your language is not on TIO, you test it on any reasonable machine. On the off chance that your grids might be so big that TIO can't print them, it's allowed to run the test with storing all 7 grids instead of printing them, such as to a size-7 list where that any of them may be retrieved.

\$\endgroup\$
11
  • \$\begingroup\$ Great challenge! I've tried to run the verification script on some of my shorter output but I get an error message (not true or false.) \$\endgroup\$ Apr 26 '20 at 4:07
  • \$\begingroup\$ @LevelRiverSt Is it one of the assertions, or something else? What's the output? Do you have the format mentioned in the footer? \$\endgroup\$
    – xnor
    Apr 26 '20 at 5:03
  • \$\begingroup\$ @LevelRiverSt Oh, oops, my verification code is assuming the grids are square. Let me fix this. \$\endgroup\$
    – xnor
    Apr 26 '20 at 5:14
  • \$\begingroup\$ Ok, I thought it might be that. Anyway, I've added a TIO link for the verification to my answer, so you can check if there is anything else I'm doing wrong. \$\endgroup\$ Apr 26 '20 at 5:15
  • \$\begingroup\$ @LevelRiverSt I updated the snippet, I think it should work now. \$\endgroup\$
    – xnor
    Apr 26 '20 at 5:22
11
\$\begingroup\$

Python 2, 141 138 bytes

Try it online!

n=input()
P=[280]
for t in[1j,9,40j-40,64j+64]:P={p+i*t for i in range(n)for p in P}
r=range(792)
print[[x+y*1jin P for x in r]for y in r]

Takes n as input and prints a list of lists of booleans.

While the grids are generated within the 60 second time limit, they are larger than TIO's 128KiB limit, so they were simplified to be printable via TIO thanks to math junkie.

I added in the verification script to the TIO link so it can also be verified within TIO.

Here's my attempt at drawing my original solution for n=3. Hopefully this helps visualize it. Replace 57 with 40 and 408 with 64 for the current solution.

hand_drawn_solution

\$\endgroup\$
4
  • \$\begingroup\$ Looking at the TIO output for n=3, I'm not sure this works, though the output I'm looking at is cut off. What is supposed it supposed to look like? I see 3 queens in the first 3 rows in the same columns, which seems like will cause a problem with the short diagonal of the first queen, as there aren't any queens in the displayed rows after, and the cut off rows seem too late to be in that diagonal. (Edit: n=2 seems to have the same issue.) \$\endgroup\$
    – xnor
    Apr 25 '20 at 23:42
  • 2
    \$\begingroup\$ I've attempted to simplify the printed output to better show the shape of the grid: Each of the xyz: headings show the character number of that O on the current line. The --- ... --- headings are meant to show the line number after a bunch of empty lines. I've edited it into your post since the TIO link is too long to be a comment \$\endgroup\$ Apr 26 '20 at 0:06
  • \$\begingroup\$ Nice solution! I'm curious where you got the constants from. Do they give the smallest displacements to always avoid unwanted sharing of lines? \$\endgroup\$
    – xnor
    Apr 26 '20 at 19:10
  • \$\begingroup\$ @xnor Yeah I just found them through brute force. I originally used [1j, n, n**2*(1+1j), n**3*(1-1j)] but changed them to constants to save bytes. \$\endgroup\$ Apr 26 '20 at 19:34
9
\$\begingroup\$

Ruby, 85 77 bytes

->n{j=n**3+n
((0...n*n).map{|i|((?.*n*n+?O)*9)[~i%n+i/n*n,j]}+[?.*j]*j)*n*$/}

Try it online!

Similar to and inspired by cardboard_box's answer, but rotated by 45 degrees.

Below are the first 16 lines of the output for n=4. It should be apparent that that within each 16x16 box, the queens form diagonal lines of 4. In between the boxes there is a single blank column. If this was not there, the diagonal lines of each n**2 x n**2 box would line up exactly with its neighbour when n is even.

There are clearly 4 queens on each horizontal row and 1 queen in each vertical column (except the blank ones.) The rest of the pattern is a repeat of the below, interspersed with n**3+n rows of blanks to ensure the diagonals do not clash (I could get away with just a few rows less, but the code is shorter this way.)

The output is truncated by TIO so it's only possible to get full output up to 5, but it's apparent from the way the pattern is constructed that it meets the rules. Output has been verified up to 5.

.............O................O................O................O...
..............O................O................O................O..
...............O................O................O................O.
................O................O................O................O
.........O................O................O................O.......
..........O................O................O................O......
...........O................O................O................O.....
............O................O................O................O....
.....O................O................O................O...........
......O................O................O................O..........
.......O................O................O................O.........
........O................O................O................O........
.O................O................O................O...............
..O................O................O................O..............
...O................O................O................O.............
....O................O................O................O............

...many blank rows, then repeat the above a total of 4 times...
\$\endgroup\$
4
  • \$\begingroup\$ How is this so fast?! For n=20, the computation takes about 1 second even though the array has size 1,313,852,399. \$\endgroup\$
    – xnor
    Apr 26 '20 at 6:36
  • \$\begingroup\$ @xnor I was a little shocked by how fast it is as well. But see what it does: A) generate an array of 20**2=400 strings 20**3+20=8020 elements long, similar to the block for n=4 shown above. B) generate a string of 8020 periods, and make an array of 8020 pointers to this string. C) take the whole thing, and make 20 copies of all the pointers. D) join the array elements into a string with the operation *$/ (where $/ is a special variable preinitialized to newline) and return the combined string. Only in step D do we have to handle the 20*(400+8020) lines of 8020 characters. \$\endgroup\$ Apr 26 '20 at 10:31
  • \$\begingroup\$ @xnor To show that we work at the pointer level until the very end, try the following program. You will find every identical line in the output is modified with an X at the begining. n=4;j=n**3+n;s=((0...n*n).map{|i|((?.*n*n+?O)*9)[~i%n+i/n*n,j]}+[?.*j]*j)*n;s[17][0]=?x;puts s*$/ Note that comments have additional control characters inserted in them at end of line so if you copy and paste code from comments you have to remove the formatting before running. \$\endgroup\$ Apr 26 '20 at 10:36
  • \$\begingroup\$ also the code as written doesn't produce the correct result for n>8. The constant 9 needs to be at least n+1, but this can be fixed for 1 or 2 more bytes; for arbitary sized n use -~n. The question specifically asked up to n=8 so I left it like this. \$\endgroup\$ Apr 26 '20 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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