Formulasi Masalah Puzzle Sudoku Menggunakan Binary Integer Linear Programming (BILP) serta Implementasinya pada Julia, Python dan Minizinc

Abstract

Sudoku merupakan permainan teka-teki angka yang populer di berbagai kalangan. Dalam matematika, Sudoku dapat dimodelkan sebagai masalah pemrograman linear khususnya masalah Binary Integer Linear Programming (BILP). Penyelesaian Sudoku menggunakan BILP cukup sulit karena membutuhkan banyak iterasi untuk itu perlu bantuan software. Penelitian ini bertujuan untuk menganalisis permasalahan Sudoku menggunakan formulasi pemrograman linear integer 0-1 dan mengimplementasikan permasalahan tersebut menggunakan package JuMP pada Julia serta membandingkan efisiensinya berdasarkan waktu komputasi pada Python dan MiniZinc. Hasil implementasi Sudoku pada Julia, Python dan MiniZinc menunjukkan bahwa bahasa pemrograman Julia memiliki performa yang lebih baik dibandingkan Python dan MiniZinc berdasarkan waktu komputasi.

Sudoku is a number puzzle game that is popular in various circles. In mathematics, Sudoku can be modeled as a linear programming problem, especially the Binary Integer Linear Programming (BILP) problem. Solving Sudoku using BILP is quite difficult because it requires many iterations for that it requires software assistance. This study aims to analyze the Sudoku problem using the 0-1 integer linear programming formulation and implement the problem using the JUMP package on Julia and compare its efficiency based on computational time in Python and MiniZinc. The results of implementing Sudoku on Julia, Python and MiniZinc show that the implement on Julia programming language has less computational time than Python and MiniZinc.