I have been playing Sudoku lately, and I've seen a problem with this general form:
Given N items, each of which belongs alone (1-to-1) in one of N boxes, and given a list of statements of the form: "item x may go in box y" So that:
- If no statement is in the list connecting item x to a box y, the item a certainly does not belong in box y.
- Between each item and the box it belongs in, there is a statement in the list connecting them.
- The statements described in 2 are a subset of all the statements in the list. (there are extra ones)
Is there an efficient process for reducing the number statements by getting rid of contradictory ones?
For instance, if a given item can only go in one box, all other statements about items that may go in that box can be erased. If a given box only has one item that can go in it, all statements connecting that item to other boxes can be erased. These generalize to subsets as well: If two items are the only items that may be in either of two boxes, all statements connecting those two items to boxes other than the two can be erased.
Are there more rules? I din't know.
It comes up in Sudoku when looking at a given block, row or column. The numbers not yet filled in are the items, the cells not filled in are the boxes, and the candidates (small numbers you write in cell that may be there) are the statements. Often, candidates can be reduced by seeing contradictions in them.
I'm just wondering if anyone knows what this problem is called, so I can read up on it. I'm not much of a math guy, and I haven't been able to find it through Internet, so any help is appreciated. I know the Sudoku version can be solved through enumeration, but I'm also curious about for N greater than 9, the general problem. Thanks!
You are describing a Constraint-Satisfaction Problem (https://en.wikipedia.org/wiki/Constraint_satisfaction_problem). In the last few years, it was shown that every CSP is either $\textsf{NP}$-complete or in $\textsf{P}$. This result was proven independently by Zhuk and (IIRC) Bulatov.
The Generalized Sudoku Problem is also known to be $\textsf{NP}$-complete (http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html), and determining the minimum number of clues needed also seems to be $\textsf{NP}$-hard (https://people.math.sc.edu/cooper/criticalsets.pdf).