Tuesday, January 10, 2012

17 Petunjuk Angka untuk Pecahkan Sudoku

17 Petunjuk Angka untuk Pecahkan Sudoku - Matematikawan asal Irlandia berhasil memecahkan masalah dalam permainan Sudoku, yakni jumlah minimal petunjuk angka sehingga bisa ditemukan jawaban unik. Gary McGuire, sang matematikawan, menggunakan alogaritma kompleks dan menghabiskan jutaan jam CPU dengan memakai superkomputer untuk bisa memecahkan masalah itu.
17 Petunjuk Angka untuk Pecahkan Sudoku

Berdasarkan temuannya, McGuire mengungkapkan bahwa jumlah petunjuk angka minimal yang diperlukan adalah 17. Bila jumlahnya 16 saja, maka jawaban yang ditemukan tidak unik atau tunggal. Kebanyakan koran yang menawarkan Sudoku memberi 25 petunjuk angka. Tingkat kesulitan makin kecil jika petunjuk bertambah.

Dalam konsensus para matematikawan pada konferensi di Boston, Massachusetts, Sabtu (7/1/2012) lalu, diakui bahwa hasil studi McGuire mungkin valid dan merupakan perkembangan berarti dalam matematika Sudoku. Matematikawan berpendapat bahwa pendekatan McGuire cukup beralasan dan masuk akal.

Sudoku merupakan permainan mengisi kotak 9 x 9 dengan nomor 1-9 tanpa diperbolehkan mengulang angka yang sama di baris atau kolom yang sama. Sejumlah orang telah menggunakan 17 petunjuk angka dan menemukan jawabannya. Namun, tak ada seorang pun yang memakai 16 angka menemukannya. Ini jadi awal hipotesis McGuire.

Sebenarnya, untuk membuktikan hipotesis bahwa Sudoku minimal membutuhkan petunjuk angka sejumlah 17, McGuire harus melakukan tes satu per satu pada kemungkinan solusi. Tetapi, kata McGuire, langkah itu akan memakan waktu 300.000 tahun. Jadilah, McGuire mengembangkan alogaritma hitting set.

Alogaritma hitting set mendeteksi angka dalam Sudoku yang bisa dipertukarkan sehingga bisa menghasilkan jawaban ganda atau lebih. Dengan menggunakan alogaritma ini, McGuire hanya butuh 2 tahun untuk menyelesaikan. Semua ia tuntaskan di Irish Centre for High-End Computing in Dublin.

Yang menarik, alogaritma yang digunakan McGuire tidak hanya bisa berguna untuk Sudoku. "Soal hitting set punya aplikasi luas di dalam banyak bidang sains, seperti bio-informasi dan tes perangkat lunak," jelas McGuire
[sumber:kompas.com]

0 comments:

Post a Comment

Share

Twitter Delicious Facebook Digg Stumbleupon Favorites