Generalized color balls in a 4x4 grid

This is a generalization of the Colored balls in a 4x4 grid puzzle that was proposed by Darrel Hoffman.

Colored balls from 4 different colors are placed in a 4x4 grid. There is at least one ball from each color. A move consists of swapping two adjacent (horizontally or vertically) balls. The value of the grid is the least number of moves required to form 4 connected components*, one for each color. Which grid has the highest value?

*Here a connected component is a collection of balls of the same color, such that there is a path of horizontal or vertical steps from any ball to any other ball.

• Out of curiosity: Do you have a workable method of scoring, i.e. determining the smallest number of moves for a given position? Nov 10 '20 at 17:12
• Not yet. But I am working on it. Nov 10 '20 at 21:53
• I have a solver now :) Nov 13 '20 at 1:37
• Just answered. I'm not 100% confident in my program. Could you perhaps use your solver to double check a few of my positions (just the number of steps since the solution paths are not unique)? Nov 15 '20 at 0:40

With the normalization that the first color occurring (starting from top left) should be R and the second G there are $$358,108,246$$ positions. This is brute-forceable. I wrote a program that first finds all $$342,074$$ end positions, then those $$914,980$$ one step away from an end, then those $$3,747,392$$ two steps away and so on. Note that I did not enforce that all four colors must be present. This ended after

$$13$$ steps.

Shown below are $$4$$ of the

$$28$$

answers each with a random shortest solution (Solutions are non-unique).

Small letters indicate the pair to be swapped in the next move. More than two small letters indicate a remapping of colors which is sometimes required to uphold the R,G-first normalization.

R G R b   R G R Y   R G r y   R G G B   R G g B   R G B B   R G B B
B G Y y b g Y B g b y b R Y B Y R Y b Y R y g Y R G Y Y
Y Y G B Y Y G B y y g b B B R Y B B R Y B B R Y B B R Y
B R G R B R G R b r g r Y g r G Y R G G Y R G G Y R G G

R G B B R G B B R G B B R G B B R G b b R G G G R G G G
R B Y Y R B Y Y R B Y Y R B Y Y R B Y Y R b Y Y R G Y Y
B G R Y B g R Y B y r Y b r Y Y R b Y Y R g Y Y R B Y Y
y r G G R y G G R G G G R G G G R g g g R B B B R B B B

R G R B   R G R B   R G r B   R G G B   R G G B   R G G B   R G G B
B Y G Y B Y G Y B Y g Y B Y R Y B Y r Y B Y B y B Y B B
y G Y B b g Y B G B Y B G b y B G Y b B G Y R b G Y R Y
b R G R Y R G R Y R G R Y R G R Y R G R Y R G R Y R G R

R G G B R G G B R G G B R g g b R R R G R R R G R R R G
B Y B B B y B B b g B B g b b b y G G G R G G G R G G G
G y g Y G g Y Y G Y Y Y g y y y r B B B y B B B B B B B
Y R R R Y R R R Y R R R y r r r B Y Y Y b Y Y Y Y Y Y Y

R G R y   R G R B   R G R B   R G R B   R G R B   R G r b   R G B R
Y G B b Y G B Y Y G B Y Y G B Y y G B Y B G b Y B G R Y
B B G Y B B g y B B y G B B G G b B G G Y b G G Y R G G
Y R G R Y R G R Y R g R Y r y R Y Y R R Y Y r r Y Y B B

R G R R R G R R R G R R R G R R R G R R R g R R R R R R
B G b Y B G g y B g y G b y G G Y b G G y r g g G Y Y Y
Y R g G Y R B G Y R B G Y R B G Y r B G y B B g G B B Y
Y Y B B Y Y B B Y Y B B Y Y B B Y Y B B y y B B G G B B

R G R Y   R G R Y   R g r Y   R R G Y   R R G Y   R R G Y   R R G Y
Y B G B y b G B B Y G B B Y G B B y g B B G Y B B G Y B
B g b Y B B G Y B B G Y B B g y B B y g B B G Y B B G Y
Y R G R Y R G R Y R G R Y R G R y R g R G R y r G R R Y

R r g y R G Y B R G Y B R G Y B R G Y B R G Y B R G Y B
b g y b G Y b r G y r B G R Y B g r Y B R G Y B R G Y B
b r g y R G Y B R G Y B R G Y B R G Y B R G Y B R G Y B
g b r y Y R G B Y R G B y r G B R Y G B R y g B R G Y B

