N-Queens Puzzle

17

(Apesar de mais de 60 perguntas marcadas como , não temos um desafio simples das n rainhas.)

No xadrez, o quebra-cabeça do N-Queens é descrito a seguir: Dado um n x ntabuleiro de xadrez e nrainhas, organize as rainhas no tabuleiro de xadrez para que não haja duas rainhas ameaçando uma à outra. Abaixo está um exemplo de solução para n = 8, emprestado da Wikipedia.

Solução de exemplo de 8 rainhas da Wikipedia

Ou, na renderização ASCII:

xxxQxxxx
xxxxxxQx
xxQxxxxx
xxxxxxxQ
xQxxxxxx
xxxxQxxx
Qxxxxxxx
xxxxxQxx

O desafio aqui será receber ne ngerar uma representação ASCII de uma solução para o quebra-cabeça -Queens. Como há mais de uma solução possível (por exemplo, pelo menos, uma rotação ou reflexão), seu código só precisa gerar uma solução válida.

Entrada

Um número inteiro positivo único ncom n >= 4 em qualquer formato conveniente . (n = 2 en = 3 não têm soluções, e n = 1 é trivial, portanto essas são excluídas)

Resultado

A representação ASCII resultante de uma solução para o quebra-cabeça N-rainhas, conforme descrito acima. Você pode escolher dois valores ASCII distintos para representar espaços em branco e rainhas. Novamente, isso pode ser produzido em qualquer formato adequado (cadeia única, uma lista de cadeias, uma matriz de caracteres, etc.).

Regras

  • Novas linhas à esquerda ou à direita ou espaços em branco são opcionais, bem como espaços em branco entre os caracteres, desde que os próprios caracteres estejam alinhados corretamente.
  • Você pode usar um algoritmo para calcular as posições possíveis ou usar o estilo explícito de solução "degrau", o que for mais positivo para o seu código.
  • Um programa completo ou uma função são aceitáveis. Se uma função, você pode retornar a saída em vez de imprimi-la.
  • Se possível, inclua um link para um ambiente de teste on-line para que outras pessoas possam experimentar seu código!
  • As brechas padrão são proibidas.
  • Isso é portanto todas as regras usuais de golfe se aplicam e o código mais curto (em bytes) vence.

Exemplos

n=4
xQxx
xxxQ
Qxxx
xxQx

n=7
xxQxxxx
xxxxxxQ
xQxxxxx
xxxQxxx
xxxxxQx
Qxxxxxx
xxxxQxx

n=10
xxxxQxxxxx
xxxxxxxxxQ
xxxQxxxxxx
xxxxxxxxQx
xxQxxxxxxx
xxxxxxxQxx
xQxxxxxxxx
xxxxxxQxxx
Qxxxxxxxxx
xxxxxQxxxx
AdmBorkBork
fonte
11
Relacionado.
totallyhuman
11
Você poderia dar casos de teste para entradas ímpares?
Kritixi Lithos
@Cowsquack Adicionado n = 7 exemplo
AdmBorkBork
11
@KeyuGan Algo parecido com a resposta do MATL? Sim, tudo bem.
AdmBorkBork
2
@JonathanAllan Nenhuma exclusão foi planejada, desde que o programa termine em tempo finito com probabilidade 1 (como padrão para todos os envios).
AdmBorkBork

Respostas:

5

MATL , 33 32 27 bytes

`x,GZ@]1Z?tt!P!,w&TXds]h1>a

Experimente online!

Força semi-bruta, abordagem não determinística:

  1. Gere uma permutação aleatória de posições de linha
  2. Gere uma permutação aleatória das posições da coluna
  3. Verifique se nenhuma rainha compartilha uma diagonal ou anti-diagonal
  4. Repita se necessário.

A solução obtida é aleatória. Se você executar o código novamente, poderá obter uma configuração válida diferente. O tempo de execução também é aleatório, mas o caso de teste mais longo ( n = 10) termina em cerca de 30 segundos no TIO na maioria das vezes.

Luis Mendo
fonte
Não tenho certeza se isso conta como uma solução, já que nem sempre dá a resposta correta.
Junkmail
11
@junkmail Hein? Não existe a resposta correta, pois existem várias soluções (conforme declarado no desafio). O código sempre dá uma resposta correta, não apenas o mesmo de cada vez
Luis Mendo
Teoricamente, é possível que o programa seja executado arbitrariamente várias vezes e ainda assim não consegue responder.
Junkmail
11
@junkmail Mas ele termina em tempo finito com uma probabilidade
Luis Mendo
11
@JamesHollis Eu discordo. Isso poderia tornar algumas permutações mais prováveis ​​que outras, mas não impediria que nenhuma permutação aparecesse. Portanto, a solução seria finalmente alcançada. E, além disso, assumindo que o gerador aleatório é ideal é normalmente aceite
Luis Mendo
5

C, 114 bytes

Q(n,o,y){o=n%2;n-=o;for(y=0;y<n+o;++y)printf("%*c\n",y<n?o+n-(n+y%(n/2)*2+(n%6?y<n/2?n/2-1:2-n/2:y<n/2))%n:0,81);}

Imprime diretamente uma solução em O (1).

orlp
fonte
11
Não está claro para mim como pode ser O (1) com um loop repetindo n vezes. Como todos esses cálculos sempre podem ser feitos em tempo constante?
poi830
11
@ poi830 Quero dizer O (1) tempo de computação por linha para determinar a posição da rainha.
orlp
você não poderia economizar alguns criando uma nova variável para n/2?
Jeffmagma
Sugerir n-=o=n%2;for(y=n+o;y--;) vez deo=n%2;n-=o;for(y=0;y<n+o;++y)
tetocat
2

Mathematica, 103 108 110 117 bytes

-5 bytes para DuplicateFreeQ->E!=##&@@@

-7 bytes para ReplacePart[Array[],]->SparseArray[]

SparseArray[Thread@#&@@Select[Permutations@Range@#~Tuples~2,And@@(E!=##&@@@{#-#2,+##})&@@#&]->1,{#,#}]&

Retorne uma matriz 2D. Demora 2.76s para calcular f[6]e 135s para f[7]. (Na versão atual, -torna-se0 - e Qpara 1.

resultado

O algoritmo é semelhante à resposta MATL, mas aqui o código é de força bruta.

Keyu Gan
fonte
1

C - 222 bytes

v,i,j,k,l,s,a[99];main(){for(scanf("%d",&s);*a-s;v=a[j*=v]-a[i],k=i<s,j+=(v=j<s&&(!k&&!!printf(2+"\n\n%c"-(!l<<!j)," #Q"[l^v?(l^j)&1:2])&&++l||a[i]<s&&v&&v-i+j&&v+i-j))&&!(l%=s),v||(i==j?a[i+=k]=0:++a[i])>=s*k&&++a[--i]);}

O código não é meu, mas do IOCCC . Espero não estar quebrando nenhuma regra. Além disso, isso exibe todas as soluções para N entre 4 e 99. Tentarei obter um link TIO posteriormente.

QuaerendoInvenietis
fonte
Como esse código não é seu, você pode convertê-lo em um Wiki da Comunidade? (basta clicar no botão abaixo da janela de edição que diz "Community Wiki")
caird coinheringaahing
Olá QuaerendoInvenietis e bem-vindo ao PPCG. Como está escrito atualmente, isso não parece ter um número específico como entrada e saída apenas para essa solução.
AdmBorkBork
1

Geléia , 24 21 bytes

,JŒc€IF€An/PC
ẊÇ¿=þRG

Experimente online!

Supondo que cada dama seja colocada em linhas separadas, precisamos apenas encontrar os índices da coluna para colocar cada dama para evitar conflitos, que podem ser encontrados gerando uma permutação aleatória de [1, 2, ..., n] e testando-a.

Explicação

,JŒc€IF€An/PC  Helper. Input: permutation of [1, 2, ..., n]
 J             Enumerate indices, obtains [1, 2, ..., n]
,              Join
  Œc€          Find all pairs in each
     I         Calculate the difference of each pair
      F€       Flatten each
        A      Absolute value
               (We now have the distance in column between each queen and
                the distance in rows between each queen. If they are unequal,
                the queens do not conflict with each other)
         n/    Reduce using not-equals
           P   Product, returns 1 only if they are all unequal
            C  Complement
               Returns 1 when there is a conflict, else 0

ẊÇ¿=þRG  Main.  Input: n
Ẋ        Shuffle (When given an integer, it will shuffle [1, 2, ..., n])
 Ç¿      While the helper returns 1, continue shuffling
     R   Range, gets [1, 2, ..., n]
   =þ    Equality table (Generates the board as a matrix)
      G  Pretty-print the matrix
milhas
fonte
Você não pode usar em Œc€vez de œc€2-1?
Erik the Outgolfer
1

Python 3, 204 189 bytes

import itertools as p
n=int(input())
r=range(n)
b='.'*(n-1)+'Q'
for c in p.permutations(r):
 if len(set((x*z+c[x],z)for x in r for z in[1,-1]))==n+n:[print(*(b[x:]+b[:x]))for x in c];break

Pesquisa de força bruta em todas as permutações. Eu poderia remover o * e imprimir as compreensões da lista, mas elas parecem horríveis.

Resultado:

10
Q . . . . . . . . .
. . Q . . . . . . .
. . . . . Q . . . .
. . . . . . . Q . .
. . . . . . . . . Q
. . . . Q . . . . .
. . . . . . . . Q .
. Q . . . . . . . .
. . . Q . . . . . .
. . . . . . Q . . .

Ligeiramente não destruído:

import itertools as p
n=int(input())
r=range(n)
b='.'*(n-1)+'Q'
for c in p.permutations(r):
    if len(set( (x*z+c[x],z) for x in r for z in[1,-1] )) == n+n:
        [print(*(b[x:] + b[:x])) for x in c]
        break
James Hollis
fonte
1

Anterior, 122 bytes

&::2%-v>2*00g++00g%00g\-\00g\`*4>8#4*#<,#-:#1_$55+"Q",,:#v_@
/2p00:<^%g01\+*+1*!!%6g00-2g01\**!!%6g00-g012!:`\g01:::-1<p01

