Решатель бинарных головоломок

10

Введение

Правила головоломки:

Головоломка Binary (также известная как Takuzu или Subiku) очень проста для понимания и имеет только несколько правил:
поскольку название игры бинарное, оно довольно очевидно, но вы можете заполнить только нули и единицы.

  1. Не более двух одинаковых цифр могут быть вертикально или горизонтально смежными друг с другом
  2. Каждая строка и каждый столбец должны содержать одинаковое количество нулей и единиц (это неявно означает, что каждая двоичная игра всегда будет иметь четные измерения).
  3. Не может быть дублированных строк и дублированных столбцов (с одинаковым порядком нулей и единиц).

Вы можете играть в игру на www.binarypuzzle.com, если хотите.

Тактика:

Из-за правила 1 мы всегда можем заполнить цифру, если:
- Уже есть две одинаковые цифры, вертикально или горизонтально смежные друг с другом, и в этом случае мы можем заполнить противоположную цифру с обеих сторон. Т.е. .11...0110...
- Есть две одинаковые цифры по вертикали или по горизонтали с одним пробелом между ними. Т.е. .1.1...101..

В соответствии с правилом 1, когда три пробела оставлены, и у нас не может быть трех смежных одинаковых цифр, мы можем заполнить один из пробелов. Т.е. .0.1.010.1.0(нам еще нужно заполнить два, и у нас не может быть трех смежных в середине, поэтому первый пробел должен быть a 1.)

Из-за правила 2 мы всегда можем заполнить оставшиеся пробелы в строке или столбце, если половина из них уже заполнена противоположной цифрой. Т.е. .1.011010011

Из-за правила 3 ​​мы всегда можем заполнить противоположные цифры, если для решения одинаково упорядочены оставлены только две цифры. Т.е. 101100 & 1..100101100 & 110100

Из-за правила 3 ​​мы можем иногда заполнить пробел, если на одинаково упорядоченной линии оставлены три пробела. Т.е. 010011 & .1.01.010011 & .1.010(Здесь мы не можем заполнить a 1в конце, потому что это означало бы, что мы должны заполнить нули в двух других пробелах, делая обе строки равными по порядку.)

Пример:

Мы начнем со следующей сетки 6х6 с заполненными нулями и нулями (а точки - это пробелы, которые нам еще предстоит заполнить):

.1....
.10.0.
1.11..
.1....
...1.0
......

В соответствии с правилами 1 и 2 мы можем заполнить эти цифры:

.1.01.
.1010.
101100
010011
.0.1.0
.010..

Из-за правила 1 мы можем заполнить 1 в строке 5, столбец 1:

.1.01.
.1010.
101100
010011
10.1.0
.010..

Из-за правила 3 ​​мы можем заполнить 0 в строке 1, столбце 6 (если смотреть в строке 4):

.1.010
.1010.
101100
010011
10.1.0
.010..

Теперь мы можем продолжать заполнять пробелы цифрами в соответствии с правилами 1 и 2:

.1.010
010101
101100
010011
10.1.0
.010.1

Теперь мы можем закончить строку 5 из-за правила 3 ​​(если смотреть на строку 3):

.1.010
010101
101100
010011
100110
.010.1

И тогда мы можем закончить головоломку по правилам 1 и 2:

011010
010101
101100
010011
100110
101001

Вызов:

Задача проста: с учетом стартовой сетки выведите решенную головоломку.

ПРИМЕЧАНИЕ. Вам не нужно применять вышеуказанные правила. Вы, конечно, можете, и это должно дать вам подсказки о том, как реализовать эту задачу, но грубое решение с учетом правил вполне подойдет.
Как вы решаете это, зависит от вас, но задача состоит в том, чтобы вывести решенную головоломку.

Правила вызова:

  • Формат ввода и вывода для сетки является гибким, но, пожалуйста, укажите, что вы используете. (Т.е. 2D байтовый массив; строка с символами новой строки; и т. Д.)
  • Это выше также относится к используемым символам. В примере, который я использовал 01., но если вы хотите, вы можете использовать ABxвместо этого. Пожалуйста, укажите, какой формат ввода / вывода и символы вы использовали.
  • Можно предположить , будет использоваться только следующие размеры сетки: 6x6; 8x8; 10x10; 12x12; 14x14; 16x16,

Основные правила:

  • Это , поэтому выигрывает самый короткий ответ в байтах.
    Не позволяйте языкам кода-гольфа отговаривать вас от публикации ответов на языках, не относящихся к кодексу. Попробуйте найти как можно более короткий ответ для «любого» языка программирования.
  • К вашему ответу применяются стандартные правила , поэтому вы можете использовать STDIN / STDOUT, функции / метод с соответствующими параметрами, полные программы. Ваш звонок.
  • По умолчанию лазейки запрещены.
  • Если возможно, добавьте ссылку с тестом для вашего кода.
  • Также, пожалуйста, добавьте объяснение, если это необходимо.

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

Точки добавляются только для удобства чтения, не стесняйтесь использовать пробелы или все, что вы предпочитаете вместо пробелов. Как в, так и в выходном формате является гибким.

Input:
1..0..
..00.1
.00..1
......
00.1..
.1..00

Output:
101010
010011
100101
011010
001101
110100

Input:
.1....
.10.0.
1.11..
.1....
...1.0
......

Output:
011010
010101
101100
010011
100110
101001

Input:
.......1..
.00..0..1.
.0..1..0.0
..1...1...
1.1......1
.......1..
.0..1...0.
....11...0
.0.0..1..0
0...0...1.

Output:
0110010101
1001100110
1001101010
0110011001
1010100101
0101010110
1001101001
0110110100
1010011010
0101001011
Кевин Круйссен
источник

Ответы:

4

Брахилог , 34 байта

{ℕ<2}ᵐ²&≜{d?ọᵐctᵐ=&{ḅlᵐ⌉<3}ᵐ}&\↰₂&

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

Это чертовски медленно, поэтому тестовый пример на TIO 4x4. В настоящее время я запускаю тестовый пример 6x6 на своем компьютере, чтобы узнать, сколько времени это займет.

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

объяснение

Мы ограничиваем значения, чтобы быть в {0,1}, затем мы пытаемся создавать экземпляры переменных, пока не соблюдаются все 3 правила. Вот почему это так медленно (потому что он будет пробовать все из них, пока не найдет один; и потому, что в этом случае Brachylog не реализован достаточно хорошо, чтобы можно было наложить ограничения перед попыткой возможной матрицы).

                                 &  Output = Input
{   }ᵐ²                             Map two levels on the Input (i.e. each cell):
 ℕ<2                                  The cell is either 0 or 1
       &≜                           Assign values to all cells
         {                  }       Define predicate 2:
          d?                          The Input with no duplicates is still the Input
                                        (i.e. all rows are different)
           ?ọᵐctᵐ=                    All occurences of 1s and 0s for each rows are equal
                  &{      }ᵐ          Map on rows:
                    ḅlᵐ                 Get the lengths of runs of equal values
                       ⌉<3              The largest one is strictly less than 3
                             &\↰₂   Apply predicate 2 on the transpose of the Input
                                      (i.e. do the same checks but on columns)
Fatalize
источник
Из любопытства, как Брахилог указывает переменные за пределами заглавного алфавита? Допустим, ваше решение будет работать быстрее, оно не сможет заполнить все пустые места в сетке 14x14 с Aпомощью параметра through YZпараметром output). Продолжает ли он с AA, ABи т.д.?
Кевин Круйссен
2
@KevinCruijssen Любой идентификатор в верхнем регистре является переменной, поэтому yes AAявляется переменной, а KEVINCRUIJSSENтакже является переменной.
Fatalize
3
Как я и подозревал, вызов для брахилога: D
Джонатан Аллан
3

JavaScript (ES6), 274 270 байт

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

f=(a,x=0,y=0,w=a.length,p,R=a[y])=>(M=z=>!a.some((r,y)=>/(0|1),\1,\1/.exec(s=r.map((v,x)=>(v=z?v:a[x][y],b-=v&1,c-=!v,m|=v&2,v),b=c=w/2))||b*c<0|o[b*c||s]&(o[s]=1),o={}))(m=0)&M(1)&&(m?R&&[0,1].map(n=>(p=R[x])==n|p>1&&(R[x]=n,f(a,z=(x+1)%w,y+!z),R[x]=p)):console.log(a))

Как это работает

Первая часть кода использует M()функцию для проверки правильности текущей доски, как по горизонтали, так и по вертикали.

M = z =>
  !a.some((r, y) =>
    /(0|1),\1,\1/.exec(
      s = r.map((v, x) =>
        (
          v = z ? v : a[x][y],
          b -= v & 1,
          c -= !v,
          m |= v & 2,
          v
        ),
        b = c = w / 2
      )
    ) ||
    b * c < 0 |
    o[b * c || s] &
    (o[s] = 1),
    o = {}
  )

Он отображает полную строку или столбец в строку s . На самом деле это массив, приведенный к строке, поэтому он выглядит следующим образом "1,2,2,0,2,2".

Оно использует:

  • Регулярное выражение /(0|1),\1,\1/для обнаружения 3 или более последовательных идентичных цифр.
  • Счетчики b и c отслеживают количество единиц и нулей . Оба счетчика инициализируются как w / 2 и уменьшаются каждый раз, когда встречается единица или ноль (соответственно). Это приводит к либо:
    • b = c = 0 b * c = 0 → линия полная и правильная (столько нулей, сколько единиц )
    • б> 0 и с> 0 B * C> 0 → линия не завершенаносих пор правильно (мы не имеем большечем ж / 2 нулей или большечем ж / 2 из них )
    • b <0 ИЛИ c <0 b * c <0 → строка недействительна
  • Флаг m (для «отсутствующего»), который не равен нулю, если на доске осталось хотя бы одно из двух .
  • Объект o для отслеживания всех встреченных на данный момент паттернов линий.

Если доска недействительна, мы немедленно остановимся. Если доска действительна и укомплектована, мы печатаем ее на консоли. В противном случае вторая часть кода пытается заменить каждые 2 на ноль или единицу рекурсивными вызовами:

[0, 1].map(n =>
  (p = a[y][x]) == n |
  p > 1 && (
    a[y][x] = n,
    f(a, z = (x + 1) % w, y + !z),
    a[y][x] = p
  )
)

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

Arnauld
источник
Спасибо за добавление объяснения. И мне нравится, как вы печатаете все возможные результаты, а не только один!
Кевин Круйссен
1
@KevinCruijssen Это, вероятно, далеко не оптимально, но было весело писать. Отличный вызов!
Арно
1

Желе , 53 51 байт

ṡ€3ḄFf0,7L
SḤnLṀȯÇ
⁻QȯÇ
Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ

Принимает список списков , представляющих сетку, содержащих 0, 1и 2(пространства). Возвращает список списков списков, каждый список списков имеет один и тот же формат (хотя и без 2s) и представляет возможное решение для ввода.

Попробуйте онлайн! (это не будет запускать ни одного из тестовых случаев вопроса из-за ограничений памяти - все 2сетки nSpaces создаются в виде списка списков целых чисел - но я поместил относительно здоровенный случай с одним решением). Нижний колонтитул отделяет и форматирует сетки.

Метод чистой грубой силы - реализует правила и проверяет их для каждой сетки, которая может быть сформирована путем замены любого из 2s на 1s или 0s.

ṡ€3ḄFf0,7L - Link 1, # of runs of 3 1s or 3 0s by row: list of lists
ṡ€3        - all contiguous slices of length 3 for €ach list
   Ḅ       - convert all results from binary
    F      - flatten into one list
     f     - filter keep values in:
      0,7  -   0 paired with 7: [0,7]
         L - length

SḤnLṀȯÇ - Link 2, unequal counts of 1s and 0s by column ...or link 1: list of lists
S       - sum (vectorises, hence "by column", counts 1s since only 1s or 0s appear)
 Ḥ      - double
   L    - length (number of rows - OK since square)
  n     - not equal? (vectorises)
    Ṁ   - maximum (1 if any not equal)
     ȯÇ - ... or last link (1) as a monad

⁻QȯÇ - Link 3, rows are unique ...or link 2: list of lists
 Q   - unique
⁻    - not equal?
  ȯÇ - ... or last link (2) as a monad

Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ - Main link: list of lists
F                           - flatten
 ṣ©2                        - split at 2s and copy the result to the register
    L                       - length (# of such slices)
     ’                      - decrement (# of 2s)
      0,1                   - 0 paired with 1
         ṗ                  - Cartesian power (all binary lists of length # of 2s)
             ®              - recall value from register (the flat version split at 2s)
          ż@€               - zip (reversed @rguments) for €ach (1s & 0s where 2s were)
              F€            - flatten €ach
                s€L         - split €ach into chunks of length length(input) (into rows)
                    Ðḟ      - filter discard if:
                   Ç        -   call last link(3) as a monad
                         Ðḟ - filter discard if:
                        $   -   last two links as a monad:
                      Z     -     transpose
                       Ç    -     call last link(3) as a monad
Джонатан Аллан
источник