Follow

New blog post: A little knowledge can make the next step harder, 11011110.github.io/blog/2019/0

It's on a phenomenon in Sudoku and other similar puzzle games, where (if you use the assumption that there is a unique solution as the basis for certain puzzle-solving rules) then it matters which order you apply your inference rules: choosing a rule that makes a weak inference can prevent you from ever later using a different rule that would have allowed you to make a stronger inference.

@11011110 how do you represent rules and their strength?
Is that what you were referring to about representation?

@11011110 One possible knowledge representation might be to keep track of the order in which each deduction was made. i.e. number each "clue" square 0 and then number the first deduction you make 1 and so on - we get persistence and so monotonicity of the rules you describe. This isn't constant of course but log n per square isn't too bad.

@11011110
I made some Smullyan-style metapuzzles using this observation for Sudoku many years ago. They were of the type that suppose that some fields are missing from a Sudoku puzzle, fill out the rest of it.

Sign in to participate in the conversation
Mathstodon

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.