CODE:

file <cb_pr.py> compile using pythran -O3 cb_pr.py

import numpy as np

# pythran export check_patt(uint8)
# pythran export inc_depth(uint8,int,int)
# pythran export find_home(uint8,int[:],int[:],int[:,24])

# To make things fast and to save memory we encode positions as 32 bit ints,
# 2 bits per color, Due to our R-G-first convention The first three bits will
# always be zero, that was necessary because of RAM limitatioins on my machine.
# Since we store only one  byte, the distance to the nearest end position, we
# need in total 2^29 bytes to store the entire lookup table

# This function runs through all patterns, identifies end positions and marks
# them with 1.
# To efficiently check for connectedness of all four colors simultaneously
# the color representation is first expanded from  2 bits to 4 bits; this still
# fits in a 64 bit int and allows to set or clear each color in each cell
# simultneously and independently. We then do a bucket fill using bit
# twiddling, starting from a random single cell germ for each color.
# for example to check for the potential top neighbors of all cells we left
# shift by 16 bits. Similarly and simultaneously we check for the three other
# directions and OR everything together.
# and then AND with the original pattern to retain only actual neighbors.

def check_patt(out):
cnt = 0
for cc in range(len(out)):
b = 0
last = np.zeros(4,int)-1
c = cc
for d in range(16):
b = b | (1<<((c&3)|(d<<2)))
last[c&3] = d
c = c >> 2
germ = 0
nxt = (15<<(last[last>=0]<<2)).sum()&b
while nxt != germ:
germ = nxt
nxt = (germ | (germ<<16) | (germ>>16) |
((germ<<4)&-0xf000f000f0010) |
((germ>>4)&0xfff0fff0fff0fff)) & b
if nxt==b:
out[cc] = 1
cnt += 1
return cnt

# This function increases the search depth by one. It looks up all positions
# labeled with the current depth, computes all 24 single step reachable
# postitions, looks them up and if they are not labeled yet labels them with
# the current depth + 1.
# The only complication occurs when the move creates a position > 2^29. In that
# case colors must be remapped. This can be done relatively cheaply with bit
# manipulations but is not easy to read.

def inc_depth(out,depth,cnt):
for cc in range(len(out)):
if out[cc] == depth:
for i in range(1,16):
if i&3:
m = (3<<(i<<1)) & (cc ^ (cc<<2))
dd = cc ^ (m | (m>>2))
if dd >= 1<<30:
dd = dd ^ (((dd>>30)) * 0x55555555)
if (dd & 0x55555555) < (dd & 0xaaaaaaaa):
sp = dd
for sh in (16,8,4,2):
spn = sp >> sh
if spn >= 2:
sp = spn
if sp&1:
dd = dd ^ ((dd&0x55555555)<<1)
else:
dd = dd ^ (((dd^(dd>>1))&0x55555555)*3)
if(dd>=1<<29):
print(hex(dd),sp)
if out[dd] == 0:
out[dd] = depth+1
cnt += 1
for i in range(4,16):
m = (3<<(i<<1)) & (cc ^ (cc<<8))
dd = cc ^ (m | (m>>8))
if dd >= 1<<30:
dd = dd ^ (((dd>>30)) * 0x55555555)
if (dd & 0x55555555) < (dd & 0xaaaaaaaa):
sp = dd
for sh in (16,8,4,2):
spn = sp >> sh
if spn >= 2:
sp = spn
if sp&1:
dd = dd ^ ((dd&0x55555555)<<1)
else:
dd = dd ^ (((dd^(dd>>1))&0x55555555)*3)
if(dd>=1<<29):
print(hex(dd),sp)
if out[dd] == 0:
out[dd] = depth+1
cnt += 1
return cnt

# This function uses the finalized lookup table to find one shortest way from
# a given position to one nearest end position

