Введение

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

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

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

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

Тактика:

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

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

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

Из-за правила 3 ​​мы всегда можем заполнить противоположные цифры, если для решения одинаково упорядочены оставлены только две цифры. Т.е. 101100 & 1..100→101100 & 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

Брахилог , 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)

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
  )
)

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

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))

console.log('Example #1')
f([
  [1,2,2,0,2,2],
  [2,2,0,0,2,1],
  [2,0,0,2,2,1],
  [2,2,2,2,2,2],
  [0,0,2,1,2,2],
  [2,1,2,2,0,0]
])

console.log('Example #2')
f([
  [2,2,2,2,2,2,2,1,2,2],
  [2,0,0,2,2,0,2,2,1,2],
  [2,0,2,2,1,2,2,0,2,0],
  [2,2,1,2,2,2,1,2,2,2],
  [1,2,1,2,2,2,2,2,2,1],
  [2,2,2,2,2,2,2,1,2,2],
  [2,0,2,2,1,2,2,2,0,2],
  [2,2,2,2,1,1,2,2,2,0],
  [2,0,2,0,2,2,1,2,2,0],
  [0,2,2,2,0,2,2,2,1,2]
])

Желе , 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