The 3-color tomography problem

The 3-color tomography problem is NP-hard, but this webpage aims to provide some intuition about the structure of the problem. The input are projections from the red and green cells. (Yellow cell projections are redundant). The input can either be entered in the form on the right, or generated by editing some grid coloring on the left. When you submit the input, a linear pogram is generated, modeling the problem, and for every cell we use some solver to decide what colors the cell can have in a solution. Note: we only solve the relaxed linear program, where cells can have fractional colors, and therefore it is possible that the solver outputs something, while the instance is not feasible, i.e. the integer program has in fact no solution.


Reload with rows and columns.

Change the pen to .

green row projections
red row projections
green column projections
red column projections
fix cells