11–20 of 22 posts
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
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.
And these colored regions can be of any size.
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.
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 ca…
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. And these colored regions can be of any size.
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 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
This is exactly it. Queens is an “under two minutes” version.
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 ca…
How are you generating the boards?
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.
Earlier quoted context omitted.
> is it possible to create a board that has multiple valid solutions? Some simple boards like 11111111 22222222 33333333 44444444 55555555 66666666 77777777 88888888 or 11112222 11112222 33334444 33334444 55556666 55556666 77778888 77778888 have many solutions.
Thank you! Can't believe I didn't think of this