2
$\begingroup$

The Zebra Problem ( also known as Einstein's Puzzle ) is a problem wherein we are given some number of houses, some number of properties of the people living in those houses, domains for the properties of these people, and a set of relations constraining the domains that any given person can have. No two people can share the same value for the same property.

The Zebra Problem is often modeled as a table, with columns representing houses and rows representing functions from a given domain to the set of houses.

Sudoku, to me, seems to be a very, very similar problem: we have three-by-three squares. Each three-by-three square seems to be similar to a row in the Zebra Problem ( because Sudoku uses a bijection to assign digits to squares, and the Zebra Problem uses a bijection to assign values to house properties--selection without replacement ).

Also, Sudoku has rules governing the legal relationships between three by three squares. ( Each row and column in a grid of three-by-three squares must add up to a certain number, for example. ) Similarly, instances of the Zebra Puzzle seem to always have at least one rule governing the relationships between rows. ( vis. The Blue House must be to the right of the house of the man who drinks tea, etc. )

I wonder, if it isn't possible to describe a general problem that can be reduced to both Sudoku and the Zebra Problem. Furthermore, I wonder if there isn't at least one algorithm that can solve the general problem, Sudoku and the Zebra Problem.

Has someone out there at any point in time sorted the answer to that question out?

$\endgroup$
  • $\begingroup$ A closer match than sudoku would be these types of puzzles: duckduckgo.com/… $\endgroup$ – Frpzzd May 23 '17 at 20:41
1
$\begingroup$

Sudoku is easy to translate into a Boolean satisfiability problem (SAT), though it isn't pretty. Let $x_{1,1},\ldots,x_{9,9}$ represent the cells, and $X_{1,1,i}$ the event that the digit $i$ appears in cell $(1,1)$.

Each cell must have a digit in it, so $$X_{1,1,1} \vee X_{1,1,2} \vee X_{1,1,3} \vee \cdots \vee X_{1,1,9},$$ but only one digit, so $$!(X_{1,1,i} \wedge X_{1,1,j})$$ for $i \neq j$. Since each digit must appear exactly once in the first row, we have $$!(X_{1,1,i} \wedge X_{1,2,i})$$ for any $i$, and so on. There are a whole lot of clauses involved, but it isn't especially hard to list them all. The initial state of the puzzle consists of additional known clauses.

Logic puzzles can also be translated into SAT, and so an algorithm like DPLL can solve both of these types of problems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.