Jumat, 31 Oktober 2014

Sudoku



Sudoku berasal dari kata “Su” yang berarti angka dalam bahasa Jepang dan “Doku” mengacu pada tempat di papan teka-teki yang setiap angka dapat masuk ke dalamnya.Walaupun namanya menggunakan bahasa Jepang sebenarnya Sudoku berasal dari Eropa dan Amerika.
Pada abad ke–18 ahli matematika Swiss Leonhard Euler mengembangkan konsep “Latin Squares” yaitu angka-angka dalam kotak muncul hanya sekali baik secara melintang ke atas dan ke bawah. Pada tahun 1979, Dell Puzzle Magazines di Amerika Serikat mulai menerbitkan teka-teki sudoku menggunakan konsep Euler dengan 9 x 9 kotak persegi yang disebut Number Place dan didesain oleh seorang arsitek Howard Garns.
Pada tahun 1984, mulai dikenalkan di Jepang dimuat di majalah bulanan Nikoli, dengan nama “Suuji Wa Dokushin Kagiru”. Selanjutnya puzzel ini dikenal sebagai Su-Doku. Pada tahun 2004, permainan ini mulai dikenalkan di Inggris dan diterbitkan pertama kali di ( The Times, pada 12 November 2004) dengan menggunakan nama sudoku.
Sudoku mulai mewabah di Inggris. The Telegraph mencoba menyajikan sudoku produknya sendiri di awal tahun 2005, menerima 60.000 email karena sudoku yang disajikan ternyata mempunyai solusi lebih dari satu. Sudoku craze atau demam sudoku pun menjalar ke segala penjuru dunia selama 222 tahun setelah Latin Square. Surat kabar di Inggris: Daily Mail, Telegraph, TimesGuardian, dan Independent, masing-masing menerbitkan kumpulan soal-soal Sudoku dalam beberapa seri buku. Di Amerika Serikat buku-buku Sudoku masuk top ten best seller. Di amazon.com, toko buku online terbesar, ada 314 judul buku Sudoku. Hanya di Inggris, dua juta buku Sudoku terjual dalam kurun waktu kurang dari setahun (Reuters, 22 Oktober 2005).
Internet pun semakin ramai. Situs-situs baru bermunculan, menyajikan soal sudoku maupun informasi lain, baik sejarah, cara-cara penyelesaian, bahkan software untuk komputer maupun handphone, bukan computer game dengan tampilan grafis memikat, tetapi sebuah puzzle sederhana. Dalam kurun satu tahun bisa merambah seluruh benua, disukai tua muda. Hampir semua koran nasional di setiap negara menyajikan sudoku. Ada yang menganggapnya sebagai Rubik's Cube abad 21, mengacu pada popularitas permainan asal Rusia pada 1980-an.
Penyebaran awal sudoku khususnya di Asia dimulai di Hindustan Times (India , Mei 2005), The Star (Malaysia, Juni 2005),  Apple Daily (Hongkong, Agustus 2005), Sport Hankook (Korea Selatan, September 2005), News Paper (Singapura, Oktober 2005). Kompas, 24 Oktober 2005 mengabarkan Wayne Gould menebar wabah Sudoku, Intisari edisi Januari 2006 menulis sudoku, kotak ajaib yang mewabah namun Indonesia tidak juga terjangkiti. Pada tanggal 27 Februari 2006, di Sudoku Players' Forum, Punky mengenal sudoku saat tinggal di Australia mengeluh tidak menemukan satu pun media cetak Indonesia yang memuat sudoku dan muncul pertanyaan pengelola forum Why would they not want Sudoku?.
Aturan permainan sudoku sangat sederhana. Isi semua matriks sampai penuh dengan angka 1, 2, 3,4, 5, 6, 7, 8, atau 9 atau sesuaikan dengan ukuran papan sudoku, dengan catatan untuk setiap kolom, baris maupun submatriks (  hanya boleh terisi masing-masing satu dan tidak boleh berulang, beberapa kotak sudah diisi sebagai petunjuk awal dan tugas pemain adalah melengkapi kotak yang masih kosong hingga terisi secara lengkap untuk memulai sudoku agar lebih mudah, mulailah dengan blok yang sudah terisi angka yang paling banyak (karena biasanya kotak sudoku memiliki beberapa blok yang terisi angka yang banyak). Sudoku berbentuk matriks  dengan submatriks  yamg ditandai dengan garis tebal. Sudoku yang paling umum adalah berbentuk matriks . Tingkat kesulitan permainan sudoku, selain diukur dari besar ukuran matriksnya juga diukur dari masalah perumusan angka-angka awal yang diberikan. Semakin sedikit angka-angka yang diberikan semakin sulit sudoku untuk diselesaikan.
Menurut Gunawan (2010:6) permainan sudoku dapat diselesaikan dengan kombinasi beberapa teknik. Teknik dalam menyelesaikan permainan sudoku antara lain: (1) pemindaian (scanning), pemindaian berupa proses memindai baris atau kolom untuk mengindentifikasi baris mana dalam suatu blok yang terdapat angka–angka tertentu. Proses ini kemudian diulang pada setiap kolom (atau baris) secara sistematis. Kemudian menentukan nilai dari suatu sel dengan membuang nilai nilai yang tak mungkin; (2) penandaan (marking), penandaan berupa logika, dengan menandai kandidat angka yang dapat dimasukkan dalam sel; (3) analisa (analyzing), analisa berupa eliminasi kandidat dimana kemajuan dicapai dengan mengeliminasi kandidat angka secara berturut-turut hingga sebuah sel hanya punya satu kandidat.

Algoritma Genetika



Algoritma genetik adalah teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimalisasi dan masalah pencarian. Algoritma genetik adalah kelas khusus dari algoritma evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover).
Algoritma genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.
Algoritma genetik khususnya diterapkan sebagai simulasi komputer sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimalisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan penggunaan penyandian (encoding) yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritma.
Secara sederhana, algoritma umum dari algoritma genetik ini dapat dirumuskan menjadi beberapa langkah, yaitu sebagai berikut:
1.    membentuk suatu populasi individual dengan keadaan acak;
2.    mengevaluasi kecocokan setiap keadaan individual dengan hasil yang diinginkan;
3.    memilih individual dengan kecocokan yang tertinggi;
4.    bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi.
Mengulangi langkah 2  sampai langkah 4 sampai ditemukan individual dengan hasil yang diinginkan.