What 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.
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:
fill the grid completely at random
search for every “COW” cluster
whenever one is found, copy a random character from one cell in the cluster into another cell of the same cluster
Iterate until no “COW” remains
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
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
end
The 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 🤔
Found it. I wonder what the designer did to make sure to have exactly one cow in there.
What 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.
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
The 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 🤔
Top of the page says find 1 cow, so yes