Rufe alle möglichen Markierungen ab, die in einem Sudoku-Puzzle platziert werden können [geschlossen]

8

Finden Sie bei einem Sudoku-Puzzle alle möglichen Markierungen, die in jede leere Zelle gefüllt werden können.

Testfall

Eingang:

[
    [
        // Top left:
        [
            0, 0, 0,
            3, 4, 0,
            0, 0, 2
        ],
        // Top middle:
        [
            7, 4, 0,
            0, 0, 0,
            0, 0, 3
        ],
        // Top right:
        [
            8, 0, 0,
            1, 7, 0,
            0, 0, 0
        ]
    ],
    [
        // Middle left:
        [
            9, 0, 4,
            7, 0, 0,
            1, 0, 3
        ],
        // Center:
        [
            0, 5, 0,
            0, 0, 0,
            0, 7, 0
        ],
        // Middle right:
        [
            0, 0, 0,
            6, 4, 0,
            0, 0, 0
        ]
    ],
    [
        // Bottom left:
        [
            0, 0, 7,
            6, 3, 0,
            0, 0, 0
        ],
        // Bottom middle:
        [
            0, 0, 5,
            0, 0, 0,
            9, 1, 0
        ],
        // Bottom right:
        [
            0, 0, 0,
            5, 2, 0,
            7, 0, 0
        ]
    ]
]

Ausgabe:

[
    [
        // Top left:
        [
            [5], [1, 5, 6, 9], [1, 5, 6, 9],
            [], [], [5, 6, 8, 9],
            [5, 8], [1, 5, 6, 7, 8, 9], []
        ],
        // Top middle:
        [
            [], [], [1, 2, 6, 9],
            [2, 5, 6, 8], [2, 6, 8, 9], [2, 6, 8, 9],
            [1, 5, 6, 8], [6, 8, 9], []
        ],
        // Top right:
        [
            [], [3, 5, 6, 9], [2, 3, 5, 6, 9],
            [], [], [2, 5, 6, 9],
            [4, 9], [5, 6, 9], [4, 5, 6, 9]
        ]
    ],
    [
        // Middle left:
        [
            [], [2, 6, 8], [],
            [], [2, 5, 8], [5, 8],
            [], [2, 5, 6, 8], []
        ],
        // Center:
        [
            [1, 2, 3, 6, 8], [], [1, 2, 6, 8],
            [1, 2, 3, 8], [2, 3, 8, 9], [1, 2, 8, 9],
            [2, 4, 6, 8], [], [2, 4, 6, 8, 9]
        ],
        // Middle right:
        [
            [2, 3], [1, 3, 8], [1, 2, 3, 7, 8],
            [], [], [1, 2, 3, 5, 8, 9],
            [2, 9], [5, 8, 9], [2, 5, 8, 9]
        ]
    ],
    [
        // Bottom left:
        [
            [2, 4, 8], [1, 2, 8, 9], [],
            [], [], [1, 8, 9],
            [2, 4, 5, 8], [2, 5, 8], [5, 8]
        ],
        // Bottom middle:
        [
            [2, 3, 4, 6, 8], [2, 3, 6, 8], [],
            [4, 8], [8], [4, 7, 8],
            [], [], [2, 4, 6, 8]
        ],
        // Bottom right:
        [
            [3, 4, 9], [1, 3, 6, 8, 9], [1, 3, 4, 6, 8, 9],
            [], [], [1, 4, 8, 9],
            [], [3, 6, 8], [3, 4, 6, 8]
        ]
    ]
]

Ausgabevisualisierung; die kleinen Zahlen:

Unvollständiges Sudoku-Raster mit allen gültigen Markierungen

