17
1
(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
AdmBorkBork
Posted 2017-07-21T14:03:59.523
Reputation: 41 581
Read the number of queens, q, from stdin and calculate two variables for later use: 
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:
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 
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.
1Related. – totallyhuman – 2017-07-21T14:07:26.230
1Could you give testcases for odd inputs? – user41805 – 2017-07-21T14:13:29.317
@Cowsquack Added n=7 example – AdmBorkBork – 2017-07-21T14:32:13.503
@KeyuGan Neither of those have the [tag:code-golf] tag, so I don’t think they’re even candidate dupes – Lynn – 2017-07-21T14:59:26.617
Could we output an array of number instead of an array of characters? – Keyu Gan – 2017-07-21T15:57:14.893
1@KeyuGan Something like the MATL answer? Yeah, that's fine. – AdmBorkBork – 2017-07-21T16:02:28.887
@AdmBorkBork was "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." meant to exclude non-deterministic solutions such as loop-with-random-permute&check? – Jonathan Allan – 2017-07-21T18:43:57.630
2@JonathanAllan No such exclusion was intended, so long as the program finishes in finite time with probability one (as standard for all submissions). – AdmBorkBork – 2017-07-21T18:45:18.770
Are one of these the relevant oeis sequence?
– programmer5000 – 2017-07-22T10:36:43.313@programmer5000 The first result, A000170, is the relevant problem in that it tells how many solutions exist, but none of OEIS gives the actual board positions, which is what this question is asking. – AdmBorkBork – 2017-07-23T14:29:17.303