Ist Magie möglich?

Ein magisches Quadrat ist ein n-mal-n- Quadratgitter, das mit eindeutigen positiven Ganzzahlen im Bereich von 1,2, ... n ^ 2 gefüllt ist , sodass jede Zelle eine andere Ganzzahl und die Summe der Ganzzahlen in jeder Zeile enthält. Spalte und Diagonale ist gleich.

Ihre Aufgabe ist es, eine n-mal-n- Matrix bestehend aus positiven Zahlen und einem Platzhalterzeichen für leere Zellen zu nehmen (ich verwende 0 , aber Sie können jedes beliebige nicht-numerische Zeichen oder jeden beliebigen Datentyp verwenden) und zu bestimmen, ob dies der Fall ist Es ist möglich, ein magisches Quadrat zu bilden, indem die fehlenden Zahlen eingegeben werden

Die Matrix wird mindestens 2 mal 2 und höchstens 10 mal 10 sein . Das kleinstmögliche nicht-triviale magische Quadrat ist 3-mal-3 . Die Zahlen in der Eingabematrix sind möglicherweise höher als n ^ 2 und es ist möglich, dass alle Zellen gefüllt sind.

Testfälle:

2   2
2   0
False

8   0   6
0   5   0
0   9   2
True

16    2    3   13
 5   11   10    8
 9    7    6   12
 4   14   15    1
True

10   0   1
 0   5   9
 3   7   5
False

99    40    74     8    15    51     0    67     0     1
 0    41    55    14     0    57    64     0    98     0
81    47    56    20    22    63    70    54     0    88
 0    28     0    21     0    69    71    60    85    19
 0    34     0     2     9    75    52    61     0    25
24    65    49     0    90    26    33    42    17    76
 0     0    30    89    91     0    39    48     0    82
 6    72    31    95     0    38    45    29     0    13
12    53     0    96    78     0     0     0    10    94
18    59    43    77     0     0    27    36     0   100
True

code-golf math number decision-problem matrix Stewie Griffin
quelle

Hmm. Ich glaube, ich habe irgendwo eine Lösung gesehen.

Matthew Roh

Vorgeschlagener Testfall, um sicherzustellen, dass die Diagonalen korrekt getestet werden: [ [ 1, 5, 9 ], [ 6, 7, 2 ], [ 8, 3, 4 ] ](falsch)

Arnauld

Können wir die Platzhalter nummerieren [[8, X1, 6], [X2, 5, X3], [X4, 9, 2]]?

Scott Milner

@ Scott sicher, fühlen Sie sich frei ...

Stewie Griffin

Antworten:

JavaScript (ES6), 270 bis 268 Byte

Nimmt die Matrix als 2D-Array. Rückgabe 0oder 1.

a=>(g=(x,y=0,w=a.length,p,R=a[y])=>[0,1,2,3].some(d=>a.some((r,y)=>(p=s)^(s=r.reduce((p,v,x)=>(o|=1<<(v=[v,(b=a[x])[y],b[x++],b[w-x]][d]),p+v),0))&&p),s=o=0)||o/2+1!=1<<w*w?R&&[...Array(w*w)].map((_,n)=>(p=R[x])==++n|!p&&(R[x]=n,g(z=(x+1)%w,y+!z),R[x]=p)):r=1)(r=0)&&r

Testfälle

Dies ist definitiv zu langsam für den letzten Testfall. :-(

Code-Snippet anzeigen

let f =

a=>(g=(x,y=0,w=a.length,p,R=a[y])=>[0,1,2,3].some(d=>a.some((r,y)=>(p=s)^(s=r.reduce((p,v,x)=>(o|=1<<(v=[v,(b=a[x])[y],b[x++],b[w-x]][d]),p+v),0))&&p),s=o=0)||o/2+1!=1<<w*w?R&&[...Array(w*w)].map((_,n)=>(p=R[x])==++n|!p&&(R[x]=n,g(z=(x+1)%w,y+!z),R[x]=p)):r=1)(r=0)&&r

console.log(f([
  [ 2,  2 ],
  [ 2,  0 ]
]));

console.log(f([
  [ 8,  0,  6 ],
  [ 0,  5,  0 ],
  [ 0,  9,  2 ]
]));

console.log(f([
  [ 16,   2,   3,  13 ],
  [  5,  11,  10,   8 ],
  [  9,   7,   6,  12 ],
  [  4,  14,  15,   1 ]
]));

console.log(f([
  [ 10,  0,  1 ],
  [  0,  5,  9 ],
  [  3,  7,  5 ]
]));

Erweitern Sie das Snippet

Arnauld
quelle

05AB1E , 45 Bytes

Zsgn©>‹®L¹˜Kœ0ªε\¹˜0y.;¹gô©O®øO®Å\O®Å/O)˜Ë}à*

$0$ $0$ $n^2$ $0$ $0$

Hätte 4 Bytes weniger sein können, aber es gibt derzeit einen Fehler im Builtin .;mit 2D-Listen. :und .:arbeite wie erwartet, aber .;mache im Moment nichts an 2D-Listen. Daher die Umgehung ˜und ¹gôVerflachung der Matrix; Verwendung .;auf der Liste; und wieder in eine Matrix zurückverwandeln.

Probieren Sie es online aus oder überprüfen Sie einige weitere Testfälle . (HINWEIS: Der letzte Testfall der Herausforderungsbeschreibung ist nicht enthalten, da er viel zu viele Nullen hat.)

Erläuterung:

Z               # Get the maximum of the (implicit) input-matrix (implicitly flattened)
                # (and without popping the matrix)
                #  i.e. [[8,0,6],[0,5,0],[0,0,2]] → 8
 s              # Swap to get the input-matrix again
  g             # Get its length (amount of rows)
                #  i.e. [[8,0,6],[0,5,0],[0,0,2]] → 3
   n            # Square it
                #  i.e. 3 → 9
    ©           # Store it in the register (without popping)
     >‹         # Check if the maximum is <= this squared matrix-dimension
                #  i.e. 8 <= 9 → 1 (truthy)
®               # Push the squared matrix-dimension again
 L              # Create a list in the range [1, squared_matrix_dimension]
                #  i.e. 9 → [1,2,3,4,5,6,7,8,9]
  ¹             # Push the input-matrix
   ˜            # Flatten it
                #  i.e. [[8,0,6],[0,5,0],[0,0,2]] → [8,0,6,0,5,0,0,0,2]
    K           # Remove all these numbers from the ranged list
                #  i.e. [1,2,3,4,5,6,7,8,9] and [8,0,6,0,5,0,0,0,2] → [1,3,4,7,9]
œ               # Get all possible permutations of the remaining numbers
                # (this part is the main bottleneck of the program;
                #  the more 0s and too high numbers, the more permutations)
                #   i.e. [1,3,4,7,9] → [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1]]
 0ª             # Add an item 0 to the list (workaround for inputs without any 0s)
                #  i.e. [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1]] 
                #   → [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1],"0"] 
   ε            # Map each permutation `y` to:
    \           #  Remove the implicit `y` which we don't need yet
    ¹˜          #  Push the flattened input again
      0         #  Push a 0
       y        #  Push permutation `y`
        .;      #  Replace all 0s with the numbers in the permutation one by one
                #   i.e. [8,0,6,0,5,0,0,0,2] and [1,3,4,7,9]
                #    → [8,1,6,3,5,4,7,9,2]
          ¹g    #  Push the input-dimension again
            ô   #  And split the flattened list into parts of that size,
                #  basically transforming it back into a matrix
                #   i.e. [8,1,6,3,5,4,7,9,2] and 3 → [[8,1,6],[3,5,4],[7,9,2]]
             ©  #  Save the matrix with all 0s filled in in the register (without popping)
    O           #  Take the sum of each row
                #   i.e. [[8,1,6],[3,5,4],[7,9,2]] → [15,12,18]
    ®øO         #  Take the sum of each column
                #   i.e. [[8,1,6],[3,5,4],[7,9,2]] → [18,15,12]
    ®Å\O        #  Take the sum of the top-left to bottom-right main diagonal
                #   i.e. [[8,1,6],[3,5,4],[7,9,2]] → 15
    ®Å/O        #  Take the sum of the top-right to bottom-left main diagonal
                #   i.e. [[8,1,6],[3,5,4],[7,9,2]] → 18
    )           #  Wrap everything on the stack into a list
                #   → [[15,12,18],[18,15,12],15,18]
     ˜          #  Flatten it
                #   i.e. [[15,12,18],[18,15,12],15,18] → [15,12,18,18,15,12,15,18]
      Ë         #  Check if all values are equal
                #   i.e. [15,12,18,18,15,12,15,18] → 0 (falsey)
}               # After the map:
                #  → [0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
 à              # Check if any are truthy by taking the maximum
                #  → 1 (truthy)
  *             # And multiply the two checks to verify both are truthy
                #  i.e. 1 and 1 → 1 (truthy)
                # (and output the result implicitly)

Der Teil ©O®øO®Å\O®Å/O)˜Ëwird auch in meiner 05AB1E-Antwort für die Challenge Verify Magic Square verwendet. In dieser Antwort finden Sie eine ausführlichere Erläuterung zu diesem Teil des Codes.

Kevin Cruijssen
quelle