Pengaplikasian Pewarnaan Graf dan Algoritma Backtracking pada Permainan Sudoku

Vanka Yuvadha Suciningtyas, Zahrotul Janah, Oryza Embun Putri Santosa, Muhamad Gani Rohman

Sari


Sudoku merupakan teka-teki logika yang secara matematis dapat dimodelkan sebagai permasalahan kombinatorial dalam teori graf. Penelitian ini bertujuan untuk memformulasikan permainan sudoku klasik berukuran 9×9 ke dalam model graf serta menganalisis penyelesaiannya melalui pendekatan pewarnaan graf dan algoritma backtracking. Penelitian ini menggunakan kajian teoretis dengan pendekatan analisis struktural graf dan formulasi algoritmik. Setiap sel pada grid sudoku direpresentasikan sebagai simpul, sedangkan hubungan ketetanggaan berdasarkan baris, kolom, dan subgrid 3×3 direpresentasikan sebagai sisi. Hasil analisis menunjukkan bahwa graf sudoku merupakan graf reguler berderajat 20 dan memiliki bilangan kromatik χ(G)=9. Permasalahan sudoku ekuivalen dengan pewarnaan graf menggunakan sembilan warna tanpa konflik ketetanggaan. Selain itu, analisis kompleksitas menunjukkan bahwa algoritma backtracking memiliki kompleksitas waktu eksponensial dalam kasus terburuk, namun struktur graf sudoku yang memuat banyak klik berukuran maksimum menyebabkan proses pemangkasan (pruning) terjadi lebih awal. Dengan demikian, integrasi analisis struktural graf dan algoritma backtracking memberikan kerangka matematis yang sistematis dalam menjelaskan karakteristik penyelesaian sudoku. 

Teks Lengkap:

PDF

Referensi


Ayusi, R., Triantika, A., & Alaydrus, Z. (2025). Penerapan Algoritma Bracktracking Dalam Penyelesaian Masalah Sistem Pakar. 1(1), 57–67.

Bangun, F. R. (2024). Menemukan Solusi Dalam Permainan Sudoku.

Barahama, R. M., Montolalu, C. E. J. C., & Tumilaar, R. (2021). Eksentrisitas Digraf pada Graf Gir Menggunakan Algoritma Breadth First Search. D’Cartesian: Jurnal Matematika Dan Aplikasi, 10(1), 31–36. https://ejournal.unsrat.ac.id/index.php/decartesian/article/view/32995

Buhaerah, Busrah, Z., & Sanjaya, H. (2019). Teori Graf dan Aplikasinya. In Living Spiritual Quotient. Danuputri, C., & Santosa, N. (2021). Aplikasi Pemecahan Soal Sudoku dengan Metode Backtracking. 6(3), 2622–4615. http://openjournal.unpam.ac.id/index.php/informatika506

Fransiskus Fran, A. H. (2019). Pewarnaan Simpul, Sisi, Wilayah Pada Graf Dan Penerapannya. Bimaster : Buletin Ilmiah Matematika, Statistika Dan Terapannya, 8(4), 773–782. https://doi.org/10.26418/bbimst.v8i4.36037

Hanafi, A. A., Hibban, N., Zulfikar, F. M., & Adhinata, F. D. (2021). Penyelesaian Permainan Sudoku Menggunakan Algoritma Backtracking Berbasis Artificial Intelligence. Journal ICTEE, 2(2), 50. https://doi.org/10.33365/jictee.v2i2.1288

Martin, T. F., Bandung, I. T., & Bandung, J. G. (2021). Aplikasi Graf pada Penyelesaian Permainan Sudoku.

Meidina, R., & Firdaus, M. (2025). Implementasi dan Analisis Algoritma Backtracking untuk Penyelesaian Sudoku. 1(1), 29–35.

Novianto, S., & Pramadhana, D. (2019). Penerapan Algorithma Backtracking Dalam Menyelesaikan Permainan Knight Tour. 205–213.

Qomaruddin, M., Bismi, W., & Hariyanto, D. (2022). Pewarnaan Graf Pada Peta Provinsi Jawa Barat Menggunakan Algoritma Welch-Powell. Jurnal Sistem Dan Teknologi Informasi (JustIN), 10(2), 258. https://doi.org/10.26418/justin.v10i2.53829

Rahman, F. A., & Anubhakti, D. (2020). Implementasi Algoritma Backtracking Pada Permainan Sudoku. MEANS (Media Informasi Analisa Dan Sistem), 5(1), 67–71. https://doi.org/10.54367/means.v5i1.711

Rifqo, M. H., & Apridiansyah, Y. (2017). Implementasi Algoritma Backtracking Dalam Sistem Informasi Perpustakaan Untuk Pencarian Judul Buku (Studi Kasus Unit Pelayanan Terpadu Perpustakaan Universitas Muhammadiyah Bengkulu). Pseudocode, 4(1), 90–96. https://doi.org/10.33369/pseudocode.4.1.90-96

Syam, R., Ihsan, H., & Asman, A. (2020). Aplikasi Pewarnaan Graf dengan Algoritma Recursive Largest First pada Penjadwalan Mata Kuliah. Journal of Mathematics, Computations, and Statistics, 2(1), 63. https://doi.org/10.35580/jmathcos.v2i1.12461

Zaturrahmi. (2017). Implementasi Permainan Sudoku Dalam Meningkatkan Pertumbuhan Kognitif Siswa Dalam Lingkungan Belajar. E-Tech, 07(00), 1–7. http://ejournal.unp.ac.id/index.php/e- tech%0ALINGKUNGAN.




DOI: http://dx.doi.org/10.25157/teorema.v10i2.19774

Refbacks

  • Saat ini tidak ada refbacks.


##submission.copyrightStatement##

Laman Teorema: https://jurnal.unigal.ac.id/index.php/teorema/index

Terindek: