Verallgemeinerte Farbkugeln in einem 4x4-Raster

Question

Dies ist eine Verallgemeinerung der farbigen Kugeln in einem 4x4-Gitter- Puzzle, das von Darrel Hoffman vorgeschlagen wurde.

Farbige Kugeln aus 4 verschiedenen Farben werden in einem 4x4-Raster platziert. Es gibt mindestens eine Kugel aus jeder Farbe. Ein Zug besteht aus dem Austausch zweier benachbarter (horizontal oder vertikal) Bälle. Der Wert des Gitters ist die geringste Anzahl von Bewegungen, die erforderlich sind, um 4 verbundene Komponenten * zu bilden, eine für jede Farbe. Welches Gitter hat den höchsten Wert?

* Hier ist eine verbundene Komponente eine Sammlung von Bällen derselben Farbe, sodass horizontale oder vertikale Schritte von jedem Ball zu jedem anderen Ball verlaufen.

Answer 1

Mit der Normalisierung, dass die erste Farbe (beginnend von oben links) R sein sollte und die zweite G es gibt $358,108,246$Positionen. Das ist brutal erzwungen. Ich habe ein Programm geschrieben, das zuerst alles findet$342,074$ Endpositionen, dann diese $914,980$ einen Schritt von einem Ende entfernt, dann diese $3,747,392$zwei Schritte entfernt und so weiter. Beachten Sie, dass ich nicht erzwungen habe, dass alle vier Farben vorhanden sein müssen. Dies endete danach

$13$ Schritte.

Unten sind dargestellt $4$ des

$28$

Antworten jeweils mit einer zufällig kürzesten Lösung (Lösungen sind nicht eindeutig).

Kleine Buchstaben zeigen das Paar an, das im nächsten Zug getauscht werden soll. Mehr als zwei kleine Buchstaben zeigen eine Neuzuordnung von Farben an, die manchmal erforderlich ist, um die R, G-erste Normalisierung aufrechtzuerhalten.

RGR b RGRYRG ry RGGBRG g BRGBBRGBB 

 BGY YBG YB gbyb RYBYRY b YR yg YRGYY 

 YYGBYYGB yygb BBRYBBRYBBRYBBRY 

 BRGRBRGR brgr Y gr GYRGGYRGGYRGG 



 RGBBRGBBRGBBRGBBRG bb RGGGRGGG 

 RBYYRBYYRBYYRBYYRBYYR b YYRGYY 

 BGRYB g RYB yr Y br YYR b YYR g YYRBYY 

 yr y GGR GGRGGGRGGGR ggg RBBBRBBB

RGRBRGRBRG r BRGGBRGGBRGGBRGGB 

 BYGYBYGYBY g YBYRYBY r YBYB y BYBB 

 y GYB bg YBGBYBG durch BGY b BGYR b GYRY 

 b RGRYRGRYRGRYRGRYRGRYR GRYRGR 



 RGGBRGGBRGGBR ggb RRRGRRRGRRRG 

 BYBBB y BB BG BB gbbby GGGRGGGRGGG 

 G YG YG g YYGYYY gyyyr BBB y BBBBBBB 

 YRRRYRRRYRRR YRRRRRRRRRR byyy b YYYYYYY

RGR y RGRBRGRBRGRBRGRBRG rb RGBR 

 YGB b YGBYYGBYYGBY y GBYBG b YBGRY 

 BBGYBB gy BB y GBBGG b BGGY b GGYRGG 

 YRGRYRGRYR g RY ry RYYRRYY rr YYBB 



 RGRRRGRRRGRRRGRRRGRRR g RRRRRR 

 BG b YBG gy B gy G durch GGY b GG yrgg GYYY 

 YR g GYRBGYRBGYRBGY r BG y BB g GBBY 

 YYBBYYBBYYBBYYBBYYBB yy BBGGBB

RGRYRGRYR gr YRRGYRRGYRRGYRRGY 

 YBGB yb GBBYGBBYGBB yg BBGYBBGYB 

 B gb YBBGYBBGYBB gy BB yg BBGYBBGY 

 YRGRYRGRYRGRYRGR y R g RGR yr GRRY 



 R RGY RGYBRGYBRGYBRGYBRGYBR GYB 

 bgyb GY br G yr BGRYB gr YBRGYBRGYB 

 Brgy RGYBRGYBRGYBRGYBRGYBR GYB 

 gbry YRGBYRGB yr GBRYGBR yg BRGYB

CODE:

Datei <cb_pr.py> kompilieren mit pythran -O3 cb_pr.py

import numpy as np

# pythran export check_patt(uint8[536870912])
# pythran export inc_depth(uint8[536870912],int,int)
# pythran export find_home(uint8[536870912],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[0]]
    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

Hauptskript:

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[0] = 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()[0]
for sol in sols:
    rec_sol(sol,"color")
    print();print()
# reset terminal colors
print("\x1B[0m")