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.
- Tidak lebih dari dua digit yang sama dapat saling berdekatan secara vertikal atau horizontal
- 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).
- 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.0
→ 10.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.011
→010011
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..100
→101100 & 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 1
di 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 menggunakannyaABx
. 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 kode-golf , 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
sumber
Jawaban:
Brachylog , 34 byte
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).sumber
A
throughY
(denganZ
sebagai output-parameter). Apakah itu melanjutkanAA
,AB
, dll?AA
adalah variabel danKEVINCRUIJSSEN
juga variabel.JavaScript (ES6),
274270 byteMengambil input sebagai array 2D, tempat sel kosong ditandai dengan
2
. Mencetak semua solusi yang mungkin untuk konsol.Bagaimana itu bekerja
Bagian pertama dari kode menggunakan
M()
fungsi untuk memeriksa validitas papan saat ini, baik secara horizontal maupun vertikal.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:
/(0|1),\1,\1/
untuk mendeteksi 3 atau lebih angka identik berturut-turut.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:
Demo
Tampilkan cuplikan kode
sumber
Jelly ,
5351 byteMembawa daftar daftar mewakili grid, mengandung
0
,1
dan2
(ruang). Mengembalikan daftar daftar daftar, masing-masing daftar daftar dalam format yang sama (meskipun tanpa2
s) 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
2
s dengan1
s atau0
s.sumber