This gives me a message "Unavailable Due to the UK Online Safety Act" which sounds like nonsense for a blog post, but IANAL. Can anyone summarise the post, or suggest why there'd be a reason my online safety is compromised by it?
mdrzn 2 hours ago [-]
It's pretty clear that the issue is not the post, but the fact that you are in UK, and the site author does not deem you important enough.
The site author himself has blocked users from the UK because of that stupid law that you cite in your comment:
"The UK's Online Safety Act requires operators of 'user to user services' to read through hundreds (if not thousands) of pages of documentation to attempt to craft "meaningful" risk assessments and 'child access assessments' or face £18,000,000 fines, even imprisonment."
I set this as part of a Scala programming assignment for my second year undergraduate class at UNE (Australia) last term. However, during the working a square is not Queen | Eliminated but Set[Queen | NotQueen]
Largely so from a programming perspective it becomes a simplified version of Einstein's Riddle that I showed the class, doing in a similar way.
Awesome, I'm writing a "logical solver" just like this - I'll hopefully also have something to post here when I'm done.
I'm trying to use it during the generation process to evaluate the difficulty a basic heuristic I'm trying to work with is counting the number of times a particular colour is eliminated - the higher the count the harder the problem since it requires more iteration of the rules to solve. (A counter example to this would be a board with 1 colour covering everything except the cells a queen of the other colours needs to be placed on)
Also I'm trying to evaluate the efficacy of performing colour swaps but it's proving more challenging than I thought. The basic idea is you can swap the colours of neighbouring cells to line up multiple colours so there are less obvious "single cells" which contains the queen. The problem with this is it can introduce other solutions and it's difficult to tell whether a swap makes the puzzle harder or simpler to solve.
b0a04gl 41 minutes ago [-]
how would you encode a constraint system where the generator must yield exactly one solution and that solution remains unique under all transformations in the problem’s symmetry group, without relying on post-solution filtering or external isomorphism checks?
mzl 34 minutes ago [-]
Directly modelling the unique solution property would be a quantified problem, essentially it would be "there exists a solution such that it is not the case that there exists a different solution". In principle, you can explode this into an enumeration of all O(n!) placements of queens and saying "either the placement is the same as the solution, or it is not a solution". That significantly increases the model size though.
For the symmetry, LinkedIn Queens generally do not have symmetric boards since that would imply more than one solution.
roland35 3 hours ago [-]
Just when I start thinking I am smart, someone drops this :) Haskell certainly looks graceful but is imposing! I feel pretty good if I can do functional stuff in Rust, but this is next level.
agnishom 3 hours ago [-]
You should write a "Solving LinkedIn Queens with Rust" post :)
LandR 5 hours ago [-]
Does anyone know of any algorithms for generating these game boards ?
That will produce challenging boards ?
CJefferson 5 hours ago [-]
It's a hard problem, for a bunch of reasons :)
1) It's not too hard to make a problem with at least one solution (just put the queens down first, then draw boxes), but there isn't any good way of making levels with unique solutions.
2) Once you've accomplished that, it's hard to predict how hard a level will be, and then it's hard to make levels easier / harder.
I happen to be currently researching this topic (well, I'm doing all kinds of these grid-based puzzles, but this is an example). The algorithm tries to make "good" levels, but there is a good probability it will end up with something useless we need to throw away, and then try again.
It's easy to make levels which are trivial, and similarly easy to make levels which are far beyond human ability, but hitting things in the 'human tricky but solvable' sweet-spot is where most of the difficulty comes from.
I should probably try writing up a human-readable version of how I do it. It involves a bunch of Rust code, so I can hit a whole bunch of trendy topics!
slig 37 minutes ago [-]
> I should probably try writing up a human-readable version of how I do it. It involves a bunch of Rust code, so I can hit a whole bunch of trendy topics!
Do you have a blog? I'm interested.
vjerancrnjak 4 hours ago [-]
Given that this could be a variant of "exact cover", using zdds to explore the problem space might simplify finding exact puzzles in addition to puzzles that require lookahead.
mzl 4 hours ago [-]
Generally what is needed is a subroutine that can tell you 1) if the problem has a solution, and 2) if the solution is unique (common requirement for puzzles like these). Using such a model as a sub-routine, a heuristic search can be done to gradually build up puzzles. If your solver technology of choice can handle quantified problems, that could be used to integrate those two problems into one, but that is quite a lot harder to to.
If the base solver you have is a system that can be run in various configurations with different levels of reasoning and assumption as well as a report on the amount of search needed if any, that can be very useful as a way to measure the hardness. In Sudoku as a Constraint problem (https://citeseerx.ist.psu.edu/document?doi=4f069d85116ab6b4c...), Helmut Simonis tested lots of 9x9 Sudoku puzzles against various levels of propagation and pre-processing as a way to measure the hardness of Sudoku puzzles by categorizing them by the level of reasoning needed to solve without search. The MiniZinc model for LinkedIn Queens (https://news.ycombinator.com/item?id=44353731) can be used with various solvers and levels of propagation as such a subroutine.
Now, for production-level puzzle making, such as what King does for Candy Crush, the problems and requirements are even harder. I've heard presentation where they talk about training neural networks to play like human testers, so not optimal play but most human like play, in order to test the hardness level of the puzzles.
tikotus 3 hours ago [-]
It's the same problem as with generating good sudoku boards. It's not easy, and there's not many publicly available solutions, but solutions exist.
A common opinion is that a good board is solvable without the use of backtracking. A set of known techniques should be enough to solve the board. To validate if a board is "fun" you need to have a program that can solve the board using these known techniques. Making that program is much harder than just making a general solver. And then you need to find the boards that can be validated as fun. Either you search through random boards, or you get clever...
Macuyiko 3 hours ago [-]
I've noticed that puzzles that can be solved with CP-SAT's presolver so that the SAT search does not even need to be invoked basically adhere to this (no backtracking, known rules), e.g.:
#Variables: 121 (91 primary variables)
- 121 Booleans in [0,1]
#kLinear1: 200 (#enforced: 200)
#kLinear2: 1
#kLinear3: 2
#kLinearN: 30 (#terms: 355)
Presolve summary:
- 1 affine relations were detected.
- rule 'affine: new relation' was applied 1 time.
- rule 'at_most_one: empty or all false' was applied 148 times.
- rule 'at_most_one: removed literals' was applied 148 times.
- rule 'at_most_one: satisfied' was applied 36 times.
- rule 'deductions: 200 stored' was applied 1 time.
- rule 'exactly_one: removed literals' was applied 2 times.
- rule 'exactly_one: satisfied' was applied 31 times.
- rule 'linear: empty' was applied 1 time.
- rule 'linear: fixed or dup variables' was applied 12 times.
- rule 'linear: positive equal one' was applied 31 times.
- rule 'linear: reduced variable domains' was applied 1 time.
- rule 'linear: remapped using affine relations' was applied 4 times.
- rule 'presolve: 120 unused variables removed.' was applied 1 time.
- rule 'presolve: iteration' was applied 2 times.
Presolved satisfaction model '': (model_fingerprint: 0xa5b85c5e198ed849)
#Variables: 0 (0 primary variables)
The solution hint is complete and is feasible.
#1 0.00s main
a a a a a a a a a a *A*
a a a b b b b *B* a a a
a a *C* b d d d b b a a
a c c d d *E* d d b b a
a c d *D* d e d d d b a
a f d d d e e e d *G* a
a *F* d d d d d d d g a
a f f d d d d d *H* g a
*I* i f f d d d h h a a
i i i f *J* j j j a a a
i i i i i k *K* j a a a
Together with validating that there is only 1 solution you would probably be able to make the search for good boards a more guided than random creation.
The site author himself has blocked users from the UK because of that stupid law that you cite in your comment: "The UK's Online Safety Act requires operators of 'user to user services' to read through hundreds (if not thousands) of pages of documentation to attempt to craft "meaningful" risk assessments and 'child access assessments' or face £18,000,000 fines, even imprisonment."
Largely so from a programming perspective it becomes a simplified version of Einstein's Riddle that I showed the class, doing in a similar way.
https://theintelligentbook.com/willscala/#/decks/einsteinPro...
Where at each step, you're just eliminating one or more possibilities from a cell that starts out containing all of them.
Queens has fewer rules to code, making it more amenable for students.
- with SMT (11 days ago, 47 comments) https://news.ycombinator.com/item?id=44259476
- with APL (10 days ago, 1 comment) https://news.ycombinator.com/item?id=44273489 and (8 days ago, 20 comments) https://news.ycombinator.com/item?id=44275900
- with MiniZinc (1 day ago, 0 comment) https://news.ycombinator.com/item?id=44353731
I'm trying to use it during the generation process to evaluate the difficulty a basic heuristic I'm trying to work with is counting the number of times a particular colour is eliminated - the higher the count the harder the problem since it requires more iteration of the rules to solve. (A counter example to this would be a board with 1 colour covering everything except the cells a queen of the other colours needs to be placed on)
Also I'm trying to evaluate the efficacy of performing colour swaps but it's proving more challenging than I thought. The basic idea is you can swap the colours of neighbouring cells to line up multiple colours so there are less obvious "single cells" which contains the queen. The problem with this is it can introduce other solutions and it's difficult to tell whether a swap makes the puzzle harder or simpler to solve.
For the symmetry, LinkedIn Queens generally do not have symmetric boards since that would imply more than one solution.
That will produce challenging boards ?
1) It's not too hard to make a problem with at least one solution (just put the queens down first, then draw boxes), but there isn't any good way of making levels with unique solutions.
2) Once you've accomplished that, it's hard to predict how hard a level will be, and then it's hard to make levels easier / harder.
I happen to be currently researching this topic (well, I'm doing all kinds of these grid-based puzzles, but this is an example). The algorithm tries to make "good" levels, but there is a good probability it will end up with something useless we need to throw away, and then try again.
It's easy to make levels which are trivial, and similarly easy to make levels which are far beyond human ability, but hitting things in the 'human tricky but solvable' sweet-spot is where most of the difficulty comes from.
I should probably try writing up a human-readable version of how I do it. It involves a bunch of Rust code, so I can hit a whole bunch of trendy topics!
Do you have a blog? I'm interested.
If the base solver you have is a system that can be run in various configurations with different levels of reasoning and assumption as well as a report on the amount of search needed if any, that can be very useful as a way to measure the hardness. In Sudoku as a Constraint problem (https://citeseerx.ist.psu.edu/document?doi=4f069d85116ab6b4c...), Helmut Simonis tested lots of 9x9 Sudoku puzzles against various levels of propagation and pre-processing as a way to measure the hardness of Sudoku puzzles by categorizing them by the level of reasoning needed to solve without search. The MiniZinc model for LinkedIn Queens (https://news.ycombinator.com/item?id=44353731) can be used with various solvers and levels of propagation as such a subroutine.
Now, for production-level puzzle making, such as what King does for Candy Crush, the problems and requirements are even harder. I've heard presentation where they talk about training neural networks to play like human testers, so not optimal play but most human like play, in order to test the hardness level of the puzzles.
A common opinion is that a good board is solvable without the use of backtracking. A set of known techniques should be enough to solve the board. To validate if a board is "fun" you need to have a program that can solve the board using these known techniques. Making that program is much harder than just making a general solver. And then you need to find the boards that can be validated as fun. Either you search through random boards, or you get clever...