WartaBulukumba - Akhirnya matematikawan menemukan celah di jalan buntu pada masalah catur.
Masalah catur yang telah membingungkan para matematikawan dimulai sejak 150 tahun lalu.
Dilansir WartaBulukumba.com dari Live Science pada Jumat 4 Februari 2022, masalah n queens dimulai sebagai teka-teki yang jauh lebih sederhana, dan pertama kali diajukan dalam edisi 1848 surat kabar catur Jerman Schachzeitung oleh komposer catur Max Bezzel.
Baca Juga: Terkendala staf, alat analitik CrowdTangle tidak terpakai sementara di Meta
Ini menanyakan berapa banyak cara delapan ratu saingan — yang merupakan bidak paling kuat di papan catur dan mampu menggerakkan sejumlah kotak secara horizontal, vertikal, dan diagonal — dapat diposisikan pada papan 64 kotak standar tanpa ada ratu yang menyerang yang lain.
Jawabannya, terungkap hanya dua tahun kemudian, adalah bahwa ada 92 konfigurasi yang menjaga delapan ratu dari tenggorokan masing-masing, dengan semua kecuali 12 dari solusi menjadi rotasi sederhana dan refleksi satu sama lain.
Tetapi pada tahun 1869, pengulangan masalah yang lebih membingungkan ditanyakan oleh ahli matematika Franz Nauck: Alih-alih mengonfigurasi delapan ratu pada papan 8-kali-8 standar, bagaimana dengan 1.000 ratu pada papan 1.000-kali-1.000? Bagaimana dengan satu juta, atau bahkan satu miliar?
Baca Juga: Ikuti TikTok dan Reddit, YouTube juga jajaki fitur NFT untuk content creator
Apa yang dulunya merupakan teka-teki yang relatif sederhana telah menjadi masalah matematika yang jauh lebih dalam — masalah yang membutuhkan penemuan aturan umum untuk jumlah cara untuk memposisikan sejumlah (diwakili sebagai "n") ratu pada papan n-oleh-n .
Sekarang, Michael Simkin, seorang ahli matematika di Pusat Ilmu dan Aplikasi Matematika Universitas Harvard, telah memberikan jawaban yang hampir pasti.
Pada papan n-by-n yang sangat besar, ada kira-kira (0,143n)^n cara untuk menempatkan n ratu sehingga tidak ada yang bisa saling menyerang. Itu berarti bahwa di papan sejuta demi sejuta, jumlah konfigurasi yang tidak mengancam yang dapat diatur oleh 1 juta ratu kira-kira 1 diikuti oleh 5 juta nol.
Baca Juga: Arkeolog temukan sedotan tertua dari Zaman Perunggu, terbuat dari emas dan panjang 3 kaki!
Simkin membutuhkan waktu hampir lima tahun untuk menemukan pendekatan persamaan yang mendekati ini.
Para matematikawan biasanya memecahkan masalah dengan menemukan cara untuk memecahnya menjadi bagian yang lebih mudah dikelola.
Karena ratu yang ditempatkan lebih dekat ke tengah papan dapat menyerang lebih banyak kotak daripada ratu di tepinya, masalah n-queens sangat asimetris, maka sangat tahan terhadap penyederhanaan.
Berkolaborasi dengan Zur Luria, seorang ahli matematika di Institut Teknologi Federal Swiss di Zurich, Simkin awalnya menyederhanakan tugas dengan mempertimbangkan versi "toroidal" yang lebih simetris dari masalah, di mana kotak tepi membungkus papan untuk membentuk bentuk donat.
Baca Juga: Benarkah matematika adalah bagian dasar alam semesta yang bukan diciptakan manusia?
Pengaturan ini memungkinkan ratu menghilang di kiri atas dan muncul kembali di kanan bawah, misalnya. Ini juga berarti bahwa di mana pun mereka ditempatkan, setiap ratu dapat menyerang jumlah kotak yang sama dengan rekan-rekannya.
Dengan menggunakan papan toroidal sebagai pendekatan pertama, kedua matematikawan selanjutnya menerapkan strategi yang disebut "algoritma rakus acak" untuk masalah tersebut.
Mereka menempatkan seorang ratu secara acak, memblokir semua kotak yang diserangnya; kemudian ratu berikutnya akan dipilih untuk duduk di tempat yang tersisa, dengan kotak serangannya diblokir secara bergantian.
Pasangan ini terus melakukan ini pada beberapa konfigurasi sampai mereka menemukan batas bawah kasar — atau angka serendah mungkin — pada jumlah konfigurasi n ratu pada papan toroidal.
Baca Juga: Pengiklan membeli ruang iklan berdasarkan minat penelusuran tanpa cookie, Google akan uji coba
Tapi perkiraan mereka jauh dari sempurna. Sifat sampul papan mencegah mereka menemukan beberapa posisi ratu terakhir dalam beberapa konfigurasi.
Setelah menyelesaikan masalah selama beberapa tahun, keduanya kembali dengan ide untuk mengadaptasi algoritme mereka ke papan biasa, yang menyediakan lebih banyak tempat persembunyian untuk ratu terakhir daripada papan toroidal. Dengan mengadaptasi algoritme rakus acak ke papan standar non-toroidal, pasangan ini agak meningkatkan akurasi perkiraan batas bawah ini.
Tapi jawaban mereka tidak sejelas yang mereka harapkan — algoritma random serakah bekerja paling baik pada masalah simetris, di mana setiap kotak papan memberikan keuntungan menyerang yang sama seperti yang lain.***