19
Andi Tenriawaru//Paradigma, Vol.15 No.1 Pebruari.2011 hlm.19–27
ALGORITMA TANDA UNTUK PENYELESAIAN FUZZLE SUDOKU Andi Tenriawaru1) Jurusan Matematika FMIPA Unhalu, Kendari, Sulawesi Tenggara 93232
ABSTRAK Puzzle Sudoku dapat diselesaikan dengan berbagai cara, antara lain dengan pewarnaan graf, algoritma pencil-and-paper, dan algoritma genetika. Tulisan ini memaparkan sebuah algoritma untuk menyelesaikan masalah Fuzzle Sudoku tanpa menggunakan bantuan komputer, yang selanjutnya disebut Algoritma Tanda. Kata kunci: Fuzzle Sudoku, Algoritma Tanda ABSTRACT Sudoku puzzle can be solved with several method such as graph colouring, pencil-and-paper algorithm and genetic algorithm. This article describes an alogrithm to solve Sudoku puzzle problems without a computer called as SIGN algorithm. Keywords: Sudoku Puzzle, SIGN Algorithm. Diterima: 9 Juni 2010 Disetujui untuk dipublikasikan: 11 September 2010
1. Pendahuluan Fuzzle Sudoku merupakan permainan yang sudah banyak dikenal. Puzzle Sudoku dengan ukuran n2 x n2 dapat diselesaikan dengan berbagai cara, antara lain
dengan
pewarnaan graf, algoritma pencil-and-paper, dan algoritma genetika. Kebanyakan dari metode yang digunakan memerlukan bantuan komputer untuk menyelesaikannya. Seperti halnya J.F. Crook, dalam tulisannya A Pencil-and-Paper Algorithm for Solving Sudoku Puzzle, penulis juga mencoba memaparkan cara menyelesaikan masalah puzzle Sudoku tanpa harus menggunakan alat bantu komputer, cukup menggunakan alat tulis, penghapus dan kertas. Penyelesaian masalah puzzle Sudoku dengan menggunakan algoritma Pencil-andPaper, membutuhkan konsentrasi yang penuh serta logika berfikir dan analisa yang baik. Hal ini tentunya tidak dimiliki oleh semua orang. Dalam tulisan ini, penulis memaparkan sebuah algoritma yang lebih sederhana untuk menyelesaikan masalah puzzle Sudoko.
20
Algoritma Tanda untuk Penyelesaian Fuzzle Sudoku
2. Puzzle Sudoku Puzzle Sudoku sebenarnya memiliki ukuran yang bervariatif, namun yang paling umum adalah berukuran n2 x n2 dengan n≥2. Puzzle Sudoku merupakan permainan pada matriks bujursangkar berukuran n2 x n2 yang memuat n2 sub-matriks bujursangkar berukuran n x n. Tujuan Puzzle Sudoku adalah menyusun angka dari 1 sampai dengan n2 dalam matriks tersebut dengan aturan tidak ada angka yang berulang dalam satu baris, satu kolom, dan satu sub-matriks. Sebagai contoh untuk n=3, diperoleh puzzle Sudoku dengan matriks berukuran 9x9, yang mana memiliki 81 sel, 9 baris, 9 kolom dan 9 sub-matriks. seperti yang terlihat dalam gambar berikut: I
II
9 3
III
8 IV
V
7 5
VIII
IX
7 1
2 5
6 2 6
3
VI
5 VII
8
1 6 7
7 1 3
6 4
8
5 7
Gambar 1. a. Matriks Puzzle Sudoku berukuran 9x9. b. Contoh Kasus Puzzle Sudoku berukuran 9x9 3. Algoritma Tanda Algoritma berikut disusun untuk menyelesaikan masalah puzzle Sudoku tanpa harus menggunakan alat bantu komputer. Algoritma ini disusun dengan mengadopsi prinsipprinsip yang ada pada algoritma backtraking. Kata sekawan digunakan dalam algoritma ini, yang artinya sel-sel yang tidak boleh memiliki angka yang sama dengan sel kawannya. Sebagai contoh, sel [x,y] yakni sel yang terdapat pada baris ke-x dan kolom ke-y, sekawan dengan sel-sel yang terdapat pada baris ke-x dan sel-sel yang terdapat pada kolom ke-y serta sel-sel yang berada pada sub-matriks yang sama dengan sel [x,y]. Adapun susunan algoritma tanda adalah sebagai berikut:
Andi Tenriawaru//Paradigma, Vol.15 No.1 Pebruari.2011 hlm.19–27
21
1. Masing-masing angka yang diberikan pada permasalahan awal dari puzzle Sudoku dihitung. Kemudian diurutkan dari yang terbanyak jumlahnya kemunculannya. 2. Langkah berikut dilakukan secara berturut-turut berdasarkan fokus angka dengan urutan pada no.1: a. Tanda X diberikan pada semua sel yang sekawan dengan sel yang berisi angka yang menjadi fokus. b. Langkah berikut dilakukan secara berulang mulai dari sub-matriks terendah sampai seluruh sub-matriks terpenuhi: i. Dilakukan pengecekan apakah ada masalah, yakni tidak ada tempat untuk tanda kandidat (missal C). Jika tidak terjadi masalah, dilanjutkan ke langkah 2.b.ii. Namun jika terjadi masalah dilakukan hal berikut: - Jika masalah terjadi pada sub-matrik pertama, maka disimpulkan masalah puzzle Sudoku tidak memiliki penyelesaian, jika tidak, lanjut. - Berpindah ke sub-matriks sebelumnya. - Tanda kandidat di sub-matriks ini beserta tanda X yang diakibatkannya dihapus. Kemudian dilanjutkan ke langkah 2.b.ii. ii. Tanda kandidat (missal C) diberikan pada sel yang kosong (sel yang berpeluang menjadi kandidat). iii. Tanda X diberikan pada semua sel yang sekawan dengan sel yang berisi tanda kandidat. iv. Dilakukan perpindahan ke sub-matriks berikutnya. c. Tanda kandidat diganti dengan angka yang menjadi fokus dan tanda X dihapus pada seluruh sel. d. Dilanjutkan ke langkah 2. 4. Contoh Penerapan Algoritma Tanda
22
Algoritma Tanda untuk Penyelesaian Fuzzle Sudoku
Berikut ini akan diperlihatkan hasil penerapan algoritma Tanda untuk menyelesaian masalah puzzle Sudoku. Contoh kasus yang akan diselesaikan adalah kasus yang terlihat pada Gambar 1(b). Berikut langkah-langkah penyelesaian puzzle Sudoku menggunakan algoritma Tanda:
1.
Urutan banyaknya masing-masing angka adalah: Tabel 1. Urutan Banyaknya Angka yang Muncul
2.
Angka
7
5
6
1
3
8
2
4
9
Banyaknya
5
4
4
3
3
3
2
1
1
Fokus: angka 7 a. Tanda X diberikan pada semua sel yang sekawan dengan angka yang menjadi focus, seperti yang terlihat pada Gambar 2(a). b. Fokus: sub-matriks I: i. Tidak ada masalah karena terdapat tempat untuk tanda kandidat. ii. Tanda kandidat C diberikan pada sel yang kosong. iii. Tanda X diberikan pada semua sel yang sekawan dengan tanda kandidat, seperti yang terlihat pada Gambar 2(b). x
9
x
7
X
x
8
6
3
1
x
X
5
x
2
6
x
X
x
x
x
x
x
7
x
X
x
x
x
6
X
x
x
3
X
7
x
x
X
5
x
x
x
1
x
7
x
x
x
x
1
x
8
x
2
x
6
5
4
x
X
X
X
9
X
7
X
X
8
6
X
C1
3
1
X
X
5
X
2
X
8
X
6
X
X
X
X
X
X
X
7
X
X
X
X
X
6
X
X
X
3
X
7
X
X
X
X
5
X
X
X
1
X
X
X
X
x
3
5
X
X
2
X
6
8
x
7
X
X
5
4
X
X
X
7
X
X
X
1
X
X
X
3
5
X
8
X
7
X
Gambar 2. (a) Hasil Langkah 2a, (b) Hasil Langkah 2b iv. Berpindah ke sub-matriks III (karena sub-matriks II sudah ada angka 7). Sub-matriks III: Dilakukan hal yang sama sepertihalnya pada sub-matriks I, sehingga diperoleh: 9
X
7
X
X
8
6
X
C1
3
1
X
X
5
X
2
X
8
X
6
X
X
X
X
X
C2
23
Andi Tenriawaru//Paradigma, Vol.15 No.1 Pebruari.2011 hlm.19–27
X
X
7
X
X
X
X
X
6
X
X
X
3
X
7
X
X
X
5
X
X
X
1
X
X
X X
2
X
6
X
5
4
X
X
X
7
X
X
X
1
X
X
X
3
5
X
8
X
7
X
Gambar 3. Hasil sub-matriks III
Berpindah ke sub-matriks VII (karena sub-matriks IV, V, dan VI sudah ada angka 7). Untuk sub-matriks VII dan VIII, dilakukan hal yang sama sepertihalnya pada sub-matriks III, sehingga diperoleh hasil seperti pada Gambar 4. Sedang untuk sub-matriks IX tidak dilakukan apa-apa karena sudah ada angka 7. X
9
X
7
X
X
8
6
X
X
9
X
7
X
X
8
6
C1
3
1
X
X
5
X
2
X
C1
3
1
X
X
5
X
2
X X
8
X
6
X
X
X
X
X
C2
8
X
6
X
X
X
X
X
C2
X
X
7
X
X
X
X
X
6
X
X
7
X
X
X
X
X
6
X
X
X
3
X
7
X
X
X
X
X
X
3
X
7
X
X
X X
5
X
X
X
1
X
7
X
X
5
X
X
X
1
X
7
X
X
C3
X
X
X
X
1
X
X
X
C3
X
X
X
X
1
X
X
X
2
X
6
X
3
5
X
X
2
X
6
C4
X
3
5
X
X
5
4
X
8
X
7
X
X
5
4
X
X
8
X
7
X
X
Gambar 4. (a) Hasil sub-matriks VII, (b) Hasil sub-matriks VIII c. Tanda kandidat diganti dengan angka yang menjadi fokus dan tanda X dihapus. 9 7
3
8
7
8
1
5
6
7
7
6 3
5
7 1
7
7
1
2 5
6 2
6 4
7
3 8
5 7
Gambar 5. Hasil Puzzle Sudoku setelah Penambahan Angka 7 d. Dilanjutkan ke langkah 2. Fokus : angka 5 Dengan langkah yang sama dengan fokus angka 7, diperoleh hasil seperti ada Gambar 6 7
9
5
3
1
7
8 5
6 2
24
Algoritma Tanda untuk Penyelesaian Fuzzle Sudoku
8
6
5
7
6
3
7
5 7 2
6
5
7
5
5
1
7
5
1
7
4
3 8
5 7
Gambar 6. Hasil Puzzle Sudoku setelah Penambahan Angka 5 Fokus : angka 6 Dengan langkah yang sama dengan fokus angka 7, diperoleh hasil seperti ada Gambar 7 dan Gambar 8. X
9
5
7
7
3
1
X
8
X
6
X
X
X
7
5
5 X
X
X
8
6
X
X
9
5
7
X
X
8
6
X
5
X
2
X
7
3
1
X
C1
5
X
2
X
X
X
5
X
7
8
X
6
X
X
X
5
X
7
X
X
X
X
6
X
X
7
5
X
X
X
X
6
7
X
X
5
7
X
X
5
7
X
X
7
X
X X
X
3
X
X
1
7
X
X
5
X
1
X
X
2
X
6
7
X
3
5
X
5
4
X
X
8
7
X
X
3
X
X
X
1
7
X
X
5
X
1
X
2
X
6
7
X
3
5
X
5
4
X
X
8
7
X
5 X
Gambar 7. a. Hasil Langkah 2a. b. Hasil sub-matriks II X
9
5
7
X
X
8
6
X
X
9
5
7
X
X
8
6
X
7
3
1
X
C1
5
X
2
X
7
3
1
X
C1
5
X
2
X
8
X
6
X
X
X
5
X
7
8
X
6
X
X
X
5
X
7
X
X
7
5
X
X
X
X
6
X
X
7
5
X
X
X
X
6
C2
X
X
3
X
7
X
X
5
C2
X
X
3
X
7
X
X
5
5
X
X
X
1
7
X
X
5
X
X
X
1
C3
7
X
X
X
7
X
X
5
X
1
X
X
X
7
X
X
5
X
1
X
X
X
2
X
6
7
X
3
5
X
X
2
X
6
7
X
3
5
X
X
5
4
X
X
8
7
X
X
5
4
X
X
8
7
X
Gambar 8. a. Hasil sub-matriks ke-4. b. Hasil sub-matriks ke-5 Pada Sub-matriks I, III, dan VI sudah ada angka 6, sehingga langsung ke submatriks VII. Namun terjadi masalah pada sub-matriks VII karena sudah tidak ada ruang kosong untuk tanda kandidat lagi, maka dilakukan langkah berikut:
-
Kembali ke sub-matriks sebelumnya, yakni sub-matriks V. Tanda kandidat di sub-matriks V ini dihapus beserta tanda X yang diakibatkannnya, sehingga diperoleh matriks seperti pada Gambar 8(a). Karena tidak ada pilihan lain di kelompok ini maka Kembali ke sub-matriks sebelumnya, yakni sub-matriks ke-4. Tanda kandidat di sub-matriks ke-4 ini dihapus beserta tanda X yang diakibatkannnya, sehingga diperoleh matriks seperti pada Gambar 7(b).
25
Andi Tenriawaru//Paradigma, Vol.15 No.1 Pebruari.2011 hlm.19–27
Dilanjutkan ke langkah 2.b.ii, yakni Tanda kandidat diberikan pada sel yang lain di dalam sub-matriks ke-4 ini dan seterusnya, sehingga diperoleh Gambar 9. X
9
5
7
X
X
8
6
X
7
3
1
X
C1
5
X
2
X
8
X
6
X
X
X
5
X
7
X
X
7
5
X
X
X
X
6
C2
X
3
X
7
X
X
5
5
X
X
X
1
7
X
X
7
X
X
5
X
1
X
X
X
2
X
6
7
X
3
5
X
5
4
X
X
8
7
X
Gambar 9. Hasil sub-matriks IV yang Baru Setelah diperoleh sub-matriks IV yang baru, dilanjutkan kembali ke submatriks V, sub-matriks VII dan sub-matriks IX, sehingga diperoleh hasil puzzle Sudoku setelah penambahan angka 6, seperti yang terlihat pada gamar-gambar berikut. X
9
5
7
X
X
8
6
X
X
9
5
7
X
X
8
6
X
7
3
1
X
C1
5
X
2
X
7
3
1
X
C1
5
X
2
X
8
X
6
X
X
X
5
X
7
8
X
6
X
X
X
5
X
7
X
X
7
5
X
X
X
X
6
X
X
7
5
X
X
X
X
6
X
C2
X
3
X
7
X
X
5
X
C2
X
3
X
7
X
X
5
5
X
X
X
1
C3
7
X
X
5
X
X
X
1
C3
7
X
X
C4
7
X
X
5
X
1
X
X
C4
7
X
X
5
X
1
X
X
X X
2 5
X 4
6 X
7 X
X 8
3
5 7
X X
X X
2 5
X 4
6 X
7 X
X 8
3 C5
5 7
X X
Gambar 10. a. Hasil sub-matriks V. b. Hasil sub-matriks VII dan IX
7
9
5
3
1
8
7
6
5
11.
7 1
7 5
6
5 6 4
7 6
3
2
6 2
5
5
Gambar
5
6 7
6
8 6
5 7 1
7 8
3
5
6
7
Hasil Puzzle Sudoku Penambahan angka 6
setelah
Langkah-langkah penambahan angka 7, 5, dan 6 dilakukan kembali untuk memperoleh penambahan angka 1, 3, 8, 2, 4, dan 9. Sehingga diperoleh hasil akhir dari masalah puzzle Sudoku, seperti yang terlihat pada Gambar 12.
26
Algoritma Tanda untuk Penyelesaian Fuzzle Sudoku
7
9
5
3
1 6
1
1
7
5
8 6
7
8 6
7 1
6
7
1
5
6
5
2
6
6
7
4
1
2 5
3
5
5
1
7 7
8
6
3
5
9
5
3
1
1
7
5 6
7
1
5
1
3
5
8
6
7
3 6
6
1
7
5
6
1
7
9
5
7
3
1
8
6
1
1
7
5
8 3
6
3
8
5
6
5
5
1 3
6
7
5 6
4
3
1
7
1
3
5
3
8
6
7
9
5
7
3
1
8
6
6
1
2
1
7
5
6
2
3
8
7
2
1
6
7
5
2
1
7
1
3
5
3
8
6
7
2
7
8
6
3
1
5
7
1
6
7
7
1
3
5
3
8
6
7
6
7
3
2
8
1
5
4
2
9
5
7
4
3
8
6
7
3
1
8
6
5
4
2
8
4
6
1
2
5
3
3
1
7
5
2
4
6
2
3
8
7
5
8
2
1
6
7
6
7
3
4
5
2
1
2
8
6
7
1
3
5
4
3
8
6
3
8
5
6
1
2 5
3
7
2
8
6
1
5
3
5
8
8
6
7
3
2
8
1
5
4
2
9
5
7
4
3
8
6
1
7
3
1
8
6
5
4
2
9
7
8
4
6
1
2
9
5
3
7
8
6
3
1
7
5
9
4
2
8
6
1
5
4
6
2
3
8
7
9
1
5
4
3
5
8
9
2
1
6
7
4
3
8
6
7
3
4
5
2
1
9
8
5
4
9
2
8
6
7
1
3
5
4
7
2
1
5
4
9
3
8
6
7
2
1
6
c
3 8
d
4
e
1
7
3
8
1
7
2
8 8 5
1
2
5
6
3
b 3
6
1
6 7
a 7
6 2
5
3
2
8
5
1
f
Gambar 12. Hasil Penambahan Angka 1,3, 8, 2, 4, dan 9
5. Kesimpulan Puzzle Sudoku dengan ukuran n2 x n2 dapat diselesaikan dengan berbagai cara, antara lain dengan pewarnaan graf, algoritma Pencil-and-Paper, dan algoritma genetika. Kebanyakan dari metode yang digunakan memerlukan bantuan komputer untuk menyelesaikannya. Algoritma Tanda merupakan algoritma yang digunakan untuk menyelesaikan masalah puzzle Sudoku tanpa harus menggunakan bantuan komputer, seperti halnya algoritma Pencil-and-Paper.
Andi Tenriawaru//Paradigma, Vol.15 No.1 Pebruari.2011 hlm.19–27
27
Daftar Pustaka [1] Craak, J.F. 2009. A pencil-and-paper algoritm for solving Sudoku puzzle. Notices of the AMS, 56(4):460-468. [2] Davis, Tom. 2008. The Mathematics of Sudoku. http:/www.geometer.org/mathecircles/Sudoku.pdf. [3] Harberg, Agnes M and M. Ram Murty. 2007. Sudoku Squares and chromatics polynomials. Notices of the AMS, 54(6):704-717.
