Pencari Sudoku Unik

19

Tantangan:

Diberikan papan Sudoku pada input standar, temukan jumlah minimum angka yang ditambahkan untuk membuat papan tersebut unik.

Spesifikasi / Aturan:

  • Input diformat sebagai berikut (semua spasi putih signifikan)

    516|827|943
    278|394|615
    349|615|872
    ---+---+---
    98 |4 2|156
    465|189|237
    12 |5 6|489
    ---+---+---
    892|743|561
    634|951|728
    751|268|394
    
  • Output diformat dengan satu angka per baris, diformat seperti (x,y):z- x dan y mulai dari satu di kiri atas dan naik turun dan kanan; z adalah nomor yang akan ditambahkan.

    • Dalam hal ini semua ini akan menjadi output yang valid: (3,4):3, (3,4):7, (5,4):3, (5,4):7, (3,6):3, (3,6):7, (5,6):3, dan (5,6):7, sebagai salah satu dari ini akan memungkinkan papan untuk dipecahkan.
  • Jika papan Sudoku unik / terpecahkan dimasukkan, program tidak boleh mencetak apa pun, bahkan baris baru.
  • Program harus berjalan dalam waktu kurang dari satu jam untuk papan apa pun (saya sarankan pengujian menggunakan papan yang sepenuhnya kosong, atau papan dengan satu nomor acak di atasnya ...).

Mencetak:

  • Ambil ukuran kode total (golf) Anda dalam karakter, termasuk semua spasi putih ...

Bonus:

1/2 ukuran kode : Jika program mencetak satu tanda seru dan berhenti setelah papan tanpa solusi dimasukkan.

1/2 ukuran kode : Jika program mencetak dua tanda seru dan berhenti setelah papan dengan kontradiksi internal dimasukkan (dua angka sama pada baris / kolom / kotak yang sama).

Root Infinity
sumber
3
Membosankan dan mungkin sulit :(
Oleh Prypin
6
Boo. 'Tidak mencetak apa pun, bahkan bukan baris baru' mengesampingkan GolfScript.
Peter Taylor
1
seorang pemecah sudoku yang tidak pernah perlu mundur / menebak untuk solusi lengkap diperlukan untuk ini, (dan setiap kali "tebakan" diperlukan, output)
ratchet freak
3
Saya tidak melihat alasan untuk membatalkan ini. Banyak upaya dilakukan untuk menunjukkan puzzle yang cantik; sangat jelas, dan dinyatakan dengan benar. Ini terlalu besar untuk seleraku, tetapi itu terlalu subjektif untuk alasan untuk menurunkan suara, bukan?
pengguna tidak diketahui

Jawaban:

10

Brachylog , 245 byte / 2 = 122,5

@n:1a:"-"x:7fF:3a$\:3a@3:4a,Fc~bCh[0:0:0]gO,Co~c[V:O:T]h:F:6f:10ao:ba(h:11a;!);"!!"w!
h"-".|:"|"x:2f.
e(~m["0123456789":.]`;0<.<=9)
:ha#d.
:@3az:ca:5a.
:3a.
hs.:=a,?t:9ac:=fl1
:Im:8f:[[I]]z:ca.
:Jm:J.
:ha.
lg:?c.
b:+a[X:Y],?h:Y:Xr:"(~d,~d):~d
"w

(Perhatikan bahwa Anda harus menggunakan versi bahasa pada komit ini . Kode ini akan membutuhkan sedikit perubahan agar dapat berfungsi dengan baik di versi Brachylog berikut)

Ini mencetak "!!"jika papan yang diberikan memiliki kontradiksi internal (ini membutuhkan beberapa detik dalam kasus itu pada TIO, jadi bersabarlah).

Saya tidak yakin saya mengerti bonus pertama dengan benar sehingga saya tidak mengatasinya.

Ini jelas non-bersaing karena bahasanya jauh lebih baru daripada tantangan, namun karena tidak ada jawaban lain saya tidak yakin ini sangat berarti ...

Penjelasan

  • Predikat utama:

    @n                Split the input on line breaks
    :1a:"-"x          Transform into a list of lists, each sublist contains a line's values
    :7fF              Transform so that cells are [Value:X:Y]
    :3a               All values on lines must be different
    $\:3a             All values on columns must be different (by transposition)
    @3:4a,            All 3*3 block values must be different
    Fc~bCh[0:0:0]gO,  Append a fake cell [0:0:0]
    Co~c[V:O:T]       Sort the board, the blank cells V will be those before O ([0:0:0])
    h:F:6f            Find all subsets of blank cells with specific values for which 
                          the board has only one solution
    :10ao             Sort the subsets by lengths
    :ba               Discard the lengths
    (                 
      h:11a             Print the first subset = an answer
    ;                 Or (board is already fully determined)
      !                 Terminate
    )          
    ;                 Or (Some values don't respect the constraints)
    "!!"w!            Print "!!" and terminate
    
  • Predikat 1: Hapus semua " |" pada garis, ubah ---+---+---menjadi -untuk menghapusnya setelah

    h"-".    If the first char is "-", then Output is "-"
    |        Or
    :"|"x    Remove all occurences of "|" from the input
    :2f.     Output is the result of all outputs of predicate 2 on the filtered string
    
  • Predikat 2: Konversi satu karakter menjadi bilangan bulat, atau jika kosong ke variabel antara 1 dan 9.

    e                      Take a char of the input string
    (
      ~m["0123456789":.]     Output is the index of the char in "0123456789"
      `                      Discard the choice point caused by the ;
    ;                      Or
      0<.<=9                 Output is an integer between 1 and 9
    )
    
  • Predikat 3: Tetapkan bahwa semua nilai daftar input sel harus berbeda

    :ha    Retrieve the head of each cell (i.e. the value) in the input 
    #d.    Apply a constraint of distinctness to those values
    
  • Predikat 4: Menerapkan batasan perbedaan pada nilai dalam 3 * 3 blok

    :@3a            Split 3 lines of the board in 3 parts
        z           Zip them together
         :ca:5a.    Concatenate each element of the zip, apply predicate 5 to that
    
  • Predikat 5:

    :3a.    Apply predicate 3 to each element of the input
    
  • Predikat 6: Tetapkan nilai yang memenuhi batasan untuk subset sel kosong, kemudian dengan nilai tersebut hanya ada satu solusi untuk papan tulis.

    hs.       Output is a subset of the blank cells
    :=a,      Assign values to those cells
    ?t:9ac    Concatenate the values of all cells of the board
    :=f       Find all solved boards
    l1        There is only 1 such solved board
    
  • Predikat 7: Mengubah papan sehingga setiap sel sekarang [V:X:Y]bukan hanya V(nilainya).

    :Im       Take the Ith line of the board
    :8f       Transform all elements of the line using predicate 8
    :[[I]]z   Zip the result with [I]
    :ca.      Concatenate each element of the zip
    
  • Predikat 8: Mengubah garis sehingga setiap sel sekarang [V:X].

    :Jm    Take the Jth element of the line
    :J.    Output is [That element:J]
    
  • Predikat 9: Ambil nilai sel

    :ha.   Take the head of each element of the input
    
  • Predikat 10: Tambahkan panjang subset di awal

    lg     Put the length of the input in a list
    :?c.   Concatenate it with the input
    
  • Predikat 11: Cetak satu sel

    b:+a[X:Y],        Increment coordinates by 1 to get X and Y
    ?h:Y:Xr:          Build the list [X:Y:Value]
    "(~d,~d):~d\n"w   Format that list as "('X','Y'):'Value'\n" to STDOUT
    
Fatalisasi
sumber
2
Tidak bisakah Anda memperluas ini menjadi jawaban Prolog? Maka itu akan bersaing! (Anda dapat mempostingnya secara terpisah.) Saya tidak yakin seberapa langsung pemetaan antara Brachylog dan Prolog.
Lynn
@ Lynn Ya saya bisa, saya bahkan bisa memposting kode Prolog yang dihasilkan oleh transpiler Brachylog (yang tentu saja akan sangat tidak dikenali). Saya tidak akan melakukannya karena saya cukup yakin poster tantangan tidak akan pernah kembali untuk menerima jawaban: p
Fatalize