Comparison Analysis of Breadth First Search and Depth Limited Search Algorithms in Sudoku Game

Authors

  • Tirsa Ninia Lina Faculty of Computer Science, Victory University of Sorong, Indonesia
  • Matheus Supriyanto Rumetna Faculty of Computer Science, Victory University of Sorong, Indonesia

DOI:

https://doi.org/10.25008/bcsee.v2i2.1146

Keywords:

Artificial Intelligence, Breadth First Search, Depth Limited Search, Sudoku Game, Information Technology

Abstract

Sudoku is a game that sharpens the brain and is very well known. But the problem faced in this condition is how we can find a solution for the completion of this game. Problems with the Sudoku game can be solved by using the concept of Artificial Intelligence (AI). Some of the algorithms that can be used are the Breadth First Search (BFS) and Depth Limited Search (DLS) algorithms. The purpose of this research is to find a solution for Sudoku and make a comparative analysis of the search results of the two algorithms. The results obtained are application design in the form of a simulation of the completion of the Sudoku game problem with two algorithms. And it has been proven from the two algorithms that DLS is more efficient and faster than BFS. While BFS itself has advantages, in terms of a more structured and systematic search system that is able to find all possible numbers in each box. In this case, if a Sudoku question has more than one answer, then BFS will find it.

Downloads

Download data is not yet available.

References

A. Wibowo, . B., . L., and F. Fathurrahman, "Implementasi Algoritma Breadth First Search Dan Obstacle Detection Dalam Penelusuran Labirin Dinamis Menggunakan Robot Lego," Ilmu Komput. dan Inf., vol. 4, no. 1, pp. 15-22, 2011,

https://doi.org/10.21609/jiki.v4i1.153

S. Tarmiandi, E. Z. Astuti, and S. Astuti, "Implementasi Algoritma Breadth First Search Pada Pencarian Rute Terpendek Tempat Kos Di Semarang Tengah," in Seminar Nasional Sistem Informasi dan Teknologi Informasi, 2018, pp. 524-528, [Online]. Available: http://www.sisfotenika.stmikpontianak.ac.id/index.php/sensitek/article/view/298.

S. Lailiyah, A. Yusnita, and T. A. Panotogomo, "Penerapan Algoritma Depth First Search Pada Sistem Pencarian Dokumen," in SNITT, 2017, pp. 174-179.

B. Prasetiyo and M. R. Hidayah, "Penggunaan Metode Depth First Search (DFS) dan Breadth First Search (BFS) pada Strategi Game Kamen Rider Decade Versi 0.3," Sci. J. Informatics, vol. 1, no. 2, pp. 161-167, 2014, https://doi.org/10.15294/sji.v1i2.4022

A. S. M. Lumenta, "Perbandingan Metode Pencarian Depth-First Search, Breadth-First Search Dan Best-First Search Pada Permainan 8-Puzzle," e-journal Tek. Elektro dan Komput., pp. 1-6, 2014.

A. Hasibuan, D. S. Tambunan, and A. Info, "Design and Development of An Automatic Door Gate Based on Internet of Things Using Arduino Uno," Bull. Comput. Sci. Electr. Eng., vol. 2, no. 1, pp. 17-27, 2021, doi: 10.25008/bcsee.v2i1.1141.

T. Espinoza-Cordero, K. Ortiz-Cotrina, and ..., "Implementation of Electronic Medical Records System EQUALI to Improve Patient Care," Bull. Comput. …, vol. 2, no. 1, pp. 9-16, 2021, https://doi.org/10.25008/bcsee.v2i1.1144

N. Nikhlis, A. Iriani, and K. D. Hartomo, "Soft System Methodology (SSM) Analysis to Increase the Number of Prospective Students," INTENSIF J. Ilm. Penelit. dan Penerapan Teknol. Sist. Inf., vol. 4, no. 1, pp. 63-74, 2020, https://doi.org/10.29407/intensif.v4i1.13552

M. Rumetna, Supriyanto et al., "PENERAPAN METODE SIMPLEKS UNTUK MENGHASILKAN KEUNTUNGAN MAKSIMUM PADA PENJUAL BUAH PINANG," J. Dedication To Papua Community2, vol. 2, no. 1, pp. 75-86, 2019. https://doi.org/10.34124/288517