Regeln

  • Das ist ein Code-Golf. Die kürzeste Antwort in Bytes (oder gleichwertig) gewinnt.
  • Die Eingabe kann im Array- oder String-Format erfolgen.
  • Die Eingabe muss in der oben angegebenen Reihenfolge erfolgen (oben links, oben in der Mitte, oben rechts usw.)
  • Die Ausgabe kann im Array- oder String-Format erfolgen, sofern die Ausgabe das erwartete Ergebnis logisch darstellen kann.
  • Die Ausgabe muss in derselben Reihenfolge wie die Eingabe erfolgen (oben links, oben in der Mitte, oben rechts usw.)
  • Die Ausgabe muss nicht verschönert werden.
  • Der Code muss auf jedes gültige unvollständige Sudoku-Raster anwendbar sein.
  • Es gelten die Standardregeln für das Golfen.

Zusätzliche Bemerkungen:

Sie erhalten zusätzliche gefälschte Internetpunkte, wenn Ihr Programm oder Ihre Funktion das Ergebnis verwendet, um das Sudoku-Rätsel so weit zu lösen, dass Zellwerte nicht mehr logisch gelöst werden können. Beispielsweise kann die allererste Zelle im Testfall möglicherweise nur die Nummer 5 enthalten, daher sollte dies beim Ausfüllen der anderen Werte berücksichtigt werden. Dies ist nur zum Spaß und zur zusätzlichen Herausforderung, andernfalls gewinnt die kürzeste Antwort, unabhängig davon, ob dieses Kriterium erfüllt ist oder nicht.

code-golf puzzle-solver sudoku Driima
quelle
Wie flexibel ist das Eingabeformat? Könnte es zum Beispiel ein Array von 9 Strings sein? (wie ["000340002", "740000003", ...])
Arnauld
1
Ist eine einzelne Zeichenfolge von links nach rechts und von oben nach unten als Eingabe zulässig? So was? Und in der gleichen Reihenfolge ausgeben?
Orlp
1
Wenn wir keine Logik anwenden, um herauszufinden, welche Zellen gelöst werden können und welche nicht, was ist die Frage, die uns eigentlich stellt?
Peter Taylor
1
Was ist der Unterschied zwischen dem und dem Lösen des Puzzles?
Peter Taylor
1
Unter welchen Umständen kann ein falscher Wert in eine Zelle eingefügt werden? Hören Sie auf, sich zu wiederholen, und definieren Sie Ihre Begriffe.
Peter Taylor

Antworten:

4

C (gcc), 193 Bytes

#define F(x)for(x=0;x<9;++x)
char s[99];main(k,r,c){gets(s);F(r)F(c){
int d[99]={};F(k)d[s[r*9+k]]=d[s[k*9+c]]=d[s[r/3*27+k/3*9+c/3*3+k%3]]=1;
F(k)s[r*9+c]<48&&!d[49+k]&&putchar(49+k);puts("");}}

Nimmt die Eingabe im folgenden Format an (dasselbe Sudoku wie oben):

..74.8..34....17...2..3...9.4.5....7.....64.1.3.7......7..5...63....52....91.7..

Und Ausgaben im folgenden Format:

5
1569
1569


1269

3569
23569


5689
etc
orlp
quelle
2

Python 2, 178 Bytes

lambda s,R=range(9):[[[(s[Y][X][i]<1)*[q+1for q in R if~-(q+1in sum([[s[j/3][X][j%3*3+i%3],s[Y][j/3][j%3+i/3*3]]for j in R],[])+s[Y][X])]for i in R]for X in R[:3]]for Y in R[:3]]

Eine anonyme Funktion, die ein dreidimensionales Array von Ints verwendet und ein vierdimensionales Array von Ints zurückgibt.

PurkkaKoodari
quelle
2

JavaScript (ES6), 208 196 190 188 186 Bytes

g=>g.map((B,i)=>[...B].map((s,x)=>+s||[..."123456789"].filter(n=>(t=i=>(k=g[i].search(n)%m)<a|k>b)(j=i%3,m=3,a=b=x%3)&t(j+3)&t(j+6)&t(j=i-j,m=9,a=x-a,b=a+2)&t(j+1)&t(j+2)&t(i,a=0,b=8))))

Eingabe :
Ein Array von 9 Zeichenfolgen (eine pro Box, von links oben nach rechts unten).

Ausgabe :
Ein Array von 9 Arrays, wobei jedes Element entweder aus der ursprünglichen Nummer an dieser Position oder aus einem Array von Zeichen besteht, die die möglichen Ziffern darstellen.

Formatiert und kommentiert

g => g.map((B, i) =>              // for each box B at position i in the grid:
  [...B].map((s, x) =>            // for each cell s at position x in this box:
    +s ||                         // if there already is a number at this position, use it
    [..."123456789"].filter(n =>  // else, for each digit n in [1 .. 9]:
      (t = i =>                   // t() = helper function that looks for the digit n inside
        (k = g[i].search(n) % m)  // a given box i and returns a truthy value if its
        < a | k > b               // position modulo m is not in the range [a .. b]
      )(                          //
        j = i % 3,                // test the top box in the current column, using:
        m = 3,                    // modulo = 3 and
        a = b = x % 3             // range = [x % 3 .. x % 3]
      ) &                         //
      t(j + 3) &                  // test the middle box in the current column
      t(j + 6) &                  // test the bottom box in the current column
      t(                          //
        j = i - j,                // test the left box in the current row, using:
        m = 9,                    // modulo = 9 and
        a = x - a, b = a + 2      // range = [floor(x / 3) .. floor(x / 3) + 2]
      ) &                         //
      t(j + 1) &                  // test the middle box in the current row
      t(j + 2) &                  // test the right box in the current row
      t(i, a = 0, b = 8)          // finally test the current box, using:
    )                             // modulo = 9 (unchanged) and
  )                               // range = [0 .. 8] (thus testing the entire box)
)                                 //

Demo

let f =

g=>g.map((B,i)=>[...B].map((s,x)=>+s||[..."123456789"].filter(n=>(t=i=>(k=g[i].search(n)%m)<a|k>b)(j=i%3,m=3,a=b=x%3)&t(j+3)&t(j+6)&t(j=i-j,m=9,a=x-a,b=a+2)&t(j+1)&t(j+2)&t(i,a=0,b=8))))

console.log(f([
  "000340002",
  "740000003",
  "800170000",
  "904700103",
  "050000070",
  "000640000",
  "007630000",
  "005000910",
  "000520700"
]));
Erweitern Sie das Snippet

Arnauld
quelle
1

Haskell, 135 Bytes

(%)=mod
x!y=x-x%y
f a=[[j|j<-[1..9],and[a!!k/=j|k<-[i!3-i!9%27+p%3+p!3*3|p<-[0..8]]++[i!9..i!9+8]++[i%9,i%9+9..80]],a!!i<1]|i<-[0..80]]

Definiert eine Funktion fvon Listen von 81 Ints bis zu Listen von Listen von Ints;

IO ist wie die Antwort von orlp , außer dass es [0,1,2,3,4,5,6,7,8,9]anstelle von verwendet wird ".123456789".

Dianne hat ein paar Bytes gespeichert.

Lynn
quelle
1

JavaScript (ES6), 185 Byte

a=>a.map((b,r)=>b.map((d,c)=>d.map((e,i)=>e.map((g,j)=>[1,2,3,4,5,6,7,8,9].filter(v=>a.every(b=>b[c].every(e=>e[j]-v))&b.every(d=>d[i].every(g=>g-v))&d.every(e=>e.every(g=>g-v))&!g)))))

Nimmt als Eingabe ein Array von drei Zeilen eines Arrays von drei Spalten eines drei mal drei Arrays von Zellen von Ganzzahlen und gibt ein fünfdimensionales Array zurück, in dem alle Ganzzahlen durch Arrays ersetzt wurden.

Neil
quelle