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.
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).
arutar 4 hours ago [-]
More 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 1 hours ago [-]
You 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 16 hours ago [-]
I used CP-SAT to enumerate the solutions. A heuristic for "interesting" solutions is those which only admit one valid bishop placement. For example:
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 2 hours ago [-]
ciao, Alex(https://rutar.org/) sent me a super cool visualization of the solutions and I added it.
NooneAtAll3 16 hours ago [-]
is there a solution where all the pieces are covered as well?
arutar 4 hours ago [-]
Unfortunately there are none
tromp 18 hours ago [-]
> The task is to place four black queens and one black bishop on the chessboard so that there is no square not under their attack. In other words, after arranging the five black pieces, it must be impossible to place the white king anywhere without it being in checkmate.
That last word should be "check". not "checkmate". A king next to an unprotected queen will be in check but not checkmate as it can capture the queen.
bryanrasmussen 5 hours ago [-]
well there are all sorts of irregularities in the stated puzzle, since you cannot move into check or checkmate it follows that you should not be able to place it on the board and have it be in those conditions.
However let us suppose that you can place it on the board and have it be in either check or checkmate.
If it has been placed on the board and it is in check, since it cannot move into check it follows that it is the king's move. If it can move out of check by taking a piece or another way of moving it is not in checkmate, this seems a pretty weird trick then, because it is not so interesting that you can place the king on the board and it will be in check and it is the king's move to get out of check.
If it can get out of check by taking an unprotected queen then it is again not very interesting, and why would I not just put the king on one of those positions and take the queen from the first.
If I cannot put it on the board without it being in checkmate, it must mean that the placing it on the board is itself the move, and you cannot move into checkmate, but if placing it on the board is the move then it follows you can take a queen with that move if you can place the king anywhere on the board.
The phrasing of the puzzle is inadequate, it seems.
Someone 3 hours ago [-]
> If it can get out of check by taking an unprotected queen then it is again not very interesting
I don’t see why that would be uninteresting. Before analyzing this, it isn’t clear that there is no way to place four black queens and a black bishop on the board in such a way that they attack all blank squares _and_ defend each other against capture.
If that were the case, the puzzle where you have to find a setup where you cannot place a king on the board without it being in check is easier than the one where you have to find a setup where you cannot place a king on the board without it being in checkmate.
Also, if you interpret the puzzle description in the latter way (and that, I think, is the most natural way to do it), it seems the puzzle doesn’t have a solution (https://news.ycombinator.com/item?id=48129115)], so do you think this puzzle is not very interesting?
jhncls 17 hours ago [-]
Although unlikely, maybe there exists a solution where all black pieces are protected?
yunwal 15 hours ago [-]
If there is, it's not listed as the solution on the puzzle website
nojs 15 hours ago [-]
Yeah, the solution given is actually wrong as stated!
chongli 12 hours ago [-]
That assumes you can place the king on the board and move immediately. I think the puzzle assumes you can’t do that; that placing your king on the board is your move, thus ending your turn.
billforsternz 12 hours ago [-]
The wording is very unambiguous, it means something very specific in chess. In every legal chess position either White is checkmated or Black is checkmated or (by far the most common except in film and TV!) neither side is checkmated. So the wording is crystal clear, you should be able to freely place the White king on any of the unoccupied 59 squares and the position will be one of those in which White is checkmated.
A real shame, this totally ruined the puzzle for me as it seemed so unlikely that all five Black pieces would be mutually protected. I should have forced myself to ignore the faulty clause and try to solve without it. The bad clause is also completely unnecessary - one of those cases where deleting text (or code!) is an improvement with no downside!
Timwi 6 hours ago [-]
I'd argue that if you remove the clause you still have the same issue. The problem statement says, “so that there is no square not under their attack”, which in my reading includes the squares occupied by the pieces, and a piece cannot attack itself.
wavemode 11 hours ago [-]
There's no legal way to reach a chess position where a king is in check or checkmate and it's not the king's turn to move.
11 hours ago [-]
Scarblac 7 hours ago [-]
You can only be in check or checkmate when it's your turn though.
hammock 13 hours ago [-]
The trick for me was to place a queen (most anywhere, but start with a corner it’s easier), then check and look for the spot with the most reds around it (eg 9, or 8, or 7), place the next queen there, repeat. Then place the bishop as needed.
The key was realizing the proximal spaces next to the placed queen are the most important to cover. Forget about trying to have a long reach, it comes naturally.
HarHarVeryFunny 3 hours ago [-]
What's the logic for putting the initial queen in a corner rather than using the same heuristic as for the remaining places?
gw32 60 minutes ago [-]
I was wondering that too. One would think that with a greedy approach, 1 square diagonally from the corner would be better. (But that doesn't work as well.)
Wow, this is really the cheatsheet of this game! It worked like a charm! Appreciate it
r3trohack3r 13 hours ago [-]
I was skeptical but, this not only worked the first time I tried it, this strategy has worked every time.
CamelCaseName 12 hours ago [-]
Wow!! That was awesome, great explanation too!
arutar 2 hours ago [-]
Thanks for sharing such an entertaining problem!
Bonus problem: find an arrangement of 4 queens on the board such that:
1. There is exactly 1 square on which a bishop can be placed, such that the 4 queens and the bishop attack all unoccupied squares
AND
2. There is exactly 1 square on which a rook can be placed, such that the 4 queens and the rook attack all unoccupied squares
Amazingly, modulo rotation / reflection, this problem has exactly 1 solution.
sowpati 4 hours ago [-]
Thanks for this OP. Really enjoyed finding solutions, and of course reading comments about all crazy looking solutions as well. This is the stuff that keeps me hooked to HN!
I remember being given another puzzle in my childhood, where the task was to put 8 queens on the board and none of them should "see" each other. Wonder how many solutions exist for that one..
> In other words, after arranging the five black pieces, it must be impossible to place the white king anywhere without it being in checkmate.
I think this is a bit ambiguous and, strictly speaking, wrong for the solution as given.
In particular, this asks for the king to be in check _mate_. Does this require all black pieces to defend each other? Otherwise, white king on the board would not be in checkmate if you place it next to a queen and can immediately capture.
From the solution, you can see it's not a checkmate requirement, just a check requirement.
tantalor 19 hours ago [-]
Really nice but I wish I didn't have to click "Check" every time after moving the pieces. It could do that automatically.
hatthew 16 hours ago [-]
I put `setInterval(checkBoard, 100)` in the console to do it automatically.
xdennis 10 hours ago [-]
I think that's intentional as in chess you're supposed to come up with the solution without feedback. The puzzle predates computers.
pimlottc 16 hours ago [-]
Please don’t use red and green for the colors in the “check” mode, it’s hard to tell apart for colorblind people (especially against the partially shaded black squares).
In fact, there isn’t really a need for two colors. Just color the squares that are threatened by the pieces and leave the rest blank. The meaning will be obvious.
layer8 4 hours ago [-]
> This is one of the most difficult among those problems.
I didn’t find it that difficult. A good (?) guess is that the queens would be in (rotational) symmetry, and hence form a square. To maximize coverage, the angle of course is neither 90° nor 45°, and the queens will have a minimum distance of 3 from each other. Going from smallest distance possible between queens to largest, one tries (3, 1), (3, 2), (4, 1), done. One might not notice that (4, 1) works (which happened to me), because it only works when the square is at the edge of the playing field. But the next one, (4, 2), works unconditionally. Or going from largest to smallest, one tries (6, 1), (5, 2), (5, 1), (4, 3), (4, 2), done.
hatthew 16 hours ago [-]
I solved it with this, a pleasingly symmetric solution. I was surprised that a solution exists with all the queens in a row.
More surprising to me is that there's a solution with no pieces on black.
archargelod 15 hours ago [-]
I found this solution (actually, it's 4 solutions, each B is a different Bishop placement and at the same time it's the only 4 spots on the board not covered by queens):
I started with 4 queens placed symmetrically on c7,g6,f2,b3, which covers everything except corners. Then I shifted all of them diagonally, i.e. to d6,h5,g1,c2. And it turns out, then only a8 and b7 are not covered, which can be easily solved by placing bishop anywhere at diagonal, e.g. h1.
tiffanyh 4 hours ago [-]
This is an interesting test for LLMs.
- ChatGPT was able to solve it in 6 seconds.
- Opus exhausted my entire days token limit on the problem & didn’t solve it.
mankyd 3 hours ago [-]
Is it? Or has ChatGPT read the answer before.
tiffanyh 3 hours ago [-]
As an end user, does it even matter?
You just want the answer.
mankyd 3 hours ago [-]
It matters if you're going to call it an "interesting test".
3 hours ago [-]
vprcic 4 hours ago [-]
A related puzzle - find a solution using a standard set of chess pieces minus the pawns. So a king, a queen and a pair of rooks, bishops and knights. That seems like a fun puzzle given a standard set of chess pieces. And to remove any doubt - it is a solvable! You can even remove one bishop and still find a solution, but that seems to be the only piece you can do it without.
gw32 58 minutes ago [-]
Neat puzzle, juggling between local and long-range effects. It's surprising how often the bishop gets in the way.
keeganpoppen 31 minutes ago [-]
damn that is hard
3 hours ago [-]
wrqvrwvq 17 hours ago [-]
fun demo. could be a daily puzzle combining various commenter suggestions. There are (didn't verify personally) 388 solutions. The daily puzzle could remove 1+ pieces and ask for a 1+ move guess.
Also a click on a square could auto place a queen and a second click would swap to the bishop. Every click could auto-check.
A separate discovery mode could start blocking out the squares visually as you place pieces. For a lot of people, that would be easier than the mental representation.
edit: Its almost the exact same solution to the one provided lol
coherentpony 15 hours ago [-]
> The task is to place four black queens and one black bishop on the chessboard so that there is no square not under their attack
> In other words, after arranging the five black pieces, it must be impossible to place the white king anywhere without it being in checkmate.
These two sentences mean very different things in the normal rules of chess. And if you replace the word “checkmate” with the word “check” in the second sentence it still doesn’t mean the same thing as the first sentence.
The first sentence implies that all the pieces must be defended.
Edit: Eh, I guess it depends on how you view the word “attack” since all the pieces are the same colour.
c4kar 18 hours ago [-]
That was an experience. Thank you
Trufa 16 hours ago [-]
Mildly related, if anyone want another chess minigame (I did this just in case).
I've definitely seen this puzzle before. of course I can't recall where
pkoiralap 32 minutes ago [-]
[dead]
ra0x3 18 hours ago [-]
Wait, the instructions are a little ambiguous. I clicked "Solution" and it has the dark-squared bishop on a white square! XD
Should maybe update the instructions to clarify that the dark-squared bishop is not constrained to dark squares.
loganc2342 18 hours ago [-]
It's a black bishop, but not necessarily a dark-squared bishop. Both the black side and white side in a normal chess game get a dark-squared and a light-squared bishop, and I don't see anywhere that specifies which type this one is. It can be either one depending on where you place it.
sltkr 16 hours ago [-]
Also if you care that much just mirror the solution horizontally or vertically, and now your bishop is on the white square instead.
danbrooks 18 hours ago [-]
The instructions likely mean that the bishop itself is black, not the square that it is on.
dwa3592 17 hours ago [-]
that's exactly what happened to me. I ended up spending so much time thinking black bishop can only go to black squares. and agreed this is a bit ambiguous.
maest 16 hours ago [-]
You can rotate any solution by 90 degrees, which would toggle the square colour of your bishop, so it doesn't ultimately matter.
fsckboy 12 hours ago [-]
>thinking black bishop can only go to black squares. and agreed this is a bit ambiguous
sorry, "The task is to place four black queens and one black bishop on the chessboard" is not at all ambiguous.
12 hours ago [-]
NooneAtAll3 16 hours ago [-]
> The task is to place four black queens and one black bishop on the chessboard
where did you read "dark-squared"?
sdsd 11 hours ago [-]
I've been playing a lot of Go lately and it's lowkey ruined chess for me. I ended up uninstalling Lichess because I simple don't use it anymore. Nothing against chess, just my personal taste.
My friend code on BadukPop is EGVNY if anyone wants to play together!
Python script: 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).
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.
That got me down to 6 free spaces.
That last word should be "check". not "checkmate". A king next to an unprotected queen will be in check but not checkmate as it can capture the queen.
However let us suppose that you can place it on the board and have it be in either check or checkmate.
If it has been placed on the board and it is in check, since it cannot move into check it follows that it is the king's move. If it can move out of check by taking a piece or another way of moving it is not in checkmate, this seems a pretty weird trick then, because it is not so interesting that you can place the king on the board and it will be in check and it is the king's move to get out of check.
If it can get out of check by taking an unprotected queen then it is again not very interesting, and why would I not just put the king on one of those positions and take the queen from the first.
If I cannot put it on the board without it being in checkmate, it must mean that the placing it on the board is itself the move, and you cannot move into checkmate, but if placing it on the board is the move then it follows you can take a queen with that move if you can place the king anywhere on the board.
The phrasing of the puzzle is inadequate, it seems.
I don’t see why that would be uninteresting. Before analyzing this, it isn’t clear that there is no way to place four black queens and a black bishop on the board in such a way that they attack all blank squares _and_ defend each other against capture.
If that were the case, the puzzle where you have to find a setup where you cannot place a king on the board without it being in check is easier than the one where you have to find a setup where you cannot place a king on the board without it being in checkmate.
Also, if you interpret the puzzle description in the latter way (and that, I think, is the most natural way to do it), it seems the puzzle doesn’t have a solution (https://news.ycombinator.com/item?id=48129115)], so do you think this puzzle is not very interesting?
A real shame, this totally ruined the puzzle for me as it seemed so unlikely that all five Black pieces would be mutually protected. I should have forced myself to ignore the faulty clause and try to solve without it. The bad clause is also completely unnecessary - one of those cases where deleting text (or code!) is an improvement with no downside!
The key was realizing the proximal spaces next to the placed queen are the most important to cover. Forget about trying to have a long reach, it comes naturally.
Bonus problem: find an arrangement of 4 queens on the board such that:
1. There is exactly 1 square on which a bishop can be placed, such that the 4 queens and the bishop attack all unoccupied squares
AND
2. There is exactly 1 square on which a rook can be placed, such that the 4 queens and the rook attack all unoccupied squares
Amazingly, modulo rotation / reflection, this problem has exactly 1 solution.
I remember being given another puzzle in my childhood, where the task was to put 8 queens on the board and none of them should "see" each other. Wonder how many solutions exist for that one..
ETA: Apparently it's a classic puzzle, and there are 92 solutions - https://en.wikipedia.org/wiki/Eight_queens_puzzle
I think this is a bit ambiguous and, strictly speaking, wrong for the solution as given.
In particular, this asks for the king to be in check _mate_. Does this require all black pieces to defend each other? Otherwise, white king on the board would not be in checkmate if you place it next to a queen and can immediately capture.
From the solution, you can see it's not a checkmate requirement, just a check requirement.
In fact, there isn’t really a need for two colors. Just color the squares that are threatened by the pieces and leave the rest blank. The meaning will be obvious.
I didn’t find it that difficult. A good (?) guess is that the queens would be in (rotational) symmetry, and hence form a square. To maximize coverage, the angle of course is neither 90° nor 45°, and the queens will have a minimum distance of 3 from each other. Going from smallest distance possible between queens to largest, one tries (3, 1), (3, 2), (4, 1), done. One might not notice that (4, 1) works (which happened to me), because it only works when the square is at the edge of the playing field. But the next one, (4, 2), works unconditionally. Or going from largest to smallest, one tries (6, 1), (5, 2), (5, 1), (4, 3), (4, 2), done.
- ChatGPT was able to solve it in 6 seconds.
- Opus exhausted my entire days token limit on the problem & didn’t solve it.
You just want the answer.
Also a click on a square could auto place a queen and a second click would swap to the bishop. Every click could auto-check.
A separate discovery mode could start blocking out the squares visually as you place pieces. For a lot of people, that would be easier than the mental representation.
> In other words, after arranging the five black pieces, it must be impossible to place the white king anywhere without it being in checkmate.
These two sentences mean very different things in the normal rules of chess. And if you replace the word “checkmate” with the word “check” in the second sentence it still doesn’t mean the same thing as the first sentence.
The first sentence implies that all the pieces must be defended.
Edit: Eh, I guess it depends on how you view the word “attack” since all the pieces are the same colour.
https://knight-queen-game.netlify.app/
Should maybe update the instructions to clarify that the dark-squared bishop is not constrained to dark squares.
sorry, "The task is to place four black queens and one black bishop on the chessboard" is not at all ambiguous.
where did you read "dark-squared"?
My friend code on BadukPop is EGVNY if anyone wants to play together!