M. S. Rumetna and T. N. Lina, "Pelatihan menghitung hasil penjualan rokok selama masa pandemi covid-19 menggunakan metode simpleks dan software pom-qm," J. Pendidik. Dan Pemberdaya. Masy., vol. 8, no. 1, pp. 69-77, 2021, https://doi.org/10.36706/jppm.v8i1.14110

V. Ngamelubun et al., "Optimalisasi Keuntungan Menggunakan Metode Simpleks Pada Produksi Batu Tela," Ris. Komput., vol. 6, no. 5, pp. 484-491, 2019.

M. S. Rumetna et al., "MENGHITUNG KEUNTUNGAN MAKSIMAL DARI PENJUALAN ROTI ABON GULUNG DENGAN MENGGUNAKAN METODE SIMPLEKS DAN SOFTWARE POM-QM," J. Jendela Ilmu, vol. 1, no. 1, pp. 6-12, 2020. https://doi.org/10.34124/ji.v1i1.49

M. S. Rumetna, D. Manongga, and A. Iriani, "PENERAPAN KNOWLEDGE CAPTURE UNTUK PROMOSI FAKULTAS MENGGUNAKAN SOFT SYSTEM METHODOLOGY ( SSM ) ( STUDI KASUS?: FAKULTAS TEKNIK , UNIVERSITAS VICTORY SORONG )," in Prosiding Seminar Nasional Geotik, 2017, pp. 106-116.

M. S. Rumetna, T. N. Lina, R. R. Pakpahan, Y. Ferdinandus, F. S. Pormes, and J. E. Lopulalan, "Implementing Knowledge Management System to Improve Effectiveness of Faculty Activities," in Bukittinggi International Conference on Education, 2020,

https://doi.org/10.4108/eai.14-9-2020.2305670

R. Ong et al., "Maksimalisasi Keuntungan Pada Usaha Dagang Martabak Sucipto Menggunakan Metode Simpleks Dan POM-QM," Ris. Komput., vol. 6, no. 4, pp. 434-441, 2019.

M. S. Rumetna, T. N. Lina, L. R. Tauran, T. Patty, A. Malak, and K. Yawan, "Penerapan Metode Simpleks pada Usaha Dagang Bintang Tiurma," J. Innov. Inf. Technol. Appl., vol. 2, no. 01, pp. 28-36, 2020. https://doi.org/10.35970/jinita.v2i01.160

M. S. Rumetna, "AUDIT LINGKUNGAN DAN PENGENDALIAN TEKNOLOGI INFORMASI PADA PT.XYZ," Simetris J. Tek. Mesin, Elektro dan Ilmu Komput., vol. 9, no. 2, pp. 753-768, 2018. https://doi.org/10.24176/simet.v9i2.2294

M. S. Rumetna et al., "BERBASIS WEBSITE PADA PERUSAHAN CENDRAWASIH WIPUTRA MANDIRI KOTA SORONG DESIGN OF A WEBSITE-BASED DEMAND INFORMATION SYSTEM IN CENDRAWASIH WIPUTRA MANDIRI COMPANY," Elektro Luceat, vol. 7, no. 1, pp. 10-19, 2021.

M. S. Rumetna, M. Pieter, and M. Manurung, "APLIKASI PENGENALAN KARAKTER ALFANUMERIK MENGGUNAKAN ALGORITMA HAMMING DISTANCE," Pros. SNATIF, no. 4, pp. 77-84, 2017, [Online]. Available: https://media.neliti.com/media/publications/173678-ID-aplikasi-pengenalan-karakter-alfanumerik.pdf.

M. S. Rumetna et al., "PENDAMPINGAN DAN PELATIHAN PENERAPAN METODE SIMPLEKS PADA USAHA DAGANG BINTANG TIURMA," J. Abdimas Bina Bangsa, vol. 01, no. 02, pp. 205-214, 2020. https://doi.org/10.46306/jabb.v1i2.28

P. Pratiwi et al., "Pengembangan Aplikasi Mobile Augmented Reality untuk Mendukung Pengenalan Koleksi Museum," J. Teknol. Inf. dan Ilmu Komput., vol. 5, no. 1, p. 147, 2018, https://doi.org/10.25126/jtiik.201853891

