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?