Tâche

Étant donné l'entrée N, générez et sortez une grille NxN où chaque ligne, colonne et les deux diagonales contiennent les nombres 1 à N(ou 0 à N-1 si c'est plus facile).

Contribution

L'entrée est un entier positif N. Il représente le nombre de colonnes et de lignes dans la grille. Pour ce problème, vous pouvez supposer Nque la taille sera raisonnable 4 ≤ N ≤ 8ou ( 1 ≤ N ≤ 8si vous optez pour le bonus ci-dessous).

Sortie

La sortie sera la grille N× N. Dans la grille, chaque ligne ne contient que les chiffres 1 à N, chaque colonne ne contient que les chiffres 1 à Net les deux diagonales de longueur N(celle de (0,0)à (N-1,N-1)et celle de (0,N-1)à (N-1, 0)) ne contiennent que les chiffres de 1 à N. Vous pouvez utiliser les chiffres de 0 à N−1. Pour chacune N, il existe de nombreuses solutions possibles, il vous suffit d'imprimer la première que vous trouvez. Vous n'avez pas besoin d'imprimer des espaces entre les chiffres.

Contraintes

Votre code devrait pouvoir produire des résultats de manière répétée pour N >= 7. Autrement dit, si vous êtes en mesure d'exécuter et d'obtenir une solution à N = 7partir de votre code à chaque fois, vous êtes bon. En termes de limite absolue, votre code devrait être en mesure de résoudre N = 7en moins de 10 minutes chaque fois que vous l'exécutez (c'est-à-dire, si vous dépendez de nombres aléatoires, dans le pire des cas, votre code devrait toujours se terminer en moins de 10 minutes N = 7) .

Exemples

• Contribution: 4

  Une sortie possible:

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

• Contribution: 5

  Une sortie possible:

  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
  

• Contribution: 8

  Une sortie possible:

  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
  

Notation

Il s'agit de code-golf , donc le code le plus court en octets l'emporte, à une exception près. Pour les entrées, N = 2, 3il n'y a pas de solutions valides. Si votre code peut gérer cela (exécuter jusqu'à la fin sans sortir quoi que ce soit pour ces cas, ou sortir une chaîne vide), et gère toujours N = 1(les sorties 1pour cela), prenez 20% sur votre nombre d'octets.

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

Approche récursive / retour en arrière. Rest la fonction récursive, lest le coLumn, west le roW, Kest l'entrée suivante.

J'ai choisi de le mettre dans un tableau 1d et de l'imprimer à la fin pour simplifier les indices.

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)

Version non golfée:

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 , non compétitif

MISE À JOUR! Amélioration massive des performances! n = 7 se termine maintenant en moins de 10 minutes! Voir explication en bas!

C'était très amusant à écrire. Il s'agit d'un solveur de force brute pour ce problème écrit en Funciton. Quelques factoids:

• Il accepte un entier sur STDIN. Tout espace blanc superflu le casse, y compris un saut de ligne après l'entier.
• Il utilise les nombres 0 à n - 1 (pas 1 à n ).
• Il remplit la grille « en arrière », de sorte que vous obtenez une solution où la rangée du bas lit 3 2 1 0plutôt que là où la ligne de haut lit 0 1 2 3.
• Il affiche correctement 0(la seule solution) pour n = 1.
• Sortie vide pour n = 2 et n = 3.
• Une fois compilé en un exe, cela prend environ 8¼ minutes pour n = 7 (c'était environ une heure avant l'amélioration des performances). Sans compilation (en utilisant l'interpréteur), cela prend environ 1,5 fois plus de temps, donc l'utilisation du compilateur en vaut la peine.
• En tant que jalon personnel, c'est la première fois que j'écris un programme Funciton complet sans d'abord l'écrire dans un langage pseudocode. Je l'ai d'abord écrit en C #.
• (Cependant, ce n'est pas la première fois que j'effectue un changement pour améliorer massivement les performances de quelque chose dans Funciton. La première fois que je l'ai fait, c'était dans la fonction factorielle. L'échange de l'ordre des opérandes de la multiplication a fait une énorme différence à cause de comment l'algorithme de multiplication fonctionne . Au cas où vous seriez curieux.)

Sans plus tarder:

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

Explication de la première version

La première version a pris environ une heure pour résoudre n = 7. Ce qui suit explique principalement comment cette version lente fonctionnait. En bas, j'expliquerai quel changement j'ai fait pour le réduire à moins de 10 minutes.

Une excursion en morceaux

Ce programme a besoin de bits. Il a besoin de beaucoup de bits et il en a besoin aux bons endroits. Les programmeurs Funciton expérimentés savent déjà que si vous avez besoin de n bits, vous pouvez utiliser la formule

qui dans Funciton peut être exprimé comme

Lors de l'optimisation des performances, il m'est venu à l'esprit que je peux calculer la même valeur beaucoup plus rapidement en utilisant cette formule:

J'espère que vous me pardonnerez que je n'ai pas mis à jour tous les graphiques d'équation dans ce post en conséquence.

Maintenant, disons que vous ne voulez pas d'un bloc de bits contigu; en fait, vous voulez n bits à intervalles réguliers chaque k -ième bit, comme ceci:

                                 LSB
                                  ↓
00000010000001000000100000010000001
                            └──┬──┘
                               k

La formule pour cela est assez simple une fois que vous le savez:

Dans le code, la fonction Ӝprend les valeurs n et k et calcule cette formule.

Garder une trace des numéros utilisés

Il y a n ² nombres dans la grille finale, et chaque nombre peut être n'importe laquelle des n valeurs possibles. Afin de garder une trace des nombres autorisés dans chaque cellule, nous conservons un nombre composé de n ³ bits, dans lequel un bit est défini pour indiquer qu'une valeur particulière est prise. Initialement, ce nombre est 0, évidemment.

L'algorithme commence dans le coin inférieur droit. Après avoir «deviné» que le premier nombre est un 0, nous devons garder une trace du fait que le 0 n'est plus autorisé dans aucune cellule de la même ligne, colonne et diagonale:

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

À cette fin, nous calculons les quatre valeurs suivantes:

• Ligne actuelle: nous avons besoin de n bits tous les n -ièmes bits (un par cellule), puis de la déplacer vers la ligne actuelle r , en se souvenant que chaque ligne contient n ² bits:

  

• Colonne actuelle: nous avons besoin de n bits tous les n ²-ème bits (un par ligne), puis de la déplacer vers la colonne actuelle c , en se souvenant que chaque colonne contient n bits:

  

• Diagonale avant: Nous avons besoin de n bits tous les ... (avez-vous fait attention? Vite, comprenez-le!) ... n ( n +1) -ème bit (bien joué!), Mais seulement si nous sommes réellement sur la diagonale avant:

  

• Diagonale arrière: Deux choses ici. Tout d'abord, comment savoir si nous sommes sur la diagonale arrière? Mathématiquement, la condition est c = ( n - 1) - r , qui est la même que c = n + (- r - 1). Hé, ça te rappelle quelque chose? C'est vrai, c'est le complément à deux, nous pouvons donc utiliser la négation au niveau du bit (très efficace dans Funciton) au lieu de la décrémentation. Deuxièmement, la formule ci-dessus suppose que nous voulons que le bit le moins significatif soit défini, mais dans la diagonale arrière, nous ne le faisons pas, nous devons donc le décaler vers le haut de ... savez-vous? ... C'est vrai, n ( n - 1).

  

  C'est aussi le seul où nous divisons potentiellement par 0 si n = 1. Cependant, Funciton s'en fiche. 0 ÷ 0 est juste 0, tu ne sais pas?

Dans le code, la fonction Җ(celle du bas) prend n et un indice (à partir duquel elle calcule r et c par division et reste), calcule ces quatre valeurs et les ors ensemble.

L'algorithme de force brute

L'algorithme de force brute est implémenté par Ӂ(la fonction en haut). Cela prend n (la taille de la grille), l' index (où dans la grille nous plaçons actuellement un nombre), et pris (le nombre avec n ³ bits nous indiquant quels nombres nous pouvons encore placer dans chaque cellule).

Cette fonction renvoie une séquence de chaînes. Chaque chaîne est une solution complète à la grille. C'est un solveur complet; il retournerait toutes les solutions si vous le permettez, mais il les renvoie comme une séquence évaluée paresseusement.

• Si l' index a atteint 0, nous avons réussi à remplir toute la grille, nous retournons donc une séquence contenant la chaîne vide (une solution unique qui ne couvre aucune des cellules). La chaîne vide est 0, et nous utilisons la fonction de bibliothèque ⌑pour la transformer en une séquence à un seul élément.

• La vérification décrite sous l' amélioration des performances ci-dessous se produit ici.

• Si l' index n'a pas encore atteint 0, nous le décrémentons de 1 pour obtenir l'index auquel nous devons maintenant placer un nombre (appelons cela ix ).

  Nous utilisons ♫pour générer une séquence paresseuse contenant les valeurs de 0 à n - 1.

  Ensuite, nous utilisons ɓ(liaison monadique) avec un lambda qui effectue les opérations suivantes dans l'ordre:

  • Examinez d'abord le bit pertinent pris pour décider si le numéro est valide ici ou non. On peut placer un nombre i si et seulement s'il est pris & (1 << ( n × ix ) << i ) n'est pas déjà défini. S'il est défini, retournez 0(séquence vide).
  • Utilisez Җpour calculer les bits correspondant à la ligne, la colonne et la ou les diagonales actuelles. Déplacez-le par i puis orsur prise .
  • Appel récursivement Ӂpour récupérer toutes les solutions pour les cellules restantes, en lui passant la nouvelle prise et la ix décrémentée . Cela renvoie une séquence de chaînes incomplètes; chaque chaîne a ix caractères (la grille remplie jusqu'à l'index ix ).
  • Utilisez ɱ(map) pour parcourir les solutions ainsi trouvées et utilisez ‼pour concaténer i à la fin de chacune. Ajoutez une nouvelle ligne si l' index est un multiple de n , sinon un espace.

Générer le résultat

Le programme principal appelle Ӂ(le forceur brut) avec n , index = n ² (rappelez-vous que nous remplissons la grille à l'envers) et pris = 0 (initialement rien n'est pris). Si le résultat est une séquence vide (aucune solution trouvée), sortez la chaîne vide. Sinon, sortez la première chaîne de la séquence. Notez que cela signifie qu'il n'évaluera que le premier élément de la séquence, c'est pourquoi le solveur ne continue pas tant qu'il n'a pas trouvé toutes les solutions.

Amélioration des performances

(Pour ceux qui ont déjà lu l'ancienne version de l'explication: le programme ne génère plus une séquence de séquences qui doit être séparément transformée en chaîne pour la sortie; il génère simplement une séquence de chaînes directement. J'ai édité l'explication en conséquence Mais ce n'était pas la principale amélioration. Ça y est.)

Sur ma machine, l'exe compilé de la première version a pris à peu près exactement 1 heure pour résoudre n = 7. Ce n'était pas dans le délai imparti de 10 minutes, donc je ne me suis pas reposé. (Eh bien, en fait, je ne me suis pas reposé parce que j'avais cette idée sur la façon d'accélérer massivement.)

L'algorithme tel que décrit ci-dessus arrête sa recherche et revient en arrière chaque fois qu'il rencontre une cellule dans laquelle tous les bits du nombre pris sont définis, indiquant que rien ne peut être mis dans cette cellule.

Cependant, l'algorithme continuera à remplir vainement la grille jusqu'à la cellule dans laquelle tous ces bits sont définis. Il serait beaucoup plus rapide si elle pouvait arrêter dès que toute cellule en encore à être rempli a déjà tous les bits mis, ce qui indique déjà que nous ne pouvons jamais résoudre le reste de la grille , peu importe ce que les numéros que nous mettons dans il. Mais comment vérifier efficacement si une cellule a ses n bits définis sans les parcourir tous?

L'astuce commence par l'ajout d'un seul bit par cellule au nombre pris . Au lieu de ce qui a été montré ci-dessus, cela ressemble maintenant à ceci:

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

Au lieu de n ³, il y a maintenant n ² ( n + 1) bits dans ce nombre. La fonction qui remplit la ligne / colonne / diagonale actuelle a été modifiée en conséquence (en fait, complètement réécrite pour être honnête). Cependant, cette fonction ne remplira que n bits par cellule, donc le bit supplémentaire que nous venons d'ajouter sera toujours 0.

Maintenant, disons que nous sommes à mi-chemin du calcul, nous venons de placer un 1dans la cellule du milieu, et le nombre pris ressemble à ceci:

                 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

Comme vous pouvez le voir, la cellule en haut à gauche (index 0) et la cellule au milieu à gauche (index 10) sont désormais impossibles. Comment pouvons-nous le déterminer le plus efficacement possible?

Considérez un nombre dans lequel le 0e bit de chaque cellule est défini, mais uniquement jusqu'à l'index actuel. Un tel nombre est facile à calculer en utilisant la formule familière:

Qu'obtiendrions-nous si nous additionnions ces deux chiffres ensemble?

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

Le résultat est:

             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

Comme vous pouvez le voir, l'addition déborde dans le bit supplémentaire que nous avons ajouté, mais seulement si tous les bits de cette cellule sont définis! Par conséquent, tout ce qui reste à faire est de masquer ces bits (même formule que ci-dessus, mais << n ) et de vérifier si le résultat est 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

S'il n'est pas nul, la grille est impossible et nous pouvons nous arrêter.

• Capture d'écran montrant la solution et le temps d'exécution pour n = 4 à 7.

Haskell, 790 * 0,80 = 632 octets

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

J'ai remarqué que ce problème est très similaire à sudoku. Je me souviens d'un ancien solveur sudoku que j'ai écrit dans Haskell basé sur cet autre en Python. Ceci est mon premier message ou tentative de golf à code.

Cela remplit le bonus car il revient Nothingpour n=2,3et Just <result>pour n>=4, où <result>est un tableau 2D de valeurs intégrales.

Voir ici pour l'interprète en ligne. Ce code est en fait plus long que celui de la publication car l'interprète en ligne a des exigences plus strictes quant à ce qui constitue un programme complet (les règles disent qu'une soumission peut être une fonction). Cette soumission prend l'entrée comme argument de fonction.

Pyth, 41 octets

#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

Force brute ftw!

Étant donné que cela continue essentiellement d'essayer des shuffles aléatoires jusqu'à ce qu'il fonctionne (enfin, il continue d'essayer n * [shuffle(range(n))]), cela prend vraiment très très longtemps. Voici quelques essais pour vous donner une idée du temps que cela prend:

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

Ce n'est que du 4x4 et il fonctionne en un peu moins d'une demi-seconde. En fait, je triche parce que c'est le meilleur de quelques essais - la plupart prennent plus d'une seconde ou deux.

Je n'ai pas encore de chronométrage sur 5x5 (il s'est terminé une fois, mais c'était dans un REPL et je ne le chronométrais pas).

Notez que la règle du délai n'a été modifiée dans la question qu'après la publication de cette réponse.

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

:-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: économisé 16 octets grâce à @Mat

Usage

Appelez a(5).votre interprète pour N=5. Cela revient falsepour N=2ou N=3.

Puisqu'il utilise la bibliothèque CLPFD, ce n'est pas de la pure bruteforce. Ce programme peut trouver une solution pendant N=20environ 15 secondes sur mon ordinateur.

Non golfé + explications:

Cela fonctionne essentiellement comme un solveur Sudoku, sauf que les contraintes de blocs sont remplacées par les contraintes de diagonales.

:-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 octets - 20% de bonus = 69,6 octets

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

Codez en dur les réponses. Contient certains non imprimables. Fonctionne pour à N = 1travers N = 8.

Fondamentalement, chaque ligne de cette mystérieuse chaîne contient des indices dans la liste des permutations de range(N), codés en caractères Unicode.

=:i0+\,m!f=indexe dans la liste des permutations, en ajoutant d'abord un 0 à la fin de la liste des index, représentant la ligne du bas 0 1 2 ... N-1. Pour N < 4, le tableau 2D résultant est un non-sens.

`1LL]crée une liste [N, pretty output, 1, "", ""]. Ensuite, (4e<=sort le premier élément de cette liste Net récupère le min(N, 4) % 4th élément du reste. Pour N >= 4, c'est la sortie, et sinon ce sont les sorties de cas spécial pour les trois premiers cas.

Essayez-le ici .

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

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

Essayez-le en ligne ici

Étant donné que quelques réponses ont déjà été publiées, j'ai pensé publier la version golf du code que j'ai utilisé pour générer la sortie des exemples. C'est la première fois que je réponds à un code-golf , donc tous les commentaires sont les bienvenus. :)

Non golfé + explications:

Essentiellement, le code force brutalement une solution. Il commence dans la première rangée, avec 0. Il commence dans la première tache, si ces taches passent tous les contrôles, il passe au numéro suivant. S'il remplit la ligne, il passe à la ligne suivante. Si c'est fait toutes les lignes, cela signifie qu'une solution a été trouvée. Si le spot ne passe pas tous les contrôles, il passe au spot suivant. Si c'est fait la ligne, alors il revient en arrière, car un nombre dans l'une des lignes précédentes empêche une solution d'être possible.

#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

Divisé en deux parties: le comptage des erreurs Set une fonction anonyme qui fait l'optimisation réelle via la recherche Tabu .

Mise à jour: plus courte S(compte des valeurs distinctes au sein des groupes), état de départ moins optimal (pas de mélange).

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

Les benchmarks monocœurs (en millisecondes) pour 4, 5, 6 et 7 s'exécutent 3 fois:

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

Je souhaite que ce Ssoit plus court, mais comme il ne compte que les occurrences de plus d'une partition, le critère d'arrêt est simple (= s 0).

De nombreux cycles CPU sont gaspillés pour des échanges non utiles, par exemple, cela n'améliore pas le score si vous échangez 2avec 2, et vous n'avez pas besoin d'échanger des nombres entre les lignes car ils ont tous des valeurs distinctes pour commencer.

Benchmarks avec Intel 6700K (en millisecondes):

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