SUDOKU

Sejarah Sudoku

Sudoku (数独 sūdoku?) juga dikenal sebagai Number Place atau Nanpure, adalah sejenis teka-teki logika. Tujuannya adalah untuk mengisikan angka-angka dari 1 sampai 9 ke dalam jaring-jaring 9x9 yang terdiri dari 9 kotak 3x3 tanpa ada angka yang berulang di satu bads, kolom atau kotak. Sudoku adalah sebuah puzzle yang didasarkan pada konsep Latin Square. Latin Square sendiri diperkenalkan pada tahun 1783 oleh Leonhard Euler, seorang matematikawan asal Swiss. Permainan ini pertama kali diterbitkan di sebuah surat kabar Perancis pada 1895. Versi modern permainan ini dimulai di Indiartapdis path 1979. Kemudian menjadi terkenal kembali di Jepang pada 1986, ketika penerbit Nikoli menemukan teka-teki ini yang diciptakan Howard Garns seorang mantan arsitek yang meninggal tahun 1989. Kemudian Nikoli membawa permainan ini ke Jepang dan menerbitkannya di sebuah media cetak khusus puzzle miliknya "Monthly Nikolist". Mereka menamakannya "Suuji Wa Dokushin Ni Kagiru" (数字は独身に限る?), disingkat Sudoku (artinya "angka-angkanya harus tetap tunggal") dan mematenkan kata ini. Media lain pun kemudian menerbitkan permainan ini dengan nama aslinya, Number Place. Mulai saat itulah permainan ini mewabah di Jepang. Lebih dari 600.000 majalah tentang Sudoku terjual di Jepang setiap bulannya. Lucunya, mereka lebih senang menyebutnya Number Place, sementara orang di luar Jepang menamakannya Sudoku. Sudoku menjadi benar-benar mewabah di Inggris ketika The Daily Telegraph mengenalkannya path pembacanya path bulan Februari 2005. Mecia lain pun kemudian mengikuti dengan menyediakan permainan ini di edisinya masing-masing.
Pertengahan Mei 2005 adalah awal demam Sudoku. Segala hal tentang Sudoku menjadi ladang uang, pemuatan di koran harian, penerbitan buku, penerbitan majalah, pertunjukkan televisi, siaran radio, pelayanan langganan lewat email, dan penyediaan layanan di telepon genggam. Khusus untuk buku, News & Star mencatat bahwa 6 dari 10 buku nonfiksi yang paling laris saat ini adalah buku tentang Sudoku. Dad Inggris, Sudoku kemudian menyebar di daratan Eropa, dari Prancis sampai Slowakia, lalu menular pula ke Australia dan Amerika.

Aturan Permainan Sudoku
Aturan permainan untuk puzzle ini sangat sederhana, untuk menyelesaikan permainan ini tidak diperlukan pengetahuan umum, kepandaian atas bahasa tertentu, juga kemampuan matematika. Tetapi hanya memerlukan kecermatan, kesabaran, dan logika.
Papan Sudoku terbuat dari sembilan buah kotak berukuran 3x3 (disebut blok/ subgrid) yang disusun sedemikian rupa sehingga menghasilkan kotak besar berukuran 9x9. Beberapa kotak sudah diisi sebagai petunjuk awal dan tugas pemain adalah melengkapi angka-angka pada kotak yang lain sehingga keseluruhan papan permainan terisi angka secara lengkap. Aturan perrnainannya sangatlah sederhana:

1. Kotak-kotak pada setiap baris, kolom, dan blog subgrid harus berisi sebuah angka. 
2. Angka-angka yang diiskan harus unik dari 1 hingga 9 sehingga dalam 1 blok/ subgrid hanya terdiri atas angka 1-9 yang tidak berulang dan tidak ada angka yang berulang dalam 1 baris maupun kolom. Angka-angka ini sebenarnya tidak memiliki hubungan aritmetis satu sama lain. Anda boleh menggantinya dengan 9 huruf, lambang, atau wama yang berbeda.

Cara Bermain Sudoku

• Sudoku dimainkan dalam 9x9 kotak yang dibagi dalam 3x3 kotak kecil (sel) yang disebut "area":

• Sudoku dimulai dengan beberapa sel yang sudah terisi dengan angka:

• Tujuan permainan Sudoku adalah mengisi sel-sel yang kosong dengan angka antara 1 dan 9 (setiak sel hanya 1 angka) sesuai dengan petunjuk berikut:
• Angka hanya dapat muncul sekali dalam setiap baris:

• Angka hanya dapat muncul sekali dalam setiap kolom:

• Angka hanya dapat muncul sekali dalam setiap area:

• Ringkasan peraturannya adalah sebuah angka harus muncul sekali disetiap baris, kolom, dan area.