def find_home(out,p,cnts,rnd):
d0 = out[p]
for d in range(d0-1):
cnts[d] = 0
for ii in rnd[d]:
if ii < 12:
i = (ii<<2)//3
m = (3<<(i<<1)) & (p[d] ^ (p[d]>>2))
pd = p[d] ^ (m | (m<<2))
else:
i = ii - 12
m = (3<<(i<<1)) & (p[d] ^ (p[d]>>8))
pd = p[d] ^ (m | (m<<8))
if pd >= 1<<30:
pd = pd ^ (((pd>>30)) * 0x55555555)
if (pd & 0x55555555) < (pd & 0xaaaaaaaa):
sp = pd
for sh in (16,8,4,2):
spn = sp >> sh
if spn >= 2:
sp = spn
if sp&1:
pd = pd ^ ((pd&0x55555555)<<1)
else:
pd = pd ^ (((pd^(pd>>1))&0x55555555)*3)
if out[pd]==d0-d-1:
if cnts[d] == 0:
p[d+1] = pd
cnts[d] = cnts[d] + 1
return 0

main script:

import numpy as np
from cb_pr import check_patt,inc_depth,find_home

# allocate lookup table
out = np.zeros(1<<29,np.uint8)
# mark end postiions
cnt = check_patt(out)
# push depth
d = 1
while cnt < 1<<29:
ncnt = inc_depth(out,d,cnt)
if ncnt == cnt:
break
d += 1
# lookup table is done

# fancy visualisation ...
b = chr(11044)
# .. using tty color escapes ...
bullets = ["\x1b[31;47m"+b,"\x1b[32;47m"+b,"\x1b[34;47m"+b,"\x1b[33;47m"+b,
"\x1b[31;49m"+b,"\x1b[32;49m"+b,"\x1b[34;49m"+b,"\x1b[33;49m"+b]
# ... or black and white unicode symbols
baw = chr(10680),chr(10682),chr(10687),chr(10686)
baws = baw

# the visualization function -- horrible code but does the job
# the "simple" style has PSE markup you may want to delete that for home use
def show(codes,style='simple',cut=7):
codes = [codes[i:i+cut] for i in range(0,len(codes),cut)]
if style=="baw":
out = "\n\n".join("\n".join("   ".join(" ".join((baws[(x>>(30-2*i))&3]) for i in range(4*j,4*j+4)) for x in cod) for j in range(4)) for cod in codes)
elif style=="color":
out = "\n\n".join(" \x1B[0m \n".join(" \x1B[0m   ".join(" \x1B[0m".join((bullets[((x>>(30-2*i))&3)+(((i+j)&1)<<2)]) for i in range(4*j,4*j+4)) for x in cod) for j in range(4)) for cod in codes)
else:
out = []
for cod in codes:
dff = np.array(cod)
dff[:-1] ^= dff[1:]
dff[-1] = 0
out.append("\n>! ".join("   ".join(" ".join(("RGBYrgby"[((x>>(30-2*i))&3)+4*(((y>>(30-2*i))&3)!=0)]) for i in range(4*j,4*j+4)) for x,y in zip(cod,dff)) for j in range(4)))
out = ">! <pre> " + "\n>!\n>! ".join(out) + " </pre>"
return out

# reconstruct solution given starting position p0 using loookup table out
def rec_sol(p0,style="simple"):
d = out[p0]
cnts = np.zeros(d-1,int)
p = np.zeros(d,int)
p = p0
rnd = np.array([np.random.permutation(24) for _ in range(d-1)],int)
if find_home(out,p,cnts,rnd) < 0:
raise RuntimeError
print(show(p,style))
return p,cnts

# some minimal statistics:
h = np.zeros(32,int)
CHUNK = 1<<24
for i in range(0,out.size,CHUNK):
h += np.bincount(out[i:i+CHUNK],None,32)
# extract farthest from end positions:
sols = (out==d).nonzero()
for sol in sols:
rec_sol(sol,"color")
print();print()
# reset terminal colors
print("\x1B[0m")
• wow great work! I haven't checked your solutions yet, but I wasn't able to find anything that takes more than 13 steps too. Nov 15 '20 at 21:26
• I ran my solver on your first grid and I was able to do it in 12 moves: pastebin.com/Z4J9pHTa Nov 17 '20 at 4:40
• However the second grid seems to require at least 13 moves, so it is a valid solution. Nov 17 '20 at 4:49
• @DmitryKamenetsky Are you sure you copied that correctly? I don't think I had any solution that wasn't 4 of each color. Nov 17 '20 at 5:24
• Yes you are right! Looks like I made a mistake during copying. Nov 17 '20 at 5:36