Ruby - 541..., 394
The basic algorithm is a recursive depth-first search of duplicates to affirmatively select, looking through row 1, then column 1, then row 2, etc, and checking that two neighbors are not killed and that the grid is connected (that's the break if clause in there, and the bit that comes before it).
K=(0...(N=gets.to_i)*N).to_a
J=gets(p).split*''
H=->m{K&[m+1,m-1,m+N,m-N]}
Q=->k{s=[k[j=0]]
(j=s.size
s.map{|x|(s+=H[x]&k).uniq!})while s[j]
break if(K-k).any?{|m|(H[m]-k)[0]}||k!=k&s
$><<K.map{|m|[k.index(m)?J[m]:?#,m%N>N-2?"
":p]}*''|exit if !g=((0...N*2).map{|x|(k.select{|m|m.divmod(N)[x/N]==x%N}.group_by{|m|J[m]}.find{|l,c|c[1]}||[])[1]}-[p]).min
g.map{|d|Q[k-g<<d]}}
Q[K]
puts"no answer"
Some neat tricks:
if w[1] is much shorter than if !w.one? and if you know there's at least one member, it's the same result.
Similarly, [0] is shorter than any? if there's no block, and s[j] is a cute shortcut for j<s.size (technically, it's more like j.abs<s.size)
And y%N+(y/N).i is much shorter than Complex(y%N,y/N)
Also, when there's two complicated conditionals to generate strings, it might be shorter to do [cond1?str1a:str1b,cond2?str2a:str2b]*'' than to add all the parens or #{}s in.
Ungolfing and explanation:
(This is from the 531 byte version. I've made changes. Most notably, I've since eliminated the call to product - just solve one digit per row/column at a time, and J is now just an array, indexed by integers. All coordinates are just integers.)
H calculates neighbors
def H m
# m, like all indices, is a complex number
# where the real part is x and the imaginary is y
# so neighbors are just +/-i and +/-1
i='i'.to_c
neighborhood = [m+1, m-1, m+i, m-i]
# and let's just make sure to eliminate out-of-bounds cells
K & neighborhood
end
N is the size of the grid
N = gets.to_i
K are the keys to the map (complex numbers)
# pretty self-explanatory
# a range of, e.g., if N=3, (0..8)
# mapped to (0+0i),(1+0i),(2+0i),(0+1i),(1+1i),(2+1i),...
K = (0..N**2-1).map{|y| (y%N) +(y/N).i }
J is the input map (jail)
# so J is [[0+0,"2"],[0+1i,"3"],....].to_h
J=K.zip($<.flat_map {|s|
# take each input line, and...
# remove the "\n" and then turn it into an array of chars
s.chomp.chars
}).to_h
k are the non-killed keys
# starts as K
Q is the main recursive method
def Q k
j=0 # j is the size of mass
# the connected mass starts arbitrarily wherever k starts
mass=[k[0]]
while j < s.size # while s hasn't grown
j = mass.size
mass.each{|cell|
# add all neighbors that are in k
(mass+=H[cell] & k).uniq!
}
end
# if mass != k, it's not all orthogonally connected
is_all_connected = k!=k&mass
# (K-k) are the killed cells
two_neighbors_killed = (K-k).any?{|m|
# if any neighbors of killed cells aren't in k,
# it means it was killed, too
(H[m]-k)[0]
}
# fail fast
return if two_neighbors_killed || is_all_connected
def u x
x.group_by{|m|J[m]}.select{|l,c|c[1]}
end
rows_with_dupes = Array.new(N){|r|u[k.select{|m|m.imag==r}]}
cols_with_dupes = Array.new(N){|r|u[k.select{|m|m.real==r}]}
# dupes is an array of hashes
# each hash represents one row or column. E.g.,
# {
# "3"=>[(0+0i),(1+0i),(3+0i)],
# "2"=>[(2+0i),(4+0i)]
# }
# means that the 0th, 1st and 3rd cells in row 0
# all are "3", and 2nd and 4th are "2".
# Any digits without a duplicate are rejected.
# Any row/col without any dupes is removed here.
dupes = (rows_with_dupes+cols_with_dupes-[{}])
# we solve one row at a time
first_row = dupes[0]
if !first_row
# no dupes => success!
J.map{|m,v|k.member?(m)?v:?#}.each_slice(N){|s|puts s*''}
exit
else
# the digit doesn't really matter
t=first_row.values
# cross-multiply all arrays in the row to get a
# small search space. We choose one cell from each
# digit grouping and drop the rest.
t.inject(:product).map{ |*e|
# Technically, we drop all cells, and add back the
# chosen cells, but it's all the same.
new_k = k-t.flatten+e.flatten
# and then search that space, recursively
Q[new_k]
}
end
end
The code is executed with:
# run with whole board
Q[K]
# if we get here, we didn't hit an exit, so we fail
puts"no answer"
Changelog
394 added @blutorange's suggestion below, and chopped out a lot more manipulation
408 revised output once more. Also use .min instead of .inject(:+) since I'm just taking one row anyway.
417 shorter output calculation
421 dropped complex numbers. Just use integers. Save a bundle
450 more input improvements
456 input improvements
462 incremental improvements - esp. find, not select
475 dropped u and squashed the row/col dupe builder
503 only solve one duplicate digit per row/column at a time.
530 use map &:pop instead of values
531 pull out the lambda that makes the dupes array
552 oops! missed a requirement
536 marginally improved population of dupes array (what was formerly d)
541 initial
4
(Also known as Singles.)
– Doorknob – 2015-05-19T11:53:55.033This puzzle is excellent. Thank you. Working on a solution – Not that Charles – 2015-05-19T19:13:18.507
1I like this puzzle, but it cannot be answered "as is" using JavaScript in a browser, as the only user input method
promptdoes not allow multi line input. – edc65 – 2015-05-22T13:40:43.743