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

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 partiall...

Full description

Saved in:

Bibliographic Details
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
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-uitm-ir.106027
record_format	uketd_dc
spelling	my-uitm-ir.1060272024-11-30T22:59:28Z Solving Sudoku puzzles in Binary Integer Linear Programming using Branch and Bound algorithm / Ahida Waliyyah Ahmad Fuad 2024 Ahmad Fuad, Ahida Waliyyah Algorithms 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. 2024 Thesis https://ir.uitm.edu.my/id/eprint/106027/ https://ir.uitm.edu.my/id/eprint/106027/1/106027.pdf text en public degree Universiti Teknologi MARA, Terengganu College of Computing, Informatics and Mathematics Nor-Al-Din, Siti Musliha
institution	Universiti Teknologi MARA
collection	UiTM Institutional Repository
language	English
advisor	Nor-Al-Din, Siti Musliha
topic	Algorithms
spellingShingle	Algorithms Ahmad Fuad, Ahida Waliyyah Solving Sudoku puzzles in Binary Integer Linear Programming using Branch and Bound algorithm / Ahida Waliyyah Ahmad Fuad
description	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.
format	Thesis
qualification_level	Bachelor degree
author	Ahmad Fuad, Ahida Waliyyah
author_facet	Ahmad Fuad, Ahida Waliyyah
author_sort	Ahmad Fuad, Ahida Waliyyah
title	Solving Sudoku puzzles in Binary Integer Linear Programming using Branch and Bound algorithm / Ahida Waliyyah Ahmad Fuad
title_short	Solving Sudoku puzzles in Binary Integer Linear Programming using Branch and Bound algorithm / Ahida Waliyyah Ahmad Fuad
title_full	Solving Sudoku puzzles in Binary Integer Linear Programming using Branch and Bound algorithm / Ahida Waliyyah Ahmad Fuad
title_fullStr	Solving Sudoku puzzles in Binary Integer Linear Programming using Branch and Bound algorithm / Ahida Waliyyah Ahmad Fuad
title_full_unstemmed	Solving Sudoku puzzles in Binary Integer Linear Programming using Branch and Bound algorithm / Ahida Waliyyah Ahmad Fuad
title_sort	solving sudoku puzzles in binary integer linear programming using branch and bound algorithm / ahida waliyyah ahmad fuad
granting_institution	Universiti Teknologi MARA, Terengganu
granting_department	College of Computing, Informatics and Mathematics
publishDate	2024
url	https://ir.uitm.edu.my/id/eprint/106027/1/106027.pdf
_version_	1818588168179417088

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

Similar Items