Шашки: король меня?

14

Вызов:

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

Правила :

Сторона красных всегда будет внизу, однако их фигуры могут начинаться в любом ряду (даже в ряду короля, в который они должны попасть). Черные фигуры являются стационарными , то есть они не перемещаются между движениями красных, но они удаляются с доски при захвате. Обратите внимание, что фигуры могут начинаться в любом месте на доске, в том числе прямо рядом друг с другом. Это не то, как играют в обычные шашки, но ваша программа должна быть способна их решить. (См. Вход 5). Однако элементы проверки должны двигаться только по диагонали (см. Вход 3). Захват в обратном направлении разрешен, если первый захват идет вперед в цепочке (см. Вход 7).

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

Шахматная доска 8x8 с пробелами, определенными как следующие символы (не стесняйтесь использовать альтернативы, если они последовательны):

, - Пусто

R - Красная часть (и)

B - Черные фигуры

Выход:

Наименьшее число ходов было бы взять красный кусок , чтобы быть «kinged», введя строку короля на верхнем ряду платы ( со стороны чёрных), 0 , если не требуется никаких шагов (красная часть началась в ряду короля), или отрицательное число, если невозможно собрать короля красного цвета (т. е. черный занимает весь первый ряд).

Вход 1:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Выход 1:

7

Вход 2:

. . . . . . . .
. . . . . . . .
. . . . . B . .
. . . . . . . .
. . . B . . . .
. . . . . . . .
. B . . . . . .
R . . . . . . .

Выход 2:

2

Вход 3:

. B . B . B . B
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Выход 3:

-1

Вход 4:

. . . . . . . R
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Выход 4:

0

Вход 5:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. B . . B . . .
B . . . . B . .
. B . B . . . .
. . B . . B . .
. . . R R . . .

Выход 5:

4

Вход 6:

. . . . . . . .
. . . . . . . .
. B . . . . . .
. . B . . . . .
. B . B . . . .
. . . . R . . .
. . . B . . . .
. . . . R . . .

Выход 6:

2

Вход 7:

. . . . . . . .
. . . . . . . .
. . B . . . . .
. . . . . . . .
. . B . . . . .
. B . B . B . .
. . . . B . . .
. . . . . R . R

Выход 7:

4

Подсчет очков:

Это , поэтому выигрывает самый короткий код в байтах.

Yodle
источник
1
Разве второй тестовый случай не должен быть 2, так как вы можете совершить двойной / тройной прыжок?
Джеймс
Оправдан ли массив массивов целых чисел в качестве входных данных?
Джонатан Аллан
1
Я добавил еще один тест, который должен оказаться трудным. Это включает в себя несколько прыжков, несколько фигур и прыжки назад, чтобы достичь наилучшего решения.
orlp
1
@ orlp Хм, я собирался сказать, что ни одна из красных фигур не может двигаться задом наперед, поскольку ни один из них не является королем (отсюда и цель испытания), но некоторые люди играют с правилами, в которых захват назад разрешен королевские фигуры, если первый захват был вперед. Я добавлю это к правилам, так как я не знал об этом раньше.
Йодль
1
оооооооо, вам не нужно выбирать только одну красную фигуру, они могут объединиться! Я понял
Грег Мартин

Ответы:

4

JavaScript (ES6), 354 322 байта

Принимает массив в качестве ввода с:

  • 0 = пустой квадрат
  • 1 = красная часть
  • 2 = черный кусок

Возвращает оптимальное количество ходов или 99, если нет решения.

Это очень быстро, но можно играть в гольф гораздо больше.

F=(b,n=0,C=-1,i)=>b.map((v,f,X,T,x=f&7,y=f>>3)=>v-1||(y&&n<m?[-9,-7,7,9].map(d=>(N=c=X=-1,r=(d&7)<2,T=(t=f+d)>=0&t<64&&(x||r)&&(x<7||!r)?(!b[t]&d<0)?t:b[t]&1?N:b[t]&2&&(d<0&y>1|d>0&C==f)?(X=t,x>1||r)&&(x<6|!r)&&!b[t+=d]?c=t:N:N:N)+1&&(b[f]=b[X]=0,b[T]=1,F(b,n+!(C==f&c>N),c,1),b[f]=1,b[X]=2,b[T]=0)):m=n<m?n:m),m=i?m:99)|m

var test = [
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,2,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,2,0,2,0,2,0,2,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,1,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,2,0,0,0,
    2,0,0,0,0,2,0,0,
    0,2,0,2,0,0,0,0,
    0,0,2,0,0,2,0,0,
    0,0,0,1,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,2,0,0,
    0,0,0,0,2,0,0,0,
    0,0,0,0,0,1,0,1
  ]
];

test.forEach((b, n) => {
  console.log("Test #" + (n + 1) + " : " + F(b));
});

Arnauld
источник
99, вероятно, хорошо, я не могу представить себе реального решения, которое бы занимало 99 ходов на доске 8х8. Хорошая работа!
Йодль