Tarefa

Dada a entrada N, gere e produza uma grade NxN em que cada linha, coluna e as duas diagonais contenham os números de 1 a N(ou 0 a N-1 se for mais fácil).

Entrada

A entrada é um número inteiro positivo N. Representa o número de colunas e linhas na grade. Para esse problema, você pode assumir Nque o tamanho é razoável 4 ≤ N ≤ 8ou ( 1 ≤ N ≤ 8se você optar pelo bônus abaixo).

Saída

A saída será a grade N× N. Na grade, cada linha contém apenas os números 1 a N, cada coluna contém apenas os números 1 a Ne as duas diagonais de comprimento N(a de (0,0)a (N-1,N-1)e a de (0,N-1)a (N-1, 0)) contêm apenas os números de 1 a N. Você pode usar os números de 0 a N−1. Para cada uma delas N, existem muitas soluções possíveis, você só precisa imprimir a primeira que encontrar. Você não precisa imprimir espaços entre os números.

Restrições

Seu código deve ser capaz de produzir resultados repetidamente para N >= 7. Ou seja, se você é capaz de executar e obter uma solução a N = 7partir do seu código a cada vez, você é bom. Em termos de um limite absoluto, seu código deve ser resolvido N = 7em menos de 10 minutos cada vez que você o executar (ou seja, se você depende de números aleatórios, na pior das hipóteses, seu código ainda deve terminar em menos de 10 minutos por N = 7) .

Exemplos

• Entrada: 4

  Uma saída possível:

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

• Entrada: 5

  Uma saída possível:

  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
  

• Entrada: 8

  Uma saída possível:

  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
  

Pontuação

Isso é código-golfe , portanto o código mais curto em bytes vence, com uma exceção. Para entradas, N = 2, 3não há soluções válidas. Se o seu código puder lidar com isso (execute até a conclusão sem gerar nada para esses casos ou gerar uma string vazia) e ainda manipule N = 1(produza 1para ele), retire 20% da sua contagem de bytes.

Python 3, 275 260 bytes * 0,8 = 220 208 bytes

Abordagem recursiva / backtracking. Ré a função recursiva, lé a coluna, wé a linha, Ké a próxima entrada.

Eu escolhi colocá-lo em uma matriz 1d e imprimi-lo no final para simplificar os índices.

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)

Versão não destruída:

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

Funciton não competitiva

ATUALIZAR! Melhoria maciça de desempenho!n = 7 agora é concluído em menos de 10 minutos! Veja a explicação na parte inferior!

Foi divertido escrever isso. Este é um solucionador de força bruta para esse problema escrito em Funciton. Alguns factóides:

• Ele aceita um número inteiro em STDIN. Qualquer espaço em branco estranho o quebra, incluindo uma nova linha após o número inteiro.
• Ele usa os números 0 a n - 1 (não 1 a n ).
• Ele preenche a grade "para trás", para que você obtenha uma solução na qual a linha inferior lê, 3 2 1 0e não na linha superior 0 1 2 3.
• Ele gera corretamente 0(a única solução) para n = 1.
• Saída vazia para n = 2 en = 3.
• Quando compilado em um exe, leva cerca de 8¼ minutos para n = 7 (foi cerca de uma hora antes da melhoria de desempenho). Sem compilar (usando o intérprete), leva cerca de 1,5 vezes mais, portanto vale a pena usar o compilador.
• Como marco pessoal, esta é a primeira vez que escrevi um programa inteiro da Funciton sem antes escrever o programa em uma linguagem de pseudocódigo. Eu escrevi em C # real primeiro.
• (Entretanto, não é a primeira vez que faço uma alteração para melhorar enormemente o desempenho de algo no Funciton. A primeira vez que fiz isso foi na função fatorial. Trocar a ordem dos operandos da multiplicação fez uma enorme diferença por causa de como o algoritmo de multiplicação funciona . Caso você tenha curiosidade.)

Sem mais delongas:

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

Explicação da primeira versão

A primeira versão levou cerca de uma hora para resolver n = 7. O seguinte explica principalmente como essa versão lenta funcionou. Na parte inferior, explicarei as alterações que fiz para reduzir para menos de 10 minutos.

Uma excursão em pedaços

Este programa precisa de bits. Ele precisa de muitos bits, e precisa deles nos lugares certos. Programadores de funções experientes já sabem que se você precisar de n bits, poderá usar a fórmula

que em Funciton pode ser expresso como

Ao fazer minha otimização de desempenho, ocorreu-me que eu posso calcular o mesmo valor muito mais rapidamente usando esta fórmula:

Espero que você me perdoe por não ter atualizado todos os gráficos de equação neste post.

Agora, digamos que você não queira um bloco contíguo de bits; na verdade, você quer n bits em intervalos regulares a cada k- ésimo bit, assim:

                                 LSB
                                  ↓
00000010000001000000100000010000001
                            └──┬──┘
                               k

A fórmula para isso é bastante direta quando você a conhece:

No código, a função Ӝtoma valores de n e k e calcula esta fórmula.

Acompanhar os números usados

Existem n ² números na grade final e cada número pode ter qualquer um dos n valores possíveis. Para acompanhar quais números são permitidos em cada célula, mantemos um número que consiste em n ³ bits, no qual um bit é definido para indicar que um valor específico é obtido. Inicialmente, esse número é 0, obviamente.

O algoritmo começa no canto inferior direito. Depois de "adivinhar" o primeiro número é um 0, precisamos acompanhar o fato de que o 0 não é mais permitido em nenhuma célula na mesma linha, coluna e diagonal:

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

Para esse fim, calculamos os quatro valores a seguir:

• Linha atual: precisamos de n bits a cada n- ésimo bit (um por célula) e, em seguida, alteramos para a linha atual r , lembrando que cada linha contém n ² bits:

  

• Coluna atual: precisamos de n bits a cada n² -ésimo bit (um por linha) e, em seguida, mudamos para a coluna atual c , lembrando que cada coluna contém n bits:

  

• Diagonal para a frente: precisamos de n bits a cada ... (você prestou atenção? Rápido, resolva isso!) ... n ( n +1) -simo bit (bom trabalho!), Mas apenas se estivermos realmente ligados a diagonal para a frente:

  

• Diagonal para trás: duas coisas aqui. Primeiro, como sabemos se estamos na diagonal para trás? Matematicamente, a condição é c = ( n - 1) - r , que é a mesma que c = n + (- r - 1). Ei, isso lembra alguma coisa? É isso mesmo, é o complemento de dois, para que possamos usar a negação bit a bit (muito eficiente no Funciton) em vez do decremento. Segundo, a fórmula acima pressupõe que queremos que o bit menos significativo seja definido, mas na diagonal reversa não, então temos que alterá-lo ... você sabe? ... Isso mesmo, n ( n - 1).

  

  Este também é o único onde potencialmente dividimos por 0 se n = 1. No entanto, o Funciton não se importa. 0 ÷ 0 é apenas 0, você não sabe?

No código, a função Җ(a inferior) pega n e um índice (do qual calcula r e c por divisão e restante), calcula esses quatro valores e oros reúne.

O algoritmo de força bruta

O algoritmo de força bruta é implementado por Ӂ(a função na parte superior). Leva n (o tamanho da grade), índice (onde atualmente estamos colocando um número na grade) e obtido (o número com n ³ bits nos dizendo quais números ainda podemos colocar em cada célula).

Esta função retorna uma sequência de strings. Cada string é uma solução completa para a grade. É um solucionador completo; retornaria todas as soluções, se você permitir, mas as retornará como uma sequência avaliada preguiçosamente.

• Se o índice atingiu 0, preenchemos com êxito a grade inteira, portanto retornamos uma sequência contendo a sequência vazia (uma solução única que não cobre nenhuma das células). A string vazia é 0, e usamos a função de biblioteca ⌑para transformá-la em uma sequência de elemento único.

• A verificação descrita em melhoria de desempenho abaixo acontece aqui.

• Se o índice ainda não atingiu 0, diminuímos em 1 para obter o índice no qual agora precisamos colocar um número (chame ix ).

  Usamos ♫para gerar uma sequência lenta contendo os valores de 0 a n - 1.

  Em seguida, usamos ɓ(ligação monádica) com um lambda que faz o seguinte na ordem:

  • Primeiro, observe o bit relevante a ser tomado para decidir se o número é válido aqui ou não. Podemos colocar um número i se, e somente se, for obtido & (1 << ( n × ix ) << i ) ainda não está definido. Se estiver definido, retorne 0(sequência vazia).
  • Use Җpara calcular os bits correspondentes à linha, coluna e diagonal (s) atuais. Desloque-o por i e depois orpara tomado .
  • Chame recursivamente Ӂpara recuperar todas as soluções para as células restantes, passando a nova tomada e a ix decrementada . Isso retorna uma sequência de cadeias incompletas; cada sequência possui caracteres ix (a grade é preenchida até o índice ix ).
  • Use ɱ(mapa) para percorrer as soluções assim encontradas e use ‼para concatenar i ao final de cada uma. Acrescente uma nova linha se o índice for múltiplo de n , caso contrário, um espaço.

Gerando o resultado

O programa principal chama Ӂ(o forçador bruto) com n , índice = n ² (lembre-se de preencher a grade para trás) e tomado = 0 (inicialmente nada é tomado). Se o resultado for uma sequência vazia (nenhuma solução encontrada), imprima a sequência vazia. Caso contrário, imprima a primeira string na sequência. Observe que isso significa que ele avaliará apenas o primeiro elemento da sequência, e é por isso que o solucionador não continua até encontrar todas as soluções.

Melhoria de desempenho

(Para quem já leu a versão antiga da explicação: o programa não gera mais uma sequência de sequências que precisa ser transformada separadamente em uma sequência de saída; apenas gera uma sequência de sequências diretamente. Editei a explicação de acordo . Mas essa não foi a principal melhoria. Aí vem.)

Na minha máquina, o exe compilado da primeira versão demorou quase exatamente 1 hora para resolver n = 7. Isso não estava dentro do prazo especificado de 10 minutos, então não descansei. (Bem, na verdade, a razão pela qual eu não descansei foi porque eu tinha essa ideia de como acelerar bastante.)

O algoritmo, conforme descrito acima, interrompe sua pesquisa e retorna sempre que encontra uma célula na qual todos os bits do número obtido são definidos, indicando que nada pode ser colocado nessa célula.

No entanto, o algoritmo continuará a preencher futilmente a grade até a célula na qual todos esses bits estão definidos. Seria muito mais rápido se pudesse parar assim que qualquer célula ainda a ser preenchida já tiver todos os bits configurados, o que já indica que nunca poderemos resolver o restante da grade, independentemente dos números que inserimos isto. Mas como você verifica com eficiência se alguma célula possui seus n bits definidos sem passar por todos eles?

O truque começa adicionando um único bit por célula ao número obtido . Em vez do que foi mostrado acima, agora fica assim:

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

Em vez de n ³, agora existem n ² ( n + 1) bits nesse número. A função que preenche a linha / coluna / diagonal atual foi alterada de acordo (na verdade, completamente reescrita para ser sincera). Porém, essa função ainda preencherá apenas n bits por célula; portanto, o bit extra que acabamos de adicionar sempre será 0.

Agora, digamos que estamos no meio do cálculo, apenas colocamos um 1na célula do meio e o número obtido é mais ou menos assim:

                 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

Como você pode ver, a célula superior esquerda (índice 0) e a célula esquerda central (índice 10) agora são impossíveis. Como determinamos isso com mais eficiência?

Considere um número no qual o 0º bit de cada célula está definido, mas apenas até o índice atual. É fácil calcular esse número usando a fórmula familiar:

O que teríamos se adicionássemos esses dois números?

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

O resultado é:

             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

Como você pode ver, a adição transborda para o bit extra que adicionamos, mas apenas se todos os bits para essa célula estiverem definidos! Portanto, tudo o que resta a fazer é mascarar esses bits (mesma fórmula acima, mas << n ) e verificar se o resultado é 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

Se não for zero, a grade é impossível e podemos parar.

• Captura de tela mostrando a solução e o tempo de execução de n = 4 a 7.

Haskell, 790 * 0,80 = 632 bytes

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

Notei que este problema é muito semelhante ao sudoku. Lembro-me de um antigo solucionador de sudoku que escrevi em Haskell com base em nesse outro em Python. Este é o meu primeiro post ou tentativa de golfe com código.

Isso cumpre o bônus porque retorna Nothingpara n=2,3eJust <result> para n>=4, onde <result>é uma matriz 2D de valores integrais.

Veja aqui o intérprete online. Na verdade, esse código é mais longo que o da publicação, porque o intérprete on-line possui requisitos mais rígidos sobre o que forma um programa completo (as regras dizem que um envio pode ser uma função). Este envio recebe entrada como argumento de função.

Pitão, 41 bytes

#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

Força bruta ftw!

Como isso basicamente continua tentando embaralhar aleatoriamente até que funcione (bem, continua tentando n * [shuffle(range(n))]), leva muito, muito tempo. Aqui estão alguns testes para dar uma idéia de quanto tempo leva:

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

Isso é apenas 4x4, e roda em pouco menos de meio segundo. Na verdade, estou trapaceando porque esse é o melhor de alguns ensaios - a maioria deles demora mais de um segundo ou dois.

Ainda estou para obter um timing em 5x5 (ele foi concluído uma vez, mas isso estava em um REPL e eu não estava no momento).

Observe que a regra para o prazo só foi editada na pergunta após a publicação desta resposta.

SWI-Prolog, 326 * 0,80 = 260,8 bytes

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

Edit: salvou 16 bytes graças a @Mat

Uso

Ligue a(5).para o seu intérprete para N=5. Isso retorna falsepara N=2ou N=3.

Como ele usa a biblioteca CLPFD, isso não é força bruta pura. Este programa pode encontrar uma solução paraN=20 em 15 segundos no meu computador.

Ungolfed + explicações:

Isso basicamente funciona como um solucionador de Sudoku, exceto que as restrições de blocos são substituídas pelas restrições de diagonais.

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

CJam, 87 bytes - bônus de 20% = 69,6 bytes

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

Codifica as respostas. Contém alguns imprimíveis. Trabalhos para N = 1através N = 8.

Basicamente, cada linha nessa cadeia misteriosa contém índices na lista de permutações de range(N), codificados como caracteres Unicode.

=:i0+\,m!f=indexa na lista de permutações, adicionando um 0 ao final da lista de índices primeiro, representando a linha inferior 0 1 2 ... N-1. Pois N < 4, a matriz 2D resultante não faz sentido.

`1LL]cria uma lista [N, pretty output, 1, "", ""]. Em seguida, (4e<=aparece o primeiro elemento dessa lista Ne recupera o min(N, 4) % 4elemento th do restante. Pois N >= 4essa é a saída e, caso contrário, são as saídas de casos especiais para os três primeiros casos.

Experimente aqui .

C ++, 672 * 0,80 645 * 0,80 = 516 bytes

#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;}}}

Experimente online aqui

Como algumas respostas já foram postadas, pensei em publicar a versão em golf do código que usei para gerar a saída para os exemplos. Esta é minha primeira vez respondendo a código de golfe , para que todos os comentários sejam bem-vindos. :)

Ungolfed + explicações:

Essencialmente, o código está forçando brutalmente uma solução. Começa na primeira linha, com 0. Começa no primeiro ponto, se esse ponto passar em todas as verificações, passará para o próximo número. Se preencher a linha, passa para a próxima linha. Se isso for feito em todas as linhas, isso significa que uma solução foi encontrada. Se o ponto não passar em todas as verificações, ele passa para o próximo ponto. Se a linha for concluída, ela retornará, pois um número em uma das linhas anteriores impede que uma solução seja possível.

#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;
                }
        }
}

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

Dividido em duas partes: contagem de erros Se uma função anônima que faz a otimização real via pesquisa Tabu .

Atualização: mais curto S(conta valores distintos dentro dos grupos), estado inicial menos ideal (sem reprodução aleatória).

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

Benchmarks de núcleo único (em milissegundos) por 4, 5, 6 e 7 executados 3 vezes:

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

Original:

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

Eu gostaria que Sfosse mais curto, mas como conta apenas ocorrências de mais de uma / partição, o critério de parada é simples(= s 0) .

Muitos ciclos de CPU são desperdiçados para trocas não úteis, por exemplo, não melhora a pontuação se você trocar 2com2 , e você não precisa de números de swap entre linhas como todos eles têm valores distintos para começar.

Benchmarks com o Intel 6700K (em milissegundos):

(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]]

Multithread com 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]]