Pernah bermain Sudoku? Jika pernah, mungkin Anda bermain Sudoku untuk mengisi waktu senggang. Atau mungkin karena Anda senang teka-teki yang menantang. Apapun itu, pernahkah terpikir oleh Anda bahwa Sudoku juga ternyata menarik bagi para peneliti di dunia?
Di balik Sudoku, terdapat pertanyaan-pertanyaan yang membuat greget para peneliti. Beberapa pertanyaan tersebut tidak bisa dijawab hingga saat ini.Sementara beberapa lain terjawab setelah dilakukan penghitungan superkomputer selama hampir 1 tahun. Begitu rumitkah Sudoku? Dan apa hubungan Sudoku, Matematika, dengan uang 1 juta dollar Amerika? Untuk menjawab pertanyaan itu, mari kita mulai dari apa itu Sudoku.
Sudoku adalah sejenis teka-teki. Dalam teka-teki ini, Anda diminta untuk mengisikan angka 1-9 ke dalam 81 kotak yang tersusun secara bujur sangkar berukuran 9 × 9. Anda tidak perlu mengisi seluruh kotak karena dalam setiap permainan, sebagian kotak sudah terisi angka. Perhatikan Gambar 1 yang memperlihatkan sebuah Sudoku yang kosong.
Gambar 1: Sudoku kosong
Tantangan dalam Sudoku muncul dari 3 aturan berikut.
- Setiap baris tidak boleh berisi 2 angka yang sama
- Setiap kolom tidak boleh berisi 2 angka yang sama
- Setiap blok, yang berukurn 3 × 3, tidak boleh berisi 2 angka yang sama
Tingkat kesulitan Sudoku ditentukan dari banyaknya kotak yang sudah terisi di awal permainan. Semakin banyak kotak yang sudah terisi, semakin mudah Sudoku diselesaikan.
Selain itu, susunan angka awal menentukan mudah sukarnya menyelesaikan Sudoku. Hal ini disebabkan setiap angka awal, akan mengurangi kemungkinan isi dari kotak yang masih kosong. Misalnya, jika 1 baris sudah terisi 7 kotak dengan angka 1-7, dua kotak sisa di baris tersebut dengan mudah dapat kita tebak berisi angka 8 atau 9. Sebagai contoh, Gambar 2 menunjukkan Sudoku untuk level mudah. Sebelum melanjutkan, Anda boleh mencoba untuk mengisi Sudoku ini.
Gambar 2: Sudoku yang mudah
Ada banyak cara menyelesaikan Sudoku. Aturan langkah per langkah atau algoritma untuk menyelesaikan teka-teki ini sudah tersedia. Dengan adanya algoritma ini, dapat dibuat program komputer yang otomatis menyelesaikan Sudoku. Penulis pernah menyelesaikan Sudoku menggunakan program komputer yang ditulis Peter Norvig , direktur riset Google Inc. Dengan program tersebut Sudoku tersulit pun dapat diselesaikan dalam hitungan milidetik.
Akan tetapi, tanpa komputer, tidak semua dari kita dapat mengerjakan Sudoku. Beberapa Sudoku dianggap sangat sulit sehingga yang bisa kita lakukan hanyalah melakukan trial and error.
Sebenarnya, dalam ilmu komputasi, masalah untuk menemukan pemecahan Sudoku termasuk ke dalam kelas yang disebut NP-Complete. Secara sederhana, permasalahan yang masuk ke dalam kelas ini adalah permasalahan yang tidak diketahui dapat diselesaikan secara cepat ataukah tidak. Namun, jika kita diberikan solusi terhadap permasalahan ini, kebenaran solusi itu dapat diperiksa dengan cepat.
Kita akan kembali menyinggung masalah NP-Complete saat membahas uang sebesar 1 juta dollar Amerika nanti. Sekarang kita beralih dulu pada fakta bahwa ilmuwan tertarik akan Sudoku karena ada beberapa pertanyaan yang menarik untuk dicari jawabannya. Di antara pertanyaan itu adalah:
- Berapa banyak kemungkinan Sudoku yang ada?
- Berapa jumlah angka awal minimal yang harus diisikan agar Sudoku memiliki solusi yang unik (hanya ada satu solusi)?
- Adakah algoritma yang dapat menyelesaikan dengan cepat Sudoku dengan sembarang ukuran (misal Sudoku 100 × 100 kotak)?
Jika kita pergi ke Google Scholar (atau dalam versi Bahasa Indonesia disebut Google Cendekia), lalu kita memasukkan kata kunci Sudoku, untuk pencarian tulisan di tahun 2012 saja, terdapat kurang lebih 1.360 daftar hasil pencarian. Ini menunjukkan bahwa minat para peneliti untuk masalah Sudoku sangatlah tinggi. Beberapa publikasi ternama pun mengangkat artikel mengenai Sudoku.
Contohnya Scientific American yang membahas Sudoku dalam satu artikelnya di tahun 2006 dengan judul “The Science Behind Sudoku”. Artikel itu ditulis oleh Jean-Paul Delahaye, seorang ahli Matematika dari Prancis. Selain itu, Nature Scientific Reports mempublikasikan artikel berjudul “The Chaos Within Sudoku” tanggal 11 Oktober 2012. Artikel ini ditulis dua orang ilmuwan Fisika dari Romania dan Amerika.
Kembali ke 3 pertanyaan yang menggusarkan para peneliti di atas. Jawaban untuk pertanyaan pertama ternyata adalah 5.472.730.538. Ini merupakan angka yang besar sekali sehingga rasanya pecandu Sudoku tidak perlu takut kehabisan teka-teki ini.
Pertanyaan kedua sempat menjadi topik riset para peneliti selama beberapa waktu. Saat itu diduga bahwa jawaban dari pertanyaan nomor 2 adalah 17. Gordon Royle, dari University of Western Australia, mengumpulkan sebanyak 38.000 Sudoku dengan 17 angka awal dan sejauh itu, setiap Sudoku tersebut memang menghasilkan 1 solusi yang unik. Di samping itu, diketahui beberapa Sudoku dengan 16 angka awal yang menghasilkan 2 solusi.
Untuk memeriksa kemungkinan adanya Sudoku dengan 16 angka awal yang memiliki solusi unik, Gary McGuire, seorang ahli Matematika dari University College Dublin, melakukan eksperimen menggunakan superkomputer. Superkomputer tersebut melakukan pemeriksaan terhadap setiap kemungkinan Sudoku 16 angka untuk mencari jika ada yang memiliki solusi unik. Setelah melakukan penghitungan menggunakan 320 komputer paralel, masing-masing 2 prosesor dengan 16 core Xeon E5650 dan RAM masing-masing 24GB, dan dilakukan tanpa henti dari Januari 2011 hingga Desember 2011, McGuire menemukan bahwa tidak ada Sudoku 16 angka yang menghasilkan solusi unik. Jadi, hingga saat ini jawaban dari pertanyaan nomor 2 adalah 17 kecuali jika suatu hari seseorang menemukan Sudoku 17 angka yang memiliki paling sedikit 2 solusi.
Dari 3 pertanyaan, nomor 3 lah yang sebenarnya pertanyaan utama yang hingga saat ini belum dapat diselesaikan siapa pun. Seperti yang disebutkan sebelumnya, permasalahan Sudoku termasuk ke dalam NP-Complete atau lebih umumnya NP. Artinya, tidak diketahui apakah ada atau tidak ada algoritma untuk menyelesaikan permasalahan ini dengan cepat.
Sampai di sini mungkin Anda agak sedikit bingung. Jika Sudoku masuk ke dalam NP, mengapa dapat dibuatkan program komputer untuk menyelesaikan Sudoku dengan cepat? Jawabannya adalah, algoritma yang ada untuk menyelesaikan Sudoku, tidak dapat mencari solusi Sudoku dengan cepat saat ukuran Sudoku bertambah, tidak lagi 9 × 9. Penambahan sedikit saja ukuran Sudoku, waktu yang dibutuhkan untuk menyelesaikan Sudoku akan meningkat tajam.
Ini bukan berarti bahwa Sudoku untuk sembarang ukuran tidak bisa dipecahkan secara cepat. Kita hanya tidak tahu apakah ada algoritma yang lebih cepat untuk menyelesaikan Sudoku sembarang ukuran ini. Jika kita dapat menemukan algoritma yang cepat ini, permasalahan Sudoku tidak lagi berada di kelas NP, tapi berada di kelas P, yaitu kelas permasalahan yang dapat diselesaikan relatif cepat dan waktu penyelesaiannya tidak akan meningkat tajam saat ukuran permasalahan sedikit bertambah. Jika semua permasalahan yang berada di kelas NP ternyata dapat dicarikan algoritmanya yang cepat, itu berarti, NP sama dengan P atau ditulis P = NP. Dan sebaliknya, jika tidak ada algoritma yang mampu untuk menyelesaikan semua masalah di NP dengan cepat, ini berarti P = NP.
Nah, bagian yang menariknya adalah, pertanyaan apakah P = NP dianggap sebagai salah satu pertanyaan terbesar milenium ini. Bagi orang yang dapat menyelesaikan permasalahan ini, Clay Mathematics Institute akan memberikan hadiah berupa uang sebesar 1 juta dollar Amerika. Tertarik?
Demikianlah Sudoku yang menjadi permasalahan seksi bagi para peneliti dunia. Sebelum mengakhiri cerita ini, Anda mungkin tertarik untuk mencoba menyelesaikan Sudoku yang diklaim sebagai salah satu Sudoku tersulit di dunia. Sudoku ini dibuat oleh Arto Inkala, seorang ahli Matematika dari Finlandia. Selamat mencoba.
Gambar 3: Arto Inkala, seorang ahli Matematika asal Finlandia, mengklaim bahwa Sudoku ini adalah Sudoku tersulit di dunia.