Ambil semua tanda yang mungkin yang dapat ditempatkan dalam teka-teki Sudoku [ditutup]

8

Diberikan teka-teki Sudoku, temukan semua tanda yang mungkin dapat diisi ke dalam setiap sel kosong.

Kasus cobaan

Memasukkan:

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

Keluaran:

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

Visualisasi keluaran; angka kecil:

Grid Sudoku tidak lengkap dengan semua tanda yang valid

Aturan

  • Ini adalah . Jawaban terpendek dalam byte (atau setara) menang.
  • Input bisa dalam format array atau string.
  • Input harus dalam urutan yang disajikan di atas (kiri atas, atas tengah, kanan atas, dll ...)
  • Output dapat dalam format array atau string, selama output secara logis dapat mewakili hasil yang diharapkan.
  • Output harus dalam urutan yang sama dengan input (kiri atas, atas tengah, kanan atas, dll ...)
  • Output tidak perlu dipanen.
  • Kode harus berlaku untuk semua kisi Sudoku yang tidak lengkap dan valid.
  • Aturan main golf standar berlaku.

Catatan tambahan:

Anda mendapatkan poin internet palsu tambahan jika program atau fungsi Anda menggunakan hasil untuk memecahkan teka-teki Sudoku ke titik di mana nilai sel tidak lagi dapat dipecahkan secara logis. Misalnya, sel pertama dalam kasus uji hanya mungkin berisi angka 5, jadi harus dipertimbangkan ketika mengisi nilai-nilai lainnya. Ini hanya untuk bersenang-senang dan tantangan tambahan, jika tidak jawaban terpendek akan menang terlepas dari apakah kriteria ini dipenuhi atau tidak.

driima
sumber
Seberapa fleksibel format input? Mungkinkah misalnya array 9 string? (misalnya ["000340002", "740000003", ...])
Arnauld
1
Apakah string tunggal dari kiri ke kanan, atas-ke-bawah diizinkan sebagai input? Seperti ini? Dan output dalam urutan yang sama?
orlp
1
Jika kita tidak menerapkan logika untuk menentukan sel mana yang bisa dan tidak bisa dipecahkan, pertanyaan apa yang sebenarnya ingin kita lakukan?
Peter Taylor
1
Apa perbedaan yang Anda gambar antara itu dan memecahkan teka-teki?
Peter Taylor
1
Jadi dalam kondisi apa nilai yang salah dapat ditempatkan dalam sel? Berhentilah mengulangi diri Anda dan mulailah mendefinisikan istilah Anda.
Peter Taylor

Jawaban:

4

C (gcc), 193 byte

#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("");}}

Mengasumsikan input dalam format berikut (sudoku yang sama seperti di atas):

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

Dan output dalam format berikut:

5
1569
1569


1269

3569
23569


5689
etc
orlp
sumber
2

Python 2, 178 byte

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

Fungsi anonim yang mengambil larik int 3 dimensi dan mengembalikan larik int 4 dimensi.

PurkkaKoodari
sumber
2

JavaScript (ES6), 208 196 190 188 186 byte

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

Input :
Array 9 string (satu per kotak, dari kiri atas ke kanan bawah).

Output :
Array 9 array, di mana setiap item terdiri dari nomor asli di posisi ini atau array karakter yang mewakili kemungkinan digit.

Diformat dan dikomentari

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"
]));

Arnauld
sumber
1

Haskell, 135 byte

(%)=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]]

Menentukan fungsi fdari daftar 81 Ints ke daftar daftar Ints;

IO seperti jawaban orlp , kecuali ia menggunakan [0,1,2,3,4,5,6,7,8,9]alih-alih ".123456789".

dianne menyimpan beberapa byte.

Lynn
sumber
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)))))

Dibawa sebagai input array tiga baris array tiga kolom dari array sel tiga oleh tiga bilangan bulat, dan mengembalikan array lima dimensi di mana semua bilangan bulat telah diganti oleh array.

Neil
sumber