Logic Programming

PROJECT NAME
SUDOKU SOLVER

Supervised By:
1. Prof. Hesham El-Deeb

2. Dr. Ahmed Allam

3. Dr. Dina Ahmed

4. Dr. Hassan Amr

5. Dr. Gehad Omar

Submitted By

Student Name
1) Omar Mahmoud Ahmed Khalil 97097
2) Mariam Homam Oyoun Alsoud 96816
3) Mohamed Ahmed Mahmoud Ahmed 98306
4) Omar Refaat Radwan Arfaa 97701
5) Esraa Atef Amen Amer 98993
6) Abdelrahman Ramadan Shaker Abdellahy 97273
7) Ali Mohamed Ali shahat 99358
8) Kholoud Youssef Tayel Abdelaty 98518
Chapter 1: Introduction
Sudoku is a globally renowned puzzle game renowned for its blend of simplicity and challenge,
making it a beloved pastime for puzzle enthusiasts worldwide. At its core, Sudoku revolves
around the goal of filling a 9x9 grid with digits from 1 to 9, ensuring that each column, row,
and 3x3 subgrid, often termed as "regions," contain all the digits without repetition.

The puzzle begins with a partially filled grid, with some cells already populated with numbers.
The player's objective is to strategically deduce and fill in the remaining cells logically,
ensuring that every digit fits into its proper place, satisfying the constraints of the game. These
constraints dictate that each digit must appear exactly once in every row, column, and 3x3
subgrid.

The allure of Sudoku lies in its scalability of difficulty, catering to a wide spectrum of players
from novices to seasoned veterans. The complexity of a Sudoku puzzle is determined by the
initial arrangement and placement of digits within the grid. While some puzzles may be
straightforward to solve, others can be notably challenging, requiring advanced problem-
solving strategies and logical deduction techniques.

In the realm of computer science, Sudoku serves as an excellent platform for exploring
constraint satisfaction techniques. This project aims to develop a program capable of efficiently
solving Sudoku puzzles through the systematic application of these techniques. By representing
the Sudoku puzzle as a Constraint Satisfaction Problem (CSP), the program navigates through
potential solutions while adhering strictly to the rules of the game. Through careful constraint
propagation and backtracking search algorithms, the program endeavors to explore and validate
potential solutions until a valid and complete Sudoku grid is achieved.
Chapter 2: System Analysis and Design
Functional Requirements:

• Input Handling: The system should be able to accept a partially filled 9x9 Sudoku grid
as input.

• Constraint Representation: It should represent the Sudoku puzzle as a Constraint

Satisfaction Problem (CSP), where variables represent empty cells and their domains are
the set of digits {1, 2, ..., 9}.

• Constraint Satisfaction: The system must employ constraint satisfaction techniques to

ensure that the solution adheres to Sudoku rules, i.e., each row, column, and 3x3 subgrid
contains all digits from 1 to 9 without repetition.

• Backtracking Algorithm: Implement a backtracking search algorithm with constraint

propagation to systematically explore and backtrack through possible solutions until a
valid solution is found.

• Output Generation: Once a valid solution is found, the system should output the
completed Sudoku grid.
Non-Functional Requirements:

• Performance: The system should be efficient in solving Sudoku puzzles of varying

difficulty levels within a reasonable time frame.

• Accuracy: The solver should guarantee correct solutions for all solvable Sudoku
puzzles.

• Usability: The program should have a user-friendly interface, allowing users to input
Sudoku puzzles easily and view the solution intuitively.

• Robustness: The system should handle invalid inputs gracefully and provide appropriate
error messages to the user.

• Scalability: The solver should be scalable to handle larger grid sizes or extended rule
sets if required in the future
Sequence Diagram
Use Case Diagram
Misuse Diagram
Activity Diagram
State Machine Diagram
Implementation Code

:- use_module(library(clpfd)).
% Predicate to solve a Sudoku puzzle
sudoku(Rows) :-

% Ensure the puzzle has 9 rows

length(Rows, 9),

% Ensure each row has 9 elements

maplist(same_length(Rows), Rows),

% Flatten the rows to a single list and restrict the domain to 1..9
append(Rows, Vs), Vs ins 1..9,

% Ensure each row has distinct digits

maplist(all_distinct, Rows),

% Transpose the grid to obtain columns

transpose(Rows, Columns),

% Ensure each column has distinct digits

maplist(all_distinct, Columns),

% Define the 3x3 subgrid blocks constraint

Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
blocks(As, Bs, Cs),
blocks(Ds, Es, Fs),
blocks(Gs, Hs, Is).

% Predicate to ensure each block has distinct digits

blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-

% Ensure distinct digits within the block

all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),

% Recursively apply to the next set of rows

blocks(Ns1, Ns2, Ns3).
% Define the Sudoku puzzle as a fact in the knowledge base
problem(1, [[_,_,_,_,_,_,_,_,_],
[_,_,_,_,_,3,_,8,5],
[_,_,1,_,2,_,_,_,_],
[_,_,_,5,_,7,_,_,_],
[_,_,4,_,_,_,1,_,_],
[_,9,_,_,_,_,_,_,_],
[5,_,_,_,_,_,_,7,3],
[_,_,2,_,1,_,_,_,_],
[_,_,_,_,4,_,_,_,9]]).

% Main predicate to solve the puzzle

solve_sudoku(ProblemId) :-
% Retrieve the puzzle from the knowledge base
problem(ProblemId, Puzzle),
% Solve the puzzle
sudoku(Puzzle),
% Print the solved puzzle
print_sudoku(Puzzle).

% Predicate to print the Sudoku puzzle

print_sudoku([]).
print_sudoku([Row|Rows]) :-
writeln(Row),
print_sudoku(Rows).
Method explanation:

• sudoku/1 Predicate: Defines constraints for solving Sudoku. Ensures rows, columns,
and 3x3 subgrids have distinct digits.

• blocks/3 Predicate: Ensures each 3x3 subgrid contains distinct digits. Recursively
checks rows within each block.

• problem/2 Predicate: Defines Sudoku puzzles with identifiers and 9x9 grids. Empty
cells are represented as underscores.

• solve_sudoku/1 Predicate: Main entry point for solving Sudoku. Takes puzzle
identifier, retrieves it, solves using sudoku/1, labels variables, and prints the solution.

• print_sudoku/1 Predicate: Prints the solved Sudoku puzzle row by row.

• labeling/2 Predicate: Assigns values from the domain to variables to satisfy constraints.
Used to label variables in the solved puzzle (with "First-Fail" heuristic).
Output