Goal

• Write a program (python or java or c/c++) that solves 3-coloring using the MiniSat solver
  • Input: a graph to be 3-colored
  • Output: corresponding boolean formula (as explained in previous video)that can be fed into MiniSAT
  • Input FormatIn the input files, the graphs are represented with adjacency lists:Each row represents the list for a node: first row for node a, second row for node b etc….Example:b c
    a c d
    a b
    brepresents a graph where:1) Node a is connected to nodes b and c
    2) Node b is connected to nodes a, c, and d
    3) Node c is connected to nodes a and b
    4) Node d is connected to nodes b