Solving Sudoku puzzles in Binary Integer Linear Programming using Branch and Bound algorithm / Ahida Waliyyah Ahmad Fuad

• Main Author: Ahmad Fuad, Ahida Waliyyah
• Format: Thesis
• Language: English
• Published: 2024
• Subjects: Algorithms
• Online Access: https://ir.uitm.edu.my/id/eprint/106027/1/106027.pdf; https://ir.uitm.edu.my/id/eprint/106027/

Sudoku is a puzzle based on logic and combinatorial number placement. The goal is to fill a 9x9 grid with digits so that every column, row, and each of the nine 3x3 subgrids (also called "regions" or "blocks") contains all the digits from 1 to 9. The puzzle starts with a partially filled grid provided by the setter, and it usually has a unique solution. This study explores the application of a Binary Integer Linear Programming (BILP) model combined with the Branch and Bound (B&B) algorithm to solve Sudoku puzzles. The research successfully formulates BILP models for various Sudoku configurations, including standard 4x4 and 9x9 grids as well as the more complex Sudoku X variant. Using the PuLP library in Python, the B&B algorithm is implemented to systematically explore feasible solutions while pruning infeasible branches, ensuring all Sudoku constraints are met. The results demonstrate that the BILP model and B&B algorithm effectively and efficiently find valid solutions to these puzzles, confirming their robustness and accuracy. Additionally, the consistency between the results obtained from the computational approach and manual B&B method underscores the reliability of these techniques for solving advanced combinatorial optimization problems like Sudoku. Recommendations for future research include extending the application to larger Sudoku grids to further test scalability and efficiency.