4 ms·
Neat. Surprisingly, there are 388 solutions, and a lot of them look rather unintuitive. ........ ...Q.... ........ ........ .....Q.. ..
by dllu 5mo ago
Neat. Surprisingly, there are 388 solutions, and a lot of them look rather unintuitive.
........
...Q....
........
........
.....Q..
........
........
Q..B..Q.
Q.......
........
........
........
..QQB..Q
........
........
........
My original intuition was to place the queens on unique rows and columns to cover as much as possible but it turns out there are solutions with three of them on the same row.
Python script: https://gist.github.com/dllu/698d5f71b2b9735c5c462ddf4a2f6fcf https://gist.github.com/dllu/698d5f71b2b9735c5c462ddf4a2f6fc...
Here's how it works:
0. precompute the attack patterns of each possible queen/bishop location as a bitmask, stored as an integer
1. generate candidate solutions, allowing attack rays to pass through other pieces, by brute forcing the positions of the 5 pieces and taking the bitwise OR of their attacks
2. out of the candidate solutions, check which ones are actually valid taking into account occlusion. Actually, you only need to check if the queen's horizontal attack is blocked by the bishop, as queens cannot block each other (the blocking queen herself has the same attacks so they effectively pass through each other).
- NooneAtAll3 5mo agois there a solution where all the pieces are covered as well?
- arutar 5mo agoUnfortunately there are none
- sobellian 5mo agoI used CP-SAT to enumerate the solutions. A heuristic for "interesting" solutions is those which only admit one valid bishop placement. For example: ........ Q..B..Q. ........ ........ .......Q ........ ........ ...Q.... Where the bishop lies at the intersection of three queens' horizontal attacks. With these queens, no other bishop placement works.
- aaron695 5mo ago[dead]
- JKCalhoun 5mo agoI also tried the "place the queens on unique rows and columns". That got me down to 6 free spaces.
- arutar 5mo agoMore fun facts: After identifying solutions up to rotation and reflection there are only 49 solutions. No solutions have rotational symmetry, and there is exactly one solution with reflection symmetry (already mentioned by an earlier commenter). Out of the 49 solution classes, there are 18 distinct queen layouts. The layouts have between 1 and 5 ways to place the bishop to complete the solution. Interestingly, there is exactly one queen layout (up to rotation / reflection) for which there are exactly 2 ways to place the bishop to complete the puzzle.
- dllu 5mo agoYou can't have rotational symmetry with 5 pieces since that would require a piece in the center but the chess board has an even number sized.
- sobellian 5mo agoEven more fun facts: if you change the problem instead to 4 queens and one knight, there is exactly one solution up to symmetries (rotations and flipping). Here it is: ..N..... ........ ........ ....Q... .....Q.. ...Q.... ......Q. ........ Edit: even more fun facts: if we take the standard piece values of Q=9, R=5, B/N=3, then we can ask for the smallest piece budget that attacks every square. The cheapest possible configuration is 24 points, you can see one with 8 bishops: ........ ....B... ....B... .B...... ...B.B.. .....B.. ..B..... ....B... Which has pleasing symmetry when you view it as a composition of light-square bishops and dark-square bishops.
- keeganpoppen 5mo agowow. oddly that seems like an easier problem, despite the solution space being smaller. not saying i woulda solved that, because i doubt it, but it’s much closer to what my raw intuition woulda spit out as a solutuon to the OG problem.
- LeifCarrotson 5mo agoIt's a bit disappointing, then, that the page's action on clicking the "solution" button is just to set the pieces to: const solution = { a8: "b1", b8: "q1", f7: "q2", a4: "q3", e3: "q4" }; It would be cool if it randomly selected one of those 388, so you could click repeatedly and develop an intuition for what kinds of distributions were a valid solution.
- Eswo 5mo agociao, Alex(https://rutar.org/ https://rutar.org/) sent me a super cool visualization of the solutions and I added it.
- keeganpoppen 5mo agoyeah i had that same intuition and then realized that you _have_ to have pieces that overlap responsibility to fully “cover”. amazing puzzle. i can’t claim i solved it, because i didn’t, but i did give it 15 minutes of focused time, which is pretty good.