Вступление

Арифметическая тюрьма - это специальное средство, которое заключает в себе положительные целые числа. Однако в последнее время положительные целые числа пытались убежать. Поэтому надзиратели решили убрать некоторые положительные целые числа, чтобы отправить сообщение другим целым числам. Они наняли разработчика программного обеспечения для написания программы, чтобы выяснить, какие целые числа исключить для достижения максимального эффекта.

Описание входа

Ввод осуществляется через STDIN, аргументы командной строки или пользовательскую функцию ввода (например, raw_input). Вы не можете иметь его в качестве аргумента функции или предварительно инициализированной переменной (например, эта программа ожидает ввода в переменную x).

Первая строка содержит одно положительное целое число, nгде 8 >= n >= 3. Далее следуют nстроки, содержащие nсимволы из набора [1,2,3,4,5,6,7,8,9]. Вот пример ввода:

5
22332
46351
65455
24463
65652

Описание выхода

Надзиратели хотели бы убрать числа, чтобы выполнялись следующие условия:

• В каждой строке и столбце результирующей сетки ни одно число не появится дважды;
• Два исключенных числа не могут быть смежными по горизонтали или вертикали;
• Выжившие числа должны образовывать ортогонально смежную группу - можно будет перейти от любого уцелевшего числа к любому другому уцелевшему числу, двигаясь только по горизонтали и вертикали и никогда не пересекая ни одно из удаленных чисел.

Выведите ввод (минус первая строка) с заменой удаленных чисел на #.

Там может быть более одного решения. Если это так, вы можете вывести любое решение.

Там также может быть никакого решения. Если это так, выведите строку no answer.

Вот возможный вывод для примера ввода:

#2#3#
46351
6#4#5
24#63
#56#2

Пример входов и выходов

Есть несколько выходов для каждого входа, поэтому эти выходы являются лишь примерами.

Входные данные:

5
46551
51565
32654
14423
43244

Выход:

46#51
#156#
326#4
1#423
#324#

Входные данные:

7
7183625
1681563
5238564
8786268
1545382
3814756
5325345

Выход:

71#362#
#6815#3
5238#64
#7#62#8
154#382
3814756
#325#4#

Входные данные:

8
21534768
75196287
68392184
96244853
44865912
76516647
89751326
43698979

Выход:

21#34768
#5196287
683#21#4
9#24#853
#4865912
7#51#64#
89751326
436#8#7#

Входные данные:

4
2222
2331
3112
1322

Выход:

no answer

Ruby, 346 344 329 316 байт, sl∞∞∞∞∞∞ww

Это код-гольф, а не код-быстрый, так что ...

N=/!/=~G=$*[1..-1]*?!
M=N*N
g=->i{(!G[i]||G[i]<?*||i<0||A[i])&&break
A[i]=0
[1,N+1,-1,-1-N].map{|a|g[i+a]}}
f=->w,a{A=[];g[/\d/=~G=a];/#.{#{N}}?#/!~G&&/(\d)([^!]*|.{#{N}}.{#{O=N+1}}*)\1/!~G&&A.count(0)+w==M&&N.times.map{|m|puts G[m*(1+N),N]}&&exit
(w...M).map{|j|b=a+'';b[j]=?#
w<M&&f[w+1,b]}}
f[0,G]
$><<"no answer"

Используйте это как:

mad_gaksha@madlab ~/Applications/Tools $ ruby -W0 c50442.rb 3 323 312 231
#23
312
231

Флаг -W0не нужен, но я предлагаю вам либо добавить его, чтобы отключить предупреждения, либо перенаправить stderr...

Скажите, хватит ли у вас терпения запустить его на примерах для n = 6,7,8

Изменения

• each⇨ map, благодаря @NotThatCharles
• проверьте наличие соседних удалений и одинаковые цифры на две regexpсекунды, аналогично тому, что предлагал @NotThatCharles
• немного оптимизирован вход для чтения
• меньше и медленнее

Рубин - 541 ..., 394

Основной алгоритм - это рекурсивный поиск дубликатов в глубину для утвердительного выбора, просматривая строку 1, затем столбец 1, затем строку 2 и т. Д., И проверяя, что два соседа не уничтожены и что сетка подключена (это break ifусловие в там, и бит, который предшествует этому).

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"

Некоторые аккуратные трюки:

if w[1]намного короче, if !w.one?и если вы знаете, что есть хотя бы один участник, это тот же результат.

Точно так же [0]короче, чем any?если нет блока, и s[j]это симпатичный ярлык для j<s.size(технически, это больше похоже на j.abs<s.size)

И y%N+(y/N).iнамного корочеComplex(y%N,y/N)

Кроме того, когда есть два сложных условия для генерации строк, это может быть короче, [cond1?str1a:str1b,cond2?str2a:str2b]*''чем добавить все парены или #{}в.

Разоблачение и объяснение:

(Это из 531-байтовой версии. Я внес изменения. Наиболее примечательно, что с тех пор я исключил обращение к продукту - просто решаю по одной цифре на строку / столбец за раз, а J теперь просто массив, проиндексированный целые числа. Все координаты просто целые числа.)

H рассчитывает соседей

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 это размер сетки

N = gets.to_i

K ключи к карте (комплексные числа)

# 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 карта ввода (джейл)

# 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 являются неубиваемыми ключами

# starts as K

Q является основным рекурсивным методом

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

Код выполняется с:

# run with whole board
Q[K]

