Essential insights from Hacker News discussions

Solving LinkedIn Queens Using Haskell

Here's a breakdown of the key themes in the Hacker News discussion about solving LinkedIn Queens puzzles, supported by direct quotes where appropriate:

Difficulty of Generating "Good" Puzzles

A major theme is the difficulty in designing algorithms that generate challenging, yet solvable, puzzles, especially those with unique solutions.

  • It's hard to create solvable puzzles with unique solutions: "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." (CJefferson)
  • Predicting and controlling difficulty is challenging: "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." (CJefferson)
  • Hitting the "sweet spot" is the key: "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." (CJefferson)
  • Good boards are solvable without backtracking: "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." (tikotus)

Techniques for Solving and Generating Puzzles

Several techniques are discussed, ranging from constraint satisfaction to heuristics.

  • Constraint Satisfaction and SAT solvers: "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)...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." (Macuyiko) This suggests that puzzles solvable by presolving in a SAT solver align with the "no backtracking" ideal.
  • Simulated Annealing: "Simulated annealing with a difficulty heuristic (like minimum required logical steps) works well - start with a valid solution, then randomly modify colors while maintaining uniqueness." (ethan_smith)
  • Heuristics and Rule-Based Solvers: One user is "writing a 'logical solver' just like this". and trying to evaluate the difficulty using a heuristic: "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." (miningape)
  • Using ZDDs: "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." (vjerancrnjak)

Measuring Puzzle Hardness

Several users discuss methods for assessing a puzzle's difficulty.

  • Levels of Reasoning: Referencing Helmut Simonis's work on Sudoku, one user suggests measuring "the hardness of Sudoku puzzles by categorizing them by the level of reasoning needed to solve without search." (mzl)
  • Search Needed: "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." (mzl)
  • Human-Like Play: For production-level puzzle generation, one suggestion is 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." (mzl)
  • Counting Elimination Steps: As described above, one user is experimenting with counting the number of times a particular color is eliminated.

Alternative Approaches

Several users recommend alternative approaches to puzzles. * Array approach: "Briefly, I'd have started with an array which for each colour had an array containing the coordinate pairs for that colour. I'd probably then have sorted by length of each array. The state also has an empty array for the coordinates of each placed queen." (ralferoo) * No board representation: "At no point would I actually have a representation of the board. That feels very imperative rather than functional to me." (ralferoo)

Tool Comparisons and Recommendations

The discussion mentions various tools and languages suitable for these types of problems. It also contains explicit tool recommendations.

  • Haskell: One user (sammycage) asked the original poster if they have tried benchmarking their "Haskell solver against an SMT solver (like Z3 or CVC5)."
  • Z3 and CVC5 (SMT Solvers): Mentioned as possible benchmarking tools for comparison to a Haskell solver
  • MiniZinc: The MiniZinc model for LinkedIn Queens is mentioned as being able to be used with various solvers and levels of propagation to measure puzzle hardness.
  • CP-SAT: Mentioned as being able to solve puzzles using the presolver

Haskell Code Commentary and Misconceptions

There's a small digression about the nature of the Haskell code presented in the original post.

  • Not representative of real-world Haskell: "As a professional haskeller, I feel it necessary to point out for people in this thread who are less exposed to Haskell and who may be Haskell-curious...this is not what real-world commercial Haskell code looks like. To use a C analogy, I'd say it's closer to IOCCC entries than Linux kernel code." (mightybyte)
  • Tackling contrived problems: "Yeah, comparing to how you'd solve this in any other mainstream language is really an apples-to-oranges comparison here because this is explicitly tackling the contrived problem of solving it at the type level rather than at the much more common value level." (mightybyte)
  • Type-level computation: "The joke is that the type system is turing complete if you enable the right extensions." (agnishom)

UK Online Safety Act

A brief discussion about the UK Online Safety Act arises when a user is unable to view a linked blog post.

  • Site blocked due to UK law: "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?" (the_other)
  • Author blocked UK users: "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..." (mdrzn)

This summary captures the main threads of discussion, from the core challenges of puzzle generation to specific implementation details and tangential observations.