Eight Queens Formatted

[MichalMarsalek]

https://code.golf/eight-queens-formatted

Description Print all solutions to the Eight queen problem.

Output

Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

Q.......
.....Q..
.......Q
..Q.....
......Q.
...Q....
.Q......
....Q...

...

[Bubbler-4]

Note: There are 92 distinct solutions in total, which can be generated by rotating and flipping 12 "root" solutions (one of which has 180deg symmetry). Each root solution can be encoded in several ways, some of which can be pretty short I think.

Reference: https://en.wikipedia.org/wiki/Eight_queens_puzzle#Constructing_and_counting_solutions_when_n_=_8

[lyphyser]

At least in Assembly and for the non-formatted version, hardcoding seems likely to be way worse than the very simple direct naive solution (loop for all possible non-formatted boards b, then loop i<j<=8 and check that b[i]-b[j] doesn't equal 0, i - j or j - i).

In Assembly my direct somewhat optimized solution is 67 bytes of which at least 30 bytes would be needed in an hardcoded solution too, plus at least 36=3*12 bytes to encode the root solutions, plus the code to read them and rotate/flip them in all possible ways (not cheap) and either produce them in the correct order or sort and deduplicate them (not trivial either).

In general I think rotating and flipping the board in all ways is generally probably harder or similarly expensive than checking it, and the 36+ byte penalty (higher in non-Assembly since you need to encode as valid UTF-8) plus the need to sort and deduplicate (or use an additional loop) seems to make hardcoding unlikely. .

[Bubbler-4]

I was thinking of J, which has builtins for generating a permutation from its index, and transposing and reversing matrices. The indices are small enough that 12 solutions can be encoded in 24 ASCII characters, though they do cost bytes to decode them.

K doesn't have permutation-related builtins, but decoding part is likely shorter in K than J. Didn't try hard enough yet.

[duckyluuk]

I really like this hole idea! Increasing the size to prevent hardcoding would indeed be nice, although I doubt its necessary for most languages. Maybe "Print all solutions to the N-Queen problem for n 4-10" could even be interesting?

Also, would it maybe make more sense to move it to the gaming or computing category, instead of mathematics? It feels somewhat out of place compared to the other holes in the category.

[Bubbler-4]

Multiple size is nice idea. That way you don't even need to go for larger sizes; 4-8 should be enough to discourage hardcoding. Adding 9 may make many viable approaches time out.

For the category, +1 for gaming.

[MichalMarsalek]

I opened a PR with sizes 4-8. Should the name stay as "Eight Queens"?

[Bubbler-4]

The generalized version is known as "N Queens problem", so that or simply "N Queens" looks good to me.