pengantar

Tulis sebuah solver untuk teka-teki Hitori menggunakan byte terkecil.

Tantangan

Tugas Anda adalah menulis sebuah pemecah untuk Hitori (ひ と り, kata untuk "sendirian" dalam bahasa Jepang; arti dari nama permainan adalah "Biarkan aku sendiri") teka-teki logis. Aturannya adalah sebagai berikut:

• Anda disajikan dengan grid sel n-by-n, setiap sel berisi bilangan bulat antara 1 dan n (inklusif).
• Tujuan Anda adalah untuk memastikan bahwa tidak ada angka yang muncul lebih dari satu kali di setiap baris dan setiap kolom grid, dengan menghapus angka dari grid yang diberikan, tunduk pada batasan yang ditunjukkan dalam dua aturan berikutnya,
• Anda tidak dapat menghapus dua angka dari dua sel yang berdekatan (horizontal atau vertikal).
• Sel-sel bernomor yang tersisa harus semuanya terhubung satu sama lain. Ini berarti bahwa setiap dua sel bernomor yang tersisa dapat dihubungkan dengan kurva yang hanya terdiri dari segmen-segmen yang menghubungkan angka-angka yang tersisa yang berdekatan (horizontal atau vertikal). (Terima kasih kepada @ user202729 untuk menunjukkan bahwa ini tidak ada)

Saya harap aturannya sudah jelas sekarang. Jika ada sesuatu yang tidak jelas tentang aturan tersebut, periksa halaman Wikipedia .

Uji Kasus

Sel-sel dari mana angka-angka dihapus diwakili dengan 0s.

Input  ->  Output

4
2 2 2 4      0 2 0 4
1 4 2 3  ->  1 4 2 3
2 3 2 1      2 3 0 1
3 4 1 2      3 0 1 2

4
4 2 4 3      0 2 4 3
4 1 1 2  ->  4 1 0 2
3 1 2 1      3 0 2 1
4 3 1 3      0 3 1 0

5
1 5 3 1 2      1 5 3 0 2
5 4 1 3 4      5 0 1 3 4
3 4 3 1 5  ->  3 4 0 1 5
4 4 2 3 3      4 0 2 0 3
2 1 5 4 4      2 1 5 4 0

8
4 8 1 6 3 2 5 7      0 8 0 6 3 2 0 7
3 6 7 2 1 6 5 4      3 6 7 2 1 0 5 4
2 3 4 8 2 8 6 1      0 3 4 0 2 8 6 1
4 1 6 5 7 7 3 5  ->  4 1 0 5 7 0 3 0
7 2 3 1 8 5 1 2      7 0 3 0 8 5 1 2
3 5 6 7 3 1 8 4      0 5 6 7 0 1 8 0
6 4 2 3 5 4 7 8      6 0 2 3 5 4 7 8
8 7 1 4 2 3 5 6      8 7 1 4 0 3 0 6

9
8 6 5 6 8 1 2 2 9      8 0 5 6 0 1 2 0 9
5 6 2 4 1 7 9 8 3      5 6 2 4 1 7 9 8 3
5 8 2 5 9 9 8 2 6      0 8 0 5 0 9 0 2 0
9 5 6 6 4 3 8 4 1      9 5 6 0 4 3 8 0 1
1 1 6 3 9 9 5 6 2  ->  0 1 0 3 9 0 5 6 2
1 1 4 7 3 8 3 8 6      1 0 4 7 0 8 3 0 6
3 7 4 1 2 6 4 5 5      3 7 0 1 2 6 4 5 0
3 3 1 9 8 7 7 4 5      0 3 1 9 8 0 7 4 5
2 9 7 5 3 5 9 1 3      2 9 7 0 3 5 0 1 0 

Test case ini diambil dari Concept Is Puzzles , PuzzleBooks , Concept Is Puzzles , Wikipedia , dan Youtube .

Spesifikasi

• Tidak perlu khawatir tentang penanganan pengecualian.

• Anda dapat mengasumsikan bahwa input selalu berupa puzzle yang valid dengan solusi yang unik dan Anda dapat mengambil keuntungan dari ini dalam menulis kode Anda.

• Ini adalah kode-golf , jumlah byte terendah yang menang.

• 4 <= n <= 9 (16 awalnya, diubah menjadi 9 mengikuti saran Stewie Griffin, juga menyimpan beberapa masalah di IO)

• Anda dapat mengambil input dan memberikan output melalui formulir standar apa pun , dan Anda bebas memilih format.

• Beberapa saran untuk format keluaran adalah (tetapi Anda tidak dibatasi untuk ini)

  • Mengeluarkan kisi terakhir
  • Mengeluarkan kisi-kisi berisi semua angka yang dihapus
  • Keluarkan daftar koordinat salah satu di atas

• Seperti biasa, celah default berlaku di sini.

_{Terkait (terinspirasi oleh tantangan ini): Periksa apakah Semua Elemen dalam Matriks Terhubung}

_{Tantangan terakhir saya: Perpanjangan Game Sevens}

Haskell , 374 byte

import Data.Array;import Data.List;r=range;p=partition
c(e,f)=p(\(b,p)->any(==1)[(b-d)^2+(p-q)^2|(d,q)<-e])f
n#g=[s|(o,(e:f))<-[p((==0).(g!))$indices g],
 null.fst$c(o,o),null.snd$until(null.fst)c([e],f),
 s<-case[((l,c),d)|((l,c),h)<-assocs g,h>0,
 d<-[filter((==h).(g!))$r((l,c+1),(l,n))++r((l+1,c),(n,c))],d/=[]]
 of[]->[g];((c,d):_)->n#(g//[(c,0)])++n#(g//[(c,0)|c<-d])]

Cobalah online!

APL (Dyalog Unicode) , 133 byte ^SBCS

{q←{⊢/4 2⍴⍵}⌺3 3⋄g←⍵=⊂∪,⍵⋄⍵×~1⊃{((⌈/q b)⌈b<{2<≢∪0,,(⍵×⊢⌈⌈/∘q)⍣≡⍵×(⍴⍵)⍴1+⍳≢,⍵}¨~b∘⌈¨⊂⍤2∘.≡⍨⍳⍴b)(+/↑w<g×⌈.⌈⍨w×g)⌈w b←⍵}⍣≡×\(⌈/=∘⌽⍨q⍵)0}

Cobalah online!

Implementasi saya dari aturan # 4 (sel-sel harus membentuk satu komponen yang terhubung) agak boros, tapi tetap ini melewati semua tes dalam waktu sekitar 10 detik pada TIO.

Algoritma keseluruhan: Menyimpan dua matriks boolean bdan wuntuk sel yang masing-masing menjadi hitam dan putih. Inisialisasi bsebagai all-zero. Inisialisasi wsebagai 1 hanya untuk sel-sel yang bertetangga dengan tetangga yang cocok.

Ulangi sampai bdan wmenetap:

• tambahkan ke bsel yang berada di garis yang sama (horizontal atau vertikal) dan dengan nilai yang sama dengan sel diw

• menambah wtetangga langsung dari semua sel dib

• tambahkan ke wsemua cutpoint - sel yang penghapusannya akan membagi grafik sel non-hitam menjadi beberapa komponen yang terhubung

Akhirnya, output not(b)dikalikan dengan matriks asli.

Jelly , 62 byte

Menggunakan tautan monadic isConnected user202729 dari pertanyaan lain.

FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3
ḟ0ĠḊ€
¬T€œ&2\;Ç€FȦ
ZÇȯÇ_1Ŀ
2ḶṗLṗLa⁸ÇÞḢ

Program lengkap mencetak representasi daftar daftar.
Bekerja dengan kekerasan dan sangat tidak efisien.

Cobalah online! - 3 oleh 3, karena terlalu tidak efisien untuk menjalankan bahkan ukuran 4 dalam batas TIO 60 detik!

Bagaimana?

FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3 - Link 1 isConnected? List of lists
...                     - 1 if connected 0 if not -- see linked answer in the header

ḟ0ĠḊ€ - Link 2, helperFor-AnyRepeatedValues: list
ḟ0    - filter out zeros
  Ġ   - group indices by value (i.e. [[indices of min],...,[indices of max]]
   Ḋ€ - dequeue €ach -- leaving a list of empty lists iff no repeated values
      -                 any remaining values are non-zero (1-based indexing in Jelly)

¬T€œ&2\;Ç€FȦ - Link 3, columnwiseAnyAdjacentZerosOrRowwiseAnyRepeatedValues: list of lists
¬            - logical not (convert all zeros to ones and all others to zeros)
 T€          - for €ach row get a list of truthy indexes (i.e. indexes of original zeros)
     2\      - pairwise reduction (i.e. for neighbouring rows) with:
   œ&        -   intersection (empty if no columnwise adjacent original zeros
             -                 any remaining values are non-zero due to 1-based indexing)
        Ç€   - call last link (1) as a monad for €ach row
       ;     - concatenate
          F  - flatten into a single list (empty iff no columnwise adjacent original zeros
             -                                   AND no rowwise repeated values)
           Ȧ - any and all (0 if empty [or contains any zero -- never] else 1)

ZÇȯÇ_1Ŀ - Link 4, validity check? list of lists
Z       - transpose
 Ç      - call last link (2) as a monad rowwiseAnyAdjacentZerosOrColumnwiseAnyRepeatedValues?
   Ç    - call last link (2) as a monad columnwiseAnyAdjacentZerosOrRowwiseAnyRepeatedValues?
  ȯ     - logical OR
     1Ŀ - call link 1 as a monad (isConnected?)
    _   - subtract
        - this yields -1 for valid, while it yields 0 or 1 if not.

2ḶṗLṗLa⁸ÇÞḢ - Main link: list of lists
2Ḷ          - lowered range of 2 -> [0,1]
   L        - length (number of rows in the input)
  ṗ         - Cartesian power (all lists of zeros and ones of length L)
     L      - length (number of rows in the input again)
    ṗ       - Cartesian power (all grids of zeros and ones of same shape as the input)
       ⁸    - the input
      a     - logical AND -- effectively uses each of the formed grids as a mask
         Þ  - sort by:
        Ç   -   last link (3) as a monad
          Ḣ - head
            - implicit print