Home > Coretan > Sudoku Solver dengan Algoritma Bruteforce

Sudoku Solver dengan Algoritma Bruteforce


Di Semester ini, di hari pertama kuliah di tingkat tiga (Sekitar sebulan yang lalu), saya langsung mendapatkan tugas. Dari ukurannya termasuk tugas kecil sih, yakni membuat program yang dapat mencarikan solusi untuk  sebuah sudoku.

Dalam penyelesaian tugas ini, saya diharuskan menggunakan metode bruteforce sebagai dasar berpikir untuk mencari solusi sudoku.

Nah, berikut proses penyelesaian Sudoku Solver yang saya buat:

Algoritma Utama:

  • Tempatkan angka “1” pada sel pertama. Periksa apakah penempatan “1” dibolehkan (dengan memeriksa baris, kolom, dan kotak).
  • Jika tidak ada pelanggaran, maju ke sel berikutnya. Tempatkan “1” pada sel tersebut dan periksa apakah ada pelanggaran.
  • Jika pada pemeriksaan ditemukan pelanggaran, yaitu penempatan “1” tidak dibolehkan, maka coba dengan menempatkan “2”.
  • Jika pada proses penempatan ditemukan bahwa tidak satupun dari 9 angka diperbolehkan, maka tinggalkan sel tersebut dalam keadaan kosong, lalu mundur satu langkah ke sel sebelumnya. Nilai di sel tersebut dinaikkan 1.
  • Ulangi sampai 81 buah sel sudah terisi solusi yang benar.

Alur Program Utama:

  • Inisiasi Sudoku dengan jumlah baris dan kolom masing-masing sembilan.
  • Lakukan pengambilan input dari file eksternal
  • Memberikan status “update-able” pada sel yang bernilai ‘0’
  • Eksekusi Algoritma Utama
  • Lakukan Penghitungan waktu awal, Proses pencarian solusi dan Penghitungan waktu akhir dimana proses berhenti.
  • Hitung selisih waktu dan frekuensi counter per detik
  • Mengeluarkan output dari program berupa solusi untuk sudoku, jumlah iterasi serta waktu eksekusinya.

Berikut adalah contoh masukan dan Hasilnya :

Contoh Masukan Satu:

5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

Hasil Satu:

Contoh Masukan Dua:

9 0 0 1 0 4 0 0 2
0 8 0 0 6 0 0 7 0
0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 1
0 7 0 0 0 0 0 3 0
3 0 0 0 0 0 0 0 7
0 0 0 0 2 0 0 0 0
0 3 0 0 7 0 0 8 0
1 0 0 0 0 9 0 0 0

Hasil Dua:

Dari Kedua Hasil di atas, dapat kita lihat hasil sudokunya benar. Namun, apabila kita melihat iterasi yang harus dilakukan serta waktu yang dibutuhkan untuk mencari solusi sudoku, algoritma ini akan memakan waktu yang sangat lama. Apalagi bila menyelesaikan sudoku yang levelnya “Impossible”.

Sekian.🙂

Nb: Algoritma di atas sengaja tidak dicantumkan terlalu detil dan tidak disertakan source codenya. Bila pembaca berminat dapat menghubungi saya.🙂

  1. feza
    15/06/2012 at 12:01

    minta source codenya dunk😀, ,
    da tugas nie bingung :’)

  2. wildan
    24/12/2013 at 14:39

    kang boleh minta source code nya? treima kasih

  3. 18/05/2015 at 19:42

    Gan, boleh bagi programnya gak ?😀

  4. 20/04/2016 at 23:18

    boleh bagi source codenya? trima kasih sebelumnya

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: