Randomly generate the puzzle (with a seed) on each run. A puzzle in CNF is an "AND of ORs" ("∧ of ∨s" or "∧ of Clauses"). Use (the new) SATLiteral as the return type of comb(el: str, loc: int) -> SATLiteral, mapping puzzle elements to literals, and neg(el: SATLiteral) -> SATLiteral to negate a literal.Īdd Clause: tuple representing a "∨" (boolean OR disjunction) of literals e.g., (1, -5, 6) is a disjunction stating that x_1 is true, x_5 is not true, or x_6 is true.Īdd ClueCNF: list, representing a "∧" (boolean AND conjunction) of Clauses. Rename SATLiteral -> PuzzleElement (smoothie, cat, etc.) this clarifies that it's not a Literal in the boolean sense and is instead a name for e.g., characters in a puzzle.Ĭreate a new type SATLiteral (which is a str in a trenchcoat) this represents the literal in the boolean-variable sense, like "Value el is at house loc" or "Value el is not at house loc." Internally, these are represented by some integer i and its negative counterpart -i. Incomplete changelog : typing improvements But the project is finally at a place that I'm happy with, and so I'm excited to share and write about it. Consider using another logic programming interface PySAT, answer set programming, more discussion in this HN thread.Try creating smaller size (4 houses) with, say, 6 categories is that easier or harder?.Create a better CLI (in-place updates during clue reduction, proper args for e.g., puzzle size).This uses the SAT solver pycosat, but PySAT is listed as a dependency, too.)ĭevelopment uses black, ruff, and pyright, though we're not totally compliant yet I created the repo in 2019, and have only made minor changes since adding the dev dependencies. generate.py is the main entry point into this project, creating new puzzles.clues.py contains the different classes of clues via a base Clue and subclasses ("x is at the same house as y", "x is somewhere to the left of z", etc.).elements.py (formerly literals.py) contains the different puzzle elements via a base PuzzleElement and subclasses (people, favorite types of tea, most-played video games, etc.).puzzle.py contains the main Puzzle class and two sample puzzles that can be solved.sat_utils.py is basic utilities for interacting with the SAT solver pycosat this code was almost entirely written by Raymond Hettinger.This project has five Python files in src/: Using modern Python and constraint satisfaction (SAT) solvers, this project can be used to create random zebra puzzles. He showed us how to solve them I wanted to learn how to generate them. I loved these as a kid, and watching Raymond Hettinger's P圜on 2019 talk inspired me to revisit these problems. The chai drinker does not like the color blue.There is one house between Tushar and Maui.Remember logic puzzles that looked like this? They had clues like: I'm using it as a playground for some things I want to try out, but I don't recommend anyone build off this. Today, in 2023, project is largely unmaintained.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |