Comment on Find Cow
Snazz@lemmy.world 1 week agoWhat I would have done is started filling in letters randomly and every time a C or W ends up next to an O, choose the same letter or an O to put on the opposite side of the O.
Its hard to prove, but I’m pretty sure there isn’t a situation where a space can’t be filled in with this algorithm.
MatSeFi@lemmy.liebeleu.de 1 week ago
Yes, this would work — but it comes with a subtle statistical bias: the character ‘W’ ends up underrepresented. With a naïve “avoid COW” approach, only about 25% of the grid will typically be ‘W’.
A more elegant solution would be:
That keeps the distribution much closer to uniform while still guaranteeing a valid puzzle. Then just insert the single “COW” manually wherever you want the hidden solution to be.
Julia code example
julia s= (320,180) #size m=rand([‘C’,‘O’,‘W’],s) #random init c=1 while c>0 #iterate till solved c=0 for i in 1:first(s) for j in 1:last(s) #check for ‘COW’ in each cluster of 3 and copy a character #from a rendom cell to an other random cell of the cluster if found if i>2 && m[i-2:i,j] ==[‘C’,‘O’,‘W’] #vertical c +=1 r =shuffle([1,2]) m[i-r[1],j] = m[i-r[2],j] end if j>2 && m[i,j-2:j] ==[‘C’,‘O’,‘W’] #horizontal c +=1 r =shuffle([0,1,2]) m[i,j-r[1]] = m[i,j-r[2]] end end end endThe neat part is that this preserves an almost perfectly balanced character frequency.
For comparison, the puzzle in the example image seems to contain roughly:
C: ~260 (~25%) O: ~520 (~50%) W: ~244 (~25%)
So the original author clearly used a different generation strategy.
Possibly on purpose: visually, ‘C’ and ‘O’ are much easier to confuse than ‘W’. Reducing the number of 'W’s therefore increases the search difficulty. In that sense, the approach suggested by @Snazz@lemmy.world is probably preferable: keep the distribution mostly balanced, but intentionally bias it just enough to make the puzzle psychologically annoying.
I wonder if there is a non iterative way to generate this puzzle with a ‘uniform’ character distribution 🤔