Sudoku Solver
Submitted in partial fulfillment of the requirements of the
degree
BACHELOR OF ENGINEERING IN COMPUTER
ENGINEERING
By
Piyush Patil B/82
Soham Parab B/78
Sahil Pawar B/85
Supervisor
Prof. Pallavi Bharambe
Department of Computer Engineering
Shivajirao S. Jondhale College of Engineering,
Dombivli (E)
University of Mumbai
(AY 2024-25)
1
CERTIFICATE
This is to certify that the Mini Project entitled “Sudoku Solver” is a bonafide
work of Piyush Patil(B/82), Soham Parab(B/78), Sahil Pawar(B/85)
submitted to the University of Mumbai in partial fulfillment of the requirement
for the award of the degree of “Bachelor of Engineering” in “Computer
Engineering”.
Prof. Pallavi Bharambe
Supervisor
Dr. Saroja T. V Dr. Uttara Gogate Dr. P. R. Rodge
Project Coordinator Head of Department Principal
2
Mini project Approval
This Mini Project entitled “Sudoku Solver” by Piyush Patil(B/82), Soham Parab
(B/78), Sahil Pawar(B/85) is approved for the degree of Bachelor of Engineering in
Computer Engineering.
Examiners
1………………………………………
(Internal Examiner Name & Sign)
2…………………………………………
(External Examiner name & Sign)
Date:
Place:
3
Contents
Abstract ii
Acknowledgments iii
List of Abbreviations iv
List of Figures v
List of Tables vi
List of Symbols vii
1 Introduction 1
1.1 Introduction
1.2 Motivation
1.3 Problem Statement & Objectives
2 Literature Survey 11
2.1 Survey of Existing System
2.2 Limitation Existing system or research gap
2.3 Mini Project Contribution
3 Proposed System (New Approach of Data Summarization) 18
3.1 Introduction
3.2 Architecture/ Framework
3.3 Algorithm and Process Design
3.4 Details of Hardware & Software
3.4 Experiment and Results
3.5 Conclusion and Future work.
References 32
4
Abstract
This project presents a Java-based Sudoku solver that automates the process of solving
standard 9x9,6x6, Alphabet, Fruits Sudoku puzzles. The solver employs a backtracking
algorithm, a common recursive technique used to explore all possible configurations while
adhering to the game's constraints. The user interface allows for easy input of puzzles, and
the system displays both the initial grid and the solved solution. Performance analysis
demonstrates the algorithm's efficiency, handling a variety of difficulty levels. This project
aims to enhance understanding of algorithmic problem-solving and provides a practical
application of recursion and data structures in Java.
The project features a user-friendly graphical interface that allows users to input puzzles
easily. Users can either enter a puzzle manually or load a pre-defined one. The interface
visually represents the grid, highlighting cells as they are filled in, which aids in
understanding the solving process. Through this project, users gain insight into the
mechanics of Sudoku solving, the principles of backtracking, and the application of Java
programming in solving real-world problems
5
AKNOWLEDGMENT
Without the constant guidance and support of those who made this project possible, efforts
would have been in vain, and the satisfaction that results from its successful completion
would not be complete. I feel privileged to be able to show respect and gratitude to everyone.
who helped us complete this project.
I would like to express my gratitude to Prof. Pallavi Bharambe, a member of the computer
engineering department who served as my project guide. Her constant support,
encouragement, and direction were invaluable in ensuring that this project was completed
successfully.
We would also like to express our gratitude to Dr. Saroja T. V., our project coordinator, for
supporting us and resolving our questions. I sincerely thank.
Dr. Uttara Gogate, head of the Department of Computer Engineering, for giving us the
chance to bring this project to life.
I would like to take this opportunity to express my sincere appreciation to our esteemed
Principal. Dr. Pramod R. Rodge, for his consistent support and encouragement.
Last but not least, we would like to express our gratitude to the teaching and non-teaching
staff of the Department of Computer Engineering for their assistance.
6
List of Abbreviations
1. GUI -Graphical user interface
2. UI -User-Friendly interface
3. OS-Operating System
4. JDK-Java Development Kit
5. IDE-Integrated Development Environment
6. 3x3-Three by Three (referring to subgrids in Sudoku)
7
CHAPTER 1: INTRODUCTION
1.1 Introduction
Sudoku is a classic logic-based number placement puzzle that has captured the
attention of millions around the world. The objective of the game is to fill a 9x9
grid with numbers so that each column, each row, and each of the nine 3x3 sub-
grids (also called boxes) contain all of the digits from 1 to 9 without repeating.
The Sudoku Solver project in Java aims to create a program that can
automatically solve Sudoku puzzles using an efficient algorithm. This project not
only reinforces fundamental programming skills but also provides insights into
algorithm design, recursion, and backtracking.
Key Feature
* Input Handling: Accepts a partially filled Sudoku grid from the user.
* Validation: Checks for the validity of numbers in rows, columns, and
boxes.
* Backtracking Algorithm: Uses a recursive approach to explore potential
solutions and backtrack when necessary.
* Output Display: Provides a clear output of the solved Sudoku grid.
* Error Handling: Manages invalid inputs and ensures the program
operates smoothly
.
Technologies Used
* Java: The primary programming language for implementing the solver.
* IDE: An Integrated Development Environment (like IntelliJ IDEA or
Eclipse) for code development and debugging.
* JUnit (Optional): For unit testing the methods and ensuring correctness.
1.2 Motivation
Sudoku puzzles provide a stimulating challenge that requires logical reasoning and
problem-solving skills.
Building a solver allows you to engage deeply with the mechanics of the puzzle while
honing your programming skills. The project offers an opportunity to implement and
understand algorithms, particularly backtracking. This helps in grasping concepts such
as recursion, depth-first search, and optimization techniques, which are applicable in
various fields of computer science. Developing a Sudoku solver involves managing
potential errors and validating inputs, providing a great learning experience in
debugging and error handling in software development. Ultimately, the project is about
having fun with a beloved puzzle game. It combines creativity with technical skills,
making the learning process enjoyable and fulfilling.
8
1.3 Problem statement and objectives
Specific Challenges:
* Handling invalid input configurations gracefully.
* Implementing an efficient algorithm to explore potential solutions.
* Ensuring the solver can handle both simple and complex puzzles.
* Providing clear feedback to the user, including the solved grid and any
errors encountered.
Objectives
1. Input Handling:
Design a method to accept and validate user input for the Sudoku grid, including both
filled and empty cells.
2. Grid Representation:
Use a suitable data structure (e.g., a 2D array) to represent the Sudoku board and
facilitate easy access to its elements.
3. Validation:
Implement a function to check whether a proposed number placement is valid according
to Sudoku rules, ensuring no duplicates exist in the respective row, column, and 3x3
sub-grid.
4. Backtracking Algorithm:
Develop a recursive backtracking algorithm to systematically explore possible placements
for the empty cells, backtracking when an invalid placement is detected.
5. Performance Optimization:
Implement techniques to reduce the search space and improve the efficiency of the solver,
such as constraint propagation and early termination of searches.
6. Error Handling:
Include robust error handling to manage invalid inputs and edge cases, ensuring the
program operates smoothly and provides informative feedback to users
9
CHAPTER 2: LITERATURE SURVEY
2.1 Literature Survey:
"A Survey of Sudoku Solving Techniques"
This survey reviews various techniques employed in Sudoku solving, categorizing them
into backtracking algorithms, constraint satisfaction methods, and heuristic approaches. It
also discusses the strengths and limitations of each method.
"Algorithms for Sudoku: A Comparative Survey"
This paper provides a comparative analysis of different algorithms used for solving Sudoku
puzzles, including traditional methods like backtracking and more modern approaches like
constraint programming and artificial intelligence.
"Recent Advances in Automated Sudoku Solving"
This survey highlights recent developments in automated Sudoku solving techniques, focusing
on algorithmic improvements and the use of machine learning and AI, providing a
comprehensive overview of state-of-the-art methods.
"Sudoku and Its Variants: A Survey of Solving Techniques"
This research explores not only traditional Sudoku but also its various variants, surveying the
solving techniques applicable to both standard and non-standard puzzles, including rule-based
and algorithmic methods.
"Artificial Intelligence Techniques for Sudoku Solving: A Review"
This review focuses on the application of AI techniques in Sudoku solving, including
genetic algorithms, neural networks, and reinforcement learning, discussing their
effectiveness and potential for future research.
"Constraint Satisfaction Problems: A Survey with Applications to Sudoku" This
paper surveys constraint satisfaction problems (CSPs) and their applications in solving
Sudoku, detailing various CSP techniques and their implementations.
"A Comprehensive Review of Sudoku Puzzle Generation and Solving Methods"
This survey discusses both the generation and solving of Sudoku puzzles, providing
insights into algorithmic approaches and challenges associated with different methods.
10
2.2 SURVEY TABLE:
Title Date of Method Used Advantages Disadvantages
Publishing
Causal Language 2024 Transformer Achieved Requires extensive
Modeling Can models 94.21% training data;
Elicit Search and trained on accuracy in performance may
Reasoning logical solving Sudoku vary with puzzle
Capabilities on sequences to puzzles; complexity
Logic Puzzles solve Sudoku demonstrates
and Zebra emergent search
[1] puzzles and reasoning
capabilities in
language
models
A 2023 Various Discusses both Complexity of
Comprehensive Algorithmic generation and methods may be
Review of Sudoku Approaches solving, offering overwhelming.
Puzzle Generation a holistic view.
and Solving
Methods
Artificial 2022 Genetic Explores Some AI methods
Intelligence Algorithms, innovative AI may require
Techniques for Neural methods extensive
Sudoku Solving: A Networks, applicable to computational
Review Reinforcemen Sudoku. resources.
t Learning
Recent Advances 2021 AI Highlights Can be overly
in Techniques, cutting-edge technical for
Automated Algorithmic methods and casual readers.
Sudoku Solving Improvements advancements.
Sudoku and Its 2020 Rule-based Covers a wide May lack depth in
Variants: A methods, range of variants specific
Survey of Algorithmic and their techniques.
Solving Techniques methods solutions.
Algorithms for 2019 Backtracking, Identifies Limited focus on
Sudoku: A Constraint strengths and practical
Comparative Programming, weaknesses of implementations.
Survey AI different
methods.
A Survey of 2018 Backtracking, Comprehensive May not cover the
Sudoku Solving Constraint overview of latest
Techniques Satisfaction, various advancements.
Heuristics techniques.
11
2.3 Existing System
Sudoku.com
Sudoku.com is a prominent online platform dedicated to the classic puzzle game of Sudoku,
designed to cater to players of all skill levels. Launched to provide an accessible and
engaging experience, Sudoku.com offers a comprehensive suite of features that make it easy
for both beginners and seasoned players to enjoy the game.
The platform provides a variety of Sudoku puzzles categorized by difficulty—easy, medium,
hard, and expert—allowing users to select challenges that match their experience and skill
level. With daily puzzles and unique challenges, Sudoku.com encourages regular
engagement and skill development.
In addition to its extensive library of puzzles, the site features helpful tools such as hints, a
user-friendly interface, and progress tracking, enabling players to improve their solving
techniques and track their performance over time.
It is a well-known platform for playing and solving Sudoku puzzles, available as both a
website and mobile app. It caters to a broad audience, from beginners to advanced players,
providing an engaging environment to enjoy the classic game.
Methods Used:
• Backtracking Algorithm: This foundational approach is employed to solve puzzles
systematically.
• Heuristic Techniques: The app integrates logical deduction methods to enhance
solving speed and provide hints.
2.4 Limitations of Existing System
Advanced Techniques: May not implement the most sophisticated solving
strategies, limiting efficiency for expert users.
Input Errors: Incorrectly entered puzzles can lead to inaccurate hints or failed
attempts at solving.
Performance: High traffic can affect loading times and app responsiveness.
Customization Limits: While some customization is available, players seeking
extensive personalization may find it lacking.
Dependency on Internet Access: As a web-based platform, it requires a stable
internet connection, which can limit accessibility in areas with poor connectivity.
12
CHAPTER 3: PROPOSED SYSTEM
Introduction
The proposed system is an advanced Sudoku Solver Game that integrates multiple Sudoku
variations, including 9×9 grid, 6×6 grid, Fruit Sudoku, and Alphabetic Sudoku. The system
is designed to provide an engaging and interactive experience while offering an efficient solver
that can handle different Sudoku types. This game is built using Java and Swing, ensuring a
user-friendly Graphical User Interface (GUI) with an intuitive design.
Objectives of the Proposed System
1. Efficient Puzzle Solving: Implement a robust backtracking algorithm, enhanced with
optimization techniques, to quickly and accurately solve Sudoku puzzles.
2. User-Friendly Interface: Develop an intuitive user interface (UI) that allows users to
easily input their Sudoku puzzles and view solutions, making the tool accessible to both
beginners and experienced players.
3. Input Flexibility: Support multiple input formats, allowing users to enter puzzles in
various ways (e.g., grid format, text input, or even importing from files).
4. Real-Time Validation: Include features that validate user input as they enter numbers,
providing immediate feedback on whether placements are correct according to Sudoku rules.
5. Error Handling: Implement comprehensive error handling to manage invalid inputs
gracefully, providing clear messages that guide users in correcting their entries.
6. Performance Optimization: Explore and integrate advanced techniques such as
constraint propagation and heuristic strategies to improve the efficiency of the solver,
especially for more complex puzzles.
13
Architecture of Sudoku Solver
The architecture of the Sudoku solver project can be organized into several key components,
each serving a specific role in the overall functionality of the system. Below is a high-level
overview of the architecture, which can be structured using a layered design pattern:
1. Presentation Layer
Console Interface: A simple text-based interface for users to input their Sudoku puzzles and
view solutions.
Graphical User Interface (GUI): (If implemented) A visual interface using Java Swing or
JavaFX that allows users to interact with the application through buttons, grids, and menus.
2. Application Layer
* Controller
Manages user interactions, directing input to the appropriate components and managing the
flow of data between the UI and the solver logic.
Handles user commands (e.g., submitting a puzzle, requesting a hint) and updates the UI
accordingly.
* Input Handling
Processes user input, allowing for various input methods (keyboard, file upload, etc.).
Validates the input format and prepares the data for processing by the solver.
* Sudoku Solver
Backtracking Algorithm :The core component that implements the backtracking algorithm for
solving Sudoku puzzles.
Validation Logic: Functions that check the validity of the Sudoku board state (ensuring no
duplicates in rows, columns, and sub-grids).
* Data Structures
Board Representation: A 2D array or similar structure to represent the 9x9 Sudoku grid, with
methods to access and modify cell values.
Candidate Tracking: Structures to track possible values for empty cells, enhancing the
efficiency of the solver.
14
Algorithm and Process Design
The primary algorithm used in the Sudoku solver is Backtracking, enhanced with
optimization techniques. Below is a step-by-step description of the algorithm:
Backtracking Algorithm Steps
1. Find an Empty Cell:
Scan the Sudoku grid to locate the first empty cell (typically represented by a zero or a specific
placeholder).
2. Try Possible Values:
For each number from 1 to 9:
Check Validity: Verify if placing the number in the empty cell adheres to Sudoku rules (i.e.,
the number does not already exist in the same row, column, or 3x3 sub-grid).
3. Place the Number:
If the number is valid, place it in the cell and proceed to the next empty cell by recursively
calling the solving function.
4. Backtrack If Necessary:
If placing the number does not lead to a solution (i.e., no valid number can be placed in the next
empty cell), remove (backtrack) the number and try the next possible number.
5. Check for Completion:
If all cells are filled correctly, the puzzle is solved. Return true.
If no numbers can be placed in the empty cell, return false to trigger backtracking.
6. Repeat Until Solved:
Continue the process until the Sudoku puzzle is completely solved or deemed unsolvable.
15
Algorithm and process design: Fruit Sudoku
1. Initialize Board:
Create a 6x6 grid and define 6 unique fruit icons (e.g., ).
2. Generate Complete Board:
Use backtracking to fill the grid by:
▪ Placing a fruit in each empty cell.
▪ Checking row, column, and 2x3 subgrid validity.
▪ Backtracking if no valid placement is found.
3. Create Puzzle:
Randomly remove some fruit icons ensuring the puzzle has one unique solution.
4. Display Grid:
Show the 6x6 grid with pre-filled fruits.
Allow users to click on empty cells to select fruits.
5. Input Handling:
Validate user input:
▪ Correct input ➔ Place the fruit.
▪ Wrong input ➔ Highlight cell red with an error message.
6. Solve and Reset:
Solve Button: Auto-fills the grid with the correct solution.
Reset Button: Clears the grid for a fresh start.
7. Win Condition:
If the board is correctly filled, display "Sudoku Solved Successfully!".
16
Fig-Backtracking Algorithm
Steps to Solve Alphabet Sudoku
1. Identify Empty Cells:
Scan the grid to locate empty cells.
2. Try Each Letter:
For each empty cell, try placing possible letters (e.g., A-I for 9x9).
3. Check Validity:
Ensure the chosen letter follows Sudoku rules:
Row Rule: No duplicate letter in the row.
Column Rule: No duplicate letter in the column.
Subgrid Rule: No duplicate letter in the respective 3x3 or 2x3 subgrid.
4. Recursion & Backtracking:
If a valid letter is placed, move to the next cell.
If no valid letter fits, backtrack by removing the last placed letter and trying the next
option.
5. Solution Found:
Repeat steps until all cells are filled correctly.
17
Hardware Requirements
1. Computer System:
Processor: A modern multi-core processor (Intel i5/Ryzen 5 or higher recommended) to ensure
efficient execution of the algorithm.
RAM: Minimum of 4 GB; 8 GB or more recommended for better multitasking.
Storage: At least 100 MB of free disk space to accommodate the Java Development Kit (JDK),
Integrated Development Environment (IDE), and project files.
Display: A standard monitor with a minimum resolution of 1366x768 for comfortable
viewing and development.
2. Network Connection:
Internet access may be required for downloading libraries, tools, and updates.
Software requirements
1. Operating System:
Windows (Windows 10 or later)
macOS (10.14 Mojave or later)
Linux (Ubuntu 18.04 or later)
2. Java Development Kit (JDK):
Version: JDK 8 or later (Java 11 or 17 recommended for long-term support).
Installation: Ensure the JDK is properly installed and configured on
the system (environment variables set).
3. Integrated Development Environment (IDE):
Recommended IDEs include:
▪ Eclipse: A popular, open-source IDE for Java development.
▪ IntelliJ IDEA: A powerful IDE with a free Community Edition.
4. Libraries (Optional):
o While the core Sudoku solving functionality can be implemented without external libraries,
you might consider using:
JavaFX: If developing a graphical user interface, JavaFX can enhance the UI experience.
18
RESULT:
Fig 3.1:9x9 Number Sudoku
19
20
Fig 3.2:Alphabet Sudoku
21
Conclusion:
The proposed Sudoku Solver Game enhances the traditional Sudoku experience by
integrating multiple variations, including 9×9, 6×6, Fruit Sudoku, and Alphabetic
Sudoku. With an efficient solver algorithm using Backtracking and Constraint
Propagation, the system ensures quick and accurate puzzle solving.
A user-friendly Java Swing-based GUI provides an engaging experience with real-time
validation, hints, and customization options. The game supports multiple modes,
including Manual Play, Auto-Solver, and Timed Challenges, making it suitable for both
casual and advanced players.
Overall, this system offers an interactive, scalable, and intelligent Sudoku-solving
platform, catering to different user preferences while maintaining efficiency and accuracy.
22
Future Work
To enhance the capabilities and usability of the Sudoku solver, several avenues for future
work are proposed:
1. Optimization Techniques:
Explore advanced solving strategies, such as constraint propagation and heuristic methods, to
further reduce solving times, especially for very hard puzzles.
2. Graphical User Interface (GUI):
Develop a more sophisticated GUI using JavaFX or Swing to improve user interaction. This
can include features like drag-and-drop puzzle input, visual hints, and step-by-step solution
displays.
3. Machine Learning Integration:
Investigate the possibility of integrating machine learning techniques to analyze user input
patterns and improve solving strategies over time.
4. Error Handling and Input Validation:
Enhance error handling to manage edge cases and invalid inputs more gracefully, providing
users with better feedback.
5. Multi-Platform Compatibility:
Consider packaging the application for multiple platforms (Windows, macOS, Linux) to reach
a broader audience.
6. Educational Resources:
Develop tutorials or interactive guides within the application to help users learn effective
Sudoku-solving techniques and strategies.
By pursuing these future directions, the Sudoku solver project can evolve into a more robust
and versatile tool, enhancing user experience and fostering a deeper understanding of both
Sudoku and algorithmic problem-solving.
23
Reference:
I. www.geeksforgeeks.org/sudoku-backtracking-7
II. www.leetcode.com/problems/sudoku-solver
III. www.algorithm-visualizer.org/brute-force/sudoku
IV. www.javatpoint.com/java-program-to-solve-sudoku-puzzle
V. www.docs.oracle.com/javase/tutorial/uiswing/
VI. www.github.com/search?q=sudoku+solver+java
VII. www.sudoku.com/how-to-play/sudoku-rules-for-complete-beginners
VIII. www.sudokuwiki.org
24
