The three color problem solver

In this page a javascript program attempts to solve the three color problem in discrete tomography. The problem has a wide number of connections and applications also in other fields as scheduling, maximum flow problems, network security, tiling and packing problems. The algorithm has been presented in the 14th International Workshop on Combinatorial Image Analysis (IWCIA 2011) and a white paper has been published in the LNCS series.

Basically, the program attempts to rebuild a table where every row and column contains a specified number of red and blue cells (the third color is the white background) even if the problem has been proved to be computationally unsolvable (NP-complete). Usage: simply insert the projections of red and blue in the boxes below as a series of integer numbers separated by commas, and press the solve button. Clearly, you must dispose of a browser with Javascript enabled.

Warning: the program is a beta, and it may crash your browser. Further: for big matrices the solving process could be quite slow (especially on explorer browsers it seems...). Use at your own risk ! To obtain an offline implementation that allows a much faster execution, you can contact the author.

Webpage created by Stefano Brocchi, of the University of Florence, Department of Systems and Computer Science.

Advanced options

Instance projections:

Horizontal color 1

Vertical color 1

Horizontal color 2

Vertical color 2

Rows

Columns

X
X
Problems examined:
Problems with no solution:
Problems possibly with solution:
Problems solved:
Problems got to step two:
Problems got to step three:
Problems got to iteration two:
Problems got to iteration three:
Problems got to iteration four:
Problems got to iteration five:
Problems got to iteration six:
Problems got to iteration seven:
Problems unsolved:
Remaining bicolored cells:
Total placed cells:
Average error:
Elaboration time:

X
Remaining bicolored cells: