Binary Puzzle Solver

10

pengantar

Aturan teka-teki:

Teka-teki Biner (juga dikenal sebagai Takuzu atau Subiku) sangat sederhana untuk dipahami, dan hanya memiliki beberapa aturan:
Karena nama gimnya biner, itu cukup jelas, tetapi Anda hanya dapat mengisi angka nol dan satu.

  1. Tidak lebih dari dua digit yang sama dapat saling berdekatan secara vertikal atau horizontal
  2. Setiap baris dan setiap kolom harus berisi jumlah yang sama dengan nol dan satu (ini secara implisit berarti setiap permainan biner akan selalu memiliki dimensi genap).
  3. Mungkin tidak ada baris duplikat dan tidak ada kolom duplikat (dengan urutan nol dan yang sama)

Anda dapat memainkan game di www.binarypuzzle.com jika Anda mau.

Taktik:

Karena aturan 1, kita selalu dapat mengisi angka jika:
- Sudah ada dua angka yang sama secara vertikal atau horizontal berdekatan satu sama lain, dalam hal ini kita dapat mengisi angka yang berlawanan di kedua sisi. Yaitu .11...0110...
- Ada dua digit yang sama secara vertikal atau horizontal dengan hanya satu celah di antaranya. Yaitu .1.1...101..

Karena aturan 1, ketika tiga celah tersisa dan kami tidak dapat memiliki tiga yang berdekatan dengan angka yang sama, kami dapat mengisi salah satu dari celah tersebut. Yaitu .0.1.010.1.0(Kita masih harus mengisi dua yang, dan kita tidak bisa memiliki tiga yang berdekatan di tengah, jadi celah pertama harus a 1.)

Karena aturan 2, kita selalu dapat mengisi celah yang tersisa di baris atau kolom jika setengahnya sudah diisi dengan angka yang berlawanan. Yaitu .1.011010011

Karena aturan 3, kita selalu dapat mengisi angka yang berlawanan jika hanya dua yang tersisa untuk diselesaikan pada garis yang diperintahkan sama. Yaitu 101100 & 1..100101100 & 110100

Karena aturan 3, kadang-kadang kita bisa mengisi kekosongan ketika tiga celah dibiarkan pada garis yang dipesan sama. Yaitu 010011 & .1.01.010011 & .1.010(Di sini kita tidak bisa mengisi a 1di akhir, karena itu berarti kita harus mengisi nol di dua celah lainnya, membuat kedua garis sama berurutan.)

Contoh:

Kita mulai dengan kisi 6x6 berikut dengan beberapa kisi dan nol yang terisi (dan titik-titiknya adalah celah yang belum kita isi):

.1....
.10.0.
1.11..
.1....
...1.0
......

Karena aturan 1 & 2 kita dapat mengisi angka-angka ini:

.1.01.
.1010.
101100
010011
.0.1.0
.010..

Karena aturan 1 kita dapat mengisi 1 di baris 5, kolom 1:

.1.01.
.1010.
101100
010011
10.1.0
.010..

Karena aturan 3 kita dapat mengisi 0 pada baris 1, kolom 6 (saat melihat baris 4):

.1.010
.1010.
101100
010011
10.1.0
.010..

Sekarang kita dapat terus mengisi celah dengan angka karena aturan 1 & 2:

.1.010
010101
101100
010011
10.1.0
.010.1

Sekarang kita bisa menyelesaikan baris 5 karena aturan 3 (ketika melihat baris 3):

.1.010
010101
101100
010011
100110
.010.1

Dan kemudian kita dapat menyelesaikan puzzle karena aturan 1 & 2:

011010
010101
101100
010011
100110
101001

Tantangan:

Tantangannya sederhana: mengingat grid awal, menampilkan puzzle yang dipecahkan.

CATATAN: Anda tidak harus menerapkan aturan di atas. Anda tentu saja bisa, dan itu akan memberi Anda petunjuk tentang bagaimana menerapkan tantangan ini, tetapi menguatkan solusi dengan aturan-aturan dalam pikiran sepenuhnya baik-baik saja.
Bagaimana Anda menyelesaikannya terserah Anda, tetapi tantangannya adalah untuk menghasilkan puzzle yang dipecahkan.

Aturan tantangan:

  • Format input dan output untuk grid fleksibel, tetapi tolong sebutkan apa yang Anda gunakan. (Yaitu byte-array 2D; String dengan baris baru; dll.)
  • Ini di atas juga berlaku untuk karakter yang digunakan. Dalam contoh yang saya gunakan 01., tetapi jika Anda mau, Anda bisa menggunakannya ABx. Harap sebutkan format input / output apa dan karakter yang Anda gunakan.
  • Anda dapat mengasumsikan hanya ukuran kotak berikut yang akan digunakan 6x6:; 8x8; 10x10; 12x12; 14x14; 16x16.

Aturan umum:

  • Ini adalah , jadi jawaban tersingkat dalam byte menang.
    Jangan biarkan bahasa kode-golf mencegah Anda dari memposting jawaban dengan bahasa yang bukan kode. Cobalah untuk memberikan jawaban sesingkat mungkin untuk bahasa pemrograman 'apa pun'.
  • Aturan standar berlaku untuk jawaban Anda, jadi Anda diperbolehkan menggunakan STDIN / STDOUT, fungsi / metode dengan parameter yang tepat, program lengkap. Panggilanmu.
  • Celah default tidak diperbolehkan.
  • Jika memungkinkan, silakan tambahkan tautan dengan tes untuk kode Anda.
  • Juga, silakan tambahkan penjelasan jika perlu.

Kasus uji:

Titik-titik hanya ditambahkan agar mudah dibaca, jangan ragu untuk menggunakan spasi atau apa pun yang Anda inginkan untuk kesenjangan. Format in dan output fleksibel.

Input:
1..0..
..00.1
.00..1
......
00.1..
.1..00

Output:
101010
010011
100101
011010
001101
110100

Input:
.1....
.10.0.
1.11..
.1....
...1.0
......

Output:
011010
010101
101100
010011
100110
101001

Input:
.......1..
.00..0..1.
.0..1..0.0
..1...1...
1.1......1
.......1..
.0..1...0.
....11...0
.0.0..1..0
0...0...1.

Output:
0110010101
1001100110
1001101010
0110011001
1010100101
0101010110
1001101001
0110110100
1010011010
0101001011
Kevin Cruijssen
sumber

Jawaban:

4

Brachylog , 34 byte

{ℕ<2}ᵐ²&≜{d?ọᵐctᵐ=&{ḅlᵐ⌉<3}ᵐ}&\↰₂&

Cobalah online!

Ini sangat lambat, jadi test case pada TIO adalah 4x4. Saat ini saya sedang menjalankan test case 6x6 di komputer saya untuk melihat berapa banyak waktu yang dibutuhkan.

Ini mengambil daftar daftar sebagai input. Nilai yang tidak diketahui harus ditandai dengan variabel, yaitu dengan string semua huruf besar (dan semuanya harus berbeda, karena jika tidak, Anda akan menunjukkan bahwa beberapa sel harus memiliki nilai yang sama)

Penjelasan

Kami membatasi nilai-nilai yang ada di dalam {0,1}, kemudian kami mencoba instantiations dari variabel sampai satu menghormati semua 3 aturan. Inilah sebabnya mengapa ini sangat lambat (karena akan mencoba semuanya sampai menemukan satu; dan karena dalam kasus itu Brachylog tidak diimplementasikan dengan cukup baik sehingga kendala dapat dikenakan sebelum mencoba kemungkinan matriks).

                                 &  Output = Input
{   }ᵐ²                             Map two levels on the Input (i.e. each cell):
 ℕ<2                                  The cell is either 0 or 1
       &≜                           Assign values to all cells
         {                  }       Define predicate 2:
          d?                          The Input with no duplicates is still the Input
                                        (i.e. all rows are different)
           ?ọᵐctᵐ=                    All occurences of 1s and 0s for each rows are equal
                  &{      }ᵐ          Map on rows:
                    ḅlᵐ                 Get the lengths of runs of equal values
                       ⌉<3              The largest one is strictly less than 3
                             &\↰₂   Apply predicate 2 on the transpose of the Input
                                      (i.e. do the same checks but on columns)
Fatalisasi
sumber
Karena penasaran, bagaimana Brachylog menunjukkan variabel di luar alfabet kapital? Jadi katakanlah solusi Anda akan bekerja lebih cepat, itu tidak akan dapat mengisi semua ruang kosong pada grid 14x14 dengan Athrough Y(dengan Zsebagai output-parameter). Apakah itu melanjutkan AA, AB, dll?
Kevin Cruijssen
2
@KevinCruijssen Setiap pengenal huruf besar semua adalah variabel, jadi ya AAadalah variabel dan KEVINCRUIJSSENjuga variabel.
Fatalkan
3
Seperti yang saya duga, tantangan dibuat untuk Brachylog: D
Jonathan Allan
3

JavaScript (ES6), 274 270 byte

Mengambil input sebagai array 2D, tempat sel kosong ditandai dengan 2. Mencetak semua solusi yang mungkin untuk konsol.

f=(a,x=0,y=0,w=a.length,p,R=a[y])=>(M=z=>!a.some((r,y)=>/(0|1),\1,\1/.exec(s=r.map((v,x)=>(v=z?v:a[x][y],b-=v&1,c-=!v,m|=v&2,v),b=c=w/2))||b*c<0|o[b*c||s]&(o[s]=1),o={}))(m=0)&M(1)&&(m?R&&[0,1].map(n=>(p=R[x])==n|p>1&&(R[x]=n,f(a,z=(x+1)%w,y+!z),R[x]=p)):console.log(a))

Bagaimana itu bekerja

Bagian pertama dari kode menggunakan M()fungsi untuk memeriksa validitas papan saat ini, baik secara horizontal maupun vertikal.

M = z =>
  !a.some((r, y) =>
    /(0|1),\1,\1/.exec(
      s = r.map((v, x) =>
        (
          v = z ? v : a[x][y],
          b -= v & 1,
          c -= !v,
          m |= v & 2,
          v
        ),
        b = c = w / 2
      )
    ) ||
    b * c < 0 |
    o[b * c || s] &
    (o[s] = 1),
    o = {}
  )

Ini memetakan baris atau kolom penuh ke string s . Ini sebenarnya sebuah array yang dipaksa untuk sebuah string, jadi sepertinya "1,2,2,0,2,2".

Ini menggunakan:

  • Ekspresi reguler /(0|1),\1,\1/untuk mendeteksi 3 atau lebih angka identik berturut-turut.
  • Counter b dan c untuk melacak jumlah orang dan nol . Kedua penghitung diinisialisasi ke w / 2 dan dikurangi setiap kali satu atau nol (masing-masing) ditemui. Ini mengarah pada:
    • b = c = 0 b * c = 0 → garis sudah selesai dan benar (sebanyak nol sama dengan yang ada )
    • b> 0 AND c> 0 b * c> 0 → garis tidak lengkap tapi benar sejauh (kami tidak memiliki lebih dari w / 2 angka nol atau lebih dari w / 2 orang )
    • b <0 ATAU c <0 b * c <0 → garis tidak valid
  • Bendera m (untuk 'hilang') yang bukan nol jika setidaknya ada dua yang tersisa di papan tulis.
  • Objek o untuk melacak semua pola garis yang ditemui sejauh ini.

Jika papan tidak valid, kami segera berhenti. Jika papan tersebut valid dan lengkap, kami mencetaknya ke konsol. Jika tidak, bagian kedua dari upaya kode untuk mengganti setiap 2 dengan baik nol atau satu dengan panggilan rekursif:

[0, 1].map(n =>
  (p = a[y][x]) == n |
  p > 1 && (
    a[y][x] = n,
    f(a, z = (x + 1) % w, y + !z),
    a[y][x] = p
  )
)

Demo

Arnauld
sumber
Terima kasih telah menambahkan penjelasan. Dan saya suka bagaimana Anda mencetak semua kemungkinan keluaran, bukan hanya satu!
Kevin Cruijssen
1
@KevinCruijssen Ini mungkin jauh dari optimal tetapi menyenangkan untuk ditulis. Tantangan yang bagus!
Arnauld
1

Jelly , 53 51 byte

ṡ€3ḄFf0,7L
SḤnLṀȯÇ
⁻QȯÇ
Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ

Membawa daftar daftar mewakili grid, mengandung 0, 1dan 2(ruang). Mengembalikan daftar daftar daftar, masing-masing daftar daftar dalam format yang sama (meskipun tanpa 2s) dan merupakan solusi yang mungkin untuk input.

Cobalah online! (ini tidak akan menjalankan kasus uji pertanyaan apa pun karena keterbatasan memori - semuakisi2 nSpaces dibuat sebagai daftar daftar bilangan bulat - tapi saya menempatkan kasus yang lumayan kuat di sana dengan satu solusi). Footer memisahkan dan memformat grid.

Metode brute force murni - mengimplementasikan aturan dan memeriksanya untuk setiap kisi yang dapat dibentuk dengan mengganti 2s dengan 1s atau 0s.

ṡ€3ḄFf0,7L - Link 1, # of runs of 3 1s or 3 0s by row: list of lists
ṡ€3        - all contiguous slices of length 3 for €ach list
   Ḅ       - convert all results from binary
    F      - flatten into one list
     f     - filter keep values in:
      0,7  -   0 paired with 7: [0,7]
         L - length

SḤnLṀȯÇ - Link 2, unequal counts of 1s and 0s by column ...or link 1: list of lists
S       - sum (vectorises, hence "by column", counts 1s since only 1s or 0s appear)
 Ḥ      - double
   L    - length (number of rows - OK since square)
  n     - not equal? (vectorises)
    Ṁ   - maximum (1 if any not equal)
     ȯÇ - ... or last link (1) as a monad

⁻QȯÇ - Link 3, rows are unique ...or link 2: list of lists
 Q   - unique
⁻    - not equal?
  ȯÇ - ... or last link (2) as a monad

Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ - Main link: list of lists
F                           - flatten
 ṣ©2                        - split at 2s and copy the result to the register
    L                       - length (# of such slices)
     ’                      - decrement (# of 2s)
      0,1                   - 0 paired with 1
         ṗ                  - Cartesian power (all binary lists of length # of 2s)
             ®              - recall value from register (the flat version split at 2s)
          ż@€               - zip (reversed @rguments) for €ach (1s & 0s where 2s were)
              F€            - flatten €ach
                s€L         - split €ach into chunks of length length(input) (into rows)
                    Ðḟ      - filter discard if:
                   Ç        -   call last link(3) as a monad
                         Ðḟ - filter discard if:
                        $   -   last two links as a monad:
                      Z     -     transpose
                       Ç    -     call last link(3) as a monad
Jonathan Allan
sumber