Dimana ada yang menghitung untuk Sudoku ukuran 9 x 9, variasi dengan satu solusi berjumlah 6.670.903.752.021.072.936.960 variasi untuk solusi penyelesaiannya. Andai solusinya disusun secara simetris, diperoleh 5.472.730.538 variasi.
Sudoku sangat berkaitan erat dengan Latin Square dan berbagai teori lainnya seperti penggunaan rumus Stirling dalam menyelesaikan permaian Sudoku ini. Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.
Latin Square adalah tabel n × n diisi dengan n simbol berbeda sedemikian rupa sehingga masing-masing simbol terjadi tepat satu kali di setiap baris dan tepat sekali dalam setiap kolom.
Banyak sekali manfaat dalam permainan Sudoku ini, contoh dengan permainan Sudoku ini kita dapat melatih mengembangkan cara berpikir dan nalar yang benar sesuai dengan logika dan masih banyak lagi manfaat lainnya.
Key words : Kombinatorial, Kombinasi, Permutasi, Sudoku, Latin Square, Stirling, Grid.
1. PENDAHULUAN
1.1 Sudoku
Sudoku adalah logika berbasis kombinatorial nomor-penempatan teka-teki. Sudoku memiliki tingkat kesulitan yang bervariasi tergantung dari modelnya, ada yang ukuran 6 x 6 dengan setiap baris, dan setiap dari enam 3 × 2 -grid sub yang membentuk grid (juga disebut "kotak", "blok", "daerah", atau "sub-kotak") berisi semua angka dari 1 sampai 6, kemudian Sudoku 4 x 4, Sudoku 8 x 8, Sudoku 9 x 9, Sudoku 16 x 16 dan lain-lain. Pada kesempatan kali ini akan dibahas untuk penyelesaian Sudoku 9 x 9. Tujuannya adalah untuk mengisi kotak 9 × 9 dengan angka sehingga setiap kolom, setiap baris, dan setiap dari sembilan 3 × 3 - sub grid yang membentuk grid (juga disebut "kotak", "blok", "daerah", atau "sub-kotak") berisi semua angka dari 1 sampai 9[1]. Sudoku pertama kali diterbitkan pertama kali di sebuah surat kabar di Perancis pada tahun 1895, yang mungkin dipengaruhi oleh matematikawan Swiss Leonhard Euler, yang membuat terkenal Latin Square. Versi modern permainan ini dimulai di Indianapolis pada 1979. Kemudian menjadi terkenal kembali di Jepang pada 1986, ketika penerbit Nikoli menemukan teka-teki ini yang diciptakan Howard Garns. Nama "Sudoku" adalah singkatan bahasa Jepang dari "Suuji wa dokushin ni kagiru" yang artinya "angka-angkanya harus tetap tunggal”. Sedangkan SU berarti angka dan DOKU berarti tunggal[2]. Berikut adalah contoh dari permaianan Sudoku 9 x 9
6
|
1
|
5
|
||||||
3
|
9
|
|||||||
4
|
3
|
|||||||
7
|
8
|
3
|
5
|
2
|
||||
2
|
9
|
|||||||
5
|
9
|
8
|
1
|
6
|
||||
1
|
9
|
|||||||
6
|
7
|
|||||||
9
|
6
|
2
|
Telah dijelaskan sebelumnya bahwa dalam permainan merupakan kombinasi angka antara 1 sampai 9 pada setiap kolom dan setiap baris yang tampak seperti pada gambar di atas. Dengan permaian Sudoku ini kita dapat melatih Mengembangkan cara berpikir dan nalar yang benar sesuai dengan logika. Mempertajam anilisis kita dalam menyelesaikan suatu masalah. Mengambil keputusan yang tepat berdasarkan analisis dan pertimbangan-pertimbangan fungsional. Mengembangkan pola berfikir interdisipliner dalam menghadapi masalah. Mengenal dan memehami proses – proses pengembangan konsep Sudoku. Melatih ketajaman, ketelitian dan kesabaran dalam menyelesaikan masalah. Mengembangkan sikap mandiri dan cepat tanggap dalam menghadapi masalah berdasarkan logika yang benar. Meningkatkan wawasan, kemampuan dan profesionalisme di berbagai bidang yang membutuhkan logika, penalaran dan analisis. Mengembangkan diri secara mandiri sehingga dapat mengikuti perkembangan ilmu pengetahuan secara global. Melatih otak kiri kita yang bekerja secara sistematis. Melatih otak kanan kita yang bekerja secara kreatif. Untuk mengisi waktu luang dan sebagai sarana hiburan ataupun hobi yang bermanfaat dalam mempertajam otak[6].
1.2 Dasar Teori
1.2.1 Kombinatorial
Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Dengan menghitung secara kombinatorial maka dapat diperoleh jumlah kemungkinan pengaturan dari sejumlah objek dalam suatu himpunan tanpa harus mengenumerasi kemungkinan tersebut satu persatu. Meskipun demikian kombinatorial menjadi sangat membantu dalam melakukan pemecahan masalah untuk menghitung banyaknya kombinasi yang memungkinkan dari nomor yang unik sperti pada permainan Sudoku ini.
1.2.1.1 Kaidah dasar perhitungan
1. Kaidah perkalian (rule of product)
Percobaan 1: p hasil
Percobaan 2: q hasil
Percobaan 1 dan percobaan 2: p + q hasil
2. Kaidah penjumlahan (rule of sum)
Percobaan 1: p hasil
Percobaan 2: q hasil
Percobaan 1 atau percobaan 2: p + q hasil
1.2.1.2 Permutasi
Permutasi adala jumlah urutan yang berbeda dari pengaturan objek-objek. Menurut kaidah perkalian, permutasi dari n objek adalah
n(n - 1)(n - 2)(n - 3)…(2)(1)=n! (1)
rumus permutasi-q (jumlah dari penyusunan berbeda objek q yang diambil dari n objek) dilambangkan dengan P(n,q)
P(n,q) = n(n - 1)(n - 2)(n - 3)…( n – (q - 1)) (2)
= n!/(n-q)
1.2.1.3 Kombinasi
Bentuk khusus dari permutasi adalah ombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan. Rumus kombinasi-r (jumlah pemilihan tidak terurut r elemen yang diambil dari n buah elemen), dilambangkan dengan C(n,r)
1.2.2 Latin Square
Dalam permainan Sudoku yang sudah dijelaskan pada bagian sebelumnya bahwa dalam perkembangan permainan ini dipengaruhi oleh Latin Square. Dalam kombinatorial dan statistik, sebuah Latin Square adalah tabel n × n diisi dengan n simbol berbeda sedemikian rupa sehingga masing-masing simbol terjadi tepat satu kali di setiap baris dan tepat sekali dalam setiap kolom. Tidak ada rumus yang mudah menghitung nomor L (n) × n, n kotak Latin dengan simbol 1,2 ,..., n. Batas atas dan bawah paling akurat dikenal untuk n besar berjauhan adalah dengan rumus berikut[3] :
Rumus diatas dikenalkan oleh Van Lint dan Wilson.
Contoh dari latin square sederhana:
1
|
3
|
2
|
3
|
2
|
1
|
2
|
1
|
3
|
Latin Square berdasarkan ordenya.
Orde
|
Latin Square
|
1
|
1
|
2
|
2
|
3
|
12
|
4
|
576
|
5
|
161280
|
6
|
812851200
|
7
|
61479419904000
|
8
|
108776032459082956800
|
9
|
5524751496156892842531225600
|
10
|
9982437658213039871725064756920320000
|
11
|
776966836171770144107444346734230682311065600000
|
Setiap Sudoku merupakan latin square berorde 9, tetapi latin square belum tentu Sudoku karena ada kondisi tambahan 9 buah sub kisi berukuran 3 x 3.
2. PEMBAHASAN
2.1 Memecahkan masalah Sudoku
Dalam menyelesaikan permainan Sudoku ini ada banyak cara yang dapat digunanakan mulai cara yang mudah hinggga yang rumit, tapi kebanyakan orang menganggap bahwa permaian Sudoku ini sangatlah rmit dan hanya orang yang ber IQ tinggilah yang bias menyelesaikan permaian ini dengan mudah dan cepat. Padahal tidak demikian jika seorang sering berlatih dan belajar pasti bias dengan mudah mengerjakan teka-teki Sudoku ini. Dalam menyelesaikan permaian Sudoku ini banyak sekali kombinasi yang ada pada setiap baris dan kolom, serta kombinasi pada 1 grid/kotak/blok yang harus diisi dengan kombinasi angka 1 sampai dengan 9. Hanya bersandar pada logika dan sebab-akibat. Ada yang menghitung untuk sudoku ukuran 9 x 9, variasi dengan satu solusi berjumlah 6.670.903.752.021.072.936.960 kombinasi untuk solusi penyelesaiannya. Andai solusinya disusun secara simetris, diperoleh 5.472.730.538 variasi.
6
|
1
|
5
|
||||||
3
|
9
|
|||||||
4
|
3
|
|||||||
7
|
8
|
3
|
5
|
2
|
||||
2
|
9
|
|||||||
5
|
9
|
8
|
1
|
6
|
||||
1
|
9
|
|||||||
6
|
7
|
|||||||
9
|
6
|
2
|
pada grid (yang berwarna merah) seperti pada gambar tabel diatas dapat diisi dengan kombinasi angka 1 sampai 9. Sedangkan pada baris dan kolomnya juga demikian harus diisi angka 1 sampai 9 dengan syarat antara angka yang diisikan pada baris dan kolom serta pada masing-masing grid/kotak/blok tidak boleh ada yang sama. Contoh pengisian Sudoku yang benar. Dalam menyelesaikan Sudoku dapat dilihat dari langkah-langkahnya sebagai berikut :
8
|
3
|
6
|
||||||
3
|
4
|
2
|
||||||
9
|
8
|
|||||||
7
|
8
|
9
|
6
|
4
|
||||
2
|
8
|
|||||||
5
|
9
|
6
|
||||||
3
|
5
|
|||||||
4
|
5
|
2
|
7
|
|||||
2
|
9
|
- a
- b
- c
Beberapa langkah-langkah dalam menyelesaikan permainan Sudoku diatas:
Ke Bawah : Dari angka yang disediakan, perhatikan 3 kotak pertama dari samping kiri yang telah diberi nomor 1, 2 dan 3 (ini merupakan 3 kotak parsial) dari sebelah kiri gambar di atas. Kita mulai dari angka yang paling sering muncul dari 3 kotak tersebut, ada angka 9, 3 dan 2. Kita pilih satu angka, misalkan angka 3. Jika : di kotak 1, angka 3 berada di kolom ke 2, di Kotak 2, angka 3 berada di kolom ke-1, maka di kotak 3, angka 3 pasti berada berada di kolom ke-3, dengan terlebih dahulu melihat kotak di samping, dimana angka 3 yang lain berada di baris 1 dan 2 dari bawah.
Ke Samping : Perhatikan kotak 3, 6 dan 9. Kita mulai dari angka yang paling sering muncul dari 3 kotak tersebut, ada angka 5 dan 2. Kita pilih satu angka, misalkan angka 5. Jika :di kotak 9, angka 5 berada di baris a, di kotak 6, angka 5 berada di baris b, maka pastilah pada kotak 3, angka 5 berada di baris c, dan satu-satunya kotak yang tersisa adalah disamping angka 9. Dengan mengikuti langkah diatas maka kita dapat menyelesaikan permainan Sudoku dengan mudah.
Dalam Sudoku ini memiliki solusi yang unik dan logis, untuk teka-teki, setiap baris, kolom dan kotak harus berisi masing-masing angka 1 sampai 9, pada Sudoku ini memiliki grid 3x3 kecil sebagai kotak dan sel yang berisi nomor sebagai persegi. Baris dan kolom yang dimaksud dengan nomor baris pertama, diikuti dengan kolom nomor: 4,5 adalah baris 4, kolom 5; 2,8 adalah baris 2, kolom 8. Kotak diberi nomor 1-9 dalam rangka membaca,, yaitu 123 456, 789. Untuk memecahkan teka-teki sudoku Anda akan menggunakan logika. Anda akan mengajukan pertanyaan diri sendiri seperti:
“jika 1 dalam kotak ini akan pergi dalam kolom ini 'atau'? jika 9 sudah di baris ini,
bisa sebuah 9 masuk kotak ini?. Untuk memulai, lihat setiap kotak dan melihat kotak yang kosong,
pada saat yang sama memeriksa kolom yang persegi dan baris untuk nomor yang hilang.
Dalam contoh ini, lihat kotak 9. Tidak ada 8 di dalam kotak, tapi ada adalah kolom 8 dalam kolom 7 dan di 8. Satu-satunya tempat untuk 8 adalah kolom 9, dan dalam kotak ini hanya persegi tersedia dalam baris 9. Jadi menempatkan 8 di persegi itu. Melanjutkan untuk berpikir tentang 8, tidak ada 8 dalam kotak 1, tetapi Anda dapat melihat 8 di baris 1 dan 2.
Jadi, dalam kotak 1, 8 hanya dapat masuk baris 3, tapi ada 2 kotak tersedia. Membuat catatan ini oleh penciling di 8 kecil di kedua kuadrat. Kemudian, ketika kita memiliki menemukan posisi 8 di kotak 4 atau 7 kita akan dapat membantah salah satu 8 yang ada di kotak 1. Ada situasi yang sama dengan 4s dalam kotak-kotak 4 dan 5, tapi di sini hasilnya tidak begitu akurat. Bersama dengan 4 dalam kolom 7 4 yang sama ini menghilangkan semua yang tersedia dikotak dalam kotak 6 terpisah dari dua. Pensil 4 kecil dikedua kotak. Kemudian, satu atau lain dari tanda pensil Anda akan dibuktikan benar atau disalahkan.
Kami melihat kotak 9. Ketika Anda dapat melihat, ada 2 di kotak 7 dan 8, tapi tidak ada di dalam kotak 9. Angka 2 di baris 8 dan baris 9 berarti hanya tempat untuk 2 dalam kotak 9 muncul berada di baris 7, dan karena ada sudah menjadi 2 pada kolom 8, ada hanya satu persegi lagi di kotak yang selama 2 untuk pergi. Anda dapat memasukkan 2 untuk kotak 9 di 7,7. Seterusnya dapat dicek seperti pada cara diatas, sehingga dapat diperoleh hasil akhir menjadi seperti berikut :
9
|
1
|
2
|
6
|
8
|
3
|
4
|
7
|
5
|
3
|
5
|
6
|
7
|
9
|
4
|
8
|
2
|
1
|
7
|
8
|
4
|
1
|
5
|
2
|
9
|
3
|
6
|
2
|
7
|
9
|
4
|
1
|
6
|
5
|
8
|
3
|
5
|
3
|
1
|
8
|
2
|
9
|
7
|
6
|
4
|
4
|
6
|
8
|
5
|
3
|
7
|
1
|
9
|
2
|
8
|
4
|
3
|
9
|
6
|
5
|
2
|
1
|
7
|
1
|
2
|
5
|
3
|
7
|
8
|
6
|
4
|
9
|
6
|
9
|
7
|
2
|
4
|
1
|
3
|
5
|
8
|
2.2 Perhitungan Sudoku
Kita juga dapat menyelesaikan Sudoku dengan rumus kombinatorial, dimana kita bisa menggunakan persamaan permutasi untuk menyelesaikan permainan ini. Untuk menyelesaiannya juga bisa menggunakan rumus Stirling[4] dan Latin Square untuk menghitung jumlah kemungkian pengisian dalam satu baris ke-i pada Sudoku. Sebelumnya telah di ketahui bahwa Sudoku merupakan Latin Square berorde 9 maka jumlah Latin Square berorde n adalah sedikitnya
3. Kesimpulan
Permainan Sudoku merupakan permainan yang cukup menantang bagi para penggemar permainan teka-teki angka, yang mana pada permainan Sudoku ini memiliki tingkat kesulitan yang bermacam-macam mulai dari tingkat yang sangat mudah hingga tersulit. Dalam meyelesaikan permainan Sudoku ini cukup udah, hanya dengan memperhatikan pada setiap grid/kotak dan baris serta kolom yang ada, kemudian mengeliminasi jika ada nomor yang sama sehingga akan diperoleh hasil yang tepat. Sebenarnya dalam permaian ini tidak banya membutuhkan banyak pengetahuan dalam matematika, karena dalam permainan ini, yang dibutuhkan hanya kemampuan berfikir logika, sehingga siapapun bisa memainkannya.
4. Referensi
[1]Sudoku http://en.wikipedia.org/wiki/Sudoku
tanggal akses : 19 november 2010, pukul 00.00 WIB.
[2]SU berarti angka dan DOKU berarti tunggal.
http://universologi.blogspot.com/2010/03/permainan-seperti-sudoku-sudah-dikenal.html
tanggal akses : 20 November 2010, pukul 10:00 WIB.
[3]Latin Square
http://en.wikipedia.org/wiki/Latin_square
tanggal akses : 20 November 2010, pukul 10:00 WIB
[4]Stirling's approximation
http://en.wikipedia.org/wiki/Stirling's_approximation
tanggal akses : 20 November 2010, pukul 10:10 WIB
[5]Angelina, Lea. Penerapan Perwarnaan Graf dalam Teka-Teki Sudoku. 2006/2007
[6]Manfaat permainan Sudoku
http://universologi.blogspot.com/2010/03/permainan-seperti-sudoku-sudah-dikenal.html
tanggal akses : 20 November 2010, pukul 10:00 WIB.
Tidak ada komentar:
Posting Komentar