Заполните строки, столбцы и диагонали сетки NxN от 1 до N

26

задача

При заданном входном N сгенерируйте и выведите сетку NxN, где каждая строка, столбец и две диагонали содержат числа от 1 до N(или от 0 до N-1, если это проще).

вход

На входе положительное целое число N. Он представляет количество столбцов и строк в сетке. Для этой проблемы, вы можете предположить, Nбудет разумный размер 4 ≤ N ≤ 8или ( 1 ≤ N ≤ 8если вы идете за бонус ниже).

Выход

На выходе будет N× Nсетка. В сетке каждая строка содержит только цифры от 1 до N, каждый столбец содержит только цифры от 1 до N, а две диагонали длины N(одна от (0,0)до (N-1,N-1)и одна от (0,N-1)до (N-1, 0)) содержат только цифры от 1 до N. Вы можете использовать цифры от 0 до N−1. Для каждого Nсуществует множество возможных решений, вам нужно распечатать только первое, которое вы найдете. Вам не нужно печатать пробелы между числами.

Ограничения

Ваш код должен иметь возможность повторять результаты для N >= 7. То есть, если вы действительно можете запускать и получать решение N = 7из своего кода каждый раз, у вас все хорошо. С точки зрения абсолютного ограничения, ваш код должен быть в состоянии решить N = 7менее чем за 10 минут каждый раз, когда вы его запускаете (т. Е. Если вы зависите от случайных чисел, в худшем случае ваш код должен завершиться менее чем за 10 минут N = 7) ,

Примеры

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

    Один из возможных выходов:

    1 2 3 4
3 4 1 2
4 3 2 1
2 1 4 3

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

    Один из возможных выходов:

    1 2 3 4 5
5 3 1 2 4
2 5 4 3 1
4 1 2 5 3
3 4 5 1 2

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

    Один из возможных выходов:

    1 2 3 4 5 6 7 8
2 3 1 5 4 8 6 7
4 1 2 3 7 5 8 6
6 4 7 8 1 2 3 5
7 5 8 2 6 3 4 1
5 8 4 6 2 7 1 3
8 7 6 1 3 4 5 2
3 6 5 7 8 1 2 4

счет

Это код-гольф , поэтому выигрывает самый короткий код в байтах, за одним исключением. Для входных N = 2, 3данных нет действительных решений. Если ваш код может обработать это (выполнить до завершения, не выводя ничего для этих случаев или не выдав пустую строку), и все еще обрабатывает N = 1(выводит 1для него), снимите 20% от вашего количества байтов.

code-golf grid generation hargasinski
источник
1
Связанный , но такая сетка не будет работать здесь из-за требования диагоналей.
xnor
Мне нравится этот вызов, но я не могу понять алгоритм для четных значений N. Этот код JavaScript работает, N = 1, 5 or 7хотя, если он кому-нибудь помогает:for(o="",y=N;y--;o+="\n")for(x=N;x--;)o+=(((N-y)*2+x)%N)+1
user81655
Очень похожий
Уровень Река Сент
@steveverrill Это не было кодом гольф, хотя.
Рандомра
1
Может быть, вы должны быть более ясны в отношении N = 1случая: должны возвращаться ответы, которые нацелены на бонус 1, а не пустая строка.
Линн

Ответы:

3

Python 3, 275 260 байт * 0,8 = 220 208 байт

Рекурсивный / возвратный подход. Rявляется рекурсивной функцией, lявляется столбцом, wявляется строкой, Kявляется следующей записью.

Я решил поместить его в 1-мерный массив и в конце довольно распечатать, чтобы упростить индексы.

r=range
n=(int)(input())
def R(A,I):
 l=I%n;w=I//n
 if I==n*n:[print(A[i*n:i*n+n])for i in r(n)];exit()
 for K in r(n):
  if all([all([A[i*n+l]!=K,w!=l or A[i+n*i]!=K,w!=n-1-l or A[n*i+n-i-1]!=K])for i in r(w)]+[A[w*n+i]!=K for i in r(l)]):R(A+[K],I+1)
R([],0)

Безголовая версия:

def Recurse(A,I,n):
 column=I%n
 row=I//n
 if I==n*n:
     [print(*A[i*n:i*n+n])for i in range(n)] # output
     exit() #end recursion
 for K in range(n):
    # try every possibility. Test if they satisfy the constraints:
    # if so, move the index on. If none of them do, we'll return None.
    # if a child returns None, we'll move onto the next potential child:
    # if all of them fail it will backtrack to the next level.
    if all([
        all([
            A[i*n+column]!=K, # column constraint
            row!=column or A[i+n*i]!=K, # diagonal constraint
            row!=n-1-column or A[n*i+n-i-1]!=K # antidiagonal constraint
            ]) for i in range(row)
        ]+[
            A[row*n+i]!=K for i in range(column) # row constraint
            ]):
        Recurse(A+[K],I+1,n)

Recurse([],0,(int)(input()))
александр-Brett
источник
22

Funciton , неконкурентный

ОБНОВИТЬ! Массовое улучшение производительности! n = 7 теперь завершается менее чем за 10 минут! Смотрите объяснение внизу!

Это было весело писать. Это решатель грубой силы для этой задачи, написанный на Funciton. Некоторые факты:

  • Он принимает целое число на STDIN. Любые посторонние пробелы разбивают его, включая перевод строки после целого числа.
  • Используются числа от 0 до n - 1 (не от 1 до n ).
  • Он заполняет сетку «в обратном направлении», поэтому вы получаете решение, в котором читается нижний ряд, 3 2 1 0а не верхний ряд 0 1 2 3.
  • Он правильно выводит 0(единственное решение) для n = 1.
  • Пустой вывод для n = 2 и n = 3.
  • При компиляции в исполняемый файл занимает около 8¼ минут для n = 7 (до улучшения производительности было около часа). Без компиляции (с использованием интерпретатора) это занимает в 1,5 раза больше времени, поэтому использование компилятора того стоит.
  • В качестве личной вехи я впервые написал целую программу Funciton без предварительного написания программы на языке псевдокодов. Я действительно написал это в фактическом C # сначала все же.
  • (Однако это не первый случай, когда я вносил изменения, чтобы значительно улучшить производительность чего-либо в Funciton. Первый раз, когда я сделал это, был в факториальной функции. Замена порядка операндов умножения имела огромное значение из-за как работает алгоритм умножения . На всякий случай, если вам было интересно.)

Без дальнейших церемоний:

            ┌────────────────────────────────────┐           ┌─────────────────┐
            │                                  ┌─┴─╖ ╓───╖ ┌─┴─╖   ┌──────┐    │
            │                    ┌─────────────┤ · ╟─╢ Ӂ ╟─┤ · ╟───┤      │    │
            │                    │             ╘═╤═╝ ╙─┬─╜ ╘═╤═╝ ┌─┴─╖    │    │
            │                    │               └─────┴─────┘   │ ♯ ║    │    │
            │                  ┌─┴─╖                             ╘═╤═╝    │    │
            │     ┌────────────┤ · ╟───────────────────────────────┴───┐  │    │
          ┌─┴─╖ ┌─┴─╖   ┌────╖ ╘═╤═╝ ┌──────────┐         ┌────────┐ ┌─┴─╖│    │
          │ ♭ ║ │ × ╟───┤ >> ╟───┴───┘        ┌─┴─╖       │ ┌────╖ └─┤ · ╟┴┐   │
          ╘═╤═╝ ╘═╤═╝   ╘══╤═╝          ┌─────┤ · ╟───────┴─┤ << ╟─┐ ╘═╤═╝ │   │
    ┌───────┴─────┘ ┌────╖ │            │     ╘═╤═╝         ╘══╤═╝ │   │   │   │
    │     ┌─────────┤ >> ╟─┘            │       └───────┐      │   │   │   │   │
    │     │         ╘══╤═╝            ┌─┴─╖   ╔═══╗   ┌─┴─╖ ┌┐ │   │ ┌─┴─╖ │   │
    │     │           ┌┴┐     ┌───────┤ ♫ ║ ┌─╢ 0 ║ ┌─┤ · ╟─┤├─┤   ├─┤ Ӝ ║ │   │
    │     │   ╔═══╗   └┬┘     │       ╘═╤═╝ │ ╚═╤═╝ │ ╘═╤═╝ └┘ │   │ ╘═╤═╝ │   │
    │     │   ║ 1 ╟───┬┘    ┌─┴─╖       └───┘ ┌─┴─╖ │   │      │   │   │ ┌─┴─╖ │
    │     │   ╚═══╝ ┌─┴─╖   │ ɓ ╟─────────────┤ ? ╟─┘   │    ┌─┴─╖ │   ├─┤ · ╟─┴─┐
    │     ├─────────┤ · ╟─┐ ╘═╤═╝             ╘═╤═╝   ┌─┴────┤ + ╟─┘   │ ╘═╤═╝   │
  ┌─┴─╖ ┌─┴─╖       ╘═╤═╝ │ ╔═╧═╕ ╔═══╗ ┌───╖ ┌─┴─╖ ┌─┴─╖    ╘═══╝     │   │     │
┌─┤ · ╟─┤ · ╟───┐     └┐  └─╢   ├─╢ 0 ╟─┤ ⌑ ╟─┤ ? ╟─┤ · ╟──────────────┘   │     │
│ ╘═╤═╝ ╘═╤═╝   └───┐ ┌┴┐   ╚═╤═╛ ╚═╤═╝ ╘═══╝ ╘═╤═╝ ╘═╤═╝                  │     │
│   │   ┌─┴─╖ ┌───╖ │ └┬┘   ┌─┴─╖ ┌─┘           │     │                    │     │
│ ┌─┴───┤ · ╟─┤ Җ ╟─┘  └────┤ ? ╟─┴─┐   ┌─────────────┘                    │     │
│ │     ╘═╤═╝ ╘═╤═╝         ╘═╤═╝   │   │╔════╗╔════╗                      │     │
│ │       │  ┌──┴─╖ ┌┐   ┌┐ ┌─┴─╖ ┌─┴─╖ │║ 10 ║║ 32 ║    ┌─────────────────┘     │
│ │       │  │ << ╟─┤├─┬─┤├─┤ · ╟─┤ · ╟─┘╚══╤═╝╚╤═══╝ ┌──┴──┐                    │
│ │       │  ╘══╤═╝ └┘ │ └┘ ╘═╤═╝ ╘═╤═╝     │ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖                  │
│ │     ┌─┴─╖ ┌─┴─╖  ┌─┴─╖  ┌─┴─╖ ╔═╧═╕     └─┤ ? ╟─┤ · ╟─┤ % ║                  │
│ └─────┤ · ╟─┤ · ╟──┤ Ӂ ╟──┤ ɱ ╟─╢   ├───┐   ╘═╤═╝ ╘═╤═╝ ╘═╤═╝                  │
│       ╘═╤═╝ ╘═╤═╝  ╘═╤═╝  ╘═══╝ ╚═╤═╛ ┌─┴─╖ ┌─┴─╖   │     └────────────────────┘
│         └─────┤      │            └───┤ ‼ ╟─┤ ‼ ║   │        ┌──────┐
│               │      │                ╘═══╝ ╘═╤═╝   │        │ ┌────┴────╖
│               │      │                      ┌─┴─╖   │        │ │ str→int ║
│               │      └──────────────────────┤ · ╟───┴─┐      │ ╘════╤════╝
│               │          ┌─────────╖        ╘═╤═╝     │    ╔═╧═╗ ┌──┴──┐
│               └──────────┤ int→str ╟──────────┘       │    ║   ║ │ ┌───┴───┐
│                          ╘═════════╝                  │    ╚═══╝ │ │ ┌───╖ │
└───────────────────────────────────────────────────────┘          │ └─┤ × ╟─┘
           ┌──────────────┐                                  ╔═══╗ │   ╘═╤═╝
╔════╗     │ ╓───╖ ┌───╖  │                              ┌───╢ 0 ║ │   ┌─┴─╖ ╔═══╗
║ −1 ║     └─╢ Ӝ ╟─┤ × ╟──┴──────┐                       │   ╚═╤═╝ └───┤ Ӂ ╟─╢ 0 ║
╚═╤══╝       ╙───╜ ╘═╤═╝         │                       │   ┌─┴─╖     ╘═╤═╝ ╚═══╝
┌─┴──╖ ┌┐ ┌───╖ ┌┐ ┌─┴──╖ ╔════╗ │                       │ ┌─┤   ╟───────┴───────┐
│ << ╟─┤├─┤ ÷ ╟─┤├─┤ << ║ ║ −1 ║ │                       │ │ └─┬─╜ ┌─┐ ┌─────┐   │
╘═╤══╝ └┘ ╘═╤═╝ └┘ ╘═╤══╝ ╚═╤══╝ │                       │ │   └───┴─┘ │   ┌─┴─╖ │
  │         └─┘      └──────┘    │                       │ └───────────┘ ┌─┤ ? ╟─┘
  └──────────────────────────────┘         ╓───╖         └───────────────┘ ╘═╤═╝
                               ┌───────────╢ Җ ╟────────────┐                │
      ┌────────────────────────┴───┐       ╙───╜            │
      │                          ┌─┴────────────────────┐ ┌─┴─╖
    ┌─┴─╖                      ┌─┴─╖                  ┌─┴─┤ · ╟──────────────────┐
    │ ♯ ║ ┌────────────────────┤ · ╟───────┐          │   ╘═╤═╝                  │
    ╘═╤═╝ │                    ╘═╤═╝       │          │     │              ┌───╖ │
┌─────┴───┘    ┌─────────────────┴─┐   ┌───┴───┐    ┌─┴─╖ ┌─┴─╖          ┌─┤ × ╟─┴─┐
│              │                 ┌─┴─╖ │   ┌───┴────┤ · ╟─┤ · ╟──────────┤ ╘═╤═╝   │
│              │ ┌───╖ ┌───╖  ┌──┤ · ╟─┘ ┌─┴─┐      ╘═╤═╝ ╘═╤═╝        ┌─┴─╖ │     │
│         ┌────┴─┤ ♭ ╟─┤ × ╟──┘  ╘═╤═╝   │ ┌─┴─╖ ┌───╖└┐ ┌──┴─╖      ┌─┤ · ╟─┘     │
│         │      ╘═══╝ ╘═╤═╝ ┌───╖ │     │ │ × ╟─┤ Ӝ ╟─┴─┤ ÷% ╟─┐    │ ╘═╤═╝ ┌───╖ │
│   ┌─────┴───┐     ┌────┴───┤ Ӝ ╟─┴─┐   │ ╘═╤═╝ ╘═╤═╝   ╘══╤═╝ │    │   └───┤ Ӝ ╟─┘
│ ┌─┴─╖ ┌───╖ │     │ ┌────╖ ╘═╤═╝   │   └───┘   ┌─┴─╖      │   │    └────┐  ╘═╤═╝
│ │ × ╟─┤ Ӝ ╟─┘     └─┤ << ╟───┘   ┌─┴─╖ ┌───────┤ · ╟───┐  │ ┌─┴─╖ ┌───╖ │    │
│ ╘═╤═╝ ╘═╤═╝         ╘══╤═╝   ┌───┤ + ║ │       ╘═╤═╝   ├──┴─┤ · ╟─┤ × ╟─┘    │
└───┤     └────┐ ╔═══╗ ┌─┴─╖ ┌─┴─╖ ╘═╤═╝ │ ╔═══╗ ┌─┴─╖ ┌─┴─╖  ╘═╤═╝ ╘═╤═╝      │
  ┌─┴─╖ ┌────╖ │ ║ 0 ╟─┤ ? ╟─┤ = ║  ┌┴┐  │ ║ 0 ╟─┤ ? ╟─┤ = ║    │     │ ┌────╖ │
  │ × ╟─┤ << ╟─┘ ╚═══╝ ╘═╤═╝ ╘═╤═╝  └┬┘  │ ╚═══╝ ╘═╤═╝ ╘═╤═╝    │     └─┤ << ╟─┘
  ╘═╤═╝ ╘═╤══╝ ┌┐     ┌┐ │     │     └───┘       ┌─┴─╖   ├──────┘       ╘═╤══╝
    │     └────┤├──┬──┤├─┘     ├─────────────────┤ · ╟───┘                │
    │          └┘┌─┴─╖└┘       │     ┌┐   ┌┐     ╘═╤═╝ ┌┐   ┌┐            │
    └────────────┤ · ╟─────────┘   ┌─┤├─┬─┤├─┐     └───┤├─┬─┤├────────────┘
                 ╘═╤═╝             │ └┘ │ └┘ │         └┘ │ └┘
                   └───────────────┘    │    └────────────┘

Объяснение первой версии

Первая версия заняла около часа, чтобы решить n = 7. Далее объясняется, как работает эта медленная версия. Внизу я объясню, какие изменения я внес, чтобы получить менее 10 минут.

Экскурсия на кусочки

Эта программа нуждается в битах. Ему нужно много битов, и они нужны во всех нужных местах. Опытные программисты Funciton уже знают, что если вам нужно n бит, вы можете использовать формулу

2 ^ п-1

который в Funciton может быть выражен как

(1 << n) - 1

При выполнении оптимизации производительности мне пришло в голову, что я могу вычислить то же значение гораздо быстрее, используя эту формулу:

¬ (−1 << n)

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

Теперь, допустим, вам не нужен непрерывный блок битов; на самом деле, вы хотите n бит через равные интервалы каждый k-й бит, вот так:

                                 LSB
                                  ↓
00000010000001000000100000010000001
                            └──┬──┘
                               k

Формула для этого довольно проста, если вы знаете это:

((1 << nk) - 1) / ((1 << k) - 1)

В коде функция Ӝпринимает значения n и k и вычисляет эту формулу.

Отслеживание используемых номеров

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

Алгоритм начинается в правом нижнем углу. После «угадывания» первое число равно 0, нам нужно отследить тот факт, что 0 больше не разрешен ни в одной ячейке в той же строке, столбце и диагонали:

LSB                               (example n=5)
 ↓
 10000 00000 00000 00000 10000
 00000 10000 00000 00000 10000
 00000 00000 10000 00000 10000
 00000 00000 00000 10000 10000
 10000 10000 10000 10000 10000
                             ↑
                            MSB

Для этого мы рассчитываем следующие четыре значения:

  • Текущая строка: нам нужно n битов каждый n-й бит (по одному на ячейку), а затем сдвинуть его к текущей строке r , помня, что каждая строка содержит n ² битов:

    ((1 << n²) -1) / ((1 << n) -1) << n²r

  • Текущий столбец: нам нужно n битов через каждый n ²-й бит (по одному на строку), а затем сдвинуть его к текущему столбцу c , помня, что каждый столбец содержит n битов:

    ((1 << n³) -1) / ((1 << n²) -1) << n²r

  • Прямая диагональ: нам нужно n бит каждый ... (вы обратили внимание? Быстро, разберитесь!) ... n ( n +1) -й бит (хорошо!), Но только если мы на самом деле включены прямая диагональ:

    ((1 << n² (n + 1)) - 1) / ((1 << n (n + 1)) - 1) если c = r

  • Обратная диагональ: две вещи здесь. Во-первых, как мы узнаем, что находимся на обратной диагонали? Математически, это условие c = ( n - 1) - r , что совпадает с c = n + (- r - 1). Эй, это напоминает тебе о чем-то? Это верно, это дополнение к двум, поэтому мы можем использовать побитовое отрицание (очень эффективное в Funciton) вместо декремента. Во-вторых, вышеприведенная формула предполагает, что мы хотим установить младший значащий бит, но в обратной диагонали мы этого не делаем, поэтому мы должны сдвинуть его вверх на ... вы знаете? ... Это верно, n ( п - 1).

    ((1 << n² (n-1)) - 1) / ((1 << n (n-1)) - 1) << n (n-1), если c = n + ¬r

    Это также единственный, где мы потенциально делим на 0, если n = 1. Однако, Funciton это не волнует. 0 ÷ 0 это просто 0, ты не знаешь?

В коде функция Җ(нижняя) берет n и индекс (из которого она вычисляет r и c делением и остатком), вычисляет эти четыре значения и orскладывает их вместе.

Алгоритм перебора

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

Эта функция возвращает последовательность строк. Каждая строка является полным решением для сетки. Это полный решатель; он вернет все решения, если вы позволите, но вернет их в виде последовательности с отложенным вычислением.

  • Если индекс достиг 0, мы успешно заполнили всю сетку, поэтому мы возвращаем последовательность, содержащую пустую строку (единственное решение, которое не охватывает ни одну из ячеек). Пустая строка есть 0, и мы используем библиотечную функцию, ⌑чтобы превратить ее в одноэлементную последовательность.

  • Проверка, описанная ниже в разделе « Улучшение производительности», происходит здесь.

  • Если индекс еще не достиг 0, мы уменьшаем его на 1, чтобы получить индекс, по которому нам теперь нужно разместить число (назовите ix ).

    Мы используем ♫для генерации ленивую последовательность, содержащую значения от 0 до n - 1.

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

    • Сначала посмотрите на соответствующий бит в кадре, чтобы решить, является ли число действительным здесь или нет. Мы можем поместить число i тогда и только тогда, когда принято & (1 << ( n × ix ) << i ) еще не установлено. Если оно установлено, вернуть 0(пустая последовательность).
    • Используется Җдля вычисления битов, соответствующих текущей строке, столбцу и диагонали. Сдвинь его на меня, а затем orна взятый .
    • Рекурсивно вызывать Ӂдля извлечения всех решений для оставшихся ячеек, передавая ему новые принятые и уменьшенные ix . Это возвращает последовательность неполных строк; каждая строка имеет символы ix (сетка заполнена до индекса ix ).
    • Используйте ɱ(map), чтобы просмотреть найденные решения и использовать, ‼чтобы объединить i до конца каждого. Добавьте новую строку, если индекс кратен n , в противном случае пробел.

Генерация результата

Основная программа вызывает Ӂ(брутфорсер) с n , index = n ² (помните, что мы заполняем сетку задом наперед) и берется = 0 (изначально ничего не берется). Если результатом является пустая последовательность (решение не найдено), выведите пустую строку. В противном случае выведите первую строку в последовательности. Обратите внимание, что это означает, что он будет оценивать только первый элемент последовательности, поэтому решатель не продолжает работу, пока не найдет все решения.

Улучшение производительности

(Для тех, кто уже прочитал старую версию объяснения: программа больше не генерирует последовательность последовательностей, которую нужно отдельно превратить в строку для вывода; она просто генерирует последовательность строк напрямую. Я соответственно отредактировал объяснение Но это было не главное улучшение. Вот оно.)

На моей машине скомпилированный exe первой версии занял ровно 1 час, чтобы решить n = 7. Это не было в заданном временном интервале в 10 минут, поэтому я не отдыхал. (Ну, на самом деле, причина, по которой я не отдыхал, заключалась в том, что у меня была идея о том, как это значительно ускорить.)

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

Однако алгоритм будет продолжать бесполезно заполнять сетку до ячейки, в которой установлены все эти биты. Было бы намного быстрее, если бы он мог остановиться, как только в любой еще не заполненной ячейке уже установлены все биты, что уже указывает на то, что мы никогда не сможем решить остальную часть сетки, независимо от того, какие числа мы вставим в Это. Но как вы эффективно проверяете, есть ли в любой ячейке свои n битов, не пройдя их все?

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

LSB                               (example n=5)
 ↓
 10000 0 00000 0 00000 0 00000 0 10000 0
 00000 0 10000 0 00000 0 00000 0 10000 0
 00000 0 00000 0 10000 0 00000 0 10000 0
 00000 0 00000 0 00000 0 10000 0 10000 0
 10000 0 10000 0 10000 0 10000 0 10000 0
                                       ↑
                                      MSB

Вместо n ³ теперь в этом числе n ² ( n + 1) бит. Функция, которая заполняет текущую строку / столбец / диагональ, была соответствующим образом изменена (на самом деле, полностью переписана, если честно). Эта функция будет по-прежнему заполнять только n битов на ячейку, поэтому добавленный нами дополнительный бит будет всегда 0.

Теперь предположим, что мы на полпути к вычислению, мы просто поместили a 1в среднюю ячейку, и полученное число выглядит примерно так:

                 current
LSB              column           (example n=5)
 ↓                 ↓
 11111 0 10010 0 01101 0 11100 0 11101 0
 00011 0 11110 0 01101 0 11101 0 11100 0
 11111 0 11110 0[11101 0]11100 0 11100 0    ← current row
 11111 0 11111 0 11111 0 11111 0 11111 0
 11111 0 11111 0 11111 0 11111 0 11111 0
                                       ↑
                                      MSB

Как видите, верхняя левая ячейка (индекс 0) и средняя левая ячейка (индекс 10) теперь невозможны. Как мы можем наиболее эффективно определить это?

Рассмотрим число, в котором установлен 0-й бит каждой ячейки, но только до текущего индекса. Такое число легко рассчитать по знакомой формуле:

((1 << (n + 1) i) - 1) / ((1 << (n + 1)) - 1)

Что мы получим, если сложим эти два числа вместе?

LSB                                               LSB
 ↓                                                 ↓
 11111 0 10010 0 01101 0 11100 0 11101 0           10000 0 10000 0 10000 0 10000 0 10000 0        ╓───╖
 00011 0 11110 0 01101 0 11101 0 11100 0     ║     10000 0 10000 0 10000 0 10000 0 10000 0            ║
 11111 0 11110 0 11101 0 11100 0 11100 0  ═══╬═══  10000 0 10000 0 00000 0 00000 0 00000 0  ═════   ╓─╜
 11111 0 11111 0 11111 0 11111 0 11111 0     ║     00000 0 00000 0 00000 0 00000 0 00000 0  ═════   ╨
 11111 0 11111 0 11111 0 11111 0 11111 0           00000 0 00000 0 00000 0 00000 0 00000 0          o
                                       ↑                                                 ↑
                                      MSB                                               MSB

Результат:

             OMG
              ↓
        00000[1]01010 0 11101 0 00010 0 00011 0
        10011 0 00001 0 11101 0 00011 0 00010 0
═════   00000[1]00001 0 00011 0 11100 0 11100 0
═════   11111 0 11111 0 11111 0 11111 0 11111 0
        11111 0 11111 0 11111 0 11111 0 11111 0

Как видите, сложение переполняется добавленным нами дополнительным битом, но только если все биты для этой ячейки установлены! Поэтому все, что осталось сделать, это замаскировать эти биты (та же формула, что и выше, но << n ) и проверить, равен ли результат 0:

00000[1]01010 0 11101 0 00010 0 00011 0    ╓╖    00000 1 00000 1 00000 1 00000 1 00000 1         ╓─╖ ╓───╖
10011 0 00001 0 11101 0 00011 0 00010 0   ╓╜╙╖   00000 1 00000 1 00000 1 00000 1 00000 1        ╓╜ ╙╖    ║
00000[1]00001 0 00011 0 11100 0 11100 0   ╙╥╥╜   00000 1 00000 1 00000 0 00000 0 00000 0  ═════ ║   ║  ╓─╜
11111 0 11111 0 11111 0 11111 0 11111 0   ╓╜╙╥╜  00000 0 00000 0 00000 0 00000 0 00000 0  ═════ ╙╖ ╓╜  ╨
11111 0 11111 0 11111 0 11111 0 11111 0   ╙──╨─  00000 0 00000 0 00000 0 00000 0 00000 0         ╙─╜   o

Если это не ноль, сетка невозможна, и мы можем остановиться.

Timwi
источник
3
СВЯТОЙ ЧЕРТ. Чувак, это впечатляет.
Деусови
1
Я второй @ комментарий Deusovi, спасибо за то, что вы приложили столько усилий для этого
hargasinski
7

Haskell, 790 * 0,80 = 632 байта

import Data.List
import Control.Monad
import Data.Array
s r=let{h as bs=[(a,b)|a<-as,b<-bs];(&)m k=(\(Just x)->x)$lookup k m;j=Just;n=Nothing;c=[1..r];q=delete;u=h[1..r]c;o=[(s,[u |u<-[h[1..r][c]|c<-c]++[h[r]c|r<-[1..r]]++[zip[1..r][1..r],zip[1..r][r,r-1..1]],s`elem`u])|s<-u];k=foldr(>=>)j;a p d g0=k[t p d2|d2<-q d(g0!p)]g0;t p d g0|not(d`elem`(g0!p))=j g0|[]<-v=n|[d2]<-v=k[t s2 d2|s2<-[(s,delete s$nub(concat(o&s)))|s<-u]&p]g1|True=k[l[s|s<-u,not(d`elem`v)]|u<-o&p]g1 where{v=q d(g0!p);g1=g0//[(p,v)];l[]_=n;l[d3]g=a d3 d g;l _ r=j r};w g0|and[case g0!s of{[_]->True;_->False}|s<-u]=j g0|True=msum[a s' d g0>>=w|d<-g0!s']where(_,s')=minimumBy(\(a,_)(b,_)->compare a b)[(l,s)|s<-u,let v=g0!s;l=length v,l>1]}in fmap(fmap(\[x]->x))$w$array((1,1),(r,r))[((i,j),[1..r])|i<-[1..r],j<-[1..r]]

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

Это выполняет бонус, потому что он возвращает Nothingдля n=2,3и Just <result>для n>=4, где <result>двумерный массив интегральных значений.

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

user2407038
источник
1
Несколько быстрых советов: а) вы определите c=[1..r], чтобы вы могли использовать его в oи w. б) minimumBy(\(a,_)(b,_)->compare a b)[...]есть head$sortOn fst[...]. в) vв v=g0!sиспользуется только один раз, так что не определить его вообще: l=length$g0!s. г) у вас еще есть несколько двухбуквенных имен параметров. д) заменить Trueна 1<2и Falseс 2<1. е) and[case g0!s of{[_]->True;_->False}|s<-u]есть all((==1).length.(g0!))u.
Ними,
Быстрые советы, часть II: г) (&)m k=может быть определен инфикс: m&k=. з) not(dЭлем (g0!p))есть notElem d$g0!p. я) concat(...)есть id=<<(...). j) использовать инфиксный оператор h, например, для as%bs=.
Ними,
3
Быстрые мета-подсказки: вы можете разделить код, который содержит обратные кавычки, используя двойные обратные кавычки ​``like`this``​!
Линн
4

Pyth, 41 байт

#Km.SQQI.AmqQl{d+.TK.Tm,@@Kdd@@Kt-QddQB;K

#                                      ;   # while(True)
 Km.SQQ                                    # K = random QxQ 2d list
       I                               ;   # if ...
        .A                                 # all of...
          m                          Q     # map(range(Q))...
                +                          # concat
                 .TK                       # transpose K
                    .Tm,@@Kdd@@Kt-Qdd      # diagonals of K
                      m             d      # map(range(d))
                       ,                   # 2-elem list of...
                        @@Kdd              # K[n][n]
                             @@Kt-Qd       # and K[len(K)-n-1][n]
                    .T                     # transpose
           qQl{d                           # subarrays have no dups...
                                      B;   # ... then, break
                                        K  # output final result

Грубая сила ФТВ!

Так как это в основном продолжает пробовать случайные тасовки, пока оно не работает (ну, это продолжает пытаться n * [shuffle(range(n))]), это занимает очень, очень много времени. Вот несколько тестовых прогонов, чтобы дать вам представление о том, сколько времени это займет:

llama@llama:~$ time echo 4 | pyth <(echo '#Km.SQQI.AmqQl{d+.TK.Tm,@@Kdd@@Kt-QddQB;K')               
[[2, 1, 0, 3], [0, 3, 2, 1], [3, 0, 1, 2], [1, 2, 3, 0]]
echo 4  0.00s user 0.00s system 0% cpu 0.001 total
pyth <(echo '#Km.SQQI.AmqQl{d+.TK.Tm,@@Kdd@@Kt-QddQB;K')  0.38s user 0.00s system 96% cpu 0.397 total

Это только 4х4, и он работает чуть меньше полсекунды. Я на самом деле обманываю, потому что это лучшее из нескольких испытаний - большинство из них занимают секунду или две.

У меня еще не было времени на 5х5 (оно дошло до завершения, но это было в REPL, и я не рассчитывал его).

Обратите внимание, что правило для ограничения времени было отредактировано в вопросе только после публикации этого ответа.

Дверная ручка
источник
Я полагаю, что это не может сделать 7x7 в течение десяти минут? ^^
Линн
@Mauris Ну, иногда это может ...;) Это требование я пропустил? Я не вижу ничего, упоминающего ограничение времени в вопросе.
Дверная ручка
Я вижу это в комментариях (не новый комментарий, 12 часов назад)
edc65
К сожалению об этом, я не думал об этом, пока кто-то не упомянул об этом, я сейчас отредактирую вызов
hargasinski
1
+1 за абстрактное искусство ASCII в вашей закомментированной версии. :)
Ильмари Каронен
3

SWI-Prolog, 326 * 0,80 = 260,8 байта

:-use_module(library(clpfd)).
a(N):-l(N,R),m(l(N),R),append(R,V),V ins 1..N,transpose(R,C),d(0,R,D),maplist(reverse,R,S),d(0,S,E),m(m(all_distinct),[R,C,[D,E]]),m(label,R),m(p,R).
l(L,M):-length(M,L).
d(X,[H|R],[A|Z]):-nth0(X,H,A),Y is X+1,(R=[],Z=R;d(Y,R,Z)).
p([H|T]):-write(H),T=[],nl;write(' '),p(T).
m(A,B):-maplist(A,B).

Редактировать: сохранено 16 байт благодаря @Mat

использование

Позвоните a(5).своему переводчику для N=5. Это возвращает falseдля N=2или N=3.

Поскольку он использует библиотеку CLPFD, это не просто грубая сила. Эта программа может найти решение N=20примерно за 15 секунд на моем компьютере.

Ungolfed + объяснения:

Это в основном работает как решатель судоку, за исключением того, что ограничения блоков заменяются ограничениями диагоналей.

:-use_module(library(clpfd)).      % Import Constraints library

a(N):-
    l(N,R),                        % R is a list of length N
    maplist(l(N),R),               % R contains sublists, each of length N
    append(R,V),                   
    V ins 1..N,                    % Each value in the matrix is between 1 and N
    maplist(all_distinct,R),       % Values must be different on each row
    transpose(R,C),
    maplist(all_distinct,C),       % Values must be different on each column
    d(0,R,D),
    maplist(reverse,R,S),          
    d(0,S,E),
    all_distinct(D),               % Values must be different on the diagonal
    all_distinct(E),               % Values must be different on the "anti"-diagonal
    maplist(label,R),              % Affects actual values to each element
    maplist(p,R).                  % Prints each row

l(L,M):-length(M,L).               % True if L is the length of M

d(X,[H|R],[A|Z]):-nth0(X,H,A),Y is X+1,(R=[],Z=R;d(Y,R,Z)). % True if the third argument is the diagonal of the second argument

p([H|T]):-write(H),T=[],nl;write(' '),p(T).  % Prints a row separated by spaces and followed by a new line
Fatalize
источник
Очень хорошо! Вы можете сохранить байты с:maplist(maplist(all_distinct), [R,C,D,E])
мат
1
@mat Спасибо за предложение, экономит 16 байтов. Мне нужно использовать, [R,C,[D,E]]хотя, потому что Eи Dпростые списки.
Роковая
Хорошо, очень хороший обходной путь!
мат
2
@Fatalize Просто чтобы вы знали, ваше решение было самым впечатляющим, так как оно единственное, которое решилоN=20
hargasinski
1
@ Zequ Спасибо! Но это главным образом из-за удивительной библиотеки Prolog CLPFD, которая выполняет тяжелую работу в подобных задачах :)
Fatalize
2

CJam, 87 байт - бонус 20% = 69,6 байт

qi__"@I/l
ŤˏūȻ
܀ᅀ൹৽჈͚
㑢鴑慚菥洠㬝᚜
"N/=:i0+\,m!f=`1LL](4e<=

Жесткие коды ответов. Содержит некоторые непечатные. Работает на N = 1протяжении N = 8.

По сути, каждая строка в этой загадочной строке содержит индексы в списке перестановок range(N), закодированных в виде символов Юникода.

=:i0+\,m!f=индексирует в список перестановок, добавляя сначала 0 в конец списка индексов, представляя нижнюю строку 0 1 2 ... N-1. Ибо N < 4результирующий двумерный массив - нонсенс.

`1LL]создает список [N, pretty output, 1, "", ""]. Затем (4e<=извлекает первый элемент из этого списка Nи извлекает его min(N, 4) % 4из остальной части. Ведь N >= 4это выходные данные, а в остальном это выходы для особых случаев для первых трех случаев.

Попробуй это здесь .

Линн
источник
0

C ++, 672 * 0,80 645 * 0,80 = 516 байт

#include <iostream>
int **b,**x,**y,*d,*a,n;
#define R(i) for(i=0;i<n;i++){
#define E(e) e=new int[n];
int f(int c,int r) {int i=0,p=c-1;if(r>=n)return 1;if(c == n + 1)return f(1,r+1);R(i)int m=r==i,s=r+i==n-1;if(!b[r][i]&&!x[r][p]&&!(m&&d[p])&&!(s&&a[p])&&!y[i][p]){b[r][i]=c;x[r][p]=1;y[i][p]=1;if(m)d[p]=1;if(s)a[p]=1;if(f(c+1,r))return 1;b[r][i]=0;x[r][p]=0;y[i][p]=0;if(m)d[p]=0;if(s)a[p]=0;}}return 0;}
int main(){std::cin>>n;int i=0,j=0;b=new int*[n];x=new int*[n];y=new int*[n];E(d);E(a);R(i)E(b[i]);E(x[i]);E(y[i]); d[i]=0;a[i]=0;R(j)b[i][j]=0;x[i][j]=0;y[i][j]=0;}}if(f(1,0)){R(i)R(j)std::cout<<b[i][j];}std::cout<<std::endl;}}}

Попробуйте онлайн здесь

Поскольку пара ответов уже была опубликована, я подумал, что опубликую версию кода, которую я использовал для создания выходных данных для примеров. Я впервые отвечаю на код-гольф , поэтому все отзывы приветствуются. :)

Ungolfed + объяснения:

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

#include <iostream>

// global variables to save bytes on passing these are function arguments
int **b, // this will store the state of the board
    **x, // if x[i][j] is true, row i of b contains the number j
    **y, // if y[i][j] is true, column i of b contains the number j
    *d,  // if d[i] the main diagonal of b contains i
    *a,  // if a[i] the antidiagonal of a contains i
    n;

// preprocessor to save bytes on repeated statements
#define R(i) for(i=0;i<n;i++){
#define E(e) e=new int[n];

// Recursively looks for a solution 
// c - the current number to insert in row r
// r - the current row to fill
int f (int c, int r) {
        int i=0,p=c-1;
        if (r >= n) return 1;             // we are done
        if (c == n + 1) return f(1,r+1);  // this row is full, move to the next row
        R(i)                              // go through the positions in this row,
                                                                            // trying to fill them with c
                int m=r==i, s=r+i==n-1;   // check if this position (r,i) is on ones
                                                                            // of the diagonals
                // if this spot isn't filled, and the row (r), column (i) and diagonals
                // (if it's on the diagonal) doesn't contain the number, fill the spot
                if (!b[r][i] && !x[r][p] && !(m&&d[p]) && !(s&&a[p]) && !y[i][p]) {
                        // fill the spot, and indicate that this row, column and diagonals 
                        // contain this number, c
                        b[r][i]=c; x[r][p]=1; y[i][p]=1;
                        if (m) d[p]=1; if (s)a[p]=1;

                        // move onto to the next number, if you find a solution, stop
                        if (f(c+1,r)) return 1;

                        // with this number in this spot, a solution is impossible, clear
                        // its, and clear the checks
                        b[r][i]=0; x[r][p]=0; y[i][p]=0;
                        if (m) d[p]=0; if (s) a[p]=0;
                }
        }

        return 0; // a solution wasn't found
}

int main() {
        std::cin >> n; // get n from STDIN

        // initialization 
        int i=0,j=0;
        b=new int*[n]; x=new int*[n]; y=new int*[n];
        E(d); E(a);
        R(i)
                E(b[i]); E(x[i]); E(y[i]); // initialization the inner arrays of b, x, y
                d[i]=0; a[i]=0;

                R(j)
                        b[i][j]=0; x[i][j]=0; y[i][j]=0; // ensure each point is initialized as 0
                }
        }

        // find a solution starting at the top-left corner and print it if it finds one
        if (f(1,0)) {
                R(i)
                        R(j)
                                std::cout<<b[i][j];
                        }
                        std::cout<<std::endl;
                }
        }
}
hargasinski
источник
После того, как перечитывать код, я понял , некоторые из проверок не может быть необходимо, например , как if (x[r][p]) return f(c+1,r);. Я работаю над его сокращением.
Hargasinski
0

Clojure, (215 + 258) * 0,8 = 378,4 (174 + 255) * 0,8 = 343,2

Разделен на две части: подсчет ошибок Sи анонимная функция, которая выполняет фактическую оптимизацию с помощью поиска в Tabu .

Обновление: короче S(считает различные значения в группах), менее оптимальное начальное состояние (без перемешивания).

(defn S[I n](count(mapcat set(vals(apply merge-with concat(flatten(for[R[(range n)]i R j R v[[(I(+(* n i)j))]]][{[1 i]v}{[2 j]v}(if(= i j){3 v})(if(=(- n 1 i)j){4 v})])))))))
#(if-let[s({1[0]2()3()}%)]s(loop[I(vec(for[R[(range %)]i R j R]i))P #{}](let[[s I](last(sort-by first(for[R[(range(count I))]i R j R I[(assoc(assoc I i(I j))j(I i))]:when(not(P I))][(S I %)I])))](if(=(*(+(* % 2)2)%)s)(partition % I)(recur I(conj P I))))))

Одноядерные тесты (в миллисекундах) для 4, 5, 6 и 7 запускаются 3 раза:

[[  131.855337   132.96267    138.745981]
 [ 1069.187325  1071.189488  1077.339372]
 [ 9114.736987  9206.65368   9322.656693]
 [36546.309408 36836.567267 36928.346312]]

Оригинал:

(defn S[I n](apply +(flatten(for[p(concat(partition n I)(for[p(apply map vector(partition n(range(count I))))](map I p))[(take-nth(inc n)I)][(rest(butlast(take-nth(dec n)I)))])](remove #{1}(vals(frequencies p)))))))
#(if-let[s({1[0]2()3()}%)]s(loop[I(vec(flatten(map shuffle(repeat %(range %)))))P #{}](let[[s I](first(sort-by first(for[R[(range(count I))]i R j R I[(assoc(assoc I i(I j))j(I i))]:when(not(P I))][(S I %)I])))](if(= s 0)(partition % I)(recur I(conj P I))))))

Хотелось бы, чтобы он Sбыл короче, но, поскольку он учитывает вхождения более одного / раздела, критерий остановки прост (= s 0).

Многие циклы процессора впустую для не-полезных свопов, например , это не улучшает счет , если вы поменяться 2с 2, и вам не нужны числами свопа между рядами , как все они имеют различные значения для начала.

Тесты с Intel 6700K (в миллисекундах):

(defn S[I n]( ... )
(def F #( ... ))

(defmacro mytime[expr]
  `(let [start# (. System (nanoTime)) ret# ~expr]
     (/ (double (- (. System (nanoTime)) start#)) 1000000.0)))

(pprint(vec(for[n[4 5 6 7]](vec(sort(repeatedly 5 #(mytime (F n)))))))

[[  43.445902   45.895107   47.277399   57.681634    62.594037]
 [ 222.964582  225.467034  240.532683  330.237721   593.686911]
 [2285.417473 2531.331068 3002.597908 6361.591714  8331.809410]
 [3569.62372  4779.062486 5725.905756 7444.941763 14120.796615]]

Многопоточный с pmap:

[[   8.881905  16.343714   18.87262  18.9717890   22.194430]
 [  90.963870 109.719332  163.00299  245.824443  385.365561]
 [ 355.872233 356.439256 1534.31059 2593.482767 3664.221550]
 [1307.727115 1554.00260 2068.35932 3626.878526 4029.543011]]
NikoNyrh
источник