H. Agung and N. Yunus Marselinus, "Implementasi Metode Breadth First Search danVikor pada Aplikasi Diagnosa Kerusakan Hardware Komputer," J. Sisfokom (Sistem Inf. dan Komputer), vol. 5, no. 2, pp. 46-53, 2016, https://doi.org/10.32736/sisfokom.v5i2.38

M. S. Rumetna et al., "Mengoptimalilasi keterbatasan sumber daya untuk memaksimalkan keuntungan penjualan es kelapa muda menggunakan metode simpleks dan software pom-qm," Pengabdi. Masy., vol. 02, no. 02, pp. 136-149, 2019. https://doi.org/10.34124/jpkm.v2i2.45

T. N. Lina and M. S. Rumetna, "Analysis of Land Use Change in Bantul Regency Using Geoprocessing Technique," in International Conference of Computer Science and Engineering Technology(ICCSET), 2018, pp. 506-512, https://doi.org/10.4108/eai.24-10-2018.2280499

M. S. Rumetna and I. Sembiring, "PEMANFAATAN CLOUD COMPUTING BAGI USAHA KECIL MENENGAH (UKM)," in Prosiding Seminar Nasional Geotik, 2017, no. ISSN:2580-8796, pp. 1-9.

M. S. Rumetna, "Audit Lingkungan Dan Pengendalian Teknologi Informasi Pada Pt. Xyz," Simetris J. Tek. Mesin, Elektro dan Ilmu Komput., vol. 9, no. 2, pp. 753-768, 2018, https://doi.org/10.24176/simet.v9i2.2294

