PENYELESAIAN PUZZLE SUDOKU MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER
MUHAMAD FARDAN WARDHANA
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
ABSTRAK MUHAMAD FARDAN WARDHANA. Penyelesaian Puzzle Sudoku Menggunakan Pemrograman Linear Integer. Dibimbing oleh AMRIL AMAN dan NGAKAN KOMANG KUTHA ARDANA. Sudoku dapat dipandang sebagai puzzle (teka-teki) dalam matematika. Pemain harus mengisi sebuah matriks n2 × n2 yang berisi beberapa unsur awal yang diberikan, sehingga setiap baris, kolom, dan mini grid n × n berisi masingmasing bilangan bulat 1 sampai n2. Tujuan penelitian ini adalah mengkaji Sudoku tradisional, Sudoku X (Sudoku diagonal) dan menggunakan metode branch and bound, untuk mencari hubungan antara kemungkinan solusi yang muncul dengan ukuran Sudoku, dan banyaknya given yang diberikan. Solusi Sudoku ditentukan dengan menggunakan metode branch and bound yang diimplementasikan pada script m-file. Kami dapat menemukan hubungan antara kemungkinan solusi yang muncul dengan ukuran Sudoku, dan banyaknya given yang diberikan. Di sisi lain, kami tidak dapat menemukan hubungan semacam itu untuk ukuran Sudoku yang umum dan konfigurasi yang umum. Kata kunci: Sudoku, linear integer, branch and bound
ABSTRACT MUHAMAD FARDAN WARDHANA. Solving Sudoku Puzzle by Using Linear Integer Programming. Supervised by AMRIL AMAN and NGAKAN KOMANG KUTHA ARDANA. Sudoku can be viewed as a puzzle in mathematics. Players must fill in a n2 × n2 matrix which is containing some given enteries, so that each row, column, and n × n mini grid contains each integer 1 through n2. The objectives of this research are to study the traditional Sudoku puzzle, Sudoku X puzzle (diagonal Sudoku) and use branch and bound method, to find the relation between the number of possible solution with the size of sudoku, and the number quantity givens. The solutions are determined using branch and bound method that was implemented on m-file script. We can find the relation between the number of possible solution with the size of sudoku, and the number quantity givens. On the other hand, we can not find such relation for general size of sudoku and general configuration. Keywords: Sudoku, linear integer, branch and bound
PENYELESAIAN PUZZLE SUDOKU MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER
MUHAMAD FARDAN WARDHANA
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
Judul Skripsi : Penyelesaian Puzzle Sudoku Menggunakan Pemrograman Linear Integer Nama : Muhamad Fardan Wardhana NIM : G54061543
Disetujui oleh
Dr Ir Amril Aman, MSc Pembimbing I
Ir Ngakan Komang Kutha Ardana, MSc Pembimbing II
Diketahui oleh
Dr Toni Bakhtiar, MSc Ketua Departemen
Tanggal Lulus:
PRAKATA
Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunia-Nya sehingga penelitian dengan judul Penyelesaian Puzzle Sudoku Menggunakan Pemrograman Linear Integer dapat diselesaikan. Terima kasih penulis ucapkan kepada Bapak Dr Ir Amril Aman, MSc dan Bapak Ir Ngakan Komang Kutha Ardana, MSc selaku pembimbing, serta Bapak Dr Ir I Gusti Putu Purnaba, DEA yang telah banyak memberi saran. Ungkapan terima kasih juga disampaikan kepada (alm) ayah, (almh) ibu, istri serta seluruh keluarga, atas segala doa dan kasih sayangnya. Semoga karya ilmiah ini bermanfaat.
Bogor, Maret 2014 Muhamad Fardan Wardhana
DAFTAR ISI PENDAHULUAN
1
Latar Belakang
1
Perumusan Masalah
1
Tujuan Penelitian
2
Ruang Lingkup Penelitian
2
TINJAUAN PUSTAKA
2
Definisi 1 Puzzle (teka-teki) Sudoku
2
Definisi 2 Persamaan Linear
2
Pemrograman Linear
3
Definisi 3 Bentuk Standar Suatu PL
3
Solusi Suatu Pemrograman Linear
3
Definisi 4 Daerah Fisibel
4
Definisi 5 Solusi Basis
4
Definisi 6 Solusi Fisibel Basis
4
Definisi 7 Solusi Optimum
4
Pemrograman Linear Integer
4
Metode Branch and Bound
5
DESKRIPSI DAN PEMODELAN MASALAH
9
Deskripsi Masalah
9
Pemodelan Masalah
9
PEMBAHASAN
13
Contoh Kasus
13
Mencari Solusi Puzzle Sudoku Tradisional pada Matriks 9 × 9
22
Mencari Solusi Puzzle Sudoku X (Sudoku Diagonal) pada Matriks 9 × 9
25
Hubungan Antar Ukuran Sudoku, Banyaknya Unsur Awal, dan Konfigurasi Sudoku Tradisional. 28 SIMPULAN DAN SARAN
29
Simpulan
29
Saran
29
DAFTAR PUSTAKA
30
DAFTAR GAMBAR 1. 2. 3. 4.
Soal Sudoku dengan input data secara acak Daerah fisibel PLI (2.5) Daerah fisibel untuk Subproblem 2 (x1 ≥ 4) dan Subproblem 3 (x1 ≤ 3) Seluruh pencabangan pada metode branch and bound untuk menentukan solusi PLI (2.5) 5. Bentuk umum Sudoku ukuran 4 × 4 6. Contoh soal Sudoku 4 × 4 7. Solusi Sudoku 4 × 4 8. Bentuk umum Sudoku ukuran 9 × 9 9. Contoh soal Sudoku tradisional 9 × 9 10. Solusi Sudoku tradisional ukuran 9 × 9 11. Contoh soal puzzle Sudoku yang memiliki banyak solusi (terhingga) 12. Contoh soal Sudoku X ukuran 9 ×9 13. Solusi Sudoku X ukuran 9 × 9
1 7 7 9 13 16 22 23 24 25 25 26 27
DAFTAR LAMPIRAN 1. Script M-File sudoku.m untuk mencari solusi Sudoku tradisional. 2. Script M-File sudokuX.m untuk mencari solusi Sudoku X (Sudoku diagonal) 3. Contoh mencari solusi untuk soal Sudoku ukuran 9 × 9 dengan script M-File 4. Contoh mencari solusi untuk soal Sudoku ukuran 9 × 9 yang memiliki banyak solusi (terhingga) dengan menggunakan script M-File 5. Contoh mencari solusi untuk soal Sudoku X ukuran 9 × 9 dengan menggunakan script M-File 6. Contoh mencari solusi untuk soal Sudoku X ukuran 9 × 9 yang memiliki banyak solusi (terhingga) dengan menggunakan script M-File 7. Hubungan antar ukuran Sudoku, banyaknya unsur awal, dan konfigurasi Sudoku tradisional
31 33 36 37 42 43 44
DAFTAR TABEL 1. Hubungan antar ukuran, unsur, dan konfigurasi Sudoku tradisional
28
PENDAHULUAN Latar Belakang Sudoku adalah sebuah puzzle berdasarkan logika yang pertama kali hadir di Amerika Serikat dengan judul “Number Place” di majalah “Dell Pencil Puzzle & Word Games” di tahun 1979. Pada tahun 1980-an, permainan ini berkembang menjadi popular di Jepang dan telah diganti nama oleh penerbit menjadi “suji wa dokushin ni kagiru”, yang diterjemahkan menjadi “the digits must remain single (angka-angkanya harus tetap tunggal)”. Pada akhirnya diperpendek menjadi ”Sudoku” atau “single number (nomor tunggal) ” (Bartlett, 2008). Sudoku pada umumnya hadir dalam bentuk matriks 9 x 9. Aturannya mudah: isi dalam matriks sehingga setiap baris, kolom, dan submatriks 3 x 3 yang diisi angka 1 sampai 9 hanya satu kali. Sesuai namanya, maka tidak boleh ada angka/digit yang sama. Hal inilah yang dinamakan dengan “Prinsip keunikan” (Principle of Uniqueness). Setiap puzzle muncul dengan sejumlah nomor yang diberikan. Nomor dan posisinya menentukan tingkat kesulitan permainan ini. Gambar 1 adalah salah satu contoh puzzle Sudoku 9 x 9.
Gambar 1 Soal Sudoku dengan input data secara acak Kesulitan tingkat permainan Sudoku, selain diukur dari besar ukuran matriksnya (n2 × n2), biasanya diukur dari problem perumusan angka-angka awal yang telah diatur posisi dan nilainya. Semakin sedikit angka-angka awal yang diberikan, tentunya akan semakin sulit. Perumusan Masalah Sudoku menghasilkan dua pertanyaan menarik secara matematika sebagai berikut: Bagaimana puzzle-puzzle ini bisa diselesaikan secara matematika? dan teknik matematika apa yang bisa digunakan untuk menciptakan dan menyelesaikan puzzle-puzzle Sudoku ini?
2 Tujuan Penelitian Di dalam tulisan ilmiah ini akan dipelajari mengenai puzzle (teka-teki) Sudoku, yang selanjutnya disebut dengan Sudoku sebagai sebuah permasalahan pemrograman bilangan bulat (Integer Programming Model). Tujuan dari karya ilmiah ini: 1. Mengkaji Sudoku tradisional menggunakan metode Branch and Bound. 2. Mengkaji Sudoku yang baru (Sudoku diagonal) menggunakan metode Branch and Bound. 3. Mencari hubungan antar ukuran Sudoku, banyaknya unsur awal, dan konfigurasi pada Sudoku tradisional. Ruang Lingkup Penelitian Sudoku memiliki berbagai ukuran. Dalam tulisan ilmiah ini, penulis membatasi pembahasan dan pencarian pola untuk Sudoku berukuran 9 × 9.
TINJAUAN PUSTAKA Definisi 1 Puzzle (teka-teki) Sudoku Sudoku adalah sebuah permainan teka-teki angka berbasis logika yang pada umumnya berbentuk matriks 9 × 9 (n2 × n2 dengan n = 3) dan memiliki aturan yang sederhana dengan menyusun bilangan-bilangan 1,2,3, … , n2 pada kotak berjumlah n2 × n2 sehingga setiap kolom, baris, maupun mini grid berukuran 3 × 3 (n × n) hanya boleh terisi dengan bilangan 1 sampai 9 yang berjumlah masingmasing satu. Definisi 2 Persamaan Linear Suatu sistem persamaan linear dalam n peubah (variabel) adalah persamaan dengan bentuk a1 x1 a2 x2 ... an xn b di mana a1 , a2 ,..., an dan b adalah bilangan-bilangan real dan x1 , x2 ,..., xn adalah peubah. Dengan demikian maka suatu sistem linear dari m persamaan dalam n peubah adalah satu sistem berbentuk: a11 x1 a12 x2 ... a1n xn b1
a21 x1 a22 x2 ... a2 n xn b2 . . . am1 x1 am 2 x2 ... amn xn bm di mana amn dan bm semuanya adalah bilangan-bilangan real. Sistem-sistem bentuk di atas sebagai sistem linear m × n. (Leon 2001)
3 Pemrograman Linear Pemrograman Linear (PL) adalah suatu masalah optimasi yang memenuhi ketentuan-ketentuan berikut: a) Tujuan masalah tersebut adalah memaksimumkan atau meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan ini disebut fungsi objektif. b) Nilai variabel-variabel keputusannya harus memenuhi suatu himpunan kendala. Setiap kendala harus berupa persamaan linear atau pertidaksamaan linear. c) Ada pembatasan tanda untuk setiap variabel dalam masalah ini. Untuk sembarang variabel xi, pembatasan tanda menentukan xi harus tak-negatif (xi ≥ 0) atau tidak dibatasi tandanya (unrestricted in sign). (Winston 2004) Suatu PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut. Definisi 3 Bentuk Standar Suatu PL Suatu pemrograman linear dalam bentuk standar didefinisikan sebagai: Max z (atau min) s.t.
(2.1) Dengan mendefinisikan: A=[
]
[
]
[
]
Maka kendala pada (2.1) dapat ditulis dengan sistem persamaan Ax = b
(2.2)
(Winston 2004) Solusi Suatu Pemrograman Linear Suatu masalah PL dapat diselesaikan dalam berbagai teknik, salah satunya adalah metode simpleks. Metode ini dapat menghasilkan suatu solusi optimum bagi masalah PL dan telah dikembangkan oleh Dantzig sejak tahun 1947 (Winston 2004), dan dalam perkembangannya merupakan metode yang paling umum digunakan untuk menyelesaikan PL. Metode ini berupa metode iteratif untuk menyelesaikan PL berbentuk standar. Pada masalah PL (2.2), vektor x yang memenuhi kendala Ax = b disebut sebagai solusi dari PL (2.2). Misalkan matriks A dapat dinyatakan sebagai A = (B N), dengan B adalah matriks taksingular berukuran m × m yang elemennya berupa koefisien variabel basis dan N merupakan matriks berukuran m × (n – m) yang
4 elemennya berupa koefisien variabel nonbasis pada matriks kendala. Dalam hal ini matriks B disebut matriks basis untuk PL (2.2). Misalkan x dinyatakan sebagai vektor x = (
) dengan xB adalah vektor
variabel basis dan xN adalah vektor variabel nonbasis, maka Ax = b dapat dinyatakan sebagai: Ax
=
(
)
= BxB + NxN = b (2.3) Karena matriks B adalah matriks tak singular, maka B memiliki invers, sehingga dari (2.3) xB dapat dinyatakan sebagai: xB = B-1b - B-1NxN (2.4) Kemudian, fungsi objektifnya berubah menjadi: min z = (Winston 2004) Definisi 4 Daerah Fisibel Daerah fisibel suatu PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada PL tersebut. (Winston 2004) Definisi 5 Solusi Basis Solusi basis adalah solusi pada PL yang didapatkan dengan mengatur variabel n – m sama dengan nol dan nilai untuk penyelesaiannya adalah dari sisa variabel m. Hal ini mengasumsikan bahwa mengatur variabel n – m sama dengan nol sehingga membuat nilai yang unik untuk sisa variabel m atau sejenisnya, dan kolom-kolom untuk sisa dari variabel m adalah bebas linear. (Winston 2004) Definisi 6 Solusi Fisibel Basis Solusi fisibel basis adalah solusi basis pada PL yang semua variabelvariabelnya tak-negatif. (Winston 2004) Definisi 7 Solusi Optimum Untuk masalah maksimalisasi, solusi optimum suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Untuk masalah minimisasi, solusi optimum suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston 2004) Pemrograman Linear Integer Pemrograman linear integer (PLI) adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua
5 variabel harus berupa integer, maka masalah tersebut dinamakan pure integer programming. Jika hanya sebagian yang harus berupa integer, maka disebut mixed integer programming (MIP). PLI dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 PLI. (Garfinkel & Nemhauser 1972) Metode Branch and Bound Prinsip dasar metode branch-and-bound adalah memecah daerah fisibel dari masalah relaksasi-PL dengan membuat subproblem-subproblem. Terdapat dua konsep dasar dalam algoritma branch-and-bound. 1. Branch (Cabang) Branching (pencabangan) adalah proses membagi permasalahan menjadi subproblem-subproblem yang mungkin mengarah ke solusi. 2. Bound (Batas) Bounding (pembatasan) adalah suatu proses untuk mencari atau menghitung batas atas (dalam masalah minimisasi) dan batas bawah (dalam masalah maksimisasi) untuk solusi optimum pada subproblem yang mengarah ke solusi. Metode branch-and-bound diawali dari menyelesaikan relaksasi-PL dari suatu pemrograman linear integer. Jika semua nilai variabel keputusan solusi optimum sudah berupa integer, maka solusi tersebut merupakan solusi optimum PLI. Jika tidak, dilakukan pencabangan dan penambahan batasan pada relaksasiPLnya kemudian diselesaikan. Winston (2004) menyebutkan bahwa untuk masalah maksimisasi nilai fungsi objektif optimum untuk PLI lebih kecil atau sama dengan nilai fungsi objektif optimum untuk relaksasi-PL, sehingga nilai fungsi objektif optimum relaksasi-PL merupakan batas atas bagi nilai fungsi objektif optimum untuk masalah PLI. Diungkapkan pula oleh Winston (2004) untuk masalah maksimisasi bahwa nilai fungsi objektif optimum untuk suatu kandidat solusi merupakan batas bawah nilai fungsi objektif optimum untuk masalah PLI asalnya. Suatu kandidat solusi diperoleh jika solusi dari suatu subproblem sudah memenuhi kendala integer pada masalah PLI, artinya fungsi objektif dan semua variabelnya sudah bernilai integer. Sebelumnya akan dibahas terlebih dahulu pengertian subproblem yang terukur. Menurut Winston (2004), suatu subproblem dikatakan terukur (fathomed) jika salah satu kondisi berikut terpenuhi: a. Subproblem tersebut takfisibel, sehingga tidak dapat menghasilkan solusi optimum bagi PLI. b. Subproblem tersebut menghasilkan suatu solusi optimum dengan semua variabelnya bernilai integer. Jika solusi optimum ini mempunyai nilai fungsi objektif yang lebih baik daripada solusi fisibel yang diperoleh sebelumnya, maka solusi ini menjadi kandidat solusi optimum dan nilai fungsi objektifnya menjadi batas bawah (dalam masalah maksimisasi) dan batas atas (dalam masalah minimisasi) nilai fungsi objektif optimum bagi masalah PLI pada saat itu. Bisa jadi subproblem ini menghasilkan solusi optimum untuk masalah PLI.
6 c.
Nilai fungsi objektif optimum untuk subproblem tersebut tidak melebihi batas bawah saat itu (untuk masalah maksimisasi). Suatu subproblem dapat dieliminasi apabila subproblem tersebut takfisibel dan batas bawah kandidat solusi lebih kecil (untuk masalah maksimisasi) dari nilai fungsi objektif optimum untuk subproblem tersebut.
Berikut ini adalah langkah-langkah penyelesaian suatu masalah maksimisasi dengan metode branch-and-bound : Langkah 0 Didefinisikan z sebagai batas bawah dari solusi PLI yang optimum. Pada awalnya tetapkan z = − dan i = 0. Langkah 1 Subproblem PL(i) dipilih sebagai bagian masalah berikutnya untuk diteliti. Subproblem PL(i) diselesaikan dan diukur dengan kondisi yang sesuai. a) Jika PL(i) terukur, maka batas bawah z dapat diperbarui. Batas bawah z dapat diperbaharui jika solusi PLI yang lebih baik telah ditemukan. Jika tidak, maka bagian masalah (subproblem) baru i dipilih dan langkah 1 diulangi. Jika semua subproblem telah diteliti, maka proses dihentikan. b) Jika PL(i) tidak terukur, lanjutkan ke langkah 2 untuk melakukan pencabangan PL(i). Langkah 2 Pilih satu variabel xj yang nilai optimumnya, yaitu xj*, tidak memenuhi batasan integer dalam solusi PL(i). Singkirkan bidang [xj*] xj [xj*]+1 dengan membuat dua bagian masalah PL yang berkaitan menjadi dua batasan yang tidak dapat dipenuhi secara bersamaan yaitu: xj ≤ [xj*] dan xj ≥ [xj*]+1, dengan [xj*] didefinisikan sebagai integer terbesar yang kurang dari atau sama dengan xj*. Jika PL(i) masih tidak terukur, maka kembali ke Langkah 1. (Taha 1996) Untuk memudahkan pemahaman mengenai metode branch-and-bound diberikan contoh sebagai berikut: Contoh 1 Misalkan diberikan PLI sebagai berikut: Maksimumkan z = 5 x1 + 4 x2 terhadap x1 + x2 5 10 x1 + 6 x2 x1, x2 0 dan integer (2.5) Solusi optimal relaksasi-PL dari masalah PLI (2.5) adalah x1=3.75, x2=1.25, dan z =23.75. Jadi batas atas nilai optimal fungsi objektif masalah PLI (2.5) adalah z= 23.75. Daerah fisibel relaksasi-PL masalah (2.5) ditunjukkan pada Gambar 2 (daerah yang diarsir) sedangkan titik-titik merupakan solusi fisibel masalah PLI (2.5).
7 x2
Daerah fisibel x1 = 3.75 x2 = 1.25
Gambar 2 Daerah fisibel PLI (2.5)
x1
Langkah berikutnya adalah memartisi daerah fisibel relaksasi-PL menjadi dua bagian berdasarkan variabel yang bernilai pecahan (non-integer). Karena x1= 3.75 dan x2=1.25 variabel bernilai pecahan maka dipilih salah satu variabel, misalkan x1, sebagai dasar pencabangan. Jika masalah relaksasi-PL dari PLI (2.5) diberi nama Subproblem 1 dan Subproblem 1 dicabangkan atas x1, maka pencabangan tersebut menghasilkan 2 subproblem, yaitu: Subproblem 2: Subproblem 1 ditambah kendala x1 ≥ 4 Subproblem 3: Subproblem 1 ditambah kendala x1 ≤ 3. Daerah fisibel untuk kedua subproblem di atas diilustrasikan secara grafis pada Gambar 3.
x2
Subproblem 3
Subproblem 2
x1 Gambar 3 Daerah fisibel untuk Subproblem 2 (x1 ≥ 4) dan Subproblem 3 (x1 ≤ 3) Setiap titik (solusi) fisibel dari PLI (2.5) termuat dalam daerah fisibel Subproblem 2 atau Subproblem 3. Setiap subproblem ini saling lepas. Sekarang dipilih subproblem yang belum diselesaikan, misalkan dipilih Subproblem 2. Solusi optimal untuk Subproblem 2 ini adalah x1 = 4, x2 = 0.8333 dan z = 23.333. Karena solusi optimal yang dihasilkan Subproblem 2 bukan solusi integer, maka Subproblem 2 dicabangkan atas x2 sehingga diperoleh dua subproblem lagi, yakni: Subproblem 4: Subproblem 3 ditambah kendala x2 ≥ 1;
8
Subproblem 5: Subproblem 3 ditambah kendala x2 ≤ 0.
Saat ini subproblem yang belum diselesaikan adalah Subproblem 3, 4 dan 5. Salah satu subproblem dipilih, misalnya dengan aturan LIFO (last in first out). Dengan aturan ini berarti dipilih Subproblem 4 atau Subproblem 5. Subproblem 4 takfisibel maka subproblem ini tidak dapat menghasilkan solusi optimal, yang tersisa adalah Subproblem 3 dan Subproblem 5. Karena aturan LIFO, dipilih Subproblem 5, yang kemudian menghasilkan solusi optimal x1=4.5, x2=0 dan z=22.5. Karena x1=4.5 bukan integer, maka dilakukan kembali pencabangan atas x1, sehingga diperoleh: Subproblem 6: Subproblem 5 ditambah kendala x1≥5 ; Subproblem 7: Subproblem 5 ditambah kendala x1≤4. Misalkan dipilih Subproblem 6. Ternyata Subproblem 6 ini juga takfisibel, sehingga tidak dapat menghasilkan solusi optimal. Dengan demikian subproblemsubproblem yang belum diselesaikan adalah Subproblem 3 dan Subproblem 7. Karena aturan LIFO, dipilih Subproblem 7. Subproblem ini kemudian menghasilkan solusi opimal x1=4, x2= 0, dan z= 20. Dapat dilihat bahwa solusi optimal subproblem ini semuanya berupa integer, sehingga merupakan kandidat solusi untuk PLI (2.5). Nilai z pada kandidat solusi ini merupakan batas bawah bagi nilai optimal PLI. Penyelesaian Subproblem 3 menghasilkan solusi optimal x1= 3, x2= 2 dan z= 23. Batas bawah yang ditetapkan dari solusi optimal Subproblem 7 tidak lebih baik dari nilai solusi optimal yang dihasilkan Subproblem 3. Dengan demikian, nilai solusi optimal Subproblem 3, yakni z = 23 menjadi batas bawah yang baru. Semua solusi optimal telah berupa integer dan tidak perlu dilakukan pencabangan kembali, sehingga solusi optimal dari Subproblem 3 merupakan solusi optimal PLI (2.5), yakni x1= 3, x2= 2 dan z= 23. Pohon pencabangan yang menunjukkan proses penyelesaian masalah PLI (2.5) secara keseluruhan ditunjukkan pada Gambar 4. (Setianto, 2011)
9
x1=3, x2=2, dan z=23 Kandidat Solusi (Solusi Optimal)
Gambar 4 Seluruh pencabangan pada metode branch and bound untuk menentukan solusi PLI (2.5)
DESKRIPSI DAN PEMODELAN MASALAH Deskripsi Masalah Untuk mendeskripsikan masalah Sudoku, hal utama yang harus diketahui adalah pada kotak berjumlah n2 × n2 dan akan digunakan kasus Sudoku umum dengan n = 3 sehingga setiap kolom, baris, maupun submatriks berukuran 3 × 3 hanya boleh terisi dengan bilangan 1 sampai 9 yang banyaknya masing-masing satu. Soal Sudoku memiliki variasi yang beragam dan memiliki tingkat kesulitan yang berbeda-beda. Pemodelan Masalah Secara matematis, memodelkan Sudoku menggunakan sebuah program linear. Lebih khusus lagi akan dirumuskan oleh formula Binary Integer Linear Programming (BLIP) untuk ukuran puzzle n2 × n2. Variabel-variabel yang digunakan dalam model untuk penyelesaian puzzle Sudoku: i = indeks baris pada puzzle Sudoku, j = indeks kolom pada puzzle Sudoku, k {1, 2,3, 4,5,6,7,8,9),
10 G = nilai Given. Untuk memulai, kita definisikan dengan variabel keputusan: 1 , jika elemen (i, j ) pada matriks Sudoku berukuran n n mengandung integer k xijk 0 , Selainnya
{
Fungsi objektif dan kendala pada Sudoku 9 × 9 (n2 × n2, n = 3) yang memiliki mini grid 3 × 3 (n × n, n = 3). Min 0T x Kendala: Kendala pertama Pada kolom Sudoku hanya boleh terisi dengan bilangan 1 sampai 9 tanpa ada pengulangan. 9
x i 1
ijk
1, j 1: 9, k 1: 9...(3.1)
Kendala kedua Pada baris Sudoku hanya boleh terisi dengan bilangan 1 sampai 9 tanpa ada pengulangan. n
x j 1
ijk
1, i 1: 9, k 1: 9...(3.2)
Kendala ketiga Pada mini grid Sudoku hanya boleh terisi dengan bilangan 1 sampai 9 tanpa ada pengulangan. 3q
3p
j 3q 31 i 3 p 31
xijk 1, k 1: 9, p 1: 3, q 1: 3...(3.3)
Kendala keempat Setiap elemen pada Sudoku harus terisi 9
x k 1
ijk
1, i 1: 9, j 1: 9 (setiap matriks terisi)
Kendala kelima Menentukan nilai Given pada Sudoku xijk 1 (i, j, k ) G (Bartlett, 2008)
11
Dari persamaan (3.1) dapat dijabarkan sebagai berikut: x111 x211 x311 x411 x511 x611 x711 x811 x911 1, x121 x221 x321 x421 x421 x621 x721 x821 x921 1, x131 x231 x331 x431 x431 x631 x731 x831 x931 1, . . . x199 x299 x399 x499 x599 x699 x799 x899 x999 1.
Bentuk umum untuk persamaan (3.1) yaitu: n
x i 1
ijk
1, j 1: n, k 1: n (hanya satu k di setiap kolom)
Dari persamaan (3.2) sebagai berikut: x111 x121 x131 x141 x151 x161 x171 x181 x191 1, x211 x221 x231 x241 x251 x261 x271 x281 x291 1, x311 x321 x331 x341 x351 x361 x371 x381 x391 1, . . . x919 x929 x939 x949 x959 x969 x979 x989 x999 1.
Bentuk umum dari persamaan (3.2) yaitu: n
x j 1
ijk
1, i 1: n, k 1: n (hanya satu k di setiap baris)
Dari persamaan (3.3) dapat dijabarkan sebagai berikut:
12
x111 x211 x311 x121 x221 x321 x131 x231 x331 1, x411 x511 x611 x421 x521 x621 x431 x531 x631 1, x711 x811 x911 x721 x821 x921 x731 x831 x931 1, x141 x241 x341 x151 x251 x351 x161 x261 x361 1, x441 x541 x641 x451 x551 x651 x461 x561 x661 1, x741 x841 x941 x751 x851 x951 x761 x861 x961 1, x171 x271 x371 x181 x281 x381 x191 x291 x391 1, x471 x571 x671 x481 x581 x681 x491 x591 x691 1, x x x x x x x x x 1. . 771 871 971 781 881 981 791 891 991 . . x119 x219 x319 x129 x229 x329 x139 x239 x339 1, x419 x519 x619 x429 x529 x629 x439 x539 x639 1, x719 x819 x919 x729 x829 x929 x739 x839 x939 1, x149 x249 x349 x159 x259 x359 x169 x269 x369 1, x449 x549 x649 x459 x559 x659 x469 x569 x669 1, x749 x849 x949 x759 x859 x959 x769 x869 x969 1, x179 x279 x379 x189 x289 x389 x199 x299 x399 1,
x479 x579 x679 x489 x589 x689 x499 x599 x699 1, x779 x879 x979 x789 x889 x989 x799 x899 x999 1. Persamaan di atas di sederhanakan menjadi: 3
x i 1
i1k
6
x i4
i1k
9
x i 7
i1k
3
x i 1
i 4k
6
x i4
i 4k
9
x i 7
i 4k
3
x i 1
i7k
xi 2 k xi 3k 1; k 1: 9, xi 2 k xi 3k 1; k 1: 9, xi 2 k xi 3k 1; k 1: 9, xi 5 k xi 6 k 1; k 1: 9, xi 5 k xi 6 k 1; k 1: 9, xi 5 k xi 6 k 1; k 1: 9, xi 8 k xi 9 k 1; k 1: 9,
13 6
x i4
i7k
9
x i 7
i7k
xi 8 k xi 9 k 1; k 1: 9, xi 8 k xi 9 k 1; k 1: 9.
Persamaan (3.3) memiliki bentuk umum yaitu: mq
mp
j mq m 1 i mp m 1
xijk 1, k 1: n, p 1: m, q 1: m (hanya satu k di setiap sub matriks)
PEMBAHASAN Contoh Kasus Pada bagian ini akan diberikan contoh kasus dalam penyelesaian Sudoku dengan ukuran 4 × 4 (n2 × n2, n = 2) dan memiliki mini grid 2 × 2 (n × n, n = 2). Misalkan elemen dari baris ke-i dan kolom ke-j adalah xi , j maka Sudoku secara umum adalah
Gambar 5 Bentuk umum Sudoku ukuran 4 × 4 Penyelesaian Sudoku tersebut menggunakan metode branch and bound memerlukan kendala-kendala sebagai berikut: 4
x i 1
ijk
4
x j 1
ijk
1, j 1: 4, k 1: 4 ...(4.1)
1, i 1: 4, k 1: 4...(4.2)
mq
mp
j mq m 1 i mp m 1
xijk 1, k 1: 4, p 1: 2, q 1: 2
Sehingga : 2
2
x j 1 i 1 2
ijk
4
x j 1 i 3 4
ijk
2
x j 3 i 1
ijk
1, k 1: 4...(4.3) 1, k 1: 4...(4.4) 1, k 1: 4...(4.5)
14 4
4
x j 3 i 3
4
x k 1
ijk
ijk
1, k 1: 4...(4.6)
1, i 1: 4, j 1: 4...(4.7)
xijk 1 (i, j, k ) G
Dari persamaan (4.1) diperoleh: x111 x211 x311 x411 1,
x121 x221 x321 x421 1, x131 x231 x331 x431 1, x141 x241 x341 x441 1, x112 x212 x312 x412 1, x122 x222 x322 x422 1, x132 x232 x332 x432 1, x142 x242 x342 x442 1, x113 x213 x313 x413 1, x123 x223 x323 x423 1, x133 x233 x333 x433 1, x143 x243 x343 x443 1, x114 x214 x314 x414 1, x124 x224 x324 x424 1, x134 x234 x334 x434 1, x144 x244 x344 x444 1. Dari persamaan (4.2) diperoleh : x111 x121 x131 x141 1,
x211 x221 x231 x241 1, x311 x321 x331 x341 1, x411 x421 x431 x441 1, x112 x122 x132 x142 1, x212 x222 x232 x242 1, x312 x322 x332 x342 1, x412 x422 x432 x442 1, x113 x123 x133 x143 1, x213 x223 x233 x243 1, x313 x323 x333 x343 1, x413 x423 x433 x443 1,
15
x114 x124 x134 x144 1, x214 x224 x234 x244 1, x314 x324 x334 x344 1, x414 x424 x434 x444 1. Dari persamaan (4.3) diperoleh: x111 x211 x121 x221 1,
x112 x212 x122 x222 1, x113 x213 x123 x223 1, x114 x214 x124 x224 1. Dari persamaan (4.4) diperoleh: x311 x411 x321 x421 1,
x312 x412 x322 x422 1, x313 x413 x323 x423 1, x314 x414 x324 x424 1. Dari persamaan (4.5) diperoleh: x131 x231 x141 x241 1,
x132 x232 x142 x242 1, x133 x233 x143 x243 1, x134 x234 x144 x244 1. Dari persamaan (4.6) diperoleh: x331 x431 x341 x441 1,
x332 x432 x342 x442 1, x333 x433 x343 x443 1, x334 x434 x344 x444 1. Dari persamaan (4.7) diperoleh: x111 x112 x113 x114 1,
x211 x212 x213 x214 1, x311 x312 x313 x314 1, x411 x412 x413 x414 1, x121 x122 x123 x124 1, x221 x222 x223 x224 1, x321 x322 x323 x324 1, x421 x422 x423 x424 1,
16
x131 x132 x133 x134 1, x231 x232 x233 x234 1, x331 x332 x333 x334 1, x431 x432 x433 x434 1, x141 x142 x143 x144 1, x241 x242 x243 x244 1, x341 x342 x343 x344 1, x441 x442 x443 x444 1. Misalkan diberikan soal Sudoku 4×4:
2 3 4
1 4
3
3
Gambar 6 Contoh soal Sudoku 4 × 4 Dari konfigurasi soal puzzle diatas jika dimasukan ke dalam kendala adalah sebagai berikut: Dari persamaan (4.1) x111 x211 x311 x411 0 0 0 0 0
x121 x221 x321 x421 0 0 0 0 0 x131 x231 x331 x431 0 1 0 0 1 x141 x241 x341 x441 0 0 0 0 0 x112 x212 x312 x412 0 0 0 0 0 x122 x222 x322 x422 1 0 0 0 1 x132 x232 x332 x432 0 0 0 0 0 x142 x242 x342 x442 0 0 0 0 0 x113 x213 x313 x413 0 1 0 0 1 x123 x223 x323 x423 0 0 0 1 1 x133 x233 x333 x433 0 0 0 0 0 x143 x243 x343 x443 0 0 1 0 1 x114 x214 x314 x414 0 0 0 1 1 x124 x224 x324 x424 0 0 0 0 0 x134 x234 x334 x434 0 0 1 0 1 x144 x244 x344 x444 0 0 0 0 0
17 Dari persamaan (4.2) x111 x121 x131 x141 0 0 0 0 0
x211 x221 x231 x241 0 0 1 0 1 x311 x321 x331 x341 0 0 0 0 0 x411 x421 x431 x441 0 0 0 0 0 x112 x122 x132 x142 0 1 0 0 1 x212 x222 x232 x242 0 0 0 0 0 x312 x322 x332 x342 0 0 0 0 0 x412 x422 x432 x442 0 0 0 0 0 x113 x123 x133 x143 0 0 0 0 0 x213 x223 x233 x243 1 0 0 0 1 x313 x323 x333 x343 0 0 0 1 1 x413 x423 x433 x443 0 1 0 0 1 x114 x124 x134 x144 0 0 0 0 0 x214 x224 x234 x244 0 0 0 0 0 x314 x324 x334 x344 0 0 1 0 1 x414 x424 x434 x444 1 0 0 0 1 Dari persamaan (4.3) x111 x211 x121 x221 0 0 0 0 0
x112 x212 x122 x222 0 0 1 0 1 x113 x213 x123 x223 0 1 0 0 1 x114 x214 x124 x224 0 0 0 0 0 Dari persamaan (4.4) x311 x411 x321 x421 0 0 0 0 0
x312 x412 x322 x422 0 0 0 0 0 x313 x413 x323 x423 0 0 0 1 1 x314 x414 x324 x424 0 1 0 0 1 Dari persamaan (4.5) x131 x231 x141 x241 0 1 0 0 1
x132 x232 x142 x242 0 0 0 0 0 x133 x233 x143 x243 0 0 0 0 0 x134 x234 x144 x244 0 0 0 0 0
18 Dari persamaan (4.6) x331 x431 x341 x441 0 0 0 0 0
x332 x432 x342 x442 0 0 0 0 0 x333 x433 x343 x443 0 0 1 0 1 x334 x434 x344 x444 1 0 0 0 1 Dari persamaan (4.7) diperoleh: x111 x112 x113 x114 0 0 0 0 0
x211 x212 x213 x214 0 0 1 0 1 x311 x312 x313 x314 0 0 0 0 0 x411 x412 x413 x414 0 0 0 1 1 x121 x122 x123 x124 0 1 0 0 1 x221 x222 x223 x224 0 0 0 0 0 x321 x322 x323 x324 0 0 0 0 0 x421 x422 x423 x424 0 0 1 0 1 x131 x132 x133 x134 0 0 0 0 0 x231 x232 x233 x234 1 0 0 0 1 x331 x332 x333 x334 0 0 0 1 1 x431 x432 x433 x434 0 0 0 0 0 x141 x142 x143 x144 0 0 0 0 0 x241 x242 x243 x244 0 0 0 0 0 x341 x342 x343 x344 0 0 1 0 1 x441 x442 x443 x444 0 0 0 0 0 Dari konfigurasi puzzle yang diberikan sudah dapat diketahui given yang diberikan yaitu: x213 1; x414 1; x122 1; x423 1; x231 1; x334 1; x343 1 Kendala di atas memiliki 64 persamaan dan 64 variabel, dan persamaan yang sudah memenuhi kondisi yaitu sebanyak 28 persamaan. Jadi membutuhkan banyak iterasi pada persamaan di atas untuk memperoleh solusi dari puzzle yang diberikan. Oleh karena itu, berdasarkan konsep yang sama, digunakan langkahlangkah yang dapat merealisasikan formulasi tersebut. Langkah pertama Menentukan kemungkinan nilai k pada setiap elemen, dengan menambahkan nilai k pada elemen yang kosong, dan menambahkan angka 0 untuk selain nilai k. Nilai k pada soal merupakan bilangan given (G)
19 Untuk k bernilai 1 2 3 1 4 4 3
3
1 0 1 0
0 1 1 0
1 1 0 1
1 1 0 1
2 0 2 0
2 2 2 0
2 0 0 2
2 2 0 2
3 3 3 0
0 3 3 3
3 0 0 3
3 3 3 3
4 0 4 4
0 4 4 0
4 0 4 4
4 4 0 4
given : x231 1 Untuk k bernilai 2 2 3 1 4 4 3
3
given : x122 1 Untuk k bernilai 3 2 3 1 4 4 3
3
given : x213 1; x423 1; x343 1 Untuk k bernilai 4 2 3 1 4 4 3
3
given : x414 1; x334 1 Langkah kedua Menentukan kemungkinan pada nilai k berdasarkan konsep hanya boleh ada 1 bilangan angka pada baris, kolom, dan mini grid dengan langkah: jadikan bilangan given sebagai poros; cek baris, kolom, dan mini grid, jika ada yang bernilai k maka ganti dengan angka 0 Kemungkinan k bernilai 1, dengan given x23 sebagai poros 1 0 1 0
0 1 1 0
1 1 0 1
1 1 0 1
1 0 1 0
0 0 1 0
0 1 0 0
0 0 0 1
20 Kemungkinan k bernilai 2, dengan given x12 sebagai poros 2 0 2 0
2 2 2 0
2 0 0 2
2 2 0 2
0 0 2 0
2 0 0 0
0 0 0 2
0 2 0 2
Kemungkinan k bernilai 3, dengan given: x21; x42 ; x34 sebagai poros 3 3 3 0
0 3 3 3
3 0 0 3
3 3 3 3
0 3 0 0
0 0 0 3
3 0 0 0
0 0 3 0
Kemungkinan k bernilai 4, dengan given: x41; x33 sebagai poros 4 0 4 4
0 4 4 0
4 0 4 4
4 4 0 4
0 0 0 4
0 4 0 0
0 0 4 0
4 4 0 0
Langkah ketiga Setelah mencari kemungkinan nilai k, barulah memasukan kendala pada semua kemungkinan nilai k. Kendala: 4
x i 1
ijk
4
x j 1 2
ijk
1, j 1: 4, k 1: 4,
1, i 1: 4, k 1: 4,
2
x j 1 i 1 2
ijk
4
x j 1 i 3 4
ijk
2
x j 3 i 1 4
ijk
4
x j 3 i 3
ijk
1, k 1: 4, 1, k 1: 4, 1, k 1: 4, 1, k 1: 4.
Kemungkinan k bernilai 1 4
x i 1
ij1
1, j 1: 4, k 1
21
x111 x211 x311 x411 1 0 1 0 2 x121 x221 x321 x421 0 0 1 0 1 x131 x231 x331 x431 0 1 0 0 1 x141 x241 x341 x441 0 0 0 1 1 4
x j 1
ij1
1, i 1: 4, k 1
x111 x121 x131 x141 1 0 0 0 1 x211 x221 x231 x241 0 0 1 0 1 x311 x321 x331 x341 1 1 0 0 2 x411 x421 x431 x441 0 0 0 1 1 2
2
x j 1 i 1
ij1
1, k 1
x111 x211 x121 x221 1 0 0 0 1 2
4
x j 1 i 3
ij1
1, k 1
x311 x411 x321 x421 1 0 1 0 0 4
2
x j 3 i 1
ij1
1, k 1
x131 x231 x141 x241 0 1 0 0 1 4
4
x j 3 i 3
ij1
1, k 1
x331 x431 x341 x441 0 0 0 1 0 Pada iterasi di atas dengan k = 1 diperoleh nilai xijk yang memenuhi kondisi yaitu:
x111 1; x231 1( given); x441 1; x321 1 dan selanjutnya iterasi dilanjutkan hingga k = 4, sehingga diperoleh nilai xijk , yaitu: x312 1; x122 1( given); x432 1; x242 1 x213 1( given); x423 1( given); x133 1; x343 1( given) x414 1( given); x214 1; x334 1( given); x144 1
22 Semua solusi dari iterasi persamaan di atas dimasukan ke dalam Sudoku, ditampilkan pada gambar di bawah ini. 1 3
2 4
3 1
4 2
2 1 4 3 4 3 2 1 Gambar 7 Solusi Sudoku 4 × 4 Mencari Solusi Puzzle Sudoku Tradisional pada Matriks 9 × 9 Untuk menyelesaikan Sudoku yang berukuran 9 × 9 dengan aturan tradisional, kita bisa menggunakan dengan kendala yang serupa, dengan nilai n=9, dan m=3, sehingga memiliki kendala: n
x i 1
ijk
1, j 1: n, k 1: n (hanya satu k di setiap kolom, dengan nilai n = 9) 9
x i 1
ijk
9
x i 2
ijk
9
x i 9
n
x j 1
ijk
ijk
9
j 1
ijk
9
x j 2
ijk
9
x j 9
1, j 1: 9, k 1: 9,
1, j 1: 9, k 1: 9.
1, i 1: n, k 1: n (hanya satu k di setiap baris dengan nilai n=9)
x
mq
1, j 1: 9, k 1: 9,
ijk
mp
j mq m 1 i mp m1
1, i 1: 9, k 1: 9, 1, i 1: 9, k 1: 9,
1, i 1: 9, k 1: 9.
xijk 1, k 1: 9, p 1: 3, q 1: 3
23 3
3
x j 1 i 1 6
ijk
3
x j 4 i 1 9
ijk
3
x j 7 i 1 3
ijk
6
x j 1 i 4
6
ijk
6
x j 4 i 4 9
ijk
6
x j 7 i 4 3
ijk
9
x j 1 i 7 6
ijk
9
x j 4 i 7 9
ijk
9
x j 7 i 7
9
x k 1
ijk
ijk
1, k 1: 9, 1, k 1: 9, 1, k 1: 9, 1, k 1: 9,
1, k 1: 9, 1, k 1: 9, 1, k 1: 9, 1, k 1: 9, 1, k 1: 9.
1, i 1: 9, j 1: 9
xijk 1 (i, j, k ) G
Bentuk matriks Sudoku ukuran 9 × 9 secara umum adalah:
Gambar 8 Bentuk umum Sudoku ukuran 9 × 9
24 Untuk memperoleh solusi dari Sudoku berukuran 9 × 9 menggunakan software MATLAB 7.10.0, dengan membuat algoritma berbentuk script m-file dengan nama sudoku.m (lampiran 1). Contoh soal Sudoku 9 × 9: 8 1 4
9 7 3
1 9 2 5
6
5 4 6 6 3
5 4 8 1
7 6 2 3 4
Gambar 9 Contoh soal Sudoku tradisional 9 × 9 Dan diubah ke dalam bentuk matriks, dengan nama matriks M:
0 0 0 0 M 0 0 0 0 6
0 8 0 9 0 5 0 0 0 1 0 7 0 4 0 0 0 4 0 3 0 6 0 0 1 0 0 0 6 0 0 7 9 0 0 0 3 0 0 0 2 0 0 5 0 0 6 0 5 0 0 4 0 0 2 0 0 0 8 0 0 0 3 0 0 0 1 0 0 0 4 0
Dan file dari sudoku.m dieksekusi akan memberikan solusi seperti di bawah ini
2 5 9 4 sol _ M 8 3 1 7 6
6 8 4 9 1 5 7 3 3 1 6 7 2 4 8 9 7 4 5 3 8 6 1 2 1 5 2 8 6 3 9 7 9 6 7 1 3 2 5 4 2 7 9 5 4 1 6 8 5 9 3 4 7 8 2 6 4 2 8 6 5 9 3 1 8 3 1 2 9 7 4 5
25 Maka diperoleh Sudoku setiap elemen pada kolom, baris dan sub-matriks terisi oleh angka 1 sampai 9 tanpa ada pengulangan. Gambar di bawah ini merupakan solusi dalam bentuk tabel. 2 5 9 4 8 3 1 7 6
6 3 7 1 9 2 5 4 8
8 1 4 5 6 7 9 2 3
4 6 5 2 7 9 3 8 1
9 7 3 8 1 5 4 6 2
1 2 8 6 3 4 7 5 9
5 4 6 3 2 1 8 9 7
7 8 1 9 5 6 2 3 4
3 9 2 7 4 8 6 1 5
Gambar 10 Solusi Sudoku tradisional ukuran 9 × 9 Pada script m-file sudoku.m dapat mengeksekusi soal Sudoku tradisional yang memiliki banyak solusi (terhingga). Output yang diberikan dari m-file ini adalah seluruh solusi. Di bawah ini akan diberikan contoh soal Sudoku yang memiliki banyak solusi yang terhingga.
2
9
4
3 4
2
9
8 6
1
8 5 6
5
2 7
7 6 3 1
9
8 1
5
Gambar 11 Contoh soal puzzle Sudoku yang memiliki banyak solusi (terhingga) Soal Sudoku di atas setelah dieksekusi memberikan output (solusi) sebanyak 16 matriks solusi (lampiran 4) Mencari Solusi Puzzle Sudoku X (Sudoku Diagonal) pada Matriks 9 × 9 Pada bagian pembahasan ini, diperlukan kendala tambahan untuk mencari solusi sudoku X, kendalanya yaitu: 9
x r 1
rrk
1, k 1: 9 (diagonal pertama tiap elemennya harus terisi angka 1-9)
x111 x221 x331 x441 x551 x661 x771 x881 x991 1
26
x112 x222 x332 x442 x552 x662 x772 x882 x992 1 x113 x223 x333 x443 x553 x663 x773 x883 x993 1 . . . x119 x229 x339 x449 x559 x669 x779 x889 x999 1 9
x r 1
r (10 r ) k
1, k 1: 9 (diagonal kedua tiap elemennya harus terisi angka 1-9)
x191 x281 x371 x461 x551 x641 x731 x821 x911 1 x192 x282 x372 x462 x552 x642 x732 x822 x912 1 x193 x283 x373 x463 x553 x643 x733 x823 x913 1 . . . x199 x289 x379 x469 x559 x649 x739 x829 x919 1
Dengan menambahkan kendala, jadi diperlukan perubahan pada script Sudoku untuk mencari solusi sudoku X. Script m-file Sudoku yang baru diberi nama sudokuX.m (Lampiran 2) untuk mencari solusi Sudoku diagonal. Contoh 8 9
2
6 8 4 9
4 1 6
9 3 2 1 8
6 8 5 9 1 2
2
7 3
9 1
6
7 6
2 6
4
1
1
5
9 6 2
Gambar 12 Contoh soal Sudoku X ukuran 9 × 9 permasalahan untuk Sudoku diagonal:
27 Bentuk matriks dengan nama matriks M: 0 8 0 0 6 0 2 1 0 0 9 0 2 8 0 0 0 7 0 0 0 0 5 3 9 0 0 6 0 0 0 9 0 0 0 1 M 0 4 9 0 1 6 7 0 0 8 1 3 0 2 0 6 5 9 4 6 2 0 0 0 0 0 0 9 0 1 0 0 2 0 0 6 0 0 8 6 4 0 1 0 2
Jika sudokuX.m dieksekusi akan memberikan solusi (lampiran 4), diperoleh solusi Sudoku X dalam bentuk matriks:
5 6 9 3 sol _ M 2 8 1 7 4
3 7 4 1 2 8 9 6 1 4 9 3 8 2 7 5 2 8 5 7 6 1 3 4 4 1 7 6 5 9 2 8 6 5 8 9 1 7 4 3 7 9 2 4 3 6 5 1 5 3 6 2 9 4 8 7 8 2 1 5 4 3 6 9 9 6 3 8 7 5 1 2
Maka solusi dalam bentuk tabel adalah: 5 6 9 3 2 8 1 7 4
3 1 2 4 6 7 5 8 9
7 4 8 1 5 9 3 2 6
4 9 5 7 8 2 6 1 3
1 3 7 6 9 4 2 5 8
2 8 6 5 1 3 9 4 7
8 2 1 9 7 6 4 3 5
9 7 3 2 4 5 8 6 1
6 5 4 8 3 1 7 9 2
Gambar 13 Solusi Sudoku X ukuran 9 × 9
28
Hubungan Antar Ukuran Sudoku, Banyaknya Unsur Awal, dan Konfigurasi Sudoku Tradisional. Tabel di bawah ini diberikan gambaran hubungan antar ukuran Sudoku, unsur awal, dan konfigurasi pada Sudoku tradisional. Ukuran Sudoku yang digunakan yaitu: 4 × 4 (n2 × n2, n = 2) dan 9 × 9 (n2 × n2, n = 3), dengan unsur awal yang diberikan beragam :
*)
#Solusi yg diberikan
Ukuran Sudoku
Unsur Awal
4×4
1
-
72
4×4
2
I
24
4×4
2
II
24
4×4
2
III
24
4×4
2
IV
18
4×4
2
V
36
4×4
2
VI
18
4×4
2
VII
18
4×4
3
I
12
4×4
3
II
6
4×4
3
III
6
4×4
3
IV
6
12
9×9
45
I
3448
2861
9×9
45
II
1356
1608
9×9
54
I
288
216
9×9
54
II
216
276
Konfigurasi*)
1
2
3
12
3
144
Lihat lampiran 12
Tabel 1 Hubungan antar ukuran, unsur, dan konfigurasi Sudoku tradisional Pada ukuran Sudoku 4 × 4 dengan pemberian 1 given, 2 given dan 3 given diketahui memiliki beragam solusi, kecuali pemberian 1 given memilik jumlah solusi yang sama (berlaku pada semua konfigurasi Sudoku ukuran 4 × 4). Dengan pemberian 2 given, pada tabel di atas diketahui ada yang memiliki solusi 24, 18,
29 36, 12 dengan konfigurasi yang berbeda-beda. Konfigurasi I, II, dan III memiliki variasi solusi yang seragam yaitu sebanyak 24 solusi. Konfigurasi I menempatkan given pada x1,1 dan x2,2 dengan x1,1 x2,2 ,konfigurasi II menempatkan given pada x1,2 dan x1,3 dengan x1,2 x1,3 , dan konfigurasi III menempatkan given pada x2,2
dan x2,3 dengan x2,2 x2,3 . Sedangkan konfigurasi IV, V dan VI memberikan banyak solusi yang beragam, yaitu: 18, 36, dan 12 (lampiran 12). Untuk konfigurasi IV dan VI menghasilkan solusi yang seragam yaitu 18 solusi, sedangkan untuk konfigurasi V memberikan solusi 36 dan 12 (lampiran 12). Jadi dari beberapa bentuk konfigurasi dengan pemberian 2 given tidak memberikan jumlah solusi yang sama, begitu juga dengan pemberian 3 given pada Sudoku ukuran 4 × 4 memberikan beragam solusi. Hal ini juga terjadi pada Sudoku ukuran 9 × 9 memberikan beragam solusi untuk given yang sama (lampiran 12).
SIMPULAN DAN SARAN Simpulan Dalam penulisan karya ilmiah ini telah diperlihatkan pencarian solusi Sudoku dari soal puzzle yang ditentukan, dengan menggunakan metode branch and bound yang diimplementasikan pada script m-file. Pencarian solusi Sudoku diperluas tidak hanya untuk mencari solusi Sudoku tradisional, tetapi dengan penambahan beberapa kendala dan perubahan pada script m-file sehingga bisa menemukan solusi untuk Sudoku diagonal atau dikenal dengan nama Sudoku X. Script m-file pada penulisan karya ilmiah ini telah berhasil memperoleh solusi Sudoku dengan menggunakan metode branch and bound. Dari pembahasan di atas dapat disimpulkan juga bahwa hubungan antar ukuran Sudoku, unsur awal, dan konfigurasi Sudoku tradisional belum dapat menentukan pola keteraturan banyaknya solusi untuk Sudoku ukuran 9 × 9, namun untuk konfigurasi tertentu dapat ditentukan pola keteraturan menentukan banyaknya solusi yang muncul (Sudoku dengan ukuran 4 × 4). Saran Pada karya ilmiah ini pencarian solusi Sudoku hanya sampai solusi untuk Sudoku tradisional dan Sudoku X (diagonal). Saran untuk penulisan selanjutnya yaitu mencari solusi beberapa varian Sudoku yang baru. Dalam tulisan ini untuk mecari soal Sudoku masih menggunakan nilai given yang sudah tersedia, mungkin untuk penulisan selanjutnya bisa membuat soal-soal Sudoku yang memiliki hanya 1 (satu) solusi.
30
DAFTAR PUSTAKA Bartlett AC, Chartier TP, Langville AN, Rankin TD. 2008. An Integer Programming Model for the Sudoku Problem. College of Charleston and Davidson College, (US). [Jurnal] Garfinkel RS & GL Nemhauser. 1972. Integer Programming, New York.(US): John Willey & Sons. Leon SJ. 2001. Aljabar Linear dan Aplikasinya. Alit Bondan: Penerjemah, Jakarta. (ID): Erlangga. Terjemahan dari: Linear Algebra With Applications. Setianto D. 2011. Penjadwalan Kereta Api Menggunakan Pemrograman Linear Integer [Skripsi]. Bogor (ID): Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Taha HA. 1996. Pengantar Riset Operasi. Drs. Daniel Wirajaya: Penerjemah, Jakarta. (ID): Binarupa Aksara. Terjemahan dari: Operations Research. Winston WL. 2004. Operations Research; Applications and Algorithms 4th ed. Duxbury, New York (US).
31 Lampiran 1 Script m-file sudoku.m untuk mencari solusi Sudoku tradisional. %created by: Michael Kleder, December 2006 %Script M-File MATLAB 7.10.0 function A=sudoku(M) if ndims(M)~=2 error('Matriks harus 2 dimensi.') end if any((size(M)-[9 9])~=0) error('Matriks yang dibuat harus memiliki 9 kolom dan 9 baris.') end if any(any(M~=floor(M))) || any(abs(M(:)-4.5)>4.5) error(soal dan solusi merupakan bilangan bulat 1 sampai 9 .') end
A=0*M; [M,imp,A]=recurse(M,A); if imp error('Tidak ada solusi.') end A=A(:,:,2:end); return function [M,imp,A]=recurse(M,A) [M,imp]=deduce(M); if imp return end z=find(~M(:)); if isempty(z) A(:,:,end+1)=M; return end impall=zeros(1,9); for v=1:9 Q=M; Q(z(1))=v; [Q,impall(v),A]=recurse(Q,A); end imp=all(impall); M=Q; return function [M,imp]=deduce(M) imp=0; Mprev = 10*M; while any(M(:)-Mprev(:)) Mprev=M; N=ones(9,9,9); [i,j]=find(M); for n=1:length(i) N(i(n),j(n),:)=0; N(i(n),j(n),M(i(n),j(n)))=1; end
32 if any(any(sum(N,3)<1)) imp=1; return end [i,j]=find(sum(N,3)<2); for n=1:length(i) if any(any(sum(N,3)<1)) imp=1; return end v = find(N(i(n),j(n),:)); M(i(n),j(n)) = v; N(:,j(n),v)=0; N(i(n),:,v)=0; br = floor((i(n)-.5)/3)*3+1; bc = floor((j(n)-.5)/3)*3+1; N(br:br+2,bc:bc+2,v)=0; N(i(n),j(n),v)=1; end for i=1:9 for j=1:9 k=find(N(i,j,:)); if length(k)==1 M(i,j)=k; end end end for i=1:9 for k=1:9 j=find(N(i,:,k)); if length(j)==1 M(i,j)=k; end end end for j=1:9 for k=1:9 i=find(N(:,j,k)); if length(i)==1 M(i,j)=k; end end end for i=[1 4 7] for j=[1 4 7] for k=1:9 Q=N(i:i+2,j:j+2,k); [pr,pc]=find(Q); if length(pr)==1 M(i+pr-1,j+pc-1)=k; end end end end end return
33 Lampiran 2
Script m-file sudokuX.m untuk mencari solusi Sudoku X (Sudoku diagonal)
%Script M-File MATLAB 7.10.0 function [A,B]=sudokuX(M) if ndims(M)~=2 error('Matriks harus 2 dimensi.') end if any((size(M)-[9 9])~=0) error('Matriks yang dibuat harus memiliki 9 kolom dan 9 baris.') end if any(any(M~=floor(M))) || any(abs(M(:)-4.5)>4.5) error('soal dan solusi merupakan bilangan bulat 1 sampai 9.') end A=0*M; [M,imp,A]=recurse(M,A); if imp error('Tidak ada solusi.') end A=A(:,:,2:end); C=numel(A)/81; for sol = 1:C seq=[1 2 3 4 5 6 7 8 9]; seqver=zeros(1,9); seqhor=zeros(1,9); for i =1:9 seqver(i)=A(i,i,sol); end for j =1:9 seqhor(j)=A(j,10-j,sol); end if ((sum(abs(seq-sort(seqver)))==0) && (sum(abs(seqsort(seqhor)))==0)) B=A(:,:,sol); return end end B='Tidak ada solusi untuk sudoku X.'; return function [M,imp,A]=recurse(M,A) [M,imp]=deduce(M); if imp return end z=find(~M(:)); if isempty(z) A(:,:,end+1)=M; return end
34 impall=zeros(1,9); for v=1:9 Q=M; Q(z(1))=v; [Q,impall(v),A]=recurse(Q,A); end imp=all(impall); M=Q; return function [M,imp]=deduce(M) imp=0; Mprev = 10*M; while any(M(:)-Mprev(:)) Mprev=M; N=ones(9,9,9); [i,j]=find(M); for n=1:length(i) N(i(n),j(n),:)=0; N(i(n),j(n),M(i(n),j(n)))=1; end if any(any(sum(N,3)<1)) imp=1; return end [i,j]=find(sum(N,3)<2); for n=1:length(i) if any(any(sum(N,3)<1)) imp=1; return end v = find(N(i(n),j(n),:)); M(i(n),j(n)) = v; N(:,j(n),v)=0; N(i(n),:,v)=0; br = floor((i(n)-.5)/3)*3+1; bc = floor((j(n)-.5)/3)*3+1; N(br:br+2,bc:bc+2,v)=0; N(i(n),j(n),v)=1; end for i=1:9 for j=1:9 k=find(N(i,j,:)); if length(k)==1 M(i,j)=k; end end end for i=1:9 for k=1:9 j=find(N(i,:,k)); if length(j)==1 M(i,j)=k; end end end
35 for j=1:9 for k=1:9 i=find(N(:,j,k)); if length(i)==1 M(i,j)=k; end end end for i=[1 4 7] for j=[1 4 7] for k=1:9 Q=N(i:i+2,j:j+2,k); [pr,pc]=find(Q); if length(pr)==1 M(i+pr-1,j+pc-1)=k; end end end end end return
36 Lampiran 3 Contoh mencari solusi untuk soal Sudoku ukuran 9 × 9 dengan script m-file >> M = [0 0 8 0 9 0 5 0 0;0 0 1 0 7 0 4 0 0;0 0 4 0 3 0 6 0 0; 0 1 0 0 0 6 0 0 7;0 9 0 0 0 3 0 0 0;0 2 0 0 5 0 0 6 0; 0 5 0 0 4 0 0 2 0;0 0 0 8 0 0 0 3 0;6 0 0 1 0 0 0 4 0]; >> sudoku(M) ans = 2 5 9 4 8 3 1 7 6
6 3 7 1 9 2 5 4 8
8 1 4 5 6 7 9 2 3
4 6 5 2 7 9 3 8 1
9 7 3 8 1 5 4 6 2
1 2 8 6 3 4 7 5 9
5 4 6 3 2 1 8 9 7
7 8 1 9 5 6 2 3 4
3 9 2 7 4 8 6 1 5
37 Lampiran 4 Contoh mencari solusi untuk soal Sudoku ukuran 9 × 9 yang memiliki banyak solusi (terhingga) dengan menggunakan script m-file
>> M=[0 0 0 2 0 9 0 0 4;0 0 3 0 0 0 0 2 0;4 9 0 0 8 0 0 0 0; 0 0 6 0 0 8 5 0 0;0 0 0 0 2 0 0 0 7;1 0 0 5 7 0 0 6 0; 0 0 0 6 0 0 0 3 0;0 0 0 0 0 1 8 0 5;0 0 0 0 9 0 1 0 0]; >> sudoku(M) ans(:,:,1) = 5 6 4 7 8 1 9 2 3
7 8 9 2 4 3 1 6 5
1 3 2 6 5 9 8 7 4
2 1 7 9 3 5 6 4 8
6 4 8 1 2 7 5 3 9
9 5 3 8 6 4 7 1 2
3 7 6 5 9 2 4 8 1
8 2 5 4 1 6 3 9 7
4 9 1 3 7 8 2 5 6
1 3 2 6 4 9 8 7 5
2 1 7 9 3 5 6 4 8
6 4 8 1 2 7 5 3 9
9 5 3 8 6 4 7 1 2
3 7 6 5 9 2 4 8 1
8 2 5 4 1 6 3 9 7
4 9 1 3 7 8 2 5 6
1 3 2 6 5 8 9 4 7
2 4 3 9 1 5 6 7 8
6 1 8 4 2 7 5 3 9
9 5 7 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
7 2 5 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
ans(:,:,2) = 5 6 4 7 8 1 9 2 3
7 8 9 2 5 3 1 6 4
ans(:,:,3) = 5 6 4 7 9 1 8 2 3
8 7 9 2 3 4 1 6 5
38 ans(:,:,4) = 5 7 4 2 9 1 8 6 3
8 6 9 7 3 4 1 2 5
1 3 2 6 5 8 9 4 7
2 4 3 9 1 5 6 7 8
6 1 8 4 2 7 5 3 9
9 5 7 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
7 2 5 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
1 3 2 6 5 8 9 4 7
2 4 3 9 1 5 6 7 8
6 1 8 4 2 7 5 3 9
9 7 5 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
5 2 7 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
5 3 2 6 8 9 1 7 4
2 1 7 9 3 5 6 4 8
6 4 8 1 2 7 5 3 9
9 5 3 8 6 4 7 1 2
3 7 6 5 9 2 4 8 1
8 2 5 4 1 6 3 9 7
4 9 1 3 7 8 2 5 6
1 3 2 6 4 9 8 7 5
2 1 7 9 3 5 6 4 8
6 4 8 1 2 7 5 3 9
9 5 3 8 6 4 7 1 2
3 7 6 5 9 2 4 8 1
8 2 5 4 1 6 3 9 7
4 9 1 3 7 8 2 5 6
ans(:,:,5) = 7 5 4 2 9 1 8 6 3
8 6 9 7 3 4 1 2 5
ans(:,:,6) = 7 8 4 2 5 1 9 6 3
1 6 9 7 4 3 8 2 5
ans(:,:,7) = 7 8 4 2 5 1 9 6 3
5 6 9 7 8 3 1 2 4
39 ans(:,:,8) = 8 5 4 2 3 1 9 6 7
1 6 9 7 5 4 8 2 3
7 3 2 6 9 8 1 4 5
2 4 3 9 1 5 6 7 8
6 1 8 4 2 7 5 3 9
9 7 5 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
5 2 7 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
7 3 2 6 9 8 1 4 5
2 4 3 9 1 5 6 7 8
1 6 8 4 2 7 5 3 9
9 7 5 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
5 2 7 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
2 4 3 9 1 5 6 7 8
6 1 8 4 2 7 5 3 9
9 5 7 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
7 2 5 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
2 4 3 9 1 5 6 7 8
6 1 8 4 2 7 5 3 9
9 7 5 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
5 2 7 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
ans(:,:,9) = 8 5 4 2 3 1 9 6 7
6 1 9 7 5 4 8 2 3
ans(:,:,10) = 8 6 4 7 3 1 9 2 5
1 7 9 2 5 4 8 6 3
5 3 2 6 9 8 1 4 7
ans(:,:,11) = 8 6 4 7 5 1 9 2 3
1 5 9 2 3 4 8 6 7
7 3 2 6 9 8 1 4 5
40 ans(:,:,12) = 8 6 4 7 5 1 9 2 3
1 7 9 2 3 4 8 6 5
5 3 2 6 9 8 1 4 7
2 4 3 9 1 5 6 7 8
6 1 8 4 2 7 5 3 9
9 5 7 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
7 2 5 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
2 4 3 9 1 5 6 7 8
6 1 8 4 2 7 5 3 9
9 5 7 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
7 2 5 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
2 4 3 9 1 5 6 7 8
1 6 8 4 2 7 5 3 9
9 5 7 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
7 2 5 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
2 4 3 9 1 5 6 7 8
6 1 8 4 2 7 5 3 9
9 5 7 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
7 2 5 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
ans(:,:,13) = 8 7 4 2 3 1 9 6 5
1 6 9 7 5 4 8 2 3
5 3 2 6 9 8 1 4 7
ans(:,:,14) = 8 7 4 2 3 1 9 6 5
6 1 9 7 5 4 8 2 3
5 3 2 6 9 8 1 4 7
ans(:,:,15) = 8 7 4 2 5 1 9 6 3
1 6 9 7 3 4 8 2 5
5 3 2 6 9 8 1 4 7
41 ans(:,:,16) = 8 7 4 2 5 1 9 6 3
6 1 9 7 3 4 8 2 5
5 3 2 6 9 8 1 4 7
2 4 3 9 1 5 6 7 8
1 6 8 4 2 7 5 3 9
9 5 7 8 6 3 4 1 2
3 9 6 5 4 2 7 8 1
7 2 5 1 8 6 3 9 4
4 8 1 3 7 9 2 5 6
42 Lampiran 5 Contoh mencari solusi untuk soal Sudoku X ukuran 9 × 9 dengan menggunakan script m-file
>> M = [ 0 8 0 0 6 0 2 1 0;0 9 0 2 8 0 0 0 7;0 0 0 0 5 3 9 0 0; 6 0 0 0 9 0 0 0 1;0 4 9 0 1 6 7 0 0;8 1 3 0 2 0 6 5 9; 4 6 2 0 0 0 0 0 0;9 0 1 0 0 2 0 0 6;0 0 8 6 4 0 1 0 2]; >> [A,B]=sudokuX(M) A= 5 3 1 6 2 8 4 9 7
8 9 2 7 4 1 6 5 3
7 4 6 5 9 3 2 1 8
9 2 7 3 5 4 1 8 6
6 8 5 9 1 2 3 7 4
4 1 3 8 6 7 9 2 5
2 5 9 4 7 6 8 3 1
1 6 8 2 3 5 7 4 9
3 7 4 1 8 9 5 6 2
8 9 2 7 4 1 6 5 3
7 4 6 5 9 3 2 1 8
9 2 7 3 5 4 1 8 6
6 8 5 9 1 2 3 7 4
4 1 3 8 6 7 9 2 5
2 5 9 4 7 6 8 3 1
1 6 8 2 3 5 7 4 9
3 7 4 1 8 9 5 6 2
B= 5 3 1 6 2 8 4 9 7
Matriks B merupakan solusi untuk Sudoku X
43 Lampiran 6 Contoh mencari solusi untuk soal Sudoku X ukuran 9 × 9 yang memiliki banyak solusi (terhingga) dengan menggunakan script m-file >> M=[6 0 8 3 0 2 0 0 7;9 0 0 0 0 0 5 0 2;0 0 0 0 0 0 3 0 4; 0 1 4 0 6 0 8 0 9;0 0 0 0 1 0 2 3 0;0 5 0 9 3 7 0 0 0; 1 8 0 0 7 4 0 0 0;5 0 7 0 0 3 6 0 1;0 0 0 0 0 0 7 5 8]; >> [A,B]=sudokuX(M) A(:,:,1) = 6 9 2 3 7 8 1 5 4
4 3 7 1 6 5 8 2 9
8 1 5 4 9 2 6 7 3
3 7 1 2 4 9 5 8 6
5 4 8 6 1 3 7 9 2
2 6 9 5 8 7 4 3 1
1 5 3 8 2 4 9 6 7
9 8 6 7 3 1 2 4 5
7 2 4 9 5 6 3 1 8
4 3 7 1 6 5 8 9 2
8 1 5 4 9 2 6 7 3
3 7 1 2 4 9 5 8 6
5 4 8 6 1 3 7 2 9
2 6 9 5 8 7 4 3 1
1 5 3 8 2 4 9 6 7
9 8 6 7 3 1 2 4 5
7 2 4 9 5 6 3 1 8
4 3 7 1 6 5 8 2 9
8 1 5 4 9 2 6 7 3
3 7 1 2 4 9 5 8 6
5 4 8 6 1 3 7 9 2
2 6 9 5 8 7 4 3 1
1 5 3 8 2 4 9 6 7
9 8 6 7 3 1 2 4 5
7 2 4 9 5 6 3 1 8
A(:,:,2) = 6 9 2 3 7 8 1 5 4
B= 6 9 2 3 7 8 1 5 4
Matriks B merupakan solusi untuk Sudoku X
44 Lampiran 7 Hubungan antar ukuran Sudoku, banyaknya unsur awal, dan konfigurasi Sudoku tradisional Sudoku 4 × 4 dengan unsur awal (given) 2 Konfigurasi I Konfigurasi II
dan
dan
Dimana Dengan konfigurasi tersebut menghasilkan 24 solusi
Dimana Dengan konfigurasi menghasilkan 24 solusi
Konfigurasi III
Konfigurasi IV
dan Dimana Dengan konfigurasi tersebut menghasilkan 24 solusi
dan Dengan konfigurasi menghasilkan 18 solusi
tersebut
tersebut
45 Konfigurasi V
Konfigurasi VI
dan Dengan konfigurasi tersebut menghasilkan beragam solusi, yaitu 36 dan 12 solusi
dan Dengan konfigurasi tersebut menghasilkan 18 solusi
Konfigurasi VII
dan Dengan konfigurasi tersebut menghasilkan 18 solusi
46 Sudoku 4 × 4 dengan unsur awal (given) 3 Konfigurasi I
Konfigurasi II
;
;
;
dan
dan
Dimana Dengan konfigurasi tersebut menghasilkan 12 solusi
Dimana Dengan konfigurasi tersebut menghasilkan 6 solusi
Konfigurasi III
Konfigurasi IV
;
;
;
;
;
dan
dan
Dimana Dengan konfigurasi tersebut menghasilkan 6 solusi
Dimana Dengan konfigurasi tersebut menghasilkan solusi yang beragam, yaitu: 6, 12, dan 3 solusi
47 Sudoku 9 × 9 dengan unsur awal (given) 45 Konfigurasi I 9
4
1
6
9
3
2
8
6
8
4
2
3
5
7
5
7
1
7
2
9
1
6
4
4
1
8
2
8
7
6
3
5
3
5
9
1
9
4
2
5
7
8
6
3
5
7
3
9
2
8
4
1
6
5
6
3
8
9
4
1
7
2
6
9
4
5
3
1
7
2
8
8
7
2
6
1
3
5
9
4
8
1
2
6
4
7
9
3
5
Menghasilkan sebanyak 3448 solusi
Menghasilkan sebanyak 2861 solusi
Konfigurasi II
5
1
8
7
6
2
3
4
1
6
5
7
2
3
7
4
9
8
6
7
2
8
3
9
6
9
4
5
1
3
5
9
8
1
4
2
7
1
9
8
2
6
3
5
4
5
4
2
8
6
9
7
1
3
6
4
8
1
5
3
2
7
9
6
7
3
1
2
4
9
8
5
3
2
5
4
7
9
6
8
1
9
8
1
7
5
3
2
6
4
Menghasilkan sebanyak 1356 solusi
Menghasilkan sebanyak 1608 solusi
48 Sudoku 9 × 9 dengan unsur awal (given) 45 Konfigurasi I 1
5
9
7
2
3
7
2
8
5
3
6
2
8
6
5
1
4
3
5
1
7
4
9
3
4
7
8
9
6
6
4
9
1
8
2
4
6
1
9
3
8
4
1
5
3
6
8
8
2
5
1
6
7
2
3
6
9
7
5
9
7
3
4
5
2
9
8
7
4
2
1
7
3
4
2
8
5
1
9
4
2
5
7
6
1
8
3
4
9
5
6
3
8
9
4
5
9
2
6
7
1
8
7
2
6
1
3
Menghasilkan sebanyak 288 solusi
Menghasilkan sebanyak 216 solusi
Konfigurasi II 6
2
3
7
5
8
9
1
5
7
6
8
5
1
7
9
4
6
7
3
8
2
4
9
9
8
4
2
3
1
2
6
4
5
1
3
4
3
6
5
1
7
8
9
2
1
3
7
8
9
5
4
6
2
4
5
6
9
8
2
2
7
1
8
9
3
3
7
1
4
5
6
1
4
8
3
7
5
5
8
3
6
2
4
7
6
9
1
2
4
6
4
9
3
7
1
3
5
2
6
8
9
1
2
7
8
9
5
Menghasilkan sebanyak 216 solusi
Menghasilkan sebanyak 276 solusi
49
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 12 Desember 1988 sebagai putra ketiga dari lima bersaudara dengan ayah (alm) Atma Heliosmara dan ibu (almh) Umi Hamidah. Tahun 2006 penulis lulus dari SMA Rimba Madya Bogor dan pada tahun yang sama lulus seleksi masuk IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Penulis memilih Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis ikut aktif dalam kegiatan kemahasiswaan, diantaranya pada tahun 2008-2009 dengan mengikuti beberapa kepanitiaan yang diselenggarakan oleh GUMATIKA salah satunya adalah Try Out SNMPTN siswa SMA sekotamadya Bogor 2008.
