4 ms·

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 su

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?

gus_massa 1y ago
> 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.
- miningape 1y ago
  Thank you! Can't believe I didn't think of this
  - gus_massa 1y ago
    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.
vidarh 1y ago
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.
kjgkjhfkjf 1y ago
How are you generating the boards?
- miningape 1y ago
  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.

gus_massa 1y ago

> 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.

miningape 1y ago
Thank you! Can't believe I didn't think of this
- gus_massa 1y ago
  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.

vidarh 1y ago

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.

kjgkjhfkjf 1y ago

How are you generating the boards?

miningape 1y ago
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.