I know this puzzle as "Star Battle" where I play it here: https://www.puzzle-star-battle.com where my favorite difficulty for a nice medium difficulty is "Normal 10x10 2 stars"
The LinkedIn Queens seems to be a much easier version of this puzzle.
I've been implementing a bare metal APL Assembly kernel on mac arm and have been surprised at the resurgence of interest in languages like it. I think people are in general thinking about symbol representation/compression to a fundamental level for these performance gains. It's been fun to try and hack AMX implementation and couldn't do any of it without the shoulders of giants / Asahi linux project
I'm not hearing about it used much in industry outside of legacy applications like what Volvo has (not that I'm big in the community or anything lol). However, there does seem to be a lot of hobby interest that might eventually go somewhere. I'd like it to catch on as APL is so cool.
I've been writing a Queens clone, while I haven't gotten to the solver part I haven't been able to think up a good/clean way to write said solver. So this is super helpful for me to get some ideas on how a solver should work, and what are the minimum number of rules that the solver should obey (in Queens there are multiple rules that could apply to the same blocks and result in the same decision, but not all rules can be applied in all situations, so narrowing them down to the "axioms" seems difficult).
More of a Math question: I'm also wondering if there's any way to prove that all Queens boards have exactly 1 solution? In other words, is it possible to create a board that has multiple valid solutions?
Mathematician here. A standard trick is to look for counterexamples as simple as possible. A usual joke is that if the professor ask a question in a class, the answer is 0 or 1. (In physics, it's 0 or infinity.) If the very simple counterexample fails, you try to understand why and make a new counterexample that is slightly less simple and solves the problem. And then you iterate until you run out of counterexamples and has proved the theorem.
Not sure what the technical terms are but there's 2 phases -
1. Placing the queens, this is a pretty basic DFS over all possible queen positions. You can visualise it by going across the board row by row and placing the queen in a random available column, then moving to the next row and placing a queen in a random available column. So for an 8x8 board with 8 queens, the 1st row has 8 possible columns, the second row has 5 possible columns, the third has 4, and so on until all the queens have been placed or there are no available cells to place the next queen on.
2. Generating the colours - This is a bit more complicated but it is essentially a flood fill with each queen as a source block. I keep an adjacency list for each colour containing the uncoloured cells it borders. At each iteration I pick a random queen/colour and a random cell from the adjacency list, then fill that cell and update the adjacency list (and remove the cell from other adjacency lists).
I'm planning on updating my colour generation algorithm to support 2 things: 1. Generating boards with unique solutions only (not sure how I'll do this without finding all the solutions). And 2. including known shapes in the generation process so there is a random chance colours takes on specific shapes (e.g. +) and the other colours will generate around them.
This tempted me into figuring out a solution from scratch, without looking at the APL version, because the stepwise iteration toward a solution for this is quite fun. (This also made me think about when we got the n-queens problem to work on at uni, and I wrote a solution in Amiga E)
To consider a solver, start with the stupid-simple option:
Step 1. For each open square, copy the board, place a queen there, and recursively call the solver until an option results in 8 placed queens. This will obviously work, but is about as bad as the solution can get. Starting with this means you have an easy test case for every improved version.
To make it better, you want to bail out of that recursion as early and often as you can.
Step 2. Sort the regions by number of open squares, and iterate over the open squares from least-number-of-possibilities to most.
This will naturally place queens for colors that have only one remaining open square first, folllowed by the ones where the odds of hitting the correct square is highest, and so will usually drive down the combinatorical explosion a lot.
Step 3. To improve on this further, at the start of the solve function, check if the board is in an invalid state. That is, the number of regions with open squares must match the number of queens yet to be placed.
This will prune any sub-trees you want to test that would place the board in an invalid state.
Any pruned sub-tree should then cause that square to be marked unavailable before you continue.
Step 4. At the start of the solver mark as many squares that can't have queens as possible. The set of rules you can apply here is pretty big, but you can probably make do with very few. E.g. simple to implement rules would include:
* if any color is present in only one row or column, mark all other squares (of other colors) in that row or column as unavailable.
* if any color is the only color present in a given row or column, mark all squares of that color in other rows / columns as unavailable.
(you can extend the first above to: if any open squares of n colors are present in the same n rows or columns, mark all other squares (of other colors) in those rows or columns as unavailable, but I'm not sure if that will cut down on the recursion enough to be worth the hassle)
There are probably much more elegant solutions, but I think I'd end up with something like this pseudo-code:
# Find a (possibly/likely incomplete) set of positions to mark as unavailable
# because they're either impossible due to the current position, or because you
# can place a queen with certainty
#
mark(board)
while changes during execution:
for each color without placed queen:
if open squares in only one row, mark all other squares of other colors in that row unavailable
if open squares in only one column, mark all other squares of other colors in that column unavailable
for each row/for each column: if only one color has open square, place queen.
# Apply more rules here if you should need it; my hunch - but it is a hunch only - is that the above will prune the tree enough
return true if still open squares, false if no open squares.
# Check if the current board is invalid. That is, each color without a placed
# queen must still have at least one open square.
#
invalid(board):
for each color without placed queen:
if no open square of this color, then return true
return false
pick_square(board):
color = color with the smallest number of open squares.
return first open square for "color"
solve(board):
while mark(board) and not invalid(board)
square = pick_square(board)
copy board.
place queen on the chosen square on the copied board.
if solve(copied board) returned solution, then return solution
else mark square unavailable.
if all queens placed, return solution,
else return unsolvable
Having looked at the APL solution, I now feel an urge I must try to resist to write a real version and golf it down and see how close in size to the APL version I'd get with the above approach.
I’ve noticed that many of the hard boards have a “choke point” in the solution where there are a small number of places you can place a specific queen but the information needed to place it can be difficult to gather.
A hacky trick is to place a queen and then ask for a hint. If deployed well, you can use this short circuit the challenge and often solve the puzzle in a fraction of the time.
There isn’t any penalty for taking a hint beyond you’re locked out of your next hint for a period of time.
edit: since I'm continuing to get down-votes despite two separate retractions below: I already agreed I was wrong. Not like I can delete the comment.
Original comment below.
This is the "N queens problem", a classic that predates both the internet and LinkedIn. Renaming and attributing it as "LinkedIn Queens" in this article is distracting.
"LinkedIn Queens" is different from the classic n-queens problem, in that the queens do not threaten each other diagonally other than immediately adjacent, and secondly each board is split into not just rows and columns, but also colors and only 1 queen can be placed on each row, column, and color.
I know this puzzle as "Star Battle" where I play it here: https://www.puzzle-star-battle.com where my favorite difficulty for a nice medium difficulty is "Normal 10x10 2 stars"
The LinkedIn Queens seems to be a much easier version of this puzzle.
You can see the Cracking the Cryptic folks (of Miracle Sudoku fame) take on the puzzle here: https://www.youtube.com/watch?v=1KGraaDXP_0
> The LinkedIn Queens seems to be a much easier version of this puzzle.
This is exactly it. Queens is an “under two minutes” version.
I've been implementing a bare metal APL Assembly kernel on mac arm and have been surprised at the resurgence of interest in languages like it. I think people are in general thinking about symbol representation/compression to a fundamental level for these performance gains. It's been fun to try and hack AMX implementation and couldn't do any of it without the shoulders of giants / Asahi linux project
I'm not hearing about it used much in industry outside of legacy applications like what Volvo has (not that I'm big in the community or anything lol). However, there does seem to be a lot of hobby interest that might eventually go somewhere. I'd like it to catch on as APL is so cool.
I've been writing a Queens clone, while I haven't gotten to the solver part I haven't been able to think up a good/clean way to write said solver. So this is super helpful for me to get some ideas on how a solver should work, and what are the minimum number of rules that the solver should obey (in Queens there are multiple rules that could apply to the same blocks and result in the same decision, but not all rules can be applied in all situations, so narrowing them down to the "axioms" seems difficult).
More of a Math question: I'm also wondering if there's any way to prove that all Queens boards have exactly 1 solution? In other words, is it possible to create a board that has multiple valid solutions?
> is it possible to create a board that has multiple valid solutions?
Some simple boards like
or have many solutions.Thank you! Can't believe I didn't think of this
Mathematician here. A standard trick is to look for counterexamples as simple as possible. A usual joke is that if the professor ask a question in a class, the answer is 0 or 1. (In physics, it's 0 or infinity.) If the very simple counterexample fails, you try to understand why and make a new counterexample that is slightly less simple and solves the problem. And then you iterate until you run out of counterexamples and has proved the theorem.
How are you generating the boards?
Not sure what the technical terms are but there's 2 phases -
1. Placing the queens, this is a pretty basic DFS over all possible queen positions. You can visualise it by going across the board row by row and placing the queen in a random available column, then moving to the next row and placing a queen in a random available column. So for an 8x8 board with 8 queens, the 1st row has 8 possible columns, the second row has 5 possible columns, the third has 4, and so on until all the queens have been placed or there are no available cells to place the next queen on.
2. Generating the colours - This is a bit more complicated but it is essentially a flood fill with each queen as a source block. I keep an adjacency list for each colour containing the uncoloured cells it borders. At each iteration I pick a random queen/colour and a random cell from the adjacency list, then fill that cell and update the adjacency list (and remove the cell from other adjacency lists).
I'm planning on updating my colour generation algorithm to support 2 things: 1. Generating boards with unique solutions only (not sure how I'll do this without finding all the solutions). And 2. including known shapes in the generation process so there is a random chance colours takes on specific shapes (e.g. +) and the other colours will generate around them.
This tempted me into figuring out a solution from scratch, without looking at the APL version, because the stepwise iteration toward a solution for this is quite fun. (This also made me think about when we got the n-queens problem to work on at uni, and I wrote a solution in Amiga E)
To consider a solver, start with the stupid-simple option:
Step 1. For each open square, copy the board, place a queen there, and recursively call the solver until an option results in 8 placed queens. This will obviously work, but is about as bad as the solution can get. Starting with this means you have an easy test case for every improved version.
To make it better, you want to bail out of that recursion as early and often as you can.
Step 2. Sort the regions by number of open squares, and iterate over the open squares from least-number-of-possibilities to most.
This will naturally place queens for colors that have only one remaining open square first, folllowed by the ones where the odds of hitting the correct square is highest, and so will usually drive down the combinatorical explosion a lot.
Step 3. To improve on this further, at the start of the solve function, check if the board is in an invalid state. That is, the number of regions with open squares must match the number of queens yet to be placed.
This will prune any sub-trees you want to test that would place the board in an invalid state.
Any pruned sub-tree should then cause that square to be marked unavailable before you continue.
Step 4. At the start of the solver mark as many squares that can't have queens as possible. The set of rules you can apply here is pretty big, but you can probably make do with very few. E.g. simple to implement rules would include:
* if any color is present in only one row or column, mark all other squares (of other colors) in that row or column as unavailable.
* if any color is the only color present in a given row or column, mark all squares of that color in other rows / columns as unavailable.
(you can extend the first above to: if any open squares of n colors are present in the same n rows or columns, mark all other squares (of other colors) in those rows or columns as unavailable, but I'm not sure if that will cut down on the recursion enough to be worth the hassle)
There are probably much more elegant solutions, but I think I'd end up with something like this pseudo-code:
Having looked at the APL solution, I now feel an urge I must try to resist to write a real version and golf it down and see how close in size to the APL version I'd get with the above approach.I’ve noticed that many of the hard boards have a “choke point” in the solution where there are a small number of places you can place a specific queen but the information needed to place it can be difficult to gather.
A hacky trick is to place a queen and then ask for a hint. If deployed well, you can use this short circuit the challenge and often solve the puzzle in a fraction of the time.
There isn’t any penalty for taking a hint beyond you’re locked out of your next hint for a period of time.
Where do I find lightbulbs anywhere similar to ⍝ in appearance? It looks like a big toe.
edit: since I'm continuing to get down-votes despite two separate retractions below: I already agreed I was wrong. Not like I can delete the comment.
Original comment below.
This is the "N queens problem", a classic that predates both the internet and LinkedIn. Renaming and attributing it as "LinkedIn Queens" in this article is distracting.
It's not "N-Queens". It's "Star Battle": https://www.puzzle-star-battle.com/.
I see now, thank you!
"LinkedIn Queens" is different from the classic n-queens problem, in that the queens do not threaten each other diagonally other than immediately adjacent, and secondly each board is split into not just rows and columns, but also colors and only 1 queen can be placed on each row, column, and color.
And these colored regions can be of any size.
Thank you for correcting me, I see the distinction now.