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. 🙂

Advertisements

4 thoughts on “Sudoku Solver dengan Algoritma Bruteforce”

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s