4
$\begingroup$

I wrote a prolog program to print out all of the possible solutions for the following problem:

You have eight colored balls: 1 black, 2 white, 2 red and 3 green. The balls in positions 2 and 3 are not green. The balls in positions 4 and 8 are the same color. The balls in positions 1 and 7 are of different colors. There is a green ball to the left of every red ball. A white ball is neither first nor last. The balls in positions 6 and 7 are not red.

The program works fine, but I need to mathematically calculate how many solutions there are (with same colors being distinct, and same colors being indistinct.) Any ideas about how to go about this? At first, I tried to find all possible of solutions of each rule independently and then multiplying that together. But i realized this was not correct because there would be a lot of solutions overlapping that will be counted more than once. My second idea was to do 8! and subtract all not-allowed solutions from this by each rule. But this would also delete duplicates. Any ideas? Thanks in advance.

  • 0
    Not sure what "mathematically calculate" means here, other than just enumerate carefully. I doubt there's a simpler way to do it, since there are so many different constraints. However, one can say that the number of solutions with distinguishable balls is $2!2!3!=24$ times greater than the number of solutions with indistinguishable balls.2012-11-25

2 Answers 2