# Color the Table

Color each cell of the table with following rules:

1. Yellow and Orange cells are adjacent, but Red and Black are not.
2. Cell with number 3 is White, Green, Blue or Red and the cell with number 5 is not White or Purple.
3. Purple and Orange are in the same column, but Yellow and Black are not, just like Green and Blue.
4. The numbers of White and Pink cells are consecutive and they are not adjacent.
5. The difference of Red and Yellow is less than 3 and the difference between White and Blue is not greater than 3.
6. Red and Blue has the difference greater than 2.
7. Green is adjacent to Pink and is odd.
8. Red and Yellow are not in the same column.
9. The number in Blue cell is greater than the Green.

Source: mehcom.com

• What's the neighbourhood for adjacency? – Peter Taylor Sep 3 '14 at 9:34
• two adjacent cells means they are neighbors even diagonally. e.g. all the cells are adjacent with 7. – Rafe Sep 3 '14 at 15:54

I have found 6 potential solutions which do not seem to contradict any rules.

1       2       3       4       5       6      7        8       9
green   orange  white   pink    blue    black   yellow  red     purple
green   orange  white   pink    blue    black   yellow  purple  red
green   orange  white   pink    black   blue    yellow  purple  red
green   purple  white   pink    blue    black   yellow  red     orange
green   purple  white   pink    blue    black   yellow  orange  red
green   purple  white   pink    black   blue    yellow  orange  red


Please let me know if I have misunderstood any rules. If not I will explain roughly how I got the answers.

Noting that I first assumed that 7 must be orange or purple. A contradiction arises depending on the order of elimination of via the rules. Basically this assumption is false so I proceeded with that knowledge.

Any color which is not adjacent to something (aka red, black, white, or pink) cannot be in 7 either as 7 is adjacent to everything. Rule 4 leads to white being in 3 or 4. So by rule 5 and 9, blue cannot be in 8 or 9 and green cannot be in 7 or 9. Working with pink/green adjacency meant green is not in 5 either. Green is therefore in the middle column and (by rule 3) blue is not. Yellow is the only option for the central cell 7.

This quickly lead to concluding that only green could be in 1 which eliminated w=4 so w=3.

The ugly options I had left where how to place red, black, orange, purple, blue, and pink in the left and right columns. Orange and purple must be in the same column while red and black must be different. Blue and pink must therefore be together. Eliminating blue=2 which requires pink=2 means blue and pink are in the left and orange and purple are in the right columns. The remaining solutions were trimmed to make sure all rules are met.

This assumes that diagonals can be adjacent. There could potentially be other solutions if diagonals are not adjacent. Of these, only the fourth option is a possible solution if diagonals are not adjacent.

The options below were found for the case where diagonals are not adjacent. This seems to mean that for either interpretation there are multiple solutions.

1       2       3       4       5       6       7       8       9
yellow  red     green   orange  black   purple  white   pink    blue
yellow  red     green   orange  black   purple  pink    white   blue
green   black   red     purple  yellow  orange  pink    white   blue
green   purple  white   pink    blue    black   yellow  red     orange

• 9 potential solutions or 6? Of the six you've posted, five rely on defining "adjacent" by the Moore neighbourhood; if we interpret it as the von Neumann neighbourhood (and OP's comment as wrong) then your fourth solution would appear to be the intended one. – Peter Taylor Sep 3 '14 at 16:04
• You cannot say that. Some rules state that things are "not adjacent" and I eliminated options that way. I could, therefore, have eliminated other potential solutions. – kaine Sep 3 '14 at 16:12
• I'm assuming that it's intended to have a unique solution. – Peter Taylor Sep 3 '14 at 16:13
• @PeterTaylor In general, I think that is a very poor assumption on this site as the sources are not perfectly reliable. – kaine Sep 3 '14 at 16:15
• I thought it has unique solution too. I have double checked you solution with the original source (not the one i have translated) and everything was match! Perfect answer BTW! – Rafe Sep 3 '14 at 16:22

This answer produces the same four solutions mentioned at the end of kaine's answer, although the solution technique I used is a little less subtle, and more along the lines of brute force. It illustrates a technique that's ok for small problems like this, but probably not for larger problems. It consists of generating and testing all permutations of cell colors, and reporting those that satisfy all tests. It takes about 0.2 seconds to complete. Here is what the program output looks like:

yellow red green orange black purple white pink blue
yellow red green orange black purple pink white blue
green purple white pink blue black yellow red orange
green black red purple yellow orange pink white blue


Edit: In light of Rafe's comment that adjacency includes diagonal neighbors [eg, all other cells are adjacent to the center cell], in nextTo I replaced two lines. I also corrected two program errors and have added some program explanation. Here's the current program's output (which matches kaine's first six solutions):

