Игра

В последнее время большую часть моего времени занимала увлекательная игра на моем телефоне под названием «Логические точки», которая вдохновила меня на написание этой задачи. Проще объяснить правила, если я покажу вам игровой экран, поэтому вот скриншот нерешенной и решенной головоломки:

Теперь здесь есть три основных момента, на которые следует обратить внимание.

1. Игровое поле (сетка квадратов 4х4 в центре)
2. Требуемые фигуры (связанные точки во втором столбце сверху, под партитурой и меню и т. Д.), Которые представляют собой все линии или aпо 1 прямоугольнику
3. Числа в строках и столбцах, обозначающие количество точек в столбце для решения

Цель игры состоит в том, чтобы вписать нужные фигуры в сетку. Вы можете вращать фигуры, но они не могут войти по диагонали.

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

Вот более крупная и немного более сложная сетка:

Обратите внимание, что в нерешенной головоломке уже заполнено несколько квадратов. Серые квадраты означают заблокированные квадраты, на которые вы НЕ МОЖЕТЕ поставить точку. Точки с хвостами говорят вам, что точка находится в этом месте, и она связана по крайней мере с еще одной точкой в ​​направлении хвоста, но не в любом другом направлении (включая противоположное направление).

нотация

В оставшейся части этого поста я буду ссылаться на доску, используя следующие символы:

• <,>, ^, v - обозначает предварительно установленную точку с хвостом, идущим в направлении точки
• * - обозначает точку. Если задано на нерешенной сетке (вход), это индивидуальная форма. Если на выходе, то это связано с точками вокруг него.
• # - обозначает заблокированный квадрат сетки (где вы не можете поместить точку)
• -, | (дефис и полоса) - обозначает точку с правым и левым хвостом и точку с хвостом вверх и вниз соответственно
• ** (пробел) - ** Обозначает пустой пробел

Используя эти символы, последний пример (нерешенный) может быть представлен следующим образом:

 <    



    # 
 ^ #

И решение может быть представлено как:

*< * *
   *  
     *
 *   *
 * *#*
 ^ # *

Обратите внимание, что две фигуры не могут соприкасаться по горизонтали, вертикали или диагонали , поэтому следующий случай недопустим:

 *** 
**   
  ** 

Вызов

Ваша задача - решить любую головоломку с логическими точками, от 4x4 до 9x9 включительно. Вы получите четыре строки ввода, затем игровое поле. Строки будут следующими:

• 1-я строка, фигуры - фигуры, которые нужно найти, каждая из которых дана в форме sizexquantity(например, 3x2для двух фигур длиной три) и разделена пробелом. Пример строки:3x1 2x1 1x1
• 2-я строка, Столбцы - разделенный пробелами список необходимого количества точек для каждого столбца. Пример строки:1 1 2 2
• 3-я строка, Rows - разделенный пробелами список необходимого количества точек для каждой строки. Пример строки:3 0 3 0
• 4-я строка, размер доски - одно целое число, размер доски, B

Затем дается доска, и это Bстроки ввода, представляющие доску с использованием обозначений, упомянутых выше. Например, полный ввод для последнего примера приведен ниже:

4x1 3x1 2x2 1x2
1 4 0 3 0 5
4 1 1 2 3 2
6
 <    



    # 
 ^ #  

Ваша программа затем выведет решенную плату в той же записи. Соответствующий вывод для вышеуказанного ввода выглядит следующим образом:

** * *
   *  
     *
 *   *
 * *#*
 * # *

Обратите внимание, что игровое поле может иметь несколько решений. В этом случае просто выведите одно правильное решение. Кроме того, ваша программа должна вывести правильное решение в течение 10 секунд на приемлемом настольном компьютере для сложной сетки 10x10.

Это код гольф, поэтому выигрывает минимум байтов.

Тестовые случаи

Вход 1

3x2 1x4
2 2 3 1 2
4 0 3 0 3
5


    #
  #  
    *

Выход 1

*** *

 ***#
  #  
* * *

Вход 2

3x1 1x6
2 0 4 0 3
3 1 2 1 2
5
*    


   # 

Выход 2

* * *
  *  
  * *
*  # 
  * *

Вход 3

5x1 4x1 2x1 1x2
1 2 3 3 2 2
0 5 0 4 0 4
6
#     
  -   


 #    
   <  

Выход 3

#     
 *****

 **** 
 #    
* ** *

Python 2: 766 739 696 663 633 байта

def f(B,S,o=0):
 if[]==S:print'\n'.join(B);exit()
 s=S[0]
 for i in r:
  for j in R(Z-s+1):
   if(B[i][j]in' '+'>v'[o])*(B[i][j+s-1]in' '+'<^'[o])*({' ','-|'[o]}>=set(B[i][j+1:j+s-1]))*all(B[x][y]in'# 'for x,y in [(x,y)for y in R(j-1,j+s+1)for x in i-1,i+1]+[(i,j-1),(i,j+s)]if 0<=x<Z>y>=0):q=B[:];q[i]=q[i][:j]+'*'*s+q[i][j+s:];q=(q,t(q))[o];any((t(q)+q)[k].count('*')>m[k]for k in R(Z+Z))or f(q,S[1:])
 o or f(t(B),S,1)
y=raw_input;S=[];s=str.split
for i in s(y()):u,v=map(int,s(i,'x'));S+=[u]*v
m=map(int,s(y())+s(y()));Z=input();R=range;r=R(Z);B=[y()for _ in r];J=''.join;t=lambda x:map(J,zip(*x))
f(B,S[:len(S)-J(B).count('*')])

Посмотрите, как это работает онлайн: Ideone.com (онлайн-версия может быть слишком медленной для больших и сложных сеток, в автономном режиме все должно быть в порядке)

Ввод осуществляется через стандартный ввод, просто скопируйте и вставьте строки из OP (но будьте осторожны, stackexchange иногда удаляет пробелы или строки).

Некоторые основные идеи этого кода: он использует рекурсивную функцию f. fпытается разместить одну фигуру на доске. Для каждого возможного местоположения он называет себя модифицированной доской. В нем 3 петли. oопределяет ориентацию (2 - горизонтальная, 3 - вертикальная). Он всегда будет располагать форму горизонтально, поэтому в конце o=2он будет транспонировать доску с функцией t. iстрока и jвсе возможные начальные столбцы. Затем происходит много проверок, если у концов фигуры есть действительные символы, если у середины фигуры есть действительные символы и если окружение пусто.

JavaScript (ES6) 661 667 695 702 745 755 786 790 784 798

Работа в процессе, может быть сокращена. Вероятно, слишком медленно на сложной сетке. Возможно, нет.

Редактировать немного дольше, намного быстрее.
Редактировать 2 Исправление ошибки, проверка столбцов / строк. Кстати, теперь это быстрее

Функция М является основной. Параметр w представляет собой многострочную строку со всеми входными данными. Функция анализирует вход и готовит стартовую доску. Символы <>^v|-*на стартовой доске заменены на ,, каждый ,должен быть заменен *на правильное решение.

Функция R пытается рекурсивно разместить все фигуры на доске. Когда фигура размещается, она вызывает себя, передавая более короткий список фигур и измененную доску. Когда все фигуры размещены, решение по-прежнему может быть недействительным, если их ,не заменить *.

Функция P проверяет, можно ли поместить фигуру в заданную позицию и ориентацию. Он проверяет все затраты (внутри доски, без перекрытия, без касания, действительное количество строк и столбцов)

M=w=>(
  [x,c,r,z]=w=w[S='split'](n='\n'),
  (b=[...w.slice(4).join(n)])
  .map((c,p)=>~(k='*<>-*^v|'.indexOf(c))&&[(q=k>3?z:1,0),k&1&&-q,k&2&&q].map(o=>b[p+o]=0),
    c=c[S](e=' '),r=r[S](e),w=z++,f='*',s='',x[S](e).map(v=>s+=v[0].repeat(v[2]))),
  R=(s,b,x=0,y=0,n=s[0],V=i=>b[i]>'#',
    P=(p,o,q,t,g,l,d=[...b])=>{
        if(l<z-n&!V(p+o*l-o)&!V(p+o*l+o*n))
        {
          for(i=-1;v=d[p],++i<w;p+=o,t-=v==f)
            if(i>=l&i-n<l)
              for(v!=e&v!=0|[q,w,~z].some(w=>V(p+w)|V(p-w))?t=0:d[p]=f,j=o*i,u=k=0;
                  ++k<z;(u+=d[j]==f)>g[i]?t=0:j+=q);
          return t>=n&&d.join('')
        }
    })=>{
    if(b){
      if(!n)return~b.search(0)?0:b;
      for(s=s.slice(1);y<w||(y=0,++x<w);++y)
        if(h=R(s,P(y*z,1,z,r[y],c,x))||n>1&&R(s,P(x,z,1,c[x],r,y)))return h
    }
  })(s,b)

Тест в консоли FireFox / FireBug

;['3x2 1x4\n2 2 3 1 2\n4 0 3 0 3\n5\n     \n     \n    #\n  #  \n    *\n'
,'3x1 1x6\n2 0 4 0 3\n3 1 2 1 2\n5\n*    \n     \n     \n   # \n     \n'
,'5x1 4x1 2x1 1x2\n1 2 3 3 2 2\n0 5 0 4 0 4\n6\n#     \n  -   \n      \n      \n #    \n   <  \n'
,'4x1 3x1 2x2 1x2\n1 4 0 3 0 5\n4 1 1 2 3 2\n6\n <    \n      \n      \n      \n    # \n ^ #  \n']
.forEach(x=>console.log(x,M(x).replace(/ /g,'`'))) // space replaced with ` for clarity

Выход (общее время выполнения <1сек)

3x2 1x4
2 2 3 1 2
4 0 3 0 3
5


    #
  #  
    *

***`*
`````
`***#
``#``
*`*`*

3x1 1x6
2 0 4 0 3
3 1 2 1 2
5
*    


   # 


*`*`*
``*``
``*`*
*``#`
``*`*

5x1 4x1 2x1 1x2
1 2 3 3 2 2
0 5 0 4 0 4
6
#     
  -   


 #    
   <  

#`````
`*****
``````
`****`
`#````
*`**`*

4x1 3x1 2x2 1x2
1 4 0 3 0 5
4 1 1 2 3 2
6
 <    



    # 
 ^ #  

**`*`*
```*``
`````*
`*```*
`*`*#*
`*`#`*