Experimente online!

Isso é mais ou menos baseado na solução C do orlp .

Explicação

Código fonte com caminhos de execução destacados

*Leia o número de rainhas, q , de stdin e calcule duas variáveis ​​para uso posterior:, n = q - q%2e hn = n/2
*Inicie o loop principal, iterando r , o número da linha, de q até 0, decrementando no início do loop, então o primeiro r é q menos 1.
*Calcule o deslocamento da rainha em cada linha com a seguinte fórmula:

offset = (n - (
  (hn <= r) * (2 - hn) * !!(n % 6) + 
  (hn > r) * ((hn - 2) * !!(n % 6) + 1) + 
  (y % hn * 2) + n
) % n) * (n > r)

*Caracteres de espaço de deslocamento de saída para recuar a posição da rainha para a linha atual, mais um espaço adicional apenas porque facilita o loop de saída.
*Saída Qpara a rainha, seguida por uma nova linha para passar para a próxima linha.
*Teste se r é zero; nesse caso, chegamos ao final do quadro e podemos sair, caso contrário, repetimos o loop principal novamente.

James Holderness
fonte
0

Haskell , 145 bytes

A abordagem óbvia da força bruta:

b=1>0
t[]=b
t(q:r)=all(/=q)r&&foldr(\(a,b)->(abs(q-b)/=a&&))b(zip[1..]r)&&t r
q n|y<-[1..n]=(\q->(' '<$[1..q])++"Q")<$>[x|x<-mapM(\_->y)y,t x]!!0

Experimente online!

ბიმო
fonte
0

Retina , 136 bytes

.+
$* 
 
$_;$`Q¶
( +)\1( ?);
:$1;
:( +);\1\1
$1$1
:((   )+);( *)
 $1$1% $3$3
: ( +);( \1)?( *)
 $1 $1%$#2$* $#2$* $#2$* $1$3$3
( +)%\1?

Experimente online! Excelente resposta C do porto da @ orlp. Explicação:

.+
$* 

Converta em unário, usando espaços (existe um espaço após o *).

$_;$`Q¶

Crie Nlinhas com Nespaços, a ;, 0..N-1espaços e, em seguida, a Q. Os estágios restantes se aplicam a todas as linhas.

( +)\1( ?);
:$1;

Divida o número inteiro Npor 2. (Coloque também o resultado :;para facilitar a ancoragem dos padrões.)

:( +);\1\1
$1$1

Se o índice do loop for igual N/2*2, deixe apenas muitos espaços.

:((   )+);( *)
 $1$1% $3$3

Se N/2for múltiplo de 3, pegue o dobro do índice de loop mais um módulo N/2*2+1.

: ( +);( \1)?( *)
 $1 $1%$#2$* $#2$* $#2$* $1$3$3

Caso contrário, pegue o dobro do índice de loop mais (N/2-1)mais um 3 extra na metade inferior da placa, módulo N/2*2.

( +)%\1?

Realize a operação do módulo.

Neil
fonte
0

Carvão , 44 bytes

Nθ≔÷θ²ηEθ◧Q⊕⎇⁼ι⊗ηι⎇﹪η³﹪⁺⁺⊗ι⊖η׳¬‹ιη⊗η﹪⊕⊗ι⊕⊗η

Experimente online! Link é a versão detalhada do código. Outra porta da excelente resposta C do @ orlp.

Neil
fonte
0

APL (Dyalog Unicode) , SBCS de 18 bytes

Programa completo solicitando ndo stdin. Imprime a solução separada por espaço no stdout usando ·quadrados vazios e Queens.

CY'dfns'
queens

Experimente online!

⎕CY'dfns'C op y os "NDR" biblioteca

 obter informações de stdin

queens encontre todas as soluções exclusivas do Queens (sem reflexos ou rotações)

 escolha a primeira solução

Adão
fonte
0

J , 49 bytes

i.=/0({(1-.@e.,)@(([:(=#\){.|@-}.)\."1)#])!A.&i.]

Experimente online!

Força bruta testando todas as permutações de comprimento n .

milhas
fonte