green purple white pink black blue yellow orange red
green orange white pink black blue yellow purple red
green purple white pink blue black yellow orange red
green purple white pink blue black yellow red orange
green orange white pink blue black yellow purple red
green orange white pink blue black yellow red purple


Following is the python 2.7 program that produced the output. I used the letters B, G, K, L, O, P, R, W, Y to stand for the nine colors Black, Green, pinK, bLue, Orange, Purple, Red, White, Yellow. The program uses cell identification numbers 0,1,2 for cells in the top row; 6,7,8 for the middle row; and 12,13,14 for the bottom row. Array cellNums embodies this map, which is such that two cells in the same column have identification numbers that differ by $\pm6$ or $\pm12$.

For adjacency, two cells adjacent in a row differ by $\pm1$; in a column, by $\pm6$; in a forward diagonal, by $\pm5$; in a back diagonal, by $\pm7$. Thus, cells x and y are Manhattan adjacent, or are in a Von Neumann neighborhood, if $|x-y| \in \{1, 6\}$; and are in a Moore neighborhood if $|x-y| \in \{1, 6, 5, 7\}$.

Array entry digCells[i] tells the cell number for digit i+1. Array entry number[j] tells what digit is in cell j.

# Ref http://puzzling.stackexchange.com/questions/2194/color-the-table
from itertools import permutations, ifilter
#-----------------------------------------------------------
def inColumn(x,y):   # Return true if x,y are in same column.
dxy = abs(x-y)
return dxy == 6 or dxy == 12
#-----------------------------------------------------------
def nextTo(x,y):     # Return true if x,y are adjacent.
#return abs(x-y) in (1, 6)       # von Neumann
return abs(x-y) in (1, 6, 5, 7)  # Moore
#-----------------------------------------------------------
# Test if permutation p satisfies all conditions.
def isGood(p):
B, G, K, L, O, P, R, W, Y = p
# Tests 1 and 2.
# Note, digit 3 is in cell 1 and digit 5 is in cell 0
# 1. nextTo(Y,O); not nextTo(R, B)
# 2. color(number(3)) in {W,G,L,R}; color(number(5)) not in {W,P};
if nextTo(R, B) or not nextTo(Y,O) or \
1 not in (W,G,L,R) or 0 in (W,P):
return False
# Tests 3 and 4.
# 3. inColumn(P,O); not inColumn(Y,B); not inColumn(G,L)
# 4. abs(number(W)-number(K)) == 1; not nextTo(W,K)
if not inColumn(P,O) or inColumn(Y,B) or inColumn(G,L) or \
abs(number[W]-number[K]) != 1 or nextTo(W,K):
return False
# Tests 5 and 6.
# 5. abs(number(R)-number(Y)) < 3; abs(number(W)-number(L)) < 4
# 6. abs(number(R)-number(L)) > 2
if abs(number[R]-number[Y]) > 2 or abs(number[W]-number[L]) > 3 \
or abs(number[R]-number[L]) < 3:
return False
# Tests 7, 8, 9.
# 7. nextTo(G,K);  odd(number(G))
# 8. not inColumn(R,Y)
# 9. number(L) > number(G)
if not nextTo(G,K) or not number[G]&1 or \
inColumn(R,Y) or \
number[L] <= number[G]:
return False
return True
#---------------------------Main program--------------------
cellNums = [0, 1, 2, 6, 7, 8, 12, 13, 14]
digCells = [13, 14, 1, 12, 0, 6, 7, 2, 8]
number = [5,3,8,0,0,0,  6,7,9,0,0,0,  4,1,2,0,0,0]
colors = ['black', 'green', 'pink', 'blue', 'orange', 'purple', 'red', 'white', 'yellow']

for p in ifilter(isGood, permutations(cellNums)):
for cn in digCells:
for j, c in enumerate(p):
if c==cn: print colors[j],
print

• Interesting code. I have not learnt python yet but editted the "nextTo(x,y)" function to allow diagonal neighbors as OPs comments indicated (dxy==5 or dxy==7). Running it at ideone.com/THCazc yielded 2 of my six solutions for the "Moore neighborhood". Is there something else in the code that restricts that definition or did I make a mistake finding those other 4? – kaine Sep 4 '14 at 13:35
• Actually I figured it out. Your "inColumn(x,y)" is incorrect. it should be "return dxy == 6 or dxy == 12". Modifying "nextTo(x,y)" therefore returns the same answer i recieved for the "diagonals can be neighbors" definition. Never comes up in the other case. – kaine Sep 4 '14 at 13:44
• I noticed the typo in inColumn and had edited the post just a few minutes before you made your first comment. With that corrected, changing nextTo's return dxy == 1 or dxy == 6 to return dxy in (1, 6, 5, 7) produces the same six answers as you have for the rectilinear+diagonal adjacency case, (the six answers all with 1=green, 3=white, 4=pink, 7=yellow). – James Waldby - jwpat7 Sep 4 '14 at 13:51