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.

- Step by step compute: executes one step of the problem, showing the progress of the result matrix. A navigator box will appear to allow the navigation to a specified step and containing a button to easily execute the next step (NS)
- Reset solution: resets the problem, and cancels the current dumps and the obtained solution
- Random input: opens the random input box, with options to generate a random input for the problem.
- Random matrix: generates a random matrix, and sets the input of the problem equal to the projections of that matrix
- Random matrix with overlaps: as above, but also allows some cells with overlapping colors, and hence may also generates problems with no solution
- Random projections: generates randomly input projection arrays
- Get problem URL: generates a link to easily replicate the current problem

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:

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: