Bagaimana cara mengatasi sudoku yang sulit. Matematikawan datang dengan formula untuk memecahkan Sudoku

Bidang Sudoku adalah tabel sel 9x9. Angka 1 sampai 9 dimasukkan di setiap sel. Tujuan dari permainan ini adalah untuk mengatur angka sedemikian rupa sehingga tidak ada pengulangan di setiap baris, kolom dan setiap blok 3x3. Dengan kata lain, setiap kolom, baris, dan blok harus berisi semua angka dari 1 hingga 9.

Untuk mengatasi masalah, kandidat dapat ditulis dalam sel kosong. Misalnya, pertimbangkan sel di kolom ke-2 dari baris ke-4: di kolom tempat ia berada, sudah ada angka 7 dan 8, di baris - angka 1, 6, 9 dan 4, di blok - 1 , 2, 8 dan 9 Oleh karena itu, kami mencoret 1, 2, 4, 6, 7, 8, 9 dari kandidat di sel ini, dan kami hanya memiliki dua kandidat yang mungkin - 3 dan 5.

Demikian pula, kami mempertimbangkan kandidat yang mungkin untuk sel lain dan mendapatkan tabel berikut:

Kandidat lebih menarik untuk dihadapi dan metode logis yang berbeda dapat diterapkan. Selanjutnya, kita akan melihat beberapa di antaranya.

penyendiri

Metode ini terdiri dalam menemukan single dalam tabel, yaitu. sel di mana hanya satu digit yang mungkin dan tidak ada yang lain. Kami menulis nomor ini di sel ini dan mengecualikannya dari sel lain di baris, kolom, dan blok ini. Misalnya: di tabel ini ada tiga "penyendiri" (mereka disorot dengan warna kuning).

penyendiri tersembunyi

Jika ada beberapa kandidat dalam sel, tetapi salah satunya tidak ditemukan di sel lain dari baris tertentu (kolom atau blok), maka kandidat seperti itu disebut "penyendiri tersembunyi". Dalam contoh berikut, kandidat "4" di blok hijau hanya ditemukan di sel tengah. Jadi, di sel ini pasti akan ada "4". Kami memasukkan "4" di sel ini dan mencoretnya dari sel lain dari kolom ke-2 dan baris ke-5. Demikian pula, di kolom kuning, kandidat "2" muncul sekali, oleh karena itu, kami memasukkan "2" di sel ini dan mengecualikan "2" dari sel baris ke-7 dan blok yang sesuai.

Dua metode sebelumnya adalah satu-satunya metode yang secara unik menentukan isi sel. Metode berikut hanya memungkinkan Anda untuk mengurangi jumlah kandidat dalam sel, yang cepat atau lambat akan menyebabkan penyendiri atau penyendiri tersembunyi.

Kandidat Terkunci

Ada kasus ketika seorang kandidat dalam satu blok hanya berada dalam satu baris (atau satu kolom). Karena fakta bahwa salah satu sel ini akan berisi kandidat ini, kandidat ini dapat dikeluarkan dari semua sel lain dari baris (kolom) ini.

Pada contoh di bawah, blok tengah berisi kandidat "2" hanya di kolom tengah (sel kuning). Jadi salah satu dari dua sel itu pasti "2", dan tidak ada sel lain di baris itu di luar blok ini yang bisa menjadi "2". Oleh karena itu, "2" dapat dikecualikan sebagai kandidat dari sel lain di kolom ini (sel berwarna hijau).

Buka Pasangan

Jika dua sel dalam suatu grup (baris, kolom, blok) berisi pasangan kandidat yang identik dan tidak ada yang lain, maka tidak ada sel lain dalam grup ini yang dapat memiliki nilai pasangan ini. 2 kandidat ini dapat dikeluarkan dari sel lain dalam grup. Pada contoh di bawah, kandidat "1" dan "5" di kolom delapan dan sembilan membentuk Pasangan Terbuka di dalam blok (sel kuning). Oleh karena itu, karena salah satu sel ini harus "1" dan yang lain harus "5", kandidat "1" dan "5" dikeluarkan dari semua sel lain dari blok ini (sel hijau).

Hal yang sama dapat dirumuskan untuk 3 dan 4 kandidat, masing-masing hanya 3 dan 4 sel yang berpartisipasi. Buka tiga kali lipat: dari sel hijau, kami mengecualikan nilai sel kuning.

Buka merangkak: dari sel hijau, kami mengecualikan nilai sel kuning.

pasangan tersembunyi

Jika dua sel dalam suatu grup (baris, kolom, blok) berisi kandidat, di antaranya ada pasangan identik yang tidak terjadi di sel lain dari blok ini, maka tidak ada sel lain dari grup ini yang dapat memiliki nilai pasangan ini. Oleh karena itu, semua kandidat lain dari dua sel ini dapat dikecualikan. Pada contoh di bawah, kandidat "7" dan "5" di kolom tengah hanya ada di sel kuning, yang berarti semua kandidat lain dari sel ini dapat dikecualikan.

Demikian pula, Anda dapat mencari triple dan four yang tersembunyi.

sayap-x

Jika suatu nilai hanya memiliki dua kemungkinan lokasi dalam satu baris (kolom), maka nilai tersebut harus ditetapkan ke salah satu sel tersebut. Jika ada satu baris (kolom) lagi, di mana kandidat yang sama juga dapat berada hanya dalam dua sel dan kolom (baris) dari sel-sel ini sama, maka tidak ada sel lain dari kolom (baris) ini yang dapat berisi nomor ini. Pertimbangkan sebuah contoh:

Pada baris ke-4 dan ke-5, angka "2" hanya boleh berada di dua sel kuning, dan sel-sel ini berada di kolom yang sama. Oleh karena itu, angka "2" hanya dapat ditulis dengan dua cara: 1) jika "2" ditulis di kolom ke-5 dari baris ke-4, maka "2" harus dikeluarkan dari sel kuning dan kemudian di baris ke-5 posisi "2" secara unik ditentukan oleh kolom ke-7.

2) jika "2" ditulis di kolom ke-7 dari baris ke-4, maka "2" harus dikeluarkan dari sel kuning dan kemudian di baris ke-5 posisi "2" ditentukan secara unik oleh kolom ke-5.

Oleh karena itu, kolom ke-5 dan ke-7 harus memiliki angka "2" baik di baris ke-4 maupun ke-5. Kemudian angka "2" dapat dikeluarkan dari sel lain dari kolom ini (sel hijau).

"Ikan Pedang" (Ikan Pedang)

Metode ini merupakan variasi dari .

Ini mengikuti aturan teka-teki bahwa jika seorang kandidat berada dalam tiga baris dan hanya dalam tiga kolom, maka di baris lain kandidat dalam kolom ini dapat dikecualikan.

Algoritma:

Kami mencari baris di mana kandidat muncul tidak lebih dari tiga kali, tetapi pada saat yang sama itu milik tepat tiga kolom.
Kami mengecualikan kandidat dari tiga kolom ini dari baris lain.

Logika yang sama berlaku dalam kasus tiga kolom, di mana kandidat dibatasi hingga tiga baris.

Pertimbangkan sebuah contoh. Dalam tiga baris (3, 5 dan 7) kandidat "5" muncul tidak lebih dari tiga kali (sel disorot dengan warna kuning). Namun, mereka hanya dimiliki tiga kolom: ke-3, ke-4 dan ke-7. Menurut metode "Swordfish", kandidat "5" dapat dikeluarkan dari sel lain dari kolom ini (sel hijau).

Pada contoh di bawah, metode Swordfish juga diterapkan, tetapi untuk kasus tiga kolom. Kami mengecualikan kandidat "1" dari sel hijau.

"X-wing" dan "Swordfish" dapat digeneralisasi menjadi empat baris dan empat kolom. Metode ini akan disebut "Medusa".

warna

Ada situasi ketika seorang kandidat muncul hanya dua kali dalam satu grup (dalam satu baris, kolom, atau blok). Maka nomor yang diinginkan pasti ada di salah satunya. Strategi metode Colors adalah melihat hubungan ini menggunakan dua warna, seperti kuning dan hijau. Dalam hal ini, solusinya bisa dalam sel hanya satu warna.

Kami memilih semua rantai yang saling berhubungan dan membuat keputusan:

Jika beberapa kandidat yang tidak diarsir memiliki dua tetangga dengan warna berbeda dalam satu grup (baris, kolom, atau blok), maka kandidat tersebut dapat dikecualikan.
Jika ada dua warna identik dalam satu kelompok (baris, kolom, atau blok), maka warna ini salah. Kandidat dari semua sel dengan warna ini dapat dikecualikan.

Dalam contoh berikut, terapkan metode "Warna" ke sel dengan kandidat "9". Kami mulai mewarnai dari sel di blok kiri atas (baris ke-2, kolom ke-2), mengecatnya dengan warna kuning. Di bloknya, ia hanya memiliki satu tetangga dengan "9", mari kita cat hijau. Dia juga hanya memiliki satu tetangga di kolom, kami mengecatnya dengan warna hijau.

Demikian pula, kami bekerja dengan sisa sel yang berisi angka "9". Kita mendapatkan:

Kandidat "9" hanya boleh di semua sel kuning, atau di semua sel hijau. Di blok tengah kanan, dua sel dengan warna yang sama bertemu, oleh karena itu, warna hijau salah, karena blok ini menghasilkan dua "9", yang tidak dapat diterima. Kami mengecualikan, "9" dari semua sel hijau.

Contoh lain dari metode "Warna". Mari kita tandai sel berpasangan untuk kandidat "6".

Sel dengan "6" di blok tengah atas (disorot dengan warna ungu) memiliki dua kandidat multi-warna:

"6" tentu akan berada dalam sel kuning atau hijau, oleh karena itu, "6" dapat dikeluarkan dari sel ungu ini.

Hal pertama yang harus ditentukan dalam metodologi pemecahan masalah adalah pertanyaan tentang benar-benar memahami apa yang kita capai dan dapat dicapai dalam hal pemecahan masalah. Pemahaman biasanya dianggap sebagai sesuatu yang tidak perlu dikatakan lagi, dan kita melupakan fakta bahwa pemahaman memiliki titik awal pemahaman yang pasti, hanya dalam kaitannya dengan itu kita dapat mengatakan bahwa pemahaman benar-benar terjadi dari saat tertentu yang telah kita tentukan. Sudoku di sini, dalam pertimbangan kami, nyaman karena memungkinkan, menggunakan contohnya, sampai batas tertentu untuk memodelkan masalah pemahaman dan pemecahan masalah. Namun, kita akan mulai dengan beberapa contoh lain yang tidak kalah pentingnya dari Sudoku.

Seorang fisikawan yang mempelajari relativitas khusus mungkin berbicara tentang proposisi "bening kristal" Einstein. Saya menemukan frasa ini di salah satu situs di Internet. Tapi dari mana pemahaman tentang "kejernihan kristal" ini dimulai? Ini dimulai dengan asimilasi notasi matematika postulat, dari mana semua konstruksi matematika multi-level SRT dapat dibangun sesuai dengan aturan yang diketahui dan dapat dipahami. Tetapi apa yang tidak dipahami oleh fisikawan, seperti saya, adalah mengapa postulat SRT bekerja dengan cara ini dan bukan sebaliknya.

Pertama-tama, sebagian besar dari mereka yang membahas doktrin ini tidak memahami apa sebenarnya yang ada dalam postulat keteguhan kecepatan cahaya dalam terjemahan dari penerapan matematikanya ke kenyataan. Dan postulat ini menyiratkan keteguhan kecepatan cahaya dalam semua pengertian yang dapat dibayangkan dan tidak dapat dipahami. Kecepatan cahaya relatif konstan terhadap setiap benda yang diam dan bergerak pada waktu yang sama. Kecepatan berkas cahaya, menurut postulat, adalah konstan bahkan terhadap berkas cahaya yang datang, melintang dan surut. Dan, pada saat yang sama, pada kenyataannya kita hanya memiliki pengukuran yang secara tidak langsung berhubungan dengan kecepatan cahaya, yang ditafsirkan sebagai keteguhannya.

Hukum Newton bagi seorang fisikawan dan bahkan bagi mereka yang hanya mempelajari fisika begitu akrab sehingga tampak begitu dapat dipahami sebagai sesuatu yang diterima begitu saja dan tidak mungkin sebaliknya. Tetapi, katakanlah, penerapan hukum gravitasi universal dimulai dengan notasi matematisnya, yang dengannya bahkan lintasan benda-benda angkasa dan karakteristik orbit dapat dihitung. Tetapi mengapa undang-undang ini bekerja dengan cara ini dan bukan sebaliknya - kami tidak memiliki pemahaman seperti itu.

Begitu juga dengan Sudoku. Di Internet, Anda dapat menemukan deskripsi berulang kali tentang cara "dasar" untuk menyelesaikan masalah Sudoku. Jika Anda mengingat aturan ini, maka Anda dapat memahami bagaimana masalah Sudoku ini atau itu diselesaikan dengan menerapkan aturan "dasar". Tapi saya punya pertanyaan: apakah kita mengerti mengapa metode "dasar" ini bekerja dengan cara ini dan bukan sebaliknya.

Jadi kita beralih ke poin kunci berikutnya dalam metodologi pemecahan masalah. Pemahaman hanya mungkin atas dasar beberapa model yang memberikan dasar untuk pemahaman ini dan kemampuan untuk melakukan beberapa eksperimen alam atau pemikiran. Tanpa ini, kita hanya dapat memiliki aturan untuk menerapkan titik awal yang dipelajari: postulat SRT, hukum Newton, atau cara "dasar" di Sudoku.

Kami tidak dan pada prinsipnya tidak dapat memiliki model yang memenuhi postulat keteguhan tak terbatas dari kecepatan cahaya. Kami tidak, tetapi model yang tidak dapat dibuktikan yang konsisten dengan hukum Newton dapat ditemukan. Dan ada model "Newtonian" seperti itu, tetapi entah bagaimana mereka tidak mengesankan dengan kemungkinan produktif untuk melakukan eksperimen skala penuh atau pemikiran. Tetapi Sudoku memberi kita peluang yang dapat kita gunakan baik untuk memahami masalah Sudoku yang sebenarnya, dan untuk menggambarkan pemodelan sebagai pendekatan umum untuk memecahkan masalah.

Salah satu model yang mungkin untuk masalah Sudoku adalah lembar kerja. Itu dibuat dengan hanya mengisi semua sel kosong (sel) dari tabel yang ditentukan dalam tugas dengan angka 123456789. Kemudian tugas dikurangi menjadi penghapusan berurutan dari semua digit tambahan dari sel sampai semua sel tabel terisi dengan satu (eksklusif) digit yang memenuhi kondisi masalah.

Saya membuat lembar kerja seperti itu di Excel. Pertama, saya memilih semua sel kosong (sel) dari tabel. Saya tekan F5-"Pilih"-"Sel kosong"-"OK". Cara yang lebih umum untuk memilih sel yang diinginkan: tahan Ctrl dan klik mouse untuk memilih sel ini. Kemudian untuk sel yang dipilih saya atur warnanya menjadi biru, ukuran 10 (asli - 12) dan font Arial Narrow. Ini semua agar perubahan selanjutnya dalam tabel terlihat jelas. Selanjutnya, saya memasukkan angka 123456789 ke dalam sel kosong, saya melakukannya sebagai berikut: Saya menulis dan menyimpan nomor ini di sel terpisah. Kemudian saya tekan F2, pilih dan salin nomor ini dengan operasi Ctrl + C. Selanjutnya, saya pergi ke sel tabel dan, secara berurutan melewati semua sel kosong, masukkan nomor 123456789 ke dalamnya menggunakan operasi Ctrl + V, dan lembar kerja sudah siap.

Nomor tambahan, yang akan dibahas nanti, saya hapus sebagai berikut. Dengan operasi Ctrl + klik mouse - Saya memilih sel dengan nomor tambahan. Lalu saya tekan Ctrl + H dan masukkan nomor yang akan dihapus di bidang atas jendela yang terbuka, dan bidang bawah harus benar-benar kosong. Kemudian tetap mengklik opsi "Ganti Semua" dan nomor tambahan dihapus.

Dilihat dari fakta bahwa saya biasanya berhasil melakukan pemrosesan tabel yang lebih maju dengan cara "dasar" yang biasa daripada dalam contoh yang diberikan di Internet, lembar kerja adalah alat paling sederhana dalam memecahkan masalah Sudoku. Selain itu, banyak situasi mengenai penerapan yang paling kompleks dari apa yang disebut aturan "dasar" tidak muncul di lembar kerja saya.

Pada saat yang sama, lembar kerja juga merupakan model di mana eksperimen dapat dilakukan dengan identifikasi selanjutnya dari semua aturan "dasar" dan berbagai nuansa penerapannya yang muncul dari eksperimen.

Jadi, sebelum Anda adalah bagian dari lembar kerja dengan sembilan blok, diberi nomor dari kiri ke kanan dan atas ke bawah. Dalam hal ini, kita memiliki blok keempat yang diisi dengan angka 123456789. Ini adalah model kami. Di luar blok, kami menyorot dengan warna merah nomor "diaktifkan" (akhirnya ditentukan), dalam hal ini, empat, yang ingin kami gantikan dalam tabel yang sedang disusun. The blue five adalah sosok yang belum ditentukan perannya di masa depan, yang akan kita bicarakan nanti. Angka-angka yang diaktifkan yang diberikan oleh kami, seolah-olah, mencoret, mendorong, menghapus - secara umum, mereka menggantikan angka yang sama di blok, sehingga mereka diwakili di sana dalam warna pucat, melambangkan fakta bahwa angka-angka pucat ini telah dihapus. Saya ingin membuat warna ini lebih pucat, tetapi kemudian mereka bisa menjadi sama sekali tidak terlihat saat dilihat di Internet.

Akibatnya, di blok keempat, di sel E5, ada satu, juga diaktifkan, tetapi disembunyikan empat. "Diaktifkan" karena dia, pada gilirannya, juga dapat menghapus digit tambahan jika sedang dalam perjalanan, dan "tersembunyi" karena dia berada di antara digit lainnya. Jika sel E5 diserang oleh yang lain, kecuali 4, nomor yang diaktifkan 12356789, maka penyendiri "telanjang" akan muncul di E5 - 4.

Sekarang mari kita hapus satu yang diaktifkan empat, misalnya dari F7. Kemudian empat di blok yang diisi bisa sudah dan hanya di sel E5 atau F5, sementara sisanya diaktifkan di baris 5. Jika lima yang diaktifkan terlibat dalam situasi ini, tanpa F7=4 dan F8=5, maka di sel E5 dan F5 ada akan menjadi pasangan aktif telanjang atau tersembunyi 45.

Setelah Anda cukup bekerja dan memahami pilihan yang berbeda dengan single telanjang dan tersembunyi, berpasangan, bertiga, dll. tidak hanya di blok, tetapi juga di baris dan kolom, kita dapat beralih ke eksperimen lain. Mari buat pasangan telanjang 45, seperti yang kita lakukan sebelumnya, lalu hubungkan F7=4 dan F8=5 yang diaktifkan. Akibatnya, situasi E5=45 akan terjadi. Situasi serupa sangat sering muncul dalam proses pemrosesan lembar kerja. Situasi ini berarti bahwa salah satu digit ini, dalam hal ini 4 atau 5, harus berada di blok, baris, dan kolom yang menyertakan sel E5, karena dalam semua kasus ini harus ada dua digit, bukan salah satunya.

Dan yang terpenting, sekarang kita sudah tahu seberapa sering situasi seperti E5=45 muncul. Dengan cara yang sama, kita akan mendefinisikan situasi ketika tiga digit muncul dalam satu sel, dll. Dan ketika kita membawa tingkat pemahaman dan persepsi situasi ini ke keadaan bukti diri dan kesederhanaan, maka langkah selanjutnya adalah, bisa dikatakan, pemahaman ilmiah tentang situasi: maka kita akan dapat melakukan analisis statistik dari Tabel Sudoku, mengidentifikasi pola dan menggunakan materi yang terkumpul untuk memecahkan masalah yang paling kompleks.

Jadi, dengan bereksperimen pada model, kami mendapatkan representasi visual dan bahkan "ilmiah" dari lajang, pasangan, kembar tiga yang tersembunyi atau terbuka, dll. Jika Anda membatasi diri Anda pada operasi dengan model sederhana yang dijelaskan, maka beberapa ide Anda akan menjadi tidak akurat atau bahkan salah. Namun, segera setelah Anda beralih ke pemecahan masalah tertentu, ketidakakuratan ide awal akan segera terungkap, tetapi model di mana eksperimen dilakukan harus dipikirkan kembali dan disempurnakan. Ini adalah jalur hipotesis dan penyempurnaan yang tak terhindarkan dalam memecahkan masalah apa pun.

Saya harus mengatakan bahwa lajang tersembunyi dan terbuka, serta pasangan terbuka, tiga kali lipat dan bahkan merangkak, adalah situasi umum yang muncul ketika memecahkan masalah Sudoku dengan lembar kerja. Pasangan tersembunyi jarang terjadi. Dan di sini adalah tiga kali lipat tersembunyi, merangkak, dll. Saya entah bagaimana tidak menemukan saat memproses lembar kerja, seperti metode untuk melewati kontur "x-wing" dan "swordfish" yang telah berulang kali dijelaskan di Internet, di mana ada "kandidat" untuk dihapus dengan salah satu dua cara alternatif untuk melewati kontur. Arti dari metode ini: jika kita menghancurkan "kandidat" x1, maka kandidat eksklusif x2 tetap dan pada saat yang sama kandidat x3 dihapus, dan jika kita menghancurkan x2, maka x1 eksklusif tetap, tetapi dalam kasus ini kandidat x3 juga dihapus, jadi bagaimanapun juga, x3 harus dihapus , tanpa mempengaruhi kandidat x1 dan x2 untuk saat ini. Lebih umum, ini adalah kasus khusus dari situasi: jika dua cara alternatif menghasilkan hasil yang sama, maka hasil ini dapat digunakan untuk memecahkan masalah Sudoku. Dalam situasi yang lebih umum ini, saya bertemu situasi, tetapi tidak dalam varian "sayap-x" dan "ikan pedang" dan tidak ketika memecahkan masalah Sudoku, yang pengetahuannya hanya tentang pendekatan "dasar" sudah cukup.

Fitur menggunakan lembar kerja dapat diperlihatkan dalam contoh non-sepele berikut. Di salah satu forum pemecah sudoku http://zforum.net/index.php?topic=3955.25;wap2 saya menemukan masalah yang disajikan sebagai salah satu masalah sudoku yang paling sulit, tidak dapat dipecahkan dengan cara biasa, tanpa menggunakan enumerasi dengan asumsi tentang nomor diganti dalam sel. Mari kita tunjukkan bahwa dengan tabel kerja dimungkinkan untuk menyelesaikan masalah ini tanpa enumerasi seperti itu:

Di sebelah kanan adalah tugas asli, di sebelah kiri adalah meja kerja setelah "penghapusan", mis. operasi rutin untuk menghilangkan digit tambahan.

Pertama, mari kita sepakati notasi. ABC4=689 berarti sel A4, B4 dan C4 berisi angka 6, 8 dan 9 - satu atau lebih digit per sel. Sama halnya dengan string. Jadi, B56=24 berarti sel B5 dan B6 berisi angka 2 dan 4. Tanda ">" adalah tanda tindakan bersyarat. Jadi, D4=5>I4-37 berarti karena pesan D4=5, angka 37 harus ditempatkan di sel I4. Pesannya bisa eksplisit - "telanjang" - dan tersembunyi, yang harus diungkapkan. Dampak pesan dapat berurutan (ditransmisikan secara tidak langsung) sepanjang rantai dan paralel (bertindak langsung pada sel lain). Sebagai contoh:

D3=2; D8=1>A9-1>A2-2>A3-4,G9-3; (D8=1)+(G9=3)>G8-7>G7-1>G5-5

Entri ini berarti D3=2, tetapi fakta ini perlu diungkapkan. D8=1 meneruskan aksinya pada rantai ke A3 dan 4 harus ditulis ke A3; pada saat yang sama, D3=2 bekerja langsung pada G9, menghasilkan G9-3. (D8=1)+(G9=3)>G8-7 – gabungan pengaruh faktor (D8=1) dan (G9=3) menghasilkan G8-7. Dll.

Catatan juga dapat berisi kombinasi tipe H56/68. Artinya angka 6 dan 8 dilarang di sel H5 dan H6, yaitu. mereka harus dikeluarkan dari sel-sel ini.

Jadi, kami mulai bekerja dengan tabel dan sebagai permulaan kami menerapkan kondisi ABC4=689 yang termanifestasi dengan baik. Ini berarti bahwa di semua sel lain (kecuali A4, B4 dan C4) dari blok 4 (tengah, kiri) dan baris ke-4, angka 6, 8 dan 9 harus dihapus:

Terapkan B56=24 dengan cara yang sama. Bersama-sama kita memiliki D4=5 dan (setelah D4=5>I4-37) HI4=37, dan juga (setelah B56=24>C6-1) C6=1. Mari kita terapkan ini ke lembar kerja:

Di I89=68hidden>I56/68>H56-68: mis. sel I8 dan I9 berisi pasangan tersembunyi dari angka 5 dan 6, yang melarang angka-angka ini berada di I56, menghasilkan hasil H56-68. Kita dapat mempertimbangkan fragmen ini dengan cara yang berbeda, seperti yang kita lakukan dalam percobaan pada model lembar kerja: (G23=68)+(AD7=68)>I89-68; (I89=68)+(ABC4=689)>H56-68. Artinya, "serangan" dua arah (G23=68) dan (AD7=68) mengarah pada fakta bahwa hanya angka 6 dan 8 yang dapat berada di I8 dan I9. Selanjutnya (I89=68) dihubungkan ke " menyerang" pada H56 bersama dengan kondisi sebelumnya, yang mengarah ke H56-68. Selain "serangan" ini terhubung (ABC4=689), yang dalam contoh ini terlihat berlebihan, namun, jika kita bekerja tanpa meja kerja, maka faktor dampak (ABC4=689) akan disembunyikan, dan itu akan cukup tepat untuk memperhatikannya secara khusus.

Tindakan selanjutnya: I5=2>G1-2,G6-9,B6-4,B5-2.

Saya harap sudah jelas tanpa komentar: ganti angka yang datang setelah tanda hubung, Anda tidak bisa salah:

H7=9>I7-4; D6=8>D1-4,H6-6>H5-8:

Rangkaian aksi selanjutnya:

D3=2; D8=1>A9-1>A2-2>A3-4,G9-3;

(D8=1)+(G9=3)>G8-7>G7-1>G5-5;

D5=9>E5-6>F5-4:

I=4>C9-4>C7-2>E9-2>EF7-35>B7-7,F89-89,

yaitu, sebagai hasil dari "mencoret" - menghapus digit tambahan - pasangan terbuka, "telanjang" 89 muncul di sel F8 dan F9, yang, bersama dengan hasil lain yang ditunjukkan dalam catatan, kami terapkan ke tabel:

H2=4>H3-1>F2-1>F1-6>A1-3>B8-3,C8-5,H1-7>I2-5>I3-3>I4-7>H4-3

Hasil mereka:

Ini diikuti oleh tindakan yang cukup rutin dan jelas:

H1=7>C1-8>E1-5>F3-7>E2-9>E3-8,C3-9>B3-5>B2-6>C2-7>C4-6>A4-9>B4- 8;

B2=6>B9-9>A8-6>I8-8>F8-9>F9-8>I9-6;

E7=3>F7-5,E6-7>F6-3

Hasil mereka: solusi akhir dari masalah:

Dengan satu atau lain cara, kami akan berasumsi bahwa kami menemukan metode "dasar" di Sudoku atau di bidang aplikasi intelektual lainnya berdasarkan model yang cocok untuk ini dan bahkan belajar bagaimana menerapkannya. Tapi ini hanya bagian dari kemajuan kami dalam metodologi pemecahan masalah. Selanjutnya, saya ulangi, berikut tidak selalu diperhitungkan, tetapi tahap yang sangat diperlukan untuk membawa metode yang dipelajari sebelumnya ke keadaan kemudahan penerapannya. Memecahkan contoh, memahami hasil dan metode solusi ini, memikirkan kembali materi ini berdasarkan model yang diterima, sekali lagi memikirkan semua opsi, membawa tingkat pemahaman mereka ke otomatisitas, ketika solusi menggunakan ketentuan "dasar" menjadi rutin dan menghilang sebagai masalah. Apa yang diberikannya: setiap orang harus merasakannya berdasarkan pengalaman mereka sendiri. Dan pada intinya ketika situasi masalah menjadi rutinitas, mekanisme pencarian akal diarahkan pada pengembangan ketentuan yang semakin kompleks di bidang masalah yang dipecahkan.

Dan apa itu "ketentuan yang lebih kompleks"? Ini hanyalah ketentuan "dasar" baru dalam memecahkan masalah, pemahaman yang, pada gilirannya, juga dapat dibawa ke keadaan sederhana jika model yang cocok ditemukan untuk tujuan ini.

Dalam artikel Vasilenko S.L. "Numeric Harmony Sudoku" Saya menemukan contoh masalah dengan 18 kunci simetris:

Mengenai tugas ini, dinyatakan bahwa itu dapat diselesaikan dengan menggunakan metode "dasar" hanya hingga keadaan tertentu, setelah mencapai itu tetap hanya menerapkan pencacahan sederhana dengan substitusi percobaan ke dalam sel-sel dari beberapa yang seharusnya eksklusif (tunggal, tunggal ) angka. Keadaan ini (maju sedikit lebih jauh daripada dalam contoh Vasilenko) terlihat seperti:

Ada model seperti itu. Ini adalah semacam mekanisme rotasi untuk digit eksklusif (tunggal) yang teridentifikasi dan tidak teridentifikasi. Dalam kasus yang paling sederhana, beberapa tiga digit eksklusif berputar ke arah kanan atau kiri, melewati grup ini dari baris ke baris atau dari kolom ke kolom. Secara umum, pada saat yang sama, tiga kelompok angka tiga kali lipat berputar dalam satu arah. Dalam kasus yang lebih kompleks, tiga pasang angka eksklusif berputar dalam satu arah, dan tiga kali lipat angka tunggal berputar ke arah yang berlawanan. Jadi, misalnya, digit eksklusif dalam tiga baris pertama dari masalah yang dipertimbangkan diputar. Dan yang terpenting, rotasi semacam ini dapat dilihat dengan mempertimbangkan letak angka pada lembar kerja yang diproses. Informasi ini cukup untuk saat ini, dan kami akan memahami nuansa lain dari model rotasi dalam proses penyelesaian masalah.

Jadi, pada tiga baris pertama (atas) (1, 2 dan 3) kita dapat melihat rotasi pasangan (3+8) dan (7+9), serta (2+x1) dengan x1 yang tidak diketahui dan triple single (x2+4+ 1) dengan x2 yang tidak diketahui. Dengan demikian, kita dapat menemukan bahwa masing-masing x1 dan x2 dapat berupa 5 atau 6.

Baris 4, 5 dan 6 melihat pasangan (2+4) dan (1+3). Juga harus ada pasangan yang tidak diketahui ke-3 dan triple dari single yang hanya satu digit 5 yang diketahui.

Demikian pula, kita melihat baris 789, kemudian triplet kolom ABC, DEF dan GHI. Kami akan menuliskan informasi yang dikumpulkan dalam bentuk simbolis dan, saya harap, cukup dapat dimengerti:

Sejauh ini, kami membutuhkan informasi ini hanya untuk memahami situasi umum. Pikirkan baik-baik dan kemudian kita dapat melangkah lebih jauh ke tabel berikut yang disiapkan khusus untuk ini:

Saya menyoroti alternatif dengan warna. Biru berarti "diperbolehkan" dan kuning berarti "dilarang". Jika, katakanlah, diperbolehkan di A2=79 diperbolehkan A2=7, maka C2=7 dilarang. Atau sebaliknya – diperbolehkan A2=9, dilarang C2=9. Dan kemudian izin dan larangan ditransmisikan sepanjang rantai logis. Pewarnaan ini dilakukan agar lebih mudah untuk melihat alternatif yang berbeda. Secara umum, ini adalah analogi dari metode "x-wing" dan "swordfish" yang disebutkan sebelumnya saat memproses tabel.

Melihat opsi B6=7 dan, masing-masing, B7=9, kita dapat segera menemukan dua titik yang tidak sesuai dengan opsi ini. Jika B7=9, maka pada baris 789 terjadi rangkap tiga yang berotasi serempak, yang tidak dapat diterima, karena hanya tiga pasang (dan tiga pasang tunggal secara asinkron) atau tiga rangkap (tanpa tunggal) dapat berotasi secara serempak (dalam satu arah). Selain itu, jika B7=9, maka setelah beberapa langkah pengolahan lembar kerja pada baris ke-7 kita akan menemukan ketidaksesuaian: B7=D7=9. Jadi kami mengganti satu-satunya yang dapat diterima dari dua alternatif B6=9, dan kemudian masalahnya diselesaikan dengan cara sederhana pemrosesan konvensional tanpa pencacahan buta:

Selanjutnya, saya memiliki contoh siap pakai menggunakan model rotasi untuk menyelesaikan masalah dari Kejuaraan Sudoku Dunia, tetapi saya menghilangkan contoh ini agar tidak terlalu meregangkan artikel ini. Selain itu, ternyata, masalah ini memiliki tiga solusi, yang kurang cocok untuk pengembangan awal model rotasi digit. Saya juga banyak menggeledah masalah 17-kunci Gary McGuire yang diambil dari Internet untuk memecahkan teka-tekinya, sampai, dengan lebih jengkel, saya menemukan bahwa "teka-teki" ini memiliki lebih dari 9 ribu solusi.

Jadi, mau tidak mau, kita harus beralih ke masalah Sudoku "paling sulit di dunia" yang dikembangkan oleh Arto Inkala, yang, seperti yang Anda tahu, memiliki solusi unik.

Setelah memasukkan dua nomor eksklusif yang cukup jelas dan memproses lembar kerja, tugasnya terlihat seperti ini:

Kunci yang ditetapkan untuk masalah asli disorot dalam font hitam dan lebih besar. Untuk bergerak maju dalam memecahkan masalah ini, kita harus kembali mengandalkan model yang memadai yang cocok untuk tujuan ini. Model ini adalah semacam mekanisme untuk memutar angka. Ini telah dibahas lebih dari sekali di artikel ini dan sebelumnya, tetapi untuk memahami materi artikel lebih lanjut, mekanisme ini harus dipikirkan dan dikerjakan secara rinci. Kira-kira seolah-olah Anda telah bekerja dengan mekanisme seperti itu selama sepuluh tahun. Tetapi Anda akan tetap dapat memahami materi ini, jika bukan dari bacaan pertama, kemudian dari bacaan kedua atau ketiga, dst. Selain itu, jika Anda bertahan, maka Anda akan membawa materi yang "sulit dipahami" ini ke keadaan rutin dan sederhana. Tidak ada yang baru dalam hal ini: apa yang sangat sulit pada awalnya, secara bertahap menjadi tidak begitu sulit, dan dengan elaborasi lebih lanjut, semuanya menjadi yang paling jelas dan tidak memerlukan upaya mental di tempat yang tepat, setelah itu Anda dapat membebaskan mental Anda. potensi untuk kemajuan lebih lanjut pada masalah yang sedang dipecahkan atau masalah lain.

Analisis yang cermat terhadap struktur masalah Arto Incal menunjukkan bahwa seluruh masalah dibangun di atas prinsip tiga pasangan yang berotasi sinkron dan rangkap tiga dari pasangan tunggal yang berotasi asinkron: (x1+x2)+(x3+x4)+(x5+ x6)+(x7+x8+ x9). Urutan rotasi dapat, misalnya, sebagai berikut: pada tiga baris pertama 123, pasangan pertama (x1+x2) bergerak dari baris pertama blok pertama ke baris kedua dari blok kedua, lalu ke baris ketiga garis blok ketiga. Pasangan kedua melompat dari baris kedua balok pertama ke baris ketiga balok kedua, kemudian, dalam putaran ini, melompat ke baris pertama balok ketiga. Pasangan ketiga dari baris ketiga balok pertama melompat ke baris pertama balok kedua dan kemudian, dengan arah putaran yang sama, melompat ke baris kedua balok ketiga. Trio tunggal bergerak dalam pola rotasi yang sama, tetapi dalam arah yang berlawanan dengan pasangan. Situasi dengan kolom terlihat serupa: jika tabel secara mental (atau sebenarnya) diputar 90 derajat, maka baris akan menjadi kolom, dengan karakter gerakan tunggal dan berpasangan yang sama seperti sebelumnya untuk baris.

Mengubah rotasi ini dalam pikiran kami sehubungan dengan masalah Arto Incal, kami secara bertahap memahami batasan yang jelas pada pilihan varian rotasi ini untuk tiga baris atau kolom yang dipilih:

Seharusnya tidak ada tiga dan pasangan yang berputar secara serempak (dalam satu arah) - tiga kali lipat seperti itu, berbeda dengan tiga kali lipat tunggal, akan disebut kembar tiga di masa depan;

Tidak boleh ada pasangan asinkron satu sama lain atau tunggal asinkron satu sama lain;

Seharusnya tidak ada pasangan dan tunggal yang berputar ke arah yang sama (misalnya, kanan) - ini adalah pengulangan dari pembatasan sebelumnya, tetapi mungkin tampak lebih dapat dimengerti.

Selain itu, ada batasan lain:

Tidak boleh ada satu pasangan di 9 baris yang cocok dengan pasangan di salah satu kolom dan sama untuk kolom dan baris. Ini harus jelas: karena fakta bahwa dua angka berada pada baris yang sama menunjukkan bahwa mereka berada di kolom yang berbeda.

Anda juga dapat mengatakan bahwa sangat jarang ada kecocokan pasangan dalam tiga kali lipat baris yang berbeda atau kecocokan serupa dalam tiga kali lipat kolom, dan juga jarang ada kecocokan tiga kali lipat tunggal dalam baris dan / atau kolom, tetapi ini, sehingga untuk berbicara , pola probabilistik.

Blok penelitian 4,5,6.

Di blok 4-6, pasangan (3+7) dan (3+9) dimungkinkan. Jika kita menerima (3+9), maka kita mendapatkan rotasi sinkron yang tidak valid dari triplet (3+7+9), jadi kita memiliki pasangan (7+3). Setelah mengganti pasangan ini dan pemrosesan tabel selanjutnya dengan cara konvensional, kami mendapatkan:

Pada saat yang sama, kita dapat mengatakan bahwa 5 di B6=5 hanya bisa penyendiri, asinkron (7+3), dan 6 di I5=6 adalah paragenerator, karena berada di baris yang sama H5=5 di keenam blok dan, oleh karena itu, tidak dapat sendiri dan hanya dapat bergerak sinkron dengan (7+3.

dan urutkan para calon jomblo berdasarkan jumlah penampilannya dalam peran ini di tabel ini:

Jika kita menerima bahwa 2, 4 dan 5 yang paling sering adalah tunggal, maka menurut aturan rotasi, hanya pasangan yang dapat digabungkan dengan mereka: (7 + 3), (9 + 6) dan (1 + 8) - a pasangan (1 + 9) dibuang karena meniadakan pasangan (9+6). Selanjutnya, setelah mengganti pasangan dan tunggal ini dan memproses lebih lanjut tabel menggunakan metode konvensional, kami mendapatkan:

Tabel bandel seperti itu ternyata - tidak ingin diproses sampai akhir.

Anda harus memaksakan diri dan perhatikan bahwa ada pasangan (7 + 4) di kolom ABC dan 6 bergerak serentak dengan 7 di kolom ini, oleh karena itu 6 adalah pasangan, jadi hanya kombinasi (6 + 3) yang mungkin di kolom "C" dari blok ke-4 +8 atau (6+8)+3. Yang pertama dari kombinasi ini tidak berfungsi, karena kemudian di blok ke-7 di kolom "B" akan muncul triple sinkron yang tidak valid - triplet (6 + 3 + 8). Nah, kemudian, setelah mengganti opsi (6 + 8) + 3 dan memproses tabel dengan cara biasa, kita sampai pada penyelesaian tugas yang berhasil.

Opsi kedua: mari kembali ke tabel yang diperoleh setelah mengidentifikasi kombinasi (7 + 3) + 5 pada baris 456 dan melanjutkan ke studi kolom ABC.

Di sini kita dapat melihat bahwa pasangan (2+9) tidak dapat terjadi di ABC. Kombinasi lain (2+4), (2+7), (9+4) dan (9+7) memberikan triple sinkron - triplet di A4+A5+A6 dan B1+B2+B3, yang tidak dapat diterima. Tetap ada satu pasangan yang dapat diterima (7+4). Selain itu, 6 dan 5 bergerak secara serempak 7, yang berarti mereka membentuk uap, mis. membentuk beberapa pasangan, tetapi tidak 5 + 6.

Mari kita buat daftar kemungkinan pasangan dan kombinasinya dengan single:

Kombinasi (6+3)+8 tidak berfungsi, karena jika tidak, triple-triplet yang tidak valid terbentuk dalam satu kolom (6 + 3 + 8), yang telah dibahas dan yang dapat kami verifikasi sekali lagi dengan memeriksa semua opsi. Dari calon tunggal, nomor 3 mencetak poin terbanyak, dan kemungkinan besar dari semua kombinasi di atas: (6 + 8) + 3, yaitu. (C4=6 + C5=8) + C6=3, yang memberikan:

Selanjutnya, kandidat yang paling mungkin untuk single adalah 2 atau 9 (masing-masing 6 poin), tetapi dalam kasus ini, kandidat 1 (4 poin) tetap valid. Mari kita mulai dengan (5+29)+1, di mana 1 asinkron dengan 5, mis. letakkan 1 dari B5=1 sebagai singleton asinkron di semua kolom ABC:

Di blok 7, kolom A, hanya opsi (5+9)+3 dan (5+2)+3 yang mungkin. Tetapi lebih baik kita memperhatikan fakta bahwa pada baris 1-3 pasangan (4 + 5) dan (8 + 9) sekarang telah muncul. Pergantian mereka mengarah pada hasil yang cepat, yaitu. hingga penyelesaian tugas setelah tabel diproses dengan cara normal.

Nah, sekarang, setelah berlatih pada opsi sebelumnya, kita dapat mencoba menyelesaikan masalah Arto Incal tanpa melibatkan perkiraan statistik.

Kami kembali ke posisi awal lagi:

Di blok 4-6, pasangan (3+7) dan (3+9) dimungkinkan. Jika kami menerima (3 + 9), maka kami mendapatkan rotasi sinkron yang tidak valid dari triplet (3 + 7 + 9), jadi untuk substitusi dalam tabel kami hanya memiliki opsi (7 + 3):

5 di sini, seperti yang kita lihat, adalah penyendiri, 6 adalah paraformer. Opsi yang valid di ABC5: (2+1)+8, (2+1)+9, (8+1)+9, (8+1)+2, (9+1)+8, (9+1) +2. Tetapi (2+1) asinkron dengan (7+3), jadi ada (8+1)+9, (8+1)+2, (9+1)+8, (9+1)+2. Bagaimanapun, 1 adalah sinkron (7 + 3) dan, oleh karena itu, paragenerasi. Mari kita substitusikan 1 dalam kapasitas ini ke dalam tabel:

Angka 6 di sini adalah paragenerator di bl. 4-6, tetapi pasangan mencolok (6+4) tidak ada dalam daftar pasangan yang valid. Oleh karena itu quad di A4=4 adalah asynchronous 6:

Karena D4+E4=(8+1) dan menurut analisis rotasi membentuk pasangan ini, kita mendapatkan:

Jika sel C456=(6+3)+8, maka B789=683, mis. kita mendapatkan triple-triplet sinkron, jadi kita dibiarkan dengan opsi (6+8)+3 dan hasil substitusinya:

B2=3 tunggal di sini, C1=5 (asynchronous 3) adalah pasangan, A2=8 juga pasangan. B3=7 bisa sinkron dan asinkron. Sekarang kita bisa membuktikan diri dalam trik yang lebih kompleks. Dengan mata yang terlatih (atau setidaknya saat memeriksa di komputer), kami melihat bahwa untuk status apa pun B3=7 - sinkron atau asinkron - kami mendapatkan hasil yang sama A1=1. Oleh karena itu, kita dapat mengganti nilai ini menjadi A1 dan kemudian menyelesaikan tugas kita, atau lebih tepatnya Arto Incala, dengan cara sederhana yang lebih biasa:

Dengan satu atau lain cara, kami dapat mempertimbangkan dan bahkan menggambarkan tiga pendekatan umum untuk memecahkan masalah: menentukan titik pemahaman masalah (bukan hipotetis atau dinyatakan secara membabi buta, tetapi momen nyata, mulai dari mana kita dapat berbicara tentang memahami masalah. ), pilih model yang memungkinkan kita untuk mewujudkan pemahaman melalui eksperimen alami atau mental dan - ketiga - untuk membawa tingkat pemahaman dan persepsi hasil yang dicapai dalam kasus ini ke keadaan bukti diri dan kesederhanaan. Ada juga pendekatan keempat, yang saya pribadi gunakan.

Setiap orang memiliki keadaan ketika tugas intelektual dan masalah yang dihadapinya diselesaikan dengan lebih mudah daripada biasanya. Negara-negara ini cukup dapat direproduksi. Untuk melakukan ini, Anda perlu menguasai teknik mematikan pikiran. Pada awalnya, setidaknya untuk sepersekian detik, kemudian, semakin lama semakin meregangkan momen pemutusan ini. Saya tidak bisa mengatakan lebih jauh, atau lebih tepatnya merekomendasikan, sesuatu dalam hal ini, karena durasi penerapan metode ini adalah masalah pribadi semata. Tetapi saya menggunakan metode ini kadang-kadang untuk waktu yang lama, ketika masalah muncul di depan saya, di mana saya tidak melihat pilihan untuk bagaimana hal itu dapat didekati dan diselesaikan. Akibatnya, cepat atau lambat, prototipe model yang sesuai muncul dari gudang memori, yang menjelaskan esensi dari apa yang perlu diselesaikan.

Saya memecahkan masalah Incal dengan beberapa cara, termasuk yang dijelaskan di artikel sebelumnya. Dan selalu dalam satu atau lain cara saya menggunakan pendekatan keempat ini dengan mematikan dan selanjutnya konsentrasi upaya mental. Saya mendapatkan solusi tercepat untuk masalah ini dengan enumerasi sederhana - apa yang disebut "metode poke" - namun, hanya menggunakan opsi "panjang": opsi yang dapat dengan cepat menghasilkan hasil positif atau negatif. Opsi lain membutuhkan lebih banyak waktu dari saya, karena sebagian besar waktu dihabiskan setidaknya untuk pengembangan kasar teknologi untuk menerapkan opsi ini.

Pilihan yang baik juga dalam semangat pendekatan keempat: mendengarkan untuk memecahkan masalah Sudoku, mengganti hanya satu digit per sel dalam proses memecahkan masalah. Artinya, sebagian besar tugas dan datanya "digulir" dalam pikiran. Ini adalah bagian utama dari proses pemecahan masalah intelektual, dan keterampilan ini harus dilatih untuk meningkatkan kemampuan Anda dalam memecahkan masalah. Misalnya, saya bukan pemecah Sudoku profesional. Saya punya tugas lain. Tetapi, bagaimanapun, saya ingin menetapkan sendiri tujuan berikut: untuk memperoleh kemampuan untuk memecahkan masalah Sudoku dengan kompleksitas yang meningkat, tanpa lembar kerja dan tanpa menggunakan lebih dari satu nomor ke dalam satu sel kosong. Dalam hal ini, cara apa pun untuk menyelesaikan Sudoku diperbolehkan, termasuk enumerasi opsi yang sederhana.

Bukan kebetulan bahwa saya mengingat enumerasi opsi di sini. Setiap pendekatan untuk memecahkan masalah Sudoku melibatkan serangkaian metode tertentu dalam gudang senjatanya, termasuk satu atau beberapa jenis enumerasi. Selain itu, salah satu metode yang digunakan di Sudoku khususnya atau dalam memecahkan masalah lain memiliki area penerapannya sendiri yang efektif. Jadi, ketika memecahkan masalah Sudoku yang relatif sederhana, yang paling efektif adalah metode "dasar" sederhana yang dijelaskan dalam banyak artikel tentang topik ini di Internet, dan "metode rotasi" yang lebih kompleks sering tidak berguna di sini, karena hanya memperumit jalannya solusi sederhana dan pada saat yang sama apa -tidak memberikan informasi baru yang muncul dalam proses pemecahan masalah. Tetapi dalam kasus yang paling sulit, seperti masalah Arto Incal, "metode rotasi" dapat memainkan peran kunci.

Sudoku dalam artikel saya hanyalah contoh ilustrasi pendekatan untuk pemecahan masalah. Di antara masalah yang telah saya pecahkan, ada juga urutan besarnya yang lebih sulit daripada Sudoku. Misalnya, model komputer boiler dan turbin yang terletak di situs web kami. Saya juga tidak keberatan membicarakan mereka. Tetapi untuk saat ini, saya telah memilih Sudoku untuk menunjukkan kepada rekan-rekan muda saya dengan cara yang agak visual tentang cara dan tahapan yang mungkin untuk bergerak menuju tujuan akhir dari masalah yang dipecahkan.

Itu saja untuk hari ini.

VKontakte Facebook Odnoklassniki

Bagi mereka yang suka memecahkan teka-teki Sudoku sendiri dan lambat, formula yang memungkinkan Anda menghitung jawaban dengan cepat mungkin tampak seperti pengakuan kelemahan atau kecurangan.

Tetapi bagi mereka yang menganggap Sudoku terlalu sulit untuk dipecahkan, ini bisa menjadi solusi yang tepat.

Dua peneliti telah mengembangkan algoritme matematika yang memungkinkan Anda menyelesaikan Sudoku dengan sangat cepat, tanpa menebak-nebak atau mundur.

Peneliti jaringan kompleks Zoltan Torozhkai dan Maria Erksi-Ravaz dari Universitas Notre Dame juga dapat menjelaskan mengapa beberapa teka-teki Sudoku lebih sulit daripada yang lain. Satu-satunya downside adalah bahwa Anda memerlukan gelar PhD dalam Matematika untuk memahami apa yang mereka tawarkan.

Bisakah kamu memecahkan teka-teki ini? Dibuat oleh matematikawan Arto Incala, Sudoku diklaim sebagai Sudoku tersulit di dunia. Foto dari nature.com

Torozhkai dan Erksi-Rawaz mulai menganalisis Sudoku sebagai bagian dari penelitian mereka tentang teori optimasi dan kompleksitas komputasi. Mereka mengatakan bahwa sebagian besar penggemar Sudoku menggunakan pendekatan brute force berdasarkan tebakan untuk memecahkan masalah ini. Jadi, pecinta Sudoku mempersenjatai diri dengan pensil dan mencoba semua kemungkinan kombinasi angka sampai jawaban yang benar ditemukan. Metode ini pasti akan mengarah pada kesuksesan, tetapi melelahkan dan memakan waktu.

Sebaliknya, Torozhkai dan Erksi-Ravaz mengusulkan algoritma analog universal yang benar-benar deterministik (tidak menggunakan tebakan atau penghitungan) dan selalu menemukan solusi yang tepat untuk masalah, dan cukup cepat.

Para peneliti menggunakan "pemecah analog deterministik" untuk menyelesaikan sudoku ini. Foto dari nature.com

Para peneliti juga menemukan bahwa waktu yang dibutuhkan untuk memecahkan teka-teki menggunakan algoritma analog mereka berkorelasi dengan tingkat kesulitan tugas, seperti yang dinilai oleh orang tersebut. Ini mengilhami mereka untuk mengembangkan skala peringkat untuk kesulitan teka-teki atau masalah.

Mereka menciptakan skala dari 1 hingga 4, di mana 1 adalah "mudah", 2 adalah "rata-rata", 3 adalah "sulit", 4 adalah "sangat sulit". Teka-teki dengan peringkat 2 membutuhkan waktu rata-rata 10 kali lebih lama untuk dipecahkan daripada teka-teki dengan peringkat 1. Menurut sistem ini, teka-teki tersulit yang diketahui sejauh ini memiliki peringkat 3,6; teka-teki Sudoku yang lebih kompleks belum diketahui.

Teori dimulai dengan pemetaan probabilitas untuk setiap kotak individu. Foto dari nature.com

“Saya tidak tertarik pada Sudoku sampai kami mulai mengerjakan kelas kepuasan umum dari masalah Boolean,” kata Torozhkay. - Karena Sudoku adalah bagian dari kelas ini, bujur sangkar Latin urutan ke-9 ternyata menjadi bidang yang bagus untuk kita uji, jadi aku mengenal mereka. Saya dan banyak peneliti yang mempelajari masalah seperti itu terpesona oleh pertanyaan tentang seberapa jauh kita manusia dapat menyelesaikan Sudoku, secara deterministik, tanpa penghilang, yang merupakan pilihan acak, dan jika tebakan tidak benar, Anda harus kembali langkah atau beberapa langkah dan mulai dari awal. Model keputusan analog kami bersifat deterministik: tidak ada pilihan acak atau pengulangan dalam dinamika.”

Teori Chaos: Tingkat kerumitan teka-teki ditampilkan di sini sebagai dinamika yang kacau. Foto dari nature.com

Torozhkai dan Erksi-Ravaz percaya bahwa algoritma analog mereka memiliki potensi untuk diterapkan pada berbagai masalah dalam industri, ilmu komputer, dan biologi komputasi.

Pengalaman penelitian juga membuat Torozhkay menjadi penggemar berat Sudoku.

“Saya dan istri saya memiliki beberapa aplikasi Sudoku di iPhone kami dan kami pasti sudah bermain ribuan kali, bersaing dalam waktu yang lebih singkat di setiap level,” katanya. - Dia sering secara intuitif melihat kombinasi pola yang tidak saya perhatikan. Aku harus membawa mereka keluar. Menjadi tidak mungkin bagi saya untuk memecahkan banyak teka-teki yang dikategorikan skala kami sebagai sulit atau sangat sulit tanpa menulis probabilitas dengan pensil.”

Metodologi Torozhkay dan Erksi-Ravaz pertama kali diterbitkan di Nature Physics dan kemudian di Nature Scientific Reports.

Gunakan angka dari 1 hingga 9

Sudoku dimainkan di grid 9 kali 9, dengan total 81 grid. Di dalam lapangan bermain ada 9 "kotak" (terdiri dari 3 x 3 sel). Setiap baris horizontal, kolom vertikal, dan kotak (masing-masing 9 sel) harus diisi dengan angka 1-9, tanpa mengulang angka pada baris, kolom, atau kotak. Apakah itu terdengar rumit? Seperti yang Anda lihat dari gambar di bawah, setiap lapangan permainan Sudoku memiliki beberapa sel yang sudah terisi. Semakin banyak sel yang awalnya diisi, semakin mudah permainannya. Semakin sedikit sel yang awalnya diisi, semakin sulit permainannya.

Jangan ulangi angka apa pun

Seperti yang Anda lihat, kotak kiri atas (dilingkari dengan warna biru) telah mengisi 7 dari 9 sel. Satu-satunya angka yang hilang dari kotak ini adalah angka 5 dan 6. Dengan melihat angka mana yang hilang dari setiap kotak, baris, atau kolom, kita dapat menggunakan proses eliminasi dan penalaran deduktif untuk memutuskan angka mana yang harus ada di setiap sel .

Misalnya, di kotak kiri atas, kita tahu bahwa untuk melengkapi kotak kita perlu menambahkan angka 5 dan 6, tetapi melihat baris dan kotak yang berdekatan, kita masih tidak dapat dengan jelas menentukan angka mana yang akan ditambahkan ke sel mana. Ini berarti bahwa kita sekarang harus melewati kotak kiri atas untuk saat ini dan sebagai gantinya mencoba mengisi celah di beberapa tempat lain di lapangan permainan.

Tidak perlu menebak

Sudoku adalah permainan logika, jadi tidak perlu menebak. Jika Anda tidak tahu nomor apa yang harus dimasukkan ke dalam sel tertentu, teruslah memindai area lain dari lapangan permainan sampai Anda melihat opsi untuk memasukkan nomor yang diinginkan. Tapi jangan mencoba untuk "memaksa" apa pun - Sudoku menghargai kesabaran, pemahaman, dan penyelesaian berbagai kombinasi, bukan keberuntungan buta atau tebakan.

Gunakan metode eliminasi

Apa yang kita lakukan ketika kita menggunakan "metode eliminasi" dalam permainan Sudoku? Berikut adalah contoh. Dalam kisi Sudoku ini (ditunjukkan di bawah), hanya beberapa angka yang hilang di kolom vertikal kiri (dilingkari dengan warna biru): 1, 5, dan 6.

Salah satu cara untuk mengetahui angka apa yang bisa muat di setiap sel adalah dengan menggunakan "metode eliminasi" dengan memeriksa angka lain yang sudah ada di setiap kotak, karena angka 1-9 tidak boleh digandakan di setiap kotak, baris, atau kolom.

Dalam hal ini, kita dapat dengan cepat melihat bahwa sudah ada angka 1 di kotak kiri atas dan kiri tengah (angka 1 dilingkari merah). Artinya hanya ada satu tempat di kolom paling kiri yang bisa disisipkan angka 1 (dilingkari hijau). Beginilah cara kerja metode eliminasi di Sudoku - Anda mengetahui sel mana yang bebas, angka mana yang hilang, dan kemudian menghilangkan angka yang sudah ada di kotak, kolom, dan baris. Dengan demikian, isi sel kosong dengan nomor yang hilang.

Aturan Sudoku relatif tidak rumit - tetapi permainannya sangat bervariasi, dengan jutaan kemungkinan kombinasi angka dan berbagai tingkat kesulitan. Tapi itu semua berdasarkan prinsip sederhana menggunakan angka 1-9, mengisi kekosongan berdasarkan pemikiran deduktif, dan tidak pernah mengulang angka di setiap kotak, baris, atau kolom.

tutorial

1. Dasar-dasar

Sebagian besar dari kita para peretas tahu apa itu sudoku. Saya tidak akan berbicara tentang aturan, tetapi segera beralih ke metode.
Untuk memecahkan teka-teki, tidak peduli seberapa rumit atau sederhana, sel-sel yang jelas untuk diisi pada awalnya dicari.

1.1 "Pahlawan Terakhir"

Pertimbangkan kotak ketujuh. Hanya empat sel bebas, jadi sesuatu dapat diisi dengan cepat.
"8 " pada D3 blok bantalan H3 Dan J3; serupa " 8 " pada G5 tutup G1 Dan G2
Dengan hati nurani yang bersih kami menempatkan " 8 " pada H1

1.2 "Pahlawan Terakhir" berturut-turut

Setelah melihat kotak untuk solusi yang jelas, lanjutkan ke kolom dan baris.
Mempertimbangkan " 4 " di lapangan. Jelas bahwa itu akan berada di suatu tempat di garis SEBUAH .
Kita punya " 4 " pada G3 yang mencakup A3, makan " 4 " pada F7, membersihkan A7. Dan satu lagi" 4 " di kotak kedua melarang pengulangannya pada A4 Dan A6.
"Pahlawan Terakhir" untuk kami " 4 " ini A2

1.3 "Tidak Ada Pilihan"

Terkadang ada beberapa alasan untuk lokasi tertentu. " 4 " di dalam J8 akan menjadi contoh yang bagus.
Biru panah menunjukkan bahwa ini adalah angka kuadrat terakhir yang mungkin. merah Dan biru panah memberi kami nomor terakhir di kolom 8 . Sayuran hijau panah memberikan nomor terakhir yang mungkin di baris J.
Seperti yang Anda lihat, kami tidak punya pilihan selain meletakkan ini " 4 "di tempat.

1.4 "Dan siapa, jika bukan aku?"

Pengisian angka lebih mudah dilakukan dengan cara-cara yang dijelaskan di atas. Namun, memeriksa nomor sebagai nilai terakhir yang mungkin juga memberikan hasil. Metode ini harus digunakan ketika tampaknya semua angka ada di sana, tetapi ada sesuatu yang hilang.
"5 " di dalam B1 diatur berdasarkan fakta bahwa semua angka dari " 1 " sebelum " 9 ", kecuali " 5 " ada di baris, kolom dan kotak (ditandai dengan warna hijau).

Dalam jargon itu adalah " penyendiri telanjang". Jika Anda mengisi bidang dengan nilai yang mungkin (kandidat), maka di sel, angka seperti itu akan menjadi satu-satunya yang mungkin. Mengembangkan teknik ini, Anda dapat mencari ". penyendiri tersembunyi" - angka unik untuk baris, kolom, atau kotak tertentu.

2. "Mil Telanjang"

2.1 pasangan telanjang

"Pasangan "telanjang"" - satu set dua kandidat yang terletak di dua sel milik satu blok umum: baris, kolom, kotak.
Jelas bahwa solusi teka-teki yang benar hanya akan ada di sel-sel ini dan hanya dengan nilai-nilai ini, sementara semua kandidat lain dari blok umum dapat dihapus.

Dalam contoh ini, ada beberapa "pasangan telanjang".
merah Di barisan TETAPI sel disorot A2 Dan A3, keduanya mengandung " 1 " Dan " 6 ". Saya belum tahu persis bagaimana mereka berada di sini, tetapi saya dapat dengan aman menghapus yang lainnya " 1 " Dan " 6 " dari string SEBUAH(ditandai dengan warna kuning). Juga A2 Dan A3 milik kotak yang sama, jadi kami menghapus " 1 " dari C1.

2.2 "Bertiga"

"Tiga Telanjang"- versi rumit dari "pasangan telanjang".
Setiap kelompok tiga sel dalam satu blok yang mengandung semua seutuhnya tiga calon adalah "tiga telanjang". Ketika kelompok seperti itu ditemukan, ketiga kandidat ini dapat dihapus dari sel lain dari blok tersebut.

Kombinasi kandidat untuk "tiga telanjang" mungkin seperti ini:

// tiga angka dalam tiga sel.
// kombinasi apa saja.
// kombinasi apa saja.

Dalam contoh ini, semuanya cukup jelas. Di kotak kelima sel E4, E5, E6 berisi [ 5,8,9 ], [5,8 ], [5,9 ] masing-masing. Ternyata secara umum ketiga sel ini memiliki [ 5,8,9 ], dan hanya angka-angka ini yang boleh ada. Ini memungkinkan kami untuk menghapusnya dari kandidat blok lainnya. Trik ini memberi kita solusinya" 3 " untuk sel E7.

2.3 "Empat Luar Biasa"

"Empat Telanjang" kejadian yang sangat langka, terutama dalam bentuk lengkapnya, namun memberikan hasil saat terdeteksi. Logika penyelesaiannya sama dengan "kembar tiga telanjang".

Dalam contoh di atas, di kotak pertama sel A1, B1, B2 Dan C1 umumnya mengandung [ 1,5,6,8 ], jadi angka-angka ini hanya akan menempati sel-sel itu dan tidak ada yang lain. Kami menghapus kandidat yang disorot dengan warna kuning.

3. "Segala sesuatu yang tersembunyi menjadi jelas"

3.1 pasangan tersembunyi

Cara yang bagus untuk membuka lapangan adalah dengan mencari pasangan tersembunyi. Metode ini memungkinkan Anda untuk menghapus kandidat yang tidak perlu dari sel dan memunculkan strategi yang lebih menarik.

Dalam teka-teki ini kita melihat bahwa 6 Dan 7 ada di kotak pertama dan kedua. di samping itu 6 Dan 7 ada di kolom 7 . Menggabungkan kondisi ini, kita dapat menyatakan bahwa di dalam sel A8 Dan A9 hanya akan ada nilai-nilai ini dan kami menghapus semua kandidat lainnya.

Contoh yang lebih menarik dan kompleks pasangan tersembunyi. Pasangan [ 2,4 ] di dalam D3 Dan E3, membersihkan 3 , 5 , 6 , 7 dari sel-sel ini. Disorot dengan warna merah adalah dua pasangan tersembunyi yang terdiri dari [ 3,7 ]. Di satu sisi, mereka unik untuk dua sel di 7 kolom, di sisi lain - untuk satu baris E. Kandidat yang disorot dengan warna kuning dihapus.

3.1 Kembar tiga tersembunyi

Kita bisa mengembangkan pasangan tersembunyi sebelum kembar tiga tersembunyi atau bahkan merangkak tersembunyi. Tiga Tersembunyi terdiri dari tiga pasang angka yang terletak dalam satu blok. Seperti, dan. Namun, seperti dalam kasus "kembar tiga telanjang", masing-masing dari tiga sel tidak harus berisi tiga angka. akan bekerja Total tiga angka dalam tiga sel. Sebagai contoh , , . Kembar tiga tersembunyi akan ditutupi oleh kandidat lain di dalam sel, jadi pertama-tama Anda harus memastikan bahwa troika berlaku untuk blok tertentu.

Dalam contoh kompleks ini, ada dua kembar tiga tersembunyi. Yang pertama, ditandai dengan warna merah, di kolom TETAPI. Sel A4 mengandung [ 2,5,6 ], A7 - [2,6 ] dan sel A9 -[2,5 ]. Tiga sel ini adalah satu-satunya di mana bisa ada 2 , 5 atau 6, jadi hanya mereka yang ada di sana. Oleh karena itu, kami menghapus kandidat yang tidak perlu.

Kedua, dalam kolom 9 . [4,7,8 ] unik untuk sel B9, C9 Dan F9. Menggunakan logika yang sama, kami menghapus kandidat.

3.1 merangkak tersembunyi

Contoh sempurna merangkak tersembunyi. [1,4,6,9 ] di kotak kelima hanya bisa di empat sel D4, D6, F4, F6. Mengikuti logika kami, kami menghapus semua kandidat lainnya (ditandai dengan warna kuning).

4. "Non-karet"

Jika salah satu angka muncul dua atau tiga kali di blok yang sama (baris, kolom, kotak), maka kita dapat menghapus angka itu dari blok konjugasi. Ada empat jenis pasangan:

Pasangkan atau Tiga dalam kotak - jika mereka berada dalam satu baris, maka Anda dapat menghapus semua nilai serupa lainnya dari baris yang sesuai.
Pasangkan atau Tiga dalam kotak - jika mereka berada di satu kolom, maka Anda dapat menghapus semua nilai serupa lainnya dari kolom yang sesuai.
Pasangkan atau Tiga berturut-turut - jika mereka berada di kotak yang sama, maka Anda dapat menghapus semua nilai serupa lainnya dari kotak yang sesuai.
Pasangkan atau Tiga dalam kolom - jika mereka berada di kotak yang sama, maka Anda dapat menghapus semua nilai serupa lainnya dari kotak yang sesuai.

4.1 Menunjuk pasangan, kembar tiga

Mari saya tunjukkan teka-teki ini sebagai contoh. Di alun-alun ketiga 3 "hanya di B7 Dan B9. Mengikuti pernyataan №1 , kami menghapus kandidat dari B1, B2, B3. Juga, " 2 " dari kotak kedelapan menghilangkan nilai yang mungkin dari G2.

Teka-teki khusus. Sangat sulit untuk dipecahkan, tetapi jika Anda melihat lebih dekat, Anda dapat melihat beberapa pasangan menunjuk. Jelas bahwa tidak selalu perlu untuk menemukan semuanya untuk maju dalam solusi, tetapi setiap penemuan tersebut membuat tugas kita lebih mudah.

4.2 Mengurangi yang tidak dapat direduksi

Strategi ini melibatkan penguraian dan perbandingan baris dan kolom dengan hati-hati dengan isi kotak (aturan №3 , №4 ).
Pertimbangkan garis TETAPI. "2 "hanya mungkin di A4 Dan A5. mengikuti aturan №3 , menghapus " 2 " mereka B5, C4, C5.

Mari kita lanjutkan untuk memecahkan teka-teki. Kami memiliki satu lokasi 4 "dalam satu kotak di 8 kolom. Menurut aturan №4 , kami menghapus kandidat yang tidak perlu dan, selain itu, kami mendapatkan solusinya " 2 " untuk C7.