I've noticed that adding a colour can make it go from having a solution to not having a solution. Maybe it should try to come up with a solution using fewer colours in that case, since it's not obvious that manually removing a colour will lead to a solution.