# if we get here, we didn't hit an exit, so we fail
puts"no answer"

Изменения

394 добавил предложение @ blutorange ниже, и вырубил намного больше манипуляций

408 пересмотрен выход еще раз. Также используйте .minвместо, .inject(:+)так как я все равно беру один ряд.

417 короче выходной расчет

421 выпало комплексных чисел. Просто используйте целые числа. Сохранить пакет

Еще 450 улучшений ввода

456 улучшений ввода

462 дополнительных улучшения - особенно findнеselect

475 упал uи раздавил строителя

503 решает только одну повторяющуюся цифру на строку / столбец за раз.

530 использовать map &:popвместоvalues

531 вытащить лямбду, которая делает массив dupes

552 упс! пропустил требование

536 незначительно улучшенная совокупность массивов дупсов (что было раньше d)

541 начальный

HTML + JavaScript ( ES6 ) 459

Использование текстовой области HTML для получения многострочного ввода.

Чтобы проверить, запустите фрагмент в Firefox. Увеличьте текстовую область, если хотите, вставьте ввод внутри текстовой области (будьте осторожны: точный ввод, без лишних пробелов ни в одной строке) и уберите вкладку. Результат прилагается.

Метод: Рекурсивная Глубина Первого Серарха. Он находит неоптимальные решения для всех тестовых случаев в считанные секунды (это gode golf, но действительный ответ должен заканчиваться для обычных тестовых случаев)

<textarea onchange="s=this.value,
  z=s[0],o=-~z,k=[],X='no answer',f='#',
  (R=(s,t,h={},r=[],d=0)=>(
    s.map((v,i)=>v>0&&[i%o,~(i/o)].map(p=>h[p+=v]=[...h[p]||[],i])),
    [h[i][1]&&h[i].map(p=>r[d=p]=p)for(i in h)],
    d?r.some(p=>(
      (s[p+o]!=f&s[p-o]!=f&s[p-1]!=f&s[p+1]!=f)&&
      (
        g=[...s],g[p]=f,e=[...g],n=0,
        (F=p=>e[p]>0&&[1,-1,o,-o].map(d=>F(p+d),e[p]=--n))(p<o?p+o:p-o),
        t+n==0&&!k[g]&&(k[g]=1,R(g,t-1))
      )
    )):X=s.join('')
  ))([...s.slice(2)],z*z-1),this.value+=`

`+X"></textarea>

Первая попытка

Метод: Глубина Первый Serarch, не рекурсивный, используя пользовательский стек.
Функция может быть легко преобразован в поиск в ширину, chaging l.popк l.shift, поэтому использование очереди вместо стека, но это слишком медленно , и я не уверен , что он может найти оптимальное решение в любом случае.

S=s=>{
  z=s[0],o=-~z,s=[...s.slice(2)];
  k=[];
  l=[[z*z,s]];

  for(d=1;d&&(t=l.pop());)
  {
    [t,s]=t,--t,

    s.map((v,i)=>v>0&&[i%o,~(i/o)].map(p=>h[p+=v]=[...h[p]||[],i]),h={},r=[])

    d=0
    for(i in h)h[i][1]&&h[i].map(p=>r[d=p]=p)

    r.map(p=>
      (s[p+o]!='#'&s[p-o]!='#'&s[p-1]!='#'&s[p+1]!='#')&&
      (
        g=[...s],g[p]='#',
        f=[...g],n=0,
        (F=p=>f[p]>0&&[1,-1,o,-o].map(d=>F(p+d),f[p]=--n))(p<o?p+o:p-o),
        t+n||k[g]||(k[g]=l.push([t,g]))
      )
    )
  }
  return d?'no answer':s.join('')
}

// TEST
cases=[
 ['5\n22332\n46351\n65455\n24463\n65652','#2#3#\n46351\n6#4#5\n24#63\n#56#2']
,['5\n46551\n51565\n32654\n14423\n43244','46#51\n#156#\n326#4\n1#423\n#324#']
,['7\n7183625\n1681563\n5238564\n8786268\n1545382\n3814756\n5325345'
 ,'71#362#\n#6815#3\n5238#64\n#7#62#8\n154#382\n3814756\n#325#4#']
,['8\n21534768\n75196287\n68392184\n96244853\n44865912\n76516647\n89751326\n43698979'
 ,'21#34768\n#5196287\n683#21#4\n9#24#853\n#4865912\n7#51#64#\n89751326\n436#8#7#']  
,['4\n2222\n2331\n3112\n1322','no answer']
]

  var out = ''
  var nt=0
  var exec =_=>{ 
    var t=cases[nt++];
    if (t) {
      var r = S(t[0]).replace(/#/g,'<b>#</b>');
      var k = t[1].replace(/#/g,'<b>#</b>');
      out += '<tr><th>Input<th>Result<th>Expected</tr>'+
      '<tr><td>'+t[0]+'</td><td>'+r+'</td><td>'+k+'</td></tr>';
      T.innerHTML = out + 'test ' + nt + ' done';
      setTimeout(exec, 100);
    }
    else
    {
      T.innerHTML = out;
    }
  }
  T.innerHTML = "...wait ..."
  setTimeout(exec, 100);  

table {
  font-size: 12px;
}
td {
  font-family: monospace;
  white-space: pre;
  vertical-align: bottom;
  margin: 2x 4px;
}

b {
  color: #ccc;  
}

<table id=T>
</table>