Hexasweep (part 1): The Solver

Question

(This is part 1 in a two-part challenge.)

Your task is to solve a Hexasweep puzzle.

A Hexasweep puzzle is set out on a grid of diamonds arranged in hexagonal shapes, of which the board looks like a hexagon, like so:

         _____
        /\    \
  _____/ X\____\_____
 /\    \  / XX /\    \
/X \____\/____/X \____\
\ X/ XX /\    \ X/    /
 \/____/  \____\/____/
 /\    \  / X  /\    \
/  \____\/____/  \____\
\  / XX /\    \  / XX /
 \/____/  \____\/____/
       \ X/    /
        \/____/

The above image is composed of 7 hexagons (21 diamonds), and is thus a Hexasweep puzzle of size 2.

• If you want to expand it, cover the current Hexasweep puzzle with more hexagons (so that there are 19 hexagons - that will make a Hexasweep puzzle of size 3).

• The same goes for the other direction - to make a Hexasweep puzzle of size 1, remove the outermost layer of hexagons (so that there's 1 hexagon).

Each diamond can contain 0, 1 or 2 "bombs", with bombs depicted as X above. With bombs filled out, this is the final solution.

Numbers are marked on "intersection points", to show how many bombs are on the diamonds which are touching those intersection points - the intersection points of this grid are shown below using O.

         _____
        /\    \
  _____/  OO___\_____
 /\    \  OO   /\    \
/  OO___OO___OO  OO___\
\  OO   OO   OO  OO   /
 \/___OO  OO___OO____/
 /\   OO  OO   OO    \
/  OO___OO___OO  OO___\
\  OO   OO   OO  OO   /
 \/____/  OO___\/____/
       \  OO   /
        \/____/

As you can see, there are two "types" of intersection points - those with 3 diamonds touching it, and those with 6 (the one that are touching the edge of the board aren't counted):

  _____
 /\  XX\
/X OO___\
\ XOO   /
 \/____/

       /\
 _____/X \_____
 \ XX \ X/    /
  \____OO____/
  / XX OO  X \
 /____/  \____\
      \ X/
       \/

The two intersections would be marked with 4 and 8 respectively.

In the original Hexasweep puzzle above, the intersection numbers would be:

   3
4 5 4 2
 2 1 3
2 4 1 2
   1

Which would be condensed to:

3,4,5,4,2,2,1,3,2,4,1,2,1

Given an input in this "condensed form", you must output the original puzzle, in "condensed form" (see above).

The solved image (the first one, with the crosses) - which would be formed from the puzzle - would be read from top to bottom, starting from the left:

2,0,0,2,0,2,1,0,1,0,2,0,1,0,0,2,0,0,0,0,2

That is now the "condensed form" of the puzzle.

If there is more than 1 answer (as in the condensed form above), the output must be N.

Examples:

0,0,4,3,1,3,4,7,1,4,3,6,1 -> 0,0,0,0,1,0,0,2,0,0,0,2,0,1,0,1,2,0,0,2,2 (size 2 Hexasweep)
6 -> 2,2,2 (size 1 Hexasweep)
0,1,5,3,1,4,4,7,2,5,3,6,1 -> N (multiple solutions)

Specs:

• Any delimiter for the "condensed form" as input are allowed (it doesn't have to be , separating the numbers).
• You may output a list, or a string with any delimiter.
• Your program must be generalised: it must be able to solve Hexasweep puzzles of any size (at least from size 1 to size 4).

This is code-golf, so lowest amount of bytes wins!

Answer 1

Javascript (V8), 1509 bytes

V=>{S=Math.sqrt(V[L="length"])/3+1|0;C=(Y=Array)(3**(W=12*(S-1)||2))[F="fill"]``.map(c=>Y(G=3*S*(S-1)+1)[F]``.map(h=>[N=-1,N,N]))
O=[];R=Y(4*S-3)[F]``.map(r=>[]);for(r=0,c=1,m=S,i=0;i<G;++r>=m&&(r=0,m+=++c>S?N:1))R[r*2+(X=Math.abs)(S-c)][P="push"](i++,N)
R=R.map(r=>(r.pop(t=Y(((T=2*S-1)-r[L]+1)/2)[F](N)),t.concat(r,t)));I=R.flat()[K="filter"](Q=r=>r+1);J=[[m=1,0]]
if(S>1){for(i=0;i<S-1;i++)J[P]([m+=3,0]);for(i=0;i<S-1;i++)J[P]([m-1,2],[m,0]);for(i=0;i<S-1;i++)J[P]([m-=3,0])}M=[]
J[K](j=>(t=j[1],Y(j[0])[F]``[K](_=>M[P](t++%3))))
z=0;g=p=>{for(j=0;j<R[L];j++)if(p<(t=R[j][K](Q))[L]){a=R[b=j].indexOf(t[p]);break}else p-=t[L]}
M=M.map((v,i)=>v?(v<2?(g(z-1),[[I[z-1],1],[I[z-1],2],[R[b-1][++a],0],[R[b-1][a],2],[R[b+1][a],0],[R[b+1][a],1]]):(g(z),[[I[z],0],[R[b-1][a-1],2],[R[b+1][a-1],1]])):(x=[0,1,2].map(d=>[I[z],d]),z++,x))
C.map((c,i)=>{r=-2;s=_=>[...i.toString(3).padStart(W,0).substr(r+=2,2).split``.map(n=>+n),N];for(j=0;j<S;c[j++]=s())
t=S-1;for(j=1;j<S;j++)c[++t]=s(),c[t+=j+S-1]=s();for(j=S-2;j>0;j--)c[++t]=s(),c[t+=j+S-1]=s();if(S>1)for(j=0;j<S;j++)c[++t]=s()})
C.map(c=>{q=1;l:while(c.find(h=>h[0]<0|h[1]<0|h[2]<0))for(j=0;j<M[L];j++){t=M[j];if(t[K](Z=v=>!(c[v[0]][v[1]]+1))[L]==1){if((s=V[j]-t.reduce(U=(a,v)=>a+(c[v[0]][v[1]]+1||1)-1,0))<0||s>2){q=0;break l};r=t.find(Z);c[r[0]][r[1]]=s}};
M.map((t,j)=>{if(t.reduce(U,0)!=V[j])q=0})
q&&O[P](c)});if(O[L]>1)return"N";O=O[p=0];E=[];for(i=0;i<T;i++){a=T-X(S-i-1);for(j=0;j<a;j++)E[P](O[p+j][0]);for(j=0;j<a;j++)E[P](O[p][1],O[p++][2])}return E}

Wow. This was not as fun as I expected it would be.

This is by far not an optimal solution. It's hard to golf something this big. I think you could save a hundred bytes or so by brute forcing the answer instead. However, my goal wasn't to be super competitive (yet!), but instead to provide a baseline for other answers to work off of.

Seeing as this challenge hasn't been answered in the four years since it was asked, it obviously took a few days. The strategy I ended up using was to generate a list of all possible values for the outer ring of hexagons, and repeatedly fill in any diamonds whose values can be inferred from the vertexes near them. If any contradictions are found, that starting value is ignored and the next one is analyzed.

This likely costs a few bytes compared to brute forcing, but it means it can finish running before the inevitable heat death of the universe. It takes less than a second for size one, about half a minute for size two, and based on the time complexity somewhere in the span of a few weeks to a few months for size three (haven't tested yet). My computer doesn't actually have enough memory for attempting higher than size two (gives me invalid array length), but with enough time and memory it's theoretically possible to use this approach for puzzles with millions of hexagons.

If anyone wants to use this to develop a shorter or faster solution, here's the pre-golfed version of my code (it's not very pretty, but it works):

var hexasweep = function(vertexes) {
    var size = Math.sqrt(vertexes.length) / 3 + 1 | 0;
    
    var configs = new Array(3 ** (2 * (6 * (size - 1) || 1))).fill(0).map(c => new Array(3 * size * (size - 1) + 1).fill(0).map(h => [-1, -1, -1]));
    
    var solutions = [];
    
    var reference_array = new Array(4 * size - 3).fill(0).map(r => []);
    
    for (let r = 0, c = 0, m = size, i = 0; i < 3 * size * (size - 1) + 1; i++) {
        reference_array[r * 2 + Math.abs(size - c - 1)].push(i, -1);
        
        if (++r >= m) {
            m += (++c >= size ? -1 : 1);
            r = 0;
        }
    }
    
    for (let t, r, i = 0; i < reference_array.length; i++) {
        r = reference_array[i];
        
        r.pop();
        
        t = new Array(((2 * size - 1) - r.length) / 2).fill(-1);
        
        reference_array[i] = t.concat(r, t);
    }
    
    var reference = reference_array.flat().filter(r => r + 1);
    
    var m = 1, length_map = [];
    
    length_map.push([m = 1, 0]);
    
    if (size > 1) {
        for (let i = 0; i < size - 1; i++) {
            length_map.push([m += 3, 0]);
        }

        for (let i = 0; i < size - 1; i++) {
            length_map.push([m - 1, 2], [m, 0]);
        }

        for (let i = 0; i < size - 1; i++) {
            length_map.push([m -= 3, 0]);
        }
    }
    
    var vertex_map = [];
    
    for (let t, i = 0; i < length_map.length; i++) {
        t = length_map[i][1];
        
        for (let j = 0; j < length_map[i][0]; j++) {
            vertex_map.push(t++ % 3);
        }
    }
    
    for (let v, z = 0, b, a, g, i = 0; i < vertex_map.length; i++) {
        v = vertex_map[i];
        
        g = p => {
            for (let t, j = 0; j < reference_array.length; j++) {
                if (p < (t = reference_array[j].filter(r => r + 1)).length) {
                    b = j;
                    a = reference_array[j].indexOf(t[p]);

                    break;
                } else {
                    p -= t.length;
                }
            }
        }
        
        if (v == 0) {
            vertex_map[i] = [0, 1, 2].map(d => [reference[z], d]);
            z++;
        } else if (v == 2) {
            g(z);
            
            vertex_map[i] = [[reference[z], 0], [reference_array[b - 1][a - 1], 2], [reference_array[b + 1][a - 1], 1]];
        } else {
            g(z - 1);
            
            vertex_map[i] = [
                [reference[z - 1], 1],
                [reference[z - 1], 2],
                [reference_array[b - 1][a + 1], 0],
                [reference_array[b - 1][a + 1], 2],
                [reference_array[b + 1][a + 1], 0],
                [reference_array[b + 1][a + 1], 1]
            ];
        }
    }
    
    for (let r, s, t, c, i = 0; i < configs.length; i++) {
        c = configs[i];
        
        r = -2;
        s = _ => (i.toString(3).padStart(2 * (6 * (size - 1) || 1), 0).substr(r += 2, 2)).split("").map(n => +n).concat(-1);
        
        for (let j = 0; j < size; j++) {
            c[j] = s();
        }
        
        t = size - 1;
        
        for (let j = 1; j < size; j++) {
            c[++t] = s();
            c[t += j + size - 1] = s();
        }
        
        for (let j = size - 2; j >= 1; j--) {
            c[++t] = s();
            c[t += j + size - 1] = s();
        }
        
        if (size > 1) {
            for (let j = 0; j < size; j++) {
                c[++t] = s();
            }
        }
    }
    
    // Validate each
    
    for (let c, i = 0; i < configs.length; i++) {
        c = configs[i];
        
        (_ => {
            while (c.find(h => h[0] == -1 || h[1] == -1 || h[2] == -1)) {
                for (let t, r, s, j = 0; j < vertexes.length; j++) {
                    t = vertex_map[j];
                    
                    if (t.filter(v => !(c[v[0]][v[1]] + 1)).length == 1) {
                        if ((s = vertexes[j] - t.reduce((a, v) => a + (c[v[0]][v[1]] + 1 || 1) - 1, 0)) < 0 || s > 2) {
                            return;
                        }
                        
                        r = t.find(v => !(c[v[0]][v[1]] + 1));
                        
                        c[r[0]][r[1]] = s;
                    }
                }
            }
            
            for (let j = 0; j < vertexes.length; j++) {
                if (vertex_map[j].reduce((a, v) => a + (c[v[0]][v[1]] + 1 || 1) - 1, 0) != vertexes[j])
                    return;
            }
            
            solutions.push(c);
        })();
    }

    if (solutions.length > 1)
        return "N";
    
    // Convert to output list format
    
    var solution = solutions[0];
    
    var result = [];
    
    for (let p = 0, a, i = 0; i < 2 * size - 1; i++) {
        a = 2 * size - 1 - Math.abs(size - i - 1);
        
        for (let j = 0; j < a; j++) {
            result.push(solution[p + j][0]);
        }
        
        for (let j = 0; j < a; j++) {
            result.push(solution[p][1], solution[p++][2]);
        }
    }
    
    return result;
};

This challenge would actually be really fun as fastest-code: I think there are a lot of byte-expensive shortcuts that could really speed this up that I didn't have time to explore.

Thank you for a fun challenge.