Baru-baru ini saya mendapat aplikasi Sudoku baru yang menghasilkan Sudoku sangat keras, yang tidak dapat diselesaikan dengan menggunakan strategi standar. Jadi saya harus belajar beberapa yang baru. Salah satu strategi ini adalah Strategi Y-Wing . Ini peringkat di bawah "Strategi Tangguh", tetapi sebenarnya tidak terlalu sulit.
Contoh
Untuk strategi ini hanya 4 sel yang penting. Karena itu saya mengabaikan semua sel lain dalam gambar.
Kami melihat semua kandidat untuk setiap sel. Dalam contoh berikut ini kami memiliki sel dengan kandidat 3 7
(itu berarti kami telah menolak kandidat 1 2 4 5 6 8 9
, misalnya karena ada 1
di baris yang sama, a 2
di kotak 3x3 yang sama, ...), sel dengan kandidat 6 7
, sel dengan kandidat 3 6
dan sel dengan kandidat 2 6
. Strategi Y-Wing akan menyarankan, bahwa 6
dapat dihapus dari kandidat sel yang benar, hanya menyisakan 2
sebagai kandidat, yang dapat Anda isi. Jadi kami menemukan angka yang benar dan selangkah lebih dekat dalam menyelesaikan Sudoku penuh.
Mengapa bisa 6
dihapus?
Penjelasan
Mari kita asumsikan bahwa itu 6
adalah angka yang benar untuk sel yang benar. Sekarang ada 6
di kolom ini, oleh karena itu kita dapat menghapus 6
dari kandidat sel kanan atas, hanya menyisakan satu 7
, yang dapat kita isi. Hal yang sama terjadi dengan sel kiri bawah. Kami dapat menghapus 6
dan mengisi 3
. Sekarang jika kita melihat sel kiri atas kita mendapat kontradiksi. Karena sekarang sudah ada 7
di baris yang sama dan 3
di kolom yang sama, sehingga kita dapat menghapus 7
dan 3
kandidat, tanpa meninggalkan kandidat sama sekali. Yang jelas tidak mungkin. Oleh karena itu 6 tidak bisa menjadi angka yang benar dari sel yang benar.
Lebih tepatnya: Jika kita memiliki 4 sel dengan kandidat [A B] [A C] [C D] [B C]
(dalam urutan ini atau diputar melingkar) dan sel terhubung (melalui baris yang sama, kolom yang sama atau kotak 3x3 yang sama) dalam lingkaran (Sel 1 terhubung ke Sel 2, yang merupakan terhubung ke Sel 3, yang terhubung ke Sel 4, yang terhubung ke Sel 1), daripada yang bisa Anda hapus C
dari [C D]
sel. Sangat penting, bahwa ketiga sel [A B]
, [A C]
dan [B C]
masing-masing hanya berisi dua kandidat. Secara berbeda sel [C D]
, yang mungkin mengandung lebih atau kurang ( D
bisa nol, satu atau bahkan lebih banyak kandidat).
Perhatikan bahwa saya secara eksplisit mengatakan mereka dapat dihubungkan dengan cara apa pun. Dalam contoh berikut Anda dapat melihat strategi diterapkan lagi. Tapi kali ini 4 sel tidak membentuk persegi panjang. Sel-sel kiri bawah dan bawah hanya terhubung, karena mereka berada di kotak 3x3 yang sama. Y-Wing mengatakan, bahwa kita dapat menghapus 1
sebagai kandidat sel kiri atas. Kali ini masih ada 2 kandidat di sel ini yang tersisa, jadi kami tidak menemukan nomor yang benar. Namun demikian, penghapusan 1
dapat membuka pintu ke strategi yang berbeda.
Jika Anda ingin informasi lebih lanjut tentang strategi atau ingin beberapa contoh lagi, kunjungi sudokuwiki.org .
Spesifikasi Tantangan
Anda akan menerima 4 daftar sebagai input, mewakili kandidat sel. Keempat sel terhubung seperti lingkaran (Sel 1 terhubung ke Sel 2, yang terhubung ke Sel 3, yang terhubung ke Sel 4, yang terhubung ke Sel 1). Anda dapat mengasumsikan bahwa setiap daftar diurutkan dalam urutan menaik.
Tugas Anda adalah menghapus satu kandidat (dengan menerapkan strategi Y-Wing) dan mengembalikan daftar kandidat yang dihasilkan dalam urutan yang sama. Jika Anda tidak dapat menerapkan strategi, kembalikan daftar kandidat yang sama.
Jika ada dua solusi yang mungkin (Anda dapat menghapus A sel B atau menghapus C sel D), daripada mengembalikan hanya satu solusi. Tidak masalah yang mana.
Input dapat dalam format daftar atau array asli apa pun. Anda juga dapat menggunakan daftar daftar atau yang serupa. Anda dapat menerima input melalui STDIN, argumen baris perintah, prompt atau argumen fungsi dan mengembalikan output melalui nilai balik atau hanya dengan mencetak ke STDOUT.
Ini adalah kode-golf. Kode terpendek (dalam byte) menang.
Uji Kasus
[3 7] [6 7] [2 6] [3 6] => [3 7] [6 7] [2] [3 6] # Example 1
[6 7] [2 6] [3 6] [3 7] => [6 7] [2] [3 6] [3 7] # Example 1, different order
[2 6] [3 6] [3 7] [6 7] => [2] [3 6] [3 7] [6 7] # Example 1, different order
[3 6] [3 7] [6 7] [2 6] => [3 6] [3 7] [6 7] [2] # Example 1, different order
[1 2 8] [1 8] [8 9] [1 9] => [2 8] [1 8] [8 9] [1 9] # Example 2
[3 8] [4 8] [3 4 8] [3 4] => [3 8] [4 8] [3 8] [3 4]
[1 3 6 7 8] [3 8] [3 4] [4 8] => [1 3 6 7] [3 8] [3 4] [4 8]
[7 8] [7 8] [4 7] [4 8] => [7 8] [8] [4 7] [4 8] or [7] [7 8] [4 7] [4 8]
[4 7] [7 8] [4 8] [4] => [4 7] [7 8] [4 8] [] # Fictional example
[3 7] [2 6] [6 7] [3 6] => [3 7] [2 6] [6 7] [3 6] # Y-Wing can't be applied here
[4 7] [2 7 8] [4 8] [1 4] => [4 7] [2 7 8] [4 8] [1 4] # -||-
7 8
adalah kandidat untuk sel pertama dan kedua. Strategi Y-Wing masih bisa diterapkan.Jawaban:
CJam, 90 byte
Ugghhh, ini terlalu lama karena kendala bahwa 3 sel lainnya hanya memiliki 2 kandidat.
Ini mengharapkan input sebagai daftar daftar dalam format CJam. Untuk ex .:
memberikan output dalam daftar format daftar CJam:
Akan menambahkan penjelasan setelah saya selesai bermain golf ..
Cobalah online di sini atau coba seluruh paket tes di sini .
sumber
Mathematica,
124110 byteContoh:
sumber