Algoritma Backtracking (Runut Balik) Dalam Permainan Sudoku
Algoritma backtracking pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950 menyajikan uraian umum tentang backtracking dan penerapannya dalam berbagai persoalan dan aplikasi. Algoritma backtracking (runut balik) merupakan salah satu metode pemecahan masalah yang termasuk dabm strategi yang berbasis pencarian pada ruang status. Algoritma backtracking bekerja secara rekursif dan melakukan pencarian solusi persoalan secara sistematis pada semua kemungkinan solusi yang ada. Oleh karena algoritma ini berbasis pada algoritma Depth-First Search (DFS) untuk mencari solusi persoalan secara lebih mangkus, maka pencarian solusi dilakukan dengan menelusuri suatu struktur berbentuk pohon berakar.
Algoritma backtracking adalah suatu algodtma yang merupakan perbaikan dari algoritma brute force, secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada. Backtracking merupakan bentuk tipikal dari algoritma rekursif dan berbasis pada DFS dalam mencari solusi yang tepat. Selain itu, algoritma ini juga merupakan metode yang mencoba-coba beberapa keputusan sampai kita menemukan salah satu yang "berjalan". Kita tidak perlu memeriksa semua kemungkinan solusi yang ada, tetapi cukup yang mengarah kepada solusi saja. Dengan memangkas (pruning) simpul-simpul yang tidak mengarah ke solusi. sehingga waktu pencarian dapat dihemat. Algoritma ini banyak diterapkan untuk program games dan permasalahan pada bidang kecerdasan buatan.

Strategi umum penyelesaian teka-teki Sudoku 

1. Pemindahan (scanning) Berupa proses memindahkan bads atau kolom untuk mengindentifikasi bads mana dalam suatu blok yang terdapat angka-angka tertentu. Proses ini kemudian diulang pada setiap kolom (atau bads) secara sistematis. Kemudian menentukan nilai dari suatu sel dengan membuang nilai-nilai yang tidak mungkin. 
2. Penandaan (marking) Berupa analisa logika, dengan menandai kandidat angka yang dapat dimasukkan dalam sebuah sel.
3. Analisa (analysing) Berupa eliminasi kandidat, dimana kemajuan dicapai dengan mengeliminasi kandidat angka secara berturut-turut hingga sebuah sel hanya punya 1 kandidat. 

Prinsip Pencarian Solusi dengan Metode Backtracking 
Seperti yang tetah dijelaskan bahwa pencarian solusi dengan menggunakan algpritma backtracking digunakan pohon ruang status. Cara kerjanya adalah dengan membentuk lintasan dari akar ke daun.

Langkah-langkah pencarian solusi pada pohon ruang status: 

1. Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan pembentukan yang dipakai adalah mengikuti metode pencarian mendalam (DFS). Simpul-simpul yang sudah dibhirkan dinamakan simpul hidup (live node). Simpul hidup yang sedang diperluas dinamakan simpul-E (Expand-node). Simpul dinomori dari alas ke bawah sesuai dengan urutan kelahirannya. 
2. Tiap kali simpul-E diperluas. lintasan yang dibangun olehnya bertambah panjang. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi maka simpul-E tersebut "dibunuh" sehingga menjadi simpul mati (dead node). Fungsi yang digunakan untuk membunuh simpul-E adalah dengan menerapkan fungsi pembatas (bounding function). Simpul yang sudah mati tidak akan pernah diperluas lagi. 
3. Jika pembentukan lintasan berakhir dengan simpul mati, maka proses pencarian diteruskan dengan membangkitkan simpul anak yang lainnya. Bila tidak ada lagi simpul anak yang dapat dibangkitkan, maka pencarian solusi dilanjutlon dengan melakukan backtracking ke simpul hidup terdekat (simpul orang tua). Selanjutnya simpul ini menjadi simpul-E yang baru. Lintasan baru dibangun kembali sampai lintasan tersebut membentuk solusi. 
4. Pencarian dihentikan bila kita telah menemukan solusi atau tidak ada simpul hidup untuk backtracking atau simpul yang dapat di diperluas. 

Manfaat Permainan Sudoku
manfaat bagi yang memainkannya yaitu dalam pengembangan otak. Sudoku lebih menekankan pada permainan logika, maka dibutuhkan logika yang tepat untuk menyelesaikannya (tentunya tiap level kesulitannya, juga membutuhkan tingkat logika yang berbeda). Dari sini, kita melatih otak kiri kita yang bekerja secara sistematis. Bukan hanya berhenti di situ, dengan bertambahnya level kesulitannya,kita juga dituntut kreatif mencari solusi penyelesaian materi. Dari sisi ini, kita dilatih juga otak kanan yang bekerja secara kreatif.

Sumber :

• https://id.wikipedia.org/wiki/Sudoku
• https://fitriafrilinda.wordpress.com/2012/04/08/permainan-sudoku/
• http://www.sudoku.name/rules/id
• http://chemistrahmah.com/sudoku-bermain-angka-untuk-kreativitas-dan-melatih-konsentrasi.html
• https://www.scribd.com/doc/21036771/ANALISIS-PENYELESAIAN-PUZZLE-SUDOKU-DENGAN-MENERAPKAN-ALGORITMA-BACKTRACKING