M. S. Rumetna and T. N. Lina, "Forecasting Number of Covid-19 Positive Patients in Sorong City Using the Moving Average and Exponential Smoothing Methods," IJICS (International J. Informatics Comput. Sci., vol. 5, no. 1, pp. 37-43, 2021, doi: 10.30865/ijics.v5i1.2908.

M. S. Rumetna, T. N. Lina, T. P. Sari, P. Mugu, A. Assem, and R. Sianturi, "Optimasi Jumlah Produksi Roti Menggunakan Program Linear Dan Software POM-QM," Comput. Based Inf. Syst. J., vol. 09, no. 01, pp. 42-49, 2021. https://doi.org/10.33884/cbis.v9i1.3645

M. S. Rumetna et al., "OPTIMALISASI PENJUALAN NOKEN KULIT KAYU MENGGUNAKAN METODE SIMPLEKS DAN SOFTWARE POM-QM," Comput. Based Inf. Syst. J., vol. 08, no. 02, pp. 37-45, 2020. https://doi.org/10.33884/cbis.v8i2.1954

M. S. Rumetna, E. Sediyono, and K. D. Hartomo, "Analisis Perubahan Tata Guna Lahan di Kabupaten Bantul Menggunakan Metode Global Moran's I," J. Buana Inform., vol. 8, no. 4, pp. 225-234, 2017, https://doi.org/10.24002/jbi.v8i4.1446

L. Sarmin et al., "PENERAPAN METODE SIMPLEKS UNTUK MENGHITUNG KEUNTUNGAN MAKSIMUM PADA PENGRAJIN GELANG BESI PUTIH DI PASAR REMU SORONG," J. KUADAS, vol. 1, no. 2, pp. 1-7, 2018. https://doi.org/10.34124/jpkm.v2i1.17

M. S. Rumetna, T. N. Lina, L. Simarmata, L. Parabang, A. Joseph, and Y. Batfin, "Pemanfaatan POM-QM Untuk Menghitung Keuntungan Maksimum UKM Aneka Cipta Rasa (ACR) Menggunakan Metode Simpleks," in GEOTIK, 2019, pp. 12-22.

T. N. Lina, B. S. Marlissa, M. S. Rumetna, and J. E. Lopulalan, "Penerapan Metode Simpleks Untuk Meningkatkan Keuntungan Produksi," Ris. Komput., vol. 7, no. 3, pp. 459-468, 2020, https://doi.org/10.30865/jurikom.v7i3.2204

M. S. Rumetna, "PEMANFAATAN SISTEM INFORMASI GEOGRAFI UNTUK DETEKSI DAERAH RAWAN LONGSOR DI KECAMATAN SIDOMUKTI, SALATIGA," KUADAS, vol. 1, no. 1, 2018.

M. S. Rumetna and T. N. Lina, "Sistem Informasi Kampung Wisata Arborek Dengan Metode Waterfall," Informatics Educ. Prof., vol. 5, no. 1, pp. 31-40, 2020.

M. S. Rumetna, T. N. Lina, and A. B. Santoso, "RANCANG BANGUN APLIKASI KOPERASI SIMPAN PINJAM MENGGUNAKAN METODE RESEARCH AND DEVELOPMENT," Tek. Mesin, Elektro dan Ilmu Komput., vol. 11, no. 1, pp. 119-128, 2020. https://doi.org/10.24176/simet.v11i1.3731

T. N. Lina et al., "PENERAPAN METODE SIMPLEKS DALAM OPTIMALISASI KEUNTUNGAN HASIL PRODUKSI LEMON CINA DAN DAUN JERUK PURUT," Elektro Luceat, vol. 6, no. 1, 2020. https://doi.org/10.32531/jelekn.v6i1.206

M. S. Rumetna and T. N. Lina, "Pelatihan Penggunaan Sistem Inventory Data Barang Pada Gudang CV Tanaya," JPM J. Pengabdi. Masy., vol. 1, no. 1, pp. 11-17, 2020.

T. N. Lina et al., "SISTEM INFORMASI E-ARSIP BERBASIS WEB (STUDI KASUS?: PT HALEYORA POWERINDO CABANG SORONG)," J. Jendela Ilmu, vol. 1, no. 1, pp. 1-5, 2020. https://doi.org/10.34124/ji.v1i1.48

M. S. Rumetna, T. N. Lina, and J. E. Lopulalan, "A knowledge management system conceptual model for the sorong COVID-19 task force," Int. J. Informatics Vis., vol. 4, no. 4, pp. 195-200, 2020, https://doi.org/10.30630/joiv.4.4.418

M. S. Rumetna, E. E. Renny, and T. N. Lina, "Designing an Information System for Inventory Forecasting," Int. J. Adv. Data Inf. Syst., vol. 1, no. 2, pp. 80-88, 2020, https://doi.org/10.25008/ijadis.v1i2.187

M. S. Rumetna et al., "Optimasi Pendapatan Pembuatan Spanduk dan Baliho Menggunakan Metode Simpleks ( Studi Kasus?: Usaha Percetakan Shiau Printing )," J. Ris. Komput., vol. 7, no. 2, pp. 278-284, 2020, https://doi.org/10.30865/jurikom.v7i2.1922

M. S. Rumetna, T. N. Lina, T. Aponno, A. Palisoa, and F. Singgir, "Penerapan Metode Simpleks Dan Software POM- QM Untuk Optimalisasi Hasil Penjualan Pentolan Bakso," Ilm. Manaj. Inform. dan Komput., vol. 02, no. 03, pp. 143-149, 2018.

T. N. Lina et al., "PREMIUM DAN PERTALITE MENGGUNAKAN METODE MAXIMIZATION OF PROFIT ON PREMIUM AND PERTALITE BUSINESSES USING SIMPLEX METHODS AND POM-QM," Elektro Luceat, vol. 7, no. 1, pp. 1-9, 2021.

M. S. Rumetna, "Pemanfaatan Cloud Computing Pada Dunia Bisnis: Studi Literatur," J. Teknol. Inf. dan Ilmu Komput., vol. 5, no. 3, pp. 305-314, 2018, https://doi.org/10.25126/jtiik.201853595

M. S. Rumetna, "KOMBINASI GNU PRIVACY GUARD DAN HAMMING DISTANCE UNTUK KEAMANAN EMAIL SERTA JALUR SERTIFIKASI COMBINATION OF GNU PRIVACY GUARD AND HAMMING DISTANCE FOR EMAIL SECURITY AND CERTIFICATION PATHS," Elektro Luceat [November], vol. 7, no. 2, pp. 151-160, 2021.

Downloads

Published

2021-12-30

How to Cite

Lina, T. N., & Rumetna, M. S. (2021). Comparison Analysis of Breadth First Search and Depth Limited Search Algorithms in Sudoku Game. Bulletin of Computer Science and Electrical Engineering, 2(2), 74–83. https://doi.org/10.25008/bcsee.v2i2.1146