Мирные сосуществующие армии

15

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

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

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

Это код-гольф, поэтому применяются стандартные правила для тега.

OEIS A250000

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

1: 0
2: 0
3: 1
4: 2
5: 4
6: 5
7: 7
8: 9
9:12
10: 14
11: 17
12: 21
13: 24
code-golf chess Пост Рок Гарф Хантер
источник
Прочитав ссылку OEIS, я не уверен, что существуют известные решения для произвольной длины стороны.
Келли Лоудер
5
@KellyLowder Вы всегда можете сделать это грубо!
musicman523
2
@ musicman523, что-то вроде 3 ^ (6 ^ 2) или 10 ^ 17 возможных состояний для доски 6x6.
Келли Лоудер
5
@KellyLowder Я не говорил, что это будет быстро: P
musicman523
Обрезка ускорит вещи.
CalculatorFeline

Ответы:

8

C, 476 байт, DFS, повторяющая белых королев, O (2 n 2 )

#define R return
#define Z(q)for(j=q;j<I;j++)
#define Q(q)memset(q,0,4*J);
#define U(q)S(w[k]/I q j,w[k]%I+j)
int*c,*w,*Y,j,k,r,I,J,m;T(i,j){R i*I+j;}S(x,y){x>=0&&x<I&&y>=0&&y<I?Y[T(x,y)]=1:0;}g(l){int i;if(l==m){Q(Y)for(k=m;k--;){Z(0)Y[T(w[k]/I,j)]=Y[T(j,w[k]%I)]=1;Z(-I)U(+),U(-);}for(r=k=J;k--;)r-=Y[k];R r>=m;}for(i=!l?0:w[l-1]+1;i<J;i++){if(!c[i]){c[i]=1;w[l]=i;if(g(l+1))R 1;c[i]=0;}}R 0;}f(s){I=s;J=I*I;int C[J],W[J],y[J];c=C;w=W;Y=y;for(m=1;;m++){Q(c)if(!g(0))R m-1;}}

518 байт, DFS с обрезкой, O (2 n )

#define R return
#define Z(q)for(j=q;j<I;j++)
#define Q(q)memset(q,0,4*J);
#define V(Q)t=Q;if(!Y[t]){G-=Y[t]=1;b[B++]=t;}
#define F(q)if(S(x q j,y+j)){V((x q j)*I+y+j)}
int*c,*w,*Y,j,k,r,I,J,m;S(x,y){R x>=0&&x<I&&y>=0&&y<I;}D(l,H){int i,b[J],B,t,x,y,G;if(l==m)R 1;for(i=!l?0:w[l-1]+1;i<J;i++){if(!c[i]){c[i]=1;w[l]=i;x=i/I;y=i%I;G=H;Z(B=0){V(x*I+j)V(j*I+y)}Z(-I){F(+)F(-)}if(G>=m&&D(l+1,G))R 1;for(j=B;j--;)Y[b[j]]=0;c[i]=0;}}R 0;}f(s){I=s;J=I*I;int C[J],W[J],y[J];c=C;w=W;Y=y;for(m=1;;m++){Q(c)Q(Y)if(!D(0,J))R m-1;}}

577 байт, DFS повторяет белые и черные королевы, O (?)

#define R return
#define U(V,r,q)S(V,r[i]/I q j,r[i]%I+j)
#define W(q)for(j=q;j<I;j++)
#define Z(r,q,t,v)for(i=0;i<r;i++){t[q[i]]=1;W(0)v[T(q[i]/I,j)]=v[T(j,q[i]%I)]=1;W(-I)U(v,q,+),U(v,q,-);};
#define P(K,L,M)memcpy(v,K,4*J);for(i=0;i<J;i++)if(!v[i]){L[M++]=i;if(g(E,N,!C))R 1;M--;};
int*w,*b,m,I,J;T(i,j){R i*I+j;}Q(int*q){memset(q,0,4*J);}S(V,x,y)int*V;{x>=0&&x<I&&y>=0&&y<I?V[T(x,y)]=1:0;}g(E,N,C){int i,j,v[J],X[J],Y[J];if(E==m&&N==m)R 1;Q(X);Q(Y);Z(E,w,X,Y)Z(N,b,Y,X)if(C){P(Y,b,N)}else{P(X,w,E)}R 0;}f(q){I=q,J=I*I;int W[J],B[J];w=W,b=B;for(m=1;;m++)if(!g(0,0,0))R m-1;}

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

Таблица скорости (в секундах):

+---+----------------------+---------------------+-----------------+--------+
| n |      DFS w & b       |        DFS w        |  DFS w/ pruning | Clingo |
+---+----------------------+---------------------+-----------------+--------+
| 3 |                 0.00 |                0.00 |            0.00 |   0.01 |
| 4 |                 0.00 |                0.00 |            0.00 |   0.02 |
| 5 |                 0.47 |                0.16 |            0.00 |   0.04 |
| 6 |                20.62 |                1.14 |            0.00 |   0.60 |
| 7 |              1125.07 |              397.88 |            0.63 |  18.14 |
| 8 |                      |                     |            1.28 | 979.35 |
| 9 |                      |                     |           23.13 |        |
+---+----------------------+---------------------+-----------------+--------+
Кейу Ган
источник
2

Клинго , 90 байт

{q(1..n,1..n)}.a(X+(-I;0;I),Y+(0;I)):-q(X,Y),I=-n..n.:~K={q(X,Y)},{a(1..n,1..n)}n*n-K.[-K]

демонстрация

$ clingo peaceable.lp -cn=6
clingo version 5.1.0
Reading from peaceable.lp
Solving...
Answer: 1

Optimization: 0
Answer: 2
q(6,1) a(7,1) a(7,2) a(8,1) a(8,3) a(9,1) a(9,4) a(10,1) a(10,5) a(11,1) a(11,6) a(12,1) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(4,1) a(4,3) a(3,1) a(3,4) a(2,1) a(2,5) a(1,1) a(1,6) a(0,1) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,0) a(4,-1) a(0,7) a(1,-4) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(0,-5) a(12,7)
Optimization: -1
Answer: 3
q(1,6) q(6,1) a(7,1) a(7,2) a(7,6) a(8,1) a(8,3) a(9,1) a(9,4) a(10,1) a(10,5) a(11,1) a(11,6) a(12,1) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(5,6) a(4,1) a(4,3) a(4,6) a(3,1) a(3,4) a(3,6) a(2,1) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,5) a(0,6) a(-1,4) a(-1,6) a(-2,3) a(-2,6) a(-3,2) a(-3,6) a(-4,1) a(-4,6) a(-5,6) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,0) a(4,-1) a(0,7) a(1,7) a(2,7) a(-1,8) a(1,8) a(3,8) a(-2,9) a(1,9) a(-3,10) a(1,10) a(-4,11) a(1,11) a(-5,12) a(1,-4) a(1,0) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(4,9) a(5,10) a(6,11) a(1,12) a(-5,0) a(0,-5) a(7,12) a(12,7)
Optimization: -2
Answer: 4
q(1,6) q(6,1) q(6,6) a(7,1) a(7,2) a(7,5) a(7,6) a(8,1) a(8,3) a(8,4) a(8,6) a(9,1) a(9,3) a(9,4) a(9,6) a(10,1) a(10,2) a(10,5) a(10,6) a(11,1) a(11,6) a(12,1) a(12,6) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(5,5) a(5,6) a(4,1) a(4,3) a(4,4) a(4,6) a(3,1) a(3,3) a(3,4) a(3,6) a(2,1) a(2,2) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,5) a(0,6) a(-1,4) a(-1,6) a(-2,3) a(-2,6) a(-3,2) a(-3,6) a(-4,1) a(-4,6) a(-5,6) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(12,0) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,0) a(4,-1) a(0,7) a(1,7) a(2,7) a(5,7) a(-1,8) a(1,8) a(3,8) a(4,8) a(-2,9) a(1,9) a(3,9) a(-3,10) a(1,10) a(2,10) a(-4,11) a(1,11) a(-5,12) a(0,12) a(1,-4) a(1,0) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(6,8) a(4,9) a(6,9) a(5,10) a(6,10) a(6,11) a(1,12) a(6,12) a(-5,0) a(0,-5) a(0,0) a(7,7) a(8,8) a(9,9) a(10,10) a(11,11) a(7,12) a(12,7) a(12,12)
Optimization: -3
Answer: 5
q(1,1) q(1,6) q(6,1) q(6,6) a(7,1) a(7,2) a(7,5) a(7,6) a(8,1) a(8,3) a(8,4) a(8,6) a(9,1) a(9,3) a(9,4) a(9,6) a(10,1) a(10,2) a(10,5) a(10,6) a(11,1) a(11,6) a(12,1) a(12,6) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(5,5) a(5,6) a(4,1) a(4,3) a(4,4) a(4,6) a(3,1) a(3,3) a(3,4) a(3,6) a(2,1) a(2,2) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,2) a(0,5) a(0,6) a(-1,1) a(-1,3) a(-1,4) a(-1,6) a(-2,1) a(-2,3) a(-2,4) a(-2,6) a(-3,1) a(-3,2) a(-3,5) a(-3,6) a(-4,1) a(-4,6) a(-5,1) a(-5,6) a(7,-5) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(12,0) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,-3) a(5,0) a(4,-2) a(4,-1) a(3,-1) a(2,0) a(0,7) a(1,7) a(2,7) a(5,7) a(-1,8) a(1,8) a(3,8) a(4,8) a(-2,9) a(1,9) a(3,9) a(-3,10) a(1,10) a(2,10) a(-4,11) a(1,11) a(-5,7) a(-5,12) a(0,12) a(1,-5) a(1,-4) a(1,-3) a(1,-2) a(1,-1) a(1,0) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(6,8) a(4,9) a(6,9) a(5,10) a(6,10) a(6,11) a(1,12) a(6,12) a(-5,-5) a(-5,0) a(-4,-4) a(-3,-3) a(-2,-2) a(-1,-1) a(0,-5) a(0,0) a(7,7) a(8,8) a(9,9) a(10,10) a(11,11) a(7,12) a(12,7) a(12,12)
Optimization: -4
Answer: 6
q(1,2) q(1,3) q(2,2) q(2,3) q(2,6) a(7,1) a(7,2) a(7,3) a(7,6) a(8,2) a(8,3) a(8,6) a(6,2) a(6,3) a(6,6) a(5,2) a(5,3) a(5,5) a(5,6) a(4,1) a(4,2) a(4,3) a(4,4) a(4,5) a(4,6) a(3,1) a(3,2) a(3,3) a(3,4) a(3,5) a(3,6) a(2,1) a(2,2) a(2,3) a(2,4) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,2) a(0,3) a(0,4) a(0,5) a(0,6) a(-1,1) a(-1,2) a(-1,3) a(-1,4) a(-1,5) a(-1,6) a(-2,2) a(-2,3) a(-2,5) a(-2,6) a(-3,1) a(-3,2) a(-3,3) a(-3,6) a(-4,2) a(-4,3) a(-4,6) a(-5,2) a(-5,3) a(7,-4) a(7,-3) a(7,-2) a(8,-4) a(8,-3) a(8,0) a(6,-3) a(6,-2) a(6,-1) a(5,-2) a(5,-1) a(5,0) a(4,-1) a(4,0) a(3,0) a(2,0) a(1,7) a(2,7) a(3,7) a(5,7) a(0,8) a(1,8) a(2,8) a(4,8) a(-2,7) a(-1,9) a(1,9) a(2,9) a(-3,7) a(-3,8) a(-2,10) a(2,10) a(-4,7) a(-4,8) a(-4,9) a(-3,11) a(-5,8) a(-5,9) a(-4,12) a(1,-4) a(1,-3) a(1,-2) a(1,-1) a(1,0) a(2,-4) a(2,-3) a(2,-2) a(2,-1) a(6,7) a(6,8) a(5,9) a(6,10) a(2,11) a(2,12) a(-5,-4) a(-5,-3) a(-4,-4) a(-4,-3) a(-4,-2) a(-4,0) a(-3,-3) a(-3,-2) a(-3,-1) a(-2,-2) a(-2,-1) a(-2,0) a(-1,-1) a(-1,0) a(0,0) a(7,7) a(7,8) a(8,8) a(7,9) a(8,9) a(7,11) a(8,12)
Optimization: -5
OPTIMUM FOUND

Models       : 6
  Optimum    : yes
Optimization : -5
Calls        : 1
Time         : 0.733s (Solving: 0.71s 1st Model: 0.00s Unsat: 0.71s)
CPU Time     : 0.730s
Андерс Касеорг
источник
не могли бы вы написать небольшое объяснение?
Кейу Ган
2

Python 2 | 325 284 217 байт

Попробуйте онлайн!

from itertools import*
N=input()
r=range(N*N)
for n in r:
 g=r
 for s in combinations(g,n):
    for p in s:g=filter(lambda q:all([abs(q%N-p%N)!=abs(q/N-p/N),q%N!=p%N,q/N!=p/N]),g)
    if len(g)>=n:break
    g=r
 else:exit(n-1)

Редактировать: заменены кортежи с целыми числами в g и других тривиальных редактированиях.

Edit2: Байт до 217 благодаря musicman523 и CalculatorFeline !

Как это устроено

Программа перебирает все возможные позиции nкоролев и отфильтровывает немирные точки, gвызванные положением королев. Если оставшиеся точки больше, чем nтогда, это означает, что nармии королевы могут оставаться мирно. Если для следующего значения nмирной ситуации не найдено, то программа завершает работу с кодом выхода:, n-1который является ответом. Короче говоря, это грубая сила

Программу можно сделать быстрее, изменив последние две строки на

for n in range(N**2):
    if not z(n,N):print n-1;break
dark32
источник
2
Совет: 1 пробел и 1 табуляция - это разные уровни отступов в Python 2. Также вы можете использовать from module import*для импорта всего из модуля и сохранения байтов.
CalculatorFeline
1
Переводчик Python 2, 217 байт
musicman523
1

Haskell , 169 156 153 152 байта

k!(a:b)=k!b++[a:c|c<-(k-1)!b]
k!x=[x|k==0]
q&l|p<-q![[x,y,x-y,x+y]|x<-l,y<-l]=or[all and$zipWith(/=)<$>b<*>w|b<-p,w<-p]
g n=last$filter(&[1..n])[0..n*n]

Определяет функцию g, может быть в дальнейшем пригоден для игры в гольф. Попробуйте онлайн! На TIO при компиляции с-O2 это занимает около 36 секунд при n = 4 и время ожидания при n = 5 . Временная сложность должна быть O (n 2 4 n 2 ) .

объяснение

Мы перебираем возможные значения количества королев ( q ). Для каждого q мы генерируем все пары подмножеств размера q в [1..n] 2 , один набор черных королев ( b ) и одну из белых королев ( w ). Затем каждый элемент b сравнивается с каждым элементом w, чтобы узнать, имеют ли они общую строку, столбец, диагональ или антидиагональ. Это также заботится о двух частях с одинаковыми координатами. Наибольшее значение q, которое допускает мирную конфигурацию, является окончательным значением.

Первые две строки программы определяют функцию !, которая вычисляет длину- kподпоследовательность списка x. Реализация осуществляется с помощью базовой рекурсии: либо выберите первый элемент в наборе, либо нет и вернитесь к хвосту, уменьшив kпри необходимости. Затем пустой список или достигнут, проверьте это k==0.

k!(a:b)=       -- ! on integer k and list with head a and tail b is
 k!b++         -- the concatenation of k!b and
 [a:c|         -- the list of lists a:c where
  c<-(k-1)!b]  -- c is drawn from (k-1)!b.
k!x=           -- If x doesn't have the form a:b (which means that it's empty),
 [x|           -- the result is a list containing x
  k==0]        -- but only if k==0.

Вторая вспомогательная функция &принимает число q(число ферзей с обеих сторон) и список l(x-координаты доски, также используемые в качестве y-координат) и возвращает логическое значение, указывающее, существует ли конфигурация с возможностью изменения мира. Сначала мы вычислим pсписокq подпоследовательностей списка значений [x,y,x-y,x+y], где xи в yдиапазоне l. Они представляют собой строку, столбец, диагональ и анти-диагональ квадрата (x,y)на доске.

q&l               -- & on inputs q and l:
 |p<-             -- define p as
  q!              -- the q-subsequences of
  [[x,y,x-y,x+y]  -- the list of these 4-lists
   |x<-l,y<-l]    -- where x and y are drawn independently from l.

Далее у нас есть результат q&l. Мы рисуем две подпоследовательности bиw из p, пара 4-списки их вместе всеми возможными способами, и убедитесь , что они всегда отличаются во всех 4 -х координат. Если какой-то выбор bи wприведет к правдивому результату, мы вернемся True.

=or            -- Does the following list contain a True:
 [all and$     -- every list contains only truthy values
  zipWith(/=)  -- if we zip with inequality
  <$>b<*>w     -- all elements of b and w in all possible ways,
 |b<-p,w<-p]   -- where b and w are drawn independently from p.

Последняя строка является основной функцией. Учитывая n, он просто находит максимально возможное значение, qдля которого q&[1..n]верно.

g n=              -- g on input n is
 last$            -- the last of
 filter(&[1..n])  -- those values q for which q&[1..n] is true
 [0..n*n]         -- in this list.
Zgarb
источник