Formulation of Sudoku Puzzle Using Binary Integer Linear Programming and Its Implementation in Julia, Python, and Minizinc

Fahren Bukhari; Sri Nurdiati; Mohamad Khoirun Najib; Nandika Safiqri

doi:10.34312/jjom.v4i2.14194

Formulation of Sudoku Puzzle Using Binary Integer Linear Programming and Its Implementation in Julia, Python, and Minizinc

Fahren Bukhari, Sri Nurdiati, Mohamad Khoirun Najib, Nandika Safiqri

Abstract

Sudoku is a number puzzle game popular among people with various difficulty levels (easy, medium, hard, and extremely hard). Sudoku can be modeled as a linear programming problem in mathematics, particularly binary integer linear programming (BILP). Completing Sudoku using BILP is quite tricky because it requires many iterations. Therefore, this study aims to analyze the Sudoku problem using the BILP formulation and implement the problem using Julia, Python, and MiniZinc. Out of 15 cases for each difficulty level, Julia performs better than Python and MiniZinc based on computation time. Moreover, Sudoku with easy difficulty levels is solved with a longer computation time than the other three difficulty levels. The computation time for solving BILP is getting faster as the difficulty level of the Sudoku problem increases. This is because Sudoku problems with easy difficulty levels have more known values as clues and generate more constraints than other difficulty levels.

Keywords

Julia; Linear Programming; Minizinc; Python; Sudoku

Full Text:

PDF

References

D. B. Mishra, R. Mishra, K. N. Das, and A. A. Acharya, “Solving Sudoku Puzzles Using Evolutionary Techniques—A Systematic Survey,” in Advances in Intelligent Systems and Computing, 2018, pp. 791–802, doi: http://dx.doi.org/10.1007/978-981-10-5687-1 71.

I. Lynce and J. Ouaknine, “Sudoku as a SAT Problem,” in AI&M, 2006.

H. Chel, D. Mylavarapu, and D. Sharma, “A novel multistage genetic algorithm approach for solving Sudoku puzzle,” in 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT). IEEE, mar 2016, pp. 808–813, doi: http://dx.doi.org/10.1109/ICEEOT.2016.7754798.

A. C. BartlettTimothy, P. Chartier, A. N. Langville, and T. D. Rankin, “An Integer Programming Model for the Sudoku Problem,” in J. Online Math. its Appl., vol. 8, no. 1, 2007.

N. Kitsuwan, P. Pavarangkoon, H. M. Widiyanto, and E. Oki, “Dynamic load balancing with learning model for Sudoku solving system,” Digital Communications and Networks, vol. 6, no. 1, pp. 108–114, feb 2020, doi: http://dx.doi.org/10.1016/j.dcan.2019.03.002.

A. Zulaihah and A. Mardati, “Penggunaan Permainan Throwing Sudoku untuk Pengenalan Konsep Bilangan,” in Optimalisasi Peran Pendidikan dalam Membangun Karakter Anak untuk Menyongsong Generasi Emas Indonesia, 2016, pp. 190–194.

K. Genova and V. Guliashki, “Linear integer programming methods and approaches - A survey,” in Cybern. Inf. Technol., vol. 11, no. 1, 2011, pp. 13–25.

M. F. Wardhana, Penyelesaiaan Puzzle Sudoku Menggunakan Pemrograman Linear Integer. Undergraduate Thesis: IPB University, 2014.

H. P. Williams, “Logic and Integer Programming,” in International Series in Operations Research & Management Science. London: Springer, 2009.

S. D. Purba and F. Ahyaningsih, “Integer Programming Dengan Metode Branch and Bound Dalam Optimasi Jumlah Produksi Setiap Jenis Roti Pada Pt. Arma Anugerah Abadi,” Karismatika, vol. 6, no. 3, pp. 20–29, 2020, doi: https://doi.org/10.24114/jmk.v6i3.22208.

J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A Fresh Approach to Numerical Computing,” SIAM Review, vol. 59, no. 1, pp. 65–98, jan 2017, doi: http://dx.doi.org/10.1137/141000671.

N. K. K. Ardhana, S. Nurdiati, M. K. Najib, and S. A. Mukrim, “Akurasi dan Efisiensi Solusi Persamaan Diferensial Biasa Dengan Masalah Nilai Batas Pada Julia dan Octave,” Jurnal Matematika UNAND, vol. 11, no. 1, pp. 32–46, apr 2022, doi: http://dx.doi.org/10.25077/jmu.11.1.32-46.2022.

K. Gao, G. Mei, F. Piccialli, S. Cuomo, J. Tu, and Z. Huo, “Julia language in machine learning: Algorithms, applications, and open issues,” Computer Science Review, vol. 37, p.

, aug 2020, doi: http://dx.doi.org/10.1016/j.cosrev.2020.100254.

I. Dunning, J. Huchette, and M. Lubin, “JuMP: A Modeling Language for Mathematical Optimization,” SIAM Review, vol. 59, no. 2, pp. 295–320, jan 2017, doi: http://dx.doi.org/10.1137/15M1020575.

J. Enterprise, Otodidak Pemrograman Python. Jakarta: PT Elex Media Komputindo, 2017.

T. C. A.-S. Zulkhaidi, E. Maria, and Y. Yulianto, “Pengenalan Pola Bentuk Wajah dengan OpenCV,” Jurnal Rekayasa Teknologi Informasi (JURTI), vol. 3, no. 2, p. 181, jun 2020, doi: http://dx.doi.org/10.30872/jurti.v3i2.4033.

K. Marriott, P. J. Stuckey, L. D. Koninck, and H. Samulowitz, A MiniZinc Tutorial, 2014.

R. Caballero, P. J. Stuckey, and A. Tenorio-Fornes, “Two type extensions for the constraint modeling language MiniZinc,” Science of Computer Programming, vol. 111, pp. 156–189, nov 2015, doi: http://dx.doi.org/10.1016/j.scico.2015.04.007.

D. Assencio, “Solving Sudoku Puzzle with Linear Programming,” 2017, url: https://diego.assencio.com/?index=25ea1e49ca59de51b4ef6885dcc3ee3b.

DOI: https://doi.org/10.34312/jjom.v4i2.14194