Final Report 1

SIX WEEKS SUMMER TRAINING REPORT
On
DSA Self-paced
Submitted by
Anaswar Aravind
Registration No. 12205985
Program Name: B-Tech CSE
Under the Guidance of
Mr. Sandeep Jain
School of Computer Science & Engineering

Lovely professional University, Phagwara
(June-July, 2024)
DECLARATION
I hereby declare that I have completed my six weeks summer training at DSA Self paced
from 25th June 2024 to 22nd July 2024 under the guidance of Mr. Sandeep Jain. I declare
that I have worked with full dedication during these six weeks of training and my
learning outcomes fulfil the requirements of training for the award of degree of Bachelor
of Technology, Lovely Professional university, Phagwara.
Anaswar Aravind
Registration no: 12205985
Date: 25th Aug, 2024
Training certificate from organization

Acknowledgement
It is with sense of gratitude; I acknowledge the efforts of entire hosts of well-wishers who
have in some way or other contributed in their own special ways to the success and
completion of the Summer Training.
Successfully completion of any type technology requires helps from a number of people. I
have also taken help from different people for the preparation of the report. Now, there is
little efforts to show my deep gratitude to those helpful people.
I would like to also thank my own college Lovely Professional University for offering
such a course which not only improve my programming skill but also introduced me to
new technologies.
Then I would like to thank my parents and friends who have helped me with their
valuable suggestions and guidance for choosing this course.
Last but not least I would like to thank my all classmates who have helped me a lot.
Table Of Contents
1. Introduction
2. Technology Learnt
3. Reason for choosing this technology.
4. Profile of the Problem
5. Problem Analysis
• Problem definition
• Feasibility Analysis
• Problem Complexity
• Constraints and Requirements
• Solution Strategy
• Performance Considerations
• Error Handling
6. Software Requirement Analysis
• Functional Requirements
• Non-Functional Requirements
• Software Requirements
• Assumptions and Constraints
7. Importance and Applicability

8. Roles and Profiles
9. Design
10. Implementation
11. Leaning Outcome from training/technology learnt
12. Bibliography
Introduction
1. What is Data Structure?
Data Structure is a way of collecting and organizing data in such a way that we can
perform operations on these data in an effective way. Data Structures is about
rendering data elements in terms of some relationship, for better organization and
storage. For example, we have some data which has, player's name "Virat" and age
26. Here "Virat" is of String data type and 26 is of integer data type.
2. What is Algorithm?
An algorithm is a finite set of instructions or logic, written in order, to accomplish a

certain predefined task. Algorithm is not the complete code or program, it is just the
core logic(solution) of a problem, which can be expressed either as an informal high
level description as pseudocode or using a flowchart.
This course is a complete package that helped me learn Data Structures and Algorithms
from basic to an advanced level. The course curriculum has been divided into 8 weeks
where one can practice questions & attempt the assessment tests according to his own
pace. The course offers me a wealth of programming challenges that will help me to
prepare for interviews with top-notch companies like Microsoft, Amazon, Adobe etc.
Technology Learnt
• Learnt Data Structures and Algorithms from basic to an advanced level.
• Learnt Topic-wise implementation of different Data Structures & Algorithms as
follows:
1. Introduction
• Asymptotic Notations
Asymptotic notations are mathematical tools to represent the time complexity

of algorithms for asymptotic analysis.
• Worst, Average and Best-Case Time Complexities

It is important to analyse an algorithm after writing it to find it's efficiency in
terms of time and space in order to improve it if possible.
When it comes to analysing algorithms, the asymptotic analysis seems to be

the best way possible to do so. This is because asymptotic analysis analyses
algorithms in terms of the input size. It checks how are the time and space
growing in terms of the input size.
• Analysis of Loops
2. Mathematics
• Finding number of Digits in a Number
• Arithmetic and Geometric Progressions
• Quadratic Equations
• Mean and Median
• Prime Numbers
• LCM and HCF
• Factorials
• Permutation and Combinations Basics
• Modular Arithmetic
3. Bit Magic
• Binary Representation
• Set and Unset
• Toggling
• Bitwise Operators
• Algorithms
Objective: The objective of this track is to familiarize the learners with

Bitwise Algorithms which can be used to solve problems efficiently and
some interesting tips and tricks using Bit Algorithms.
4. Recursion
• Recursion Basics
The process in which a function calls itself directly or indirectly is called
recursion and the corresponding function is called as recursive function. Using
recursive algorithm, certain problems can be solved quite easily. Examples of
such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree
Traversals, DFS of Graph, etc.
• Basic Problems on Recursion
• Tail Recursion
A recursive function is said to be following Tail Recursion if it invokes itself at
the end of the function. That is, if all of the statements are executed before the
function invokes itself then it is said to be following Tail Recursion.
void printN(int N)
{ if(N==0)
return; else
cout<<N<<" ";
printN(N-1);
}
The above function call for N = 5 will print:
54321
• Explanation of Subset Generation Problem
• Explanation of Josephus Problem
• Explanation of permutations of a string
We iterate from first to last index. For every index i, we swap the i-th character
with the first index. This is how we fix characters at the current first index,
then we recursively generate all permutations beginning with fixed characters
(by parent recursive calls). After we have recursively generated all permutations
with the first character fixed, then we move the first character back to its original
position so that we can get the original string back and fix the next character at
first position.
5. Arrays
• Introduction to Arrays
• Insertion and Deletion in Arrays
• Array Rotation
• Reversing an Array
• Sliding Window Technique
• Prefix Sum Array
• Implementing Arrays in C++ using STL
• Iterators in C++ STL
• Implementing Arrays in Java
• Sample Problems on Array
• XOR Linked List - A Memory Efficient Doubly Linked List | Set 1
6. Searching
• Binary Search Iterative and Recursive
• Binary Search and various associated problems
• Two Pointer Approach Problems
7. Sorting
• Implementation of C++ STL sort() function in Arrays and Vectors
• Sorting in Java
• Arrays.sort() in Java
• Collection.sort() in Java
• Stability in Sorting Algorithms
• Insertion Sort
• Merge Sort
• Quick Sort
• Overview of Sorting Algorithms
8. Matrix
• Introduction to Matrix in C++ and Java
• Multidimensional Matrix
• Pass Matrix as Argument
• Printing matrix in a snake pattern
• Transposing a matrix
• Rotating a Matrix
• Check if the element is present in a row and column-wise sorted matrix.
• Boundary Traversal
• Spiral Traversal
• Matrix Multiplication
• Search in row-wise and column-wise Sorted Matrix
9. Hashing
• Introduction and Time complexity analysis
• Application of Hashing
• Discussion on Direct Address Table
• Working and examples on various Hash Functions
• Introduction and Various techniques on Collision Handling
• Chaining and its implementation
• Open Addressing and its Implementation
• Chaining V/S Open Addressing
• Double Hashing
• C++
• Unordered Set
• Unordered Map
• Java
• HashSet
• HashMap
10. Strings
• Discussion of String DS
• Strings in CPP
• Strings in Java
• Rabin Karp Algorithm
• KMP Algorithm
11. Linked List
• Introduction Implementation in CPP
• Implementation in Java
• Comparison with Array DS
• Doubly Linked List
• Circular Linked List
• Loop Problems
• Detecting Loops
• Detecting loops using Floyd cycle detection
• Detecting and Removing Loops in Linked List
12. Stack
• Understanding the Stack data structure
• Applications of Stack
• Implementation of Stack in Array and Linked List
• In C++
• In Java
13. Queue
• Introduction and Application
• Implementation of the queue using array and LinkedList
• In C++ STL
• In Java
• Stack using queue
14. Deque
• Introduction and Application
• Implementation
• In C++ STL 14
• In Java
• Problems (With Video Solutions)
• Maximums of all subarrays of size k
• ArrayDeque in Java
• Design a DS with min max operations
15. Tree
• Introduction
• Tree
• Application
• Binary Tree • Tree Traversal
• Implementation of:
• Inorder Traversal
• Preorder Traversal
• Postorder Traversal
• Level Order Traversal (Line by Line)
• Tree Traversal in Spiral Form
16. Binary Search Tree
• Background, Introduction and Application
• Implementation of Search in BST
• Insertion in BST
• Deletion in BST
• Floor in BST
• Self Balancing BST
• AVL Tree
17. Heap
• Introduction & Implementation
• Binary Heap
• Insertion
• Heapify and Extract
• Decrease Key, Delete and Build Heap
• Heap Sort
• Priority Queue in C++
• PriorityQueue in Java
18. Graph
• Introduction to Graph
• Graph Representation
• Adjacency Matrix
• Adjacency List in CPP and Java
• Adjacency Matrix VS List
• Breadth-First Search
• Applications
• Depth First Search
• Applications
• Shortest Path in Directed Acyclic Graph
• Prim's Algorithm/Minimum Spanning Tree
• Implementation in CPP
• Dijkstra's Shortest Path Algorithm
• Implementation in CPP 16
• Bellman-Ford Shortest Path Algorithm
• Kosaraju's Algorithm
• Articulation Point
• Bridges in Graph
• Tarjan’s Algorithm
19. Greedy
• Introduction
• Activity Selection Problem
• Fractional Knapsack
• Job Sequencing Problem
20. Backtracking
• Concepts of Backtracking
• Rat In a Maze
• N Queen Problem
21. Dynamic Programming
• Introduction
• Dynamic Programming
• Memoization
• Tabulation
22. Tree
• Introduction
• Representation
• Search
• Insert
• Delete
• Count Distinct Rows in a Binary Matrix
23. Segment Tree
• Introduction
• Construction
• Range Query
• Update Query
24. Disjoint Set
• Introduction
• Find and Union Operations
• Union by Rank
• Path Compression
• Kruskal's Algorithm
Reason for choosing this technology

With advancement and innovation in technology, programming is becoming a highly
in-demand skill for Software Developers. Everything you see around yourself from
Smart TVs, ACs, Lights, Traffic Signals uses some kind of programming for executing
user commands.
Data Structures and Algorithms are the identity of a good Software Developer. The
interviews for technical roles in some of the tech giants like Google, Facebook,
Amazon, Flipkart is more focused on measuring the knowledge of Data Structures and
Algorithms of the candidates. The main reason behind this is Data Structures and
Algorithms improves the problem-solving ability of a candidate to a great extent.
1. This course has video lectures of all the topics from which one can easily learn. I
prefer learning from video rather than books and notes. I know books and notes and
thesis have their own significance but still video lecture or face to face lectures make
it easy to understand faster as we are involved Practically.
2. It has 200+ algorithmic coding problems with video explained solutions.
3. It has track based learning and weekly assessment to test my skills.

4. It was a great opportunity for me to invest my time in learning instead of wasting it
here and there during my summer break in this Covid-19 pandemic.
5. This was a life time accessible course which I can use to learn even after my training
whenever I want to revise.
Profile of the Problem

The problem addressed in this project is solving Sudoku puzzles, a popular logic-based
number placement game. The goal is to develop a Sudoku solver that can automatically fill
in the grid to complete the puzzle, adhering to the game's rules.
 Problem Overview:
o Sudoku Rules: A standard Sudoku puzzle consists of a 9x9 grid divided into
3x3 sub grids, where some cells are pre-filled with numbers. The objective
is to fill in the remaining cells so that each row, column, and 3x3 sub grid
contains all digits from 1 to 9 without repetition.
o Challenge: Solving Sudoku puzzles involves determining the correct
number for each empty cell based on the constraints provided by the filled
cells. This requires a systematic approach to explore potential solutions
while adhering to Sudoku's rules.
 Specific Issues:
o Complexity: As the puzzle size and difficulty increase, the number of
possible configurations grows exponentially, making it challenging to solve
efficiently.
o Validation: Ensuring that each placement adheres to Sudoku rules (no
duplicate numbers in rows, columns, and sub grids) is crucial.
o Efficiency: The solver must be efficient enough to handle various levels of
difficulty within a reasonable time frame.
 Objective of the Solution:

o Develop an algorithm that can solve Sudoku puzzles of varying difficulty
levels by applying logical reasoning and backtracking techniques.
o Create a user-friendly interface to input Sudoku puzzles and display the
solved grid.
Problem Analysis
1. Problem Definition:
Sudoku is a popular logic puzzle where the objective is to fill a 9x9 grid with numbers
from 1 to 9 such that each number appears exactly once in each row, column, and 3x3 sub
grid. The challenge is to devise an algorithm that can correctly and efficiently solve these
puzzles, given the initial numbers in some cells.
2. Problem Complexity:
 Puzzle Size: The Sudoku grid is 9x9, leading to 81 cells in total. This size can lead
to a significant number of possible configurations.
 Difficulty Levels: Sudoku puzzles come in various difficulty levels, from easy to
very hard, which affects the complexity of the solving process. Harder puzzles have
fewer pre-filled numbers, requiring more complex strategies for solving.
3. Constraints and Requirements:
 Sudoku Rules:
o Each row must contain numbers 1-9, with no repetitions.
o Each column must contain numbers 1-9, with no repetitions.
o Each 3x3 sub grid must contain numbers 1-9, with no repetitions.
o Input: The solver must accept a Sudoku puzzle as input, represented by a
string or grid format, where pre-filled cells are given, and empty cells are
marked (e.g., with a dash).
o Output: The solver should return the completed Sudoku grid that satisfies all
the rules, or indicate if the puzzle is unsolvable.
4. Solution Strategy:
 Backtracking Algorithm: The primary approach used is backtracking, a depth-first

search method that tries possible numbers in empty cells, backtracks when a
constraint is violated, and continues until the puzzle is solved or determined to be
unsolvable.
 Constraint Propagation: Additional techniques, such as constraint propagation, help
reduce the search space by applying Sudoku rules to narrow down the possible
numbers for each cell.
5. Performance Considerations:
 Efficiency: The algorithm must handle various puzzle difficulties efficiently. While
backtracking can be computationally intensive, optimizing it with techniques such
as constraint propagation can improve performance.
 Scalability: The solution should work for all standard Sudoku puzzles, regardless of
their difficulty.
6. Error Handling:
 Invalid Puzzles: The solver should be able to detect and handle cases where the
input puzzle is invalid or unsolvable, providing appropriate feedback to the user.
Software Requirement Analysis
1. Functional Requirements:
 Puzzle Input:
o The software must accept a Sudoku puzzle as input, which can be provided
in various formats (e.g., a string of numbers with placeholders for empty
cells or a 9x9 grid).
o The input must be validated to ensure it adheres to the standard Sudoku
rules (correct grid size, valid numbers, etc.).
 Puzzle Solving:
o The solver must use an algorithm (e.g., backtracking) to fill in the empty
cells while adhering to Sudoku rules.
o The software should handle different difficulty levels, from easy to very
hard, and provide a solution if one exists.
 Solution Output:
o The software should output the solved Sudoku puzzle, displaying the
completed grid.
o It should also indicate if the puzzle is unsolvable or if there are any errors in
the provided input.
 User Interaction:
o The software should include a user interface that allows users to input their
puzzles and view the solution.
o It should provide buttons for solving the puzzle and clearing the board,
along with any necessary feedback or error messages.
2. Non-Functional Requirements:
 Performance:
o The solver must handle standard Sudoku puzzles efficiently, providing solutions
within a reasonable timeframe.
o The performance should be optimized to handle different levels of puzzle
difficulty.
 Usability:
o The user interface should be intuitive and user-friendly, allowing users to
easily input puzzles and understand the results.
o The design should be responsive and accessible, accommodating various
screen sizes and devices.
 Reliability:
o The software should be reliable and robust, with minimal risk of crashing or
producing incorrect results.
o It should include error handling to manage invalid input or unsolvable
puzzles gracefully.
 Maintainability:
o The code should be well-documented and organized, making it easy to

understand, modify, and extend in the future.
o It should follow best practices for coding standards and include comments
where necessary.
3. Software Requirements:
 Platform:
o The software should be compatible with modern web browsers, allowing for
easy deployment and access via a web-based interface.
 Technology Stack:
o Frontend: HTML, CSS, JavaScript for the user interface and interaction.
o Backend: JavaScript (in the form of a Node.js environment or similar) for
the puzzle-solving algorithm.
 Dependencies:
o The software may require libraries or frameworks for JavaScript to support
features such as event handling and DOM manipulation.
4. Assumptions and Constraints:
 Assumptions:
o Users are familiar with basic Sudoku rules and conventions.

o The input format will adhere to the expected standards for Sudoku puzzles.
 Constraints:
o The software must work within the limitations of web browsers and
JavaScript performance.
o It should be compatible with the typical range of Sudoku puzzles but may
not handle highly unusual or non-standard variations.
Importance and Applicability
1. Problem-Solving and Educational Value:
 Importance: Sudoku is a popular puzzle that enhances logical thinking, pattern
recognition, and problem-solving skills. Developing a Sudoku solver helps in
understanding algorithmic approaches like backtracking, recursion, and
optimization, which are fundamental in computer science and mathematics.
 Applicability: This solver can be used as a teaching tool in educational settings to
demonstrate how algorithms can be applied to solve complex problems
systematically.
2. User Convenience and Entertainment:
 Importance: Sudoku puzzles are a common pastime, and solving them can be time-
consuming and challenging. This solver provides users with an easy way to
complete puzzles, offering a quick solution when they are stuck or simply wish to
check their answers.
 Applicability: The Sudoku solver is applicable to both casual players who need
assistance and enthusiasts who want to verify the correctness of their solutions.
3. Demonstration of Algorithmic Efficiency:
 Importance: The project showcases how algorithms can be optimized for efficiency,
particularly in solving constraint satisfaction problems like Sudoku. It highlights
the practical application of backtracking algorithms in real-world scenarios.
 Applicability: The algorithm can be adapted for other puzzles or problems that
require similar constraint-solving techniques, making it a versatile tool in software
development and problem-solving contexts.
4. Foundation for Advanced Features:

 Importance: The project lays the groundwork for implementing more advanced
features, such as generating Sudoku puzzles, providing hints, or adjusting difficulty
levels based on user preferences.
 Applicability: This makes the solver a potential starting point for more
comprehensive applications, such as mobile apps or educational software that
includes a suite of logic-based puzzles.
5. Enhancing Web Development Skills:
 Importance: Building the Sudoku solver involves working with web technologies
like HTML, CSS, and JavaScript, offering developers the opportunity to refine their
front-end development skills and gain experience in interactive web applications.
 Applicability: The skills and knowledge gained from this project are transferable to
other web development projects, especially those requiring user interactivity and
algorithm integration.
6. Real-Time Application in Digital Tools:
 Importance: Sudoku solvers can be integrated into digital tools, websites, or apps
that provide puzzle games or brain-training exercises, offering users immediate
solutions and enhancing the tool's functionality.
 Applicability: The solver can be used in a variety of applications, including mobile
games, educational platforms, and productivity tools, where users may seek
automated assistance or verification of puzzle solutions.
Role and Profile
As the developer and algorithm designer of the Sudoku solver, I took on the
responsibility of conceptualizing, designing, and implementing a system that
efficiently solves Sudoku puzzles. My work required a deep understanding of
algorithmic principles, particularly those related to constraint satisfaction problems like
Sudoku.
Key Responsibilities:
 Algorithm Design and Implementation:

I developed a robust algorithm capable of solving Sudoku puzzles efficiently.
This involved designing a backtracking algorithm and ensuring it could handle
various difficulty levels of puzzles.
 User Interface Development:
I created an intuitive and interactive user interface that allows users to input
Sudoku puzzles and receive solutions. This included writing HTML, CSS, and
JavaScript to build and style the web application.
 Code Optimization and Testing:
I ensured the algorithm was optimized for performance, minimizing the time
required to solve puzzles. I also performed thorough testing to verify the
accuracy of the solutions and the reliability of the application.
 Problem Solving and Debugging:
I addressed issues that arose during the development process, including

debugging the code and resolving logical errors in the algorithm.
Skills Applied:
 Proficiency in JavaScript: I utilized my skills in JavaScript to implement the

algorithm and handle user interactions within the web application.
 Knowledge of Algorithms: I applied my understanding of backtracking and

recursion to develop an effective solution for solving Sudoku puzzles.
 Web Development: I leveraged my experience in HTML and CSS to create a

functional and visually appealing user interface.
 Problem-Solving: I addressed challenges that arose during the development

process, optimizing the algorithm for performance and ensuring it handled all
possible inputs and edge cases.
 Attention to Detail: I ensured that the solver accurately processed a wide range
of puzzles, including edge cases.
Professional Background:
 Experience: I drew on my background in computer science and software

engineering, as well as my experience in developing web applications and
implementing algorithms.
 Interests: My work on this project reflects my interest in puzzles, problem-

solving, and applying algorithms to real-world problems.
 Tools and Technologies: I utilized web development tools and environments, as

well as version control systems, to manage and deliver this project successfully.
Design
Implementation
<html>
<head>
<title></title>
<script type="text/javascript" src="sudoku.js"></script>
<script type="text/javascript" src="analytics.js"></script>
<style type="text/css">
body { font-family: Calibri, sans-serif; }
#container { text-align: center }
table { border-collapse: collapse; font-size: 2em; margin: 0 auto; }
colgroup, tbody { border: solid medium; }
td { border: solid thin; height: 1.4em; width: 1.4em; text-align: center; padding: 0; }
button { margin-top: 15px; font-size: 1.5em; }
.padd
{padding-bottom: 100px;}
</style>
</head>
<body>
<div id="container">
<h1 class = "padd">Sudoku Solver</h1>
<table id="sudoku-board">
<colgroup><col><col><col>
<tbody>
<tr> <td contenteditable="true"></td> <td contenteditable="true"></td> <td

contenteditable="true"></td> <td contenteditable="true"></td> <td
contenteditable="true"></td>


<tbody>


<tbody>



</table>
<div>
<button id="solve-button">Solve!</button>
</div>
<div>
<button id="clear-button">Clear board</button>
</div>
</div>
</body>
<script type="text/javascript">
document.getElementById("sudoku-board").addEventListener("keyup", function(event)
{
if(event.target && event.target.nodeName == "TD") {
var validNum = /[1-9]/;
var tdEl = event.target;
if (tdEl.innerText.length > 0 && validNum.test(tdEl.innerText[0])) {
tdEl.innerText = tdEl.innerText[0];
} else {
tdEl.innerText = "";
});
document.getElementById("solve-button").addEventListener("click", function(event) {
var boardString = boardToString();
var solution = SudokuSolver.solve(boardString);
if (solution) {
stringToBoard(solution);
} else {
alert("Invalid board!");
})
document.getElementById("clear-button").addEventListener("click", clearBoard);
function clearBoard() {
var tds = document.getElementsByTagName("td");
for (var i = 0; i < tds.length; i++) {
tds[i].innerText = "";
function boardToString() {
var string = "";
if (validNum.test(tds[i].innerText[0])) {
string += tds[i].innerText;
} else {
string += "-";
return string;
function stringToBoard(string) {
var currentCell;

var cells = string.split("");
currentCell = cells.shift();
if (validNum.test(currentCell)) {
tds[i].innerText = currentCell;
</script>
</html>
Javascript file is as follows:
"use strict";
var EASY_PUZZLE = "1-58-2----9--764-52--4--819-19--73-6762-83-9-----61-5---76---

3-43--2-5-16--3-89--";
var MEDIUM_PUZZLE = "-3-5--8-45-42---1---8--9---79-8-61-3-----54---5------78-----

7-2---7-46--61-3--5--";
var HARD_PUZZLE = "8----------36------7--9-2---5---7-------457-----1---3---1----68--

85---1--9----4--";
var TESTABLE = true;
var SudokuSolver = function (testable) {

var solver;
function solve(boardString) {
var boardArray = boardString.split("");
if (boardIsInvalid(boardArray)) {
return false;
return recursiveSolve(boardString);
function solveAndPrint(boardString) {
var solvedBoard = solve(boardString);
console.log(toString(solvedBoard.split("")));
return solvedBoard;
function recursiveSolve(boardString) {
var boardArray = boardString.split("");
if (boardIsSolved(boardArray)) {
return boardArray.join("");
var cellPossibilities = getNextCellAndPossibilities(boardArray);
var nextUnsolvedCellIndex = cellPossibilities.index;
var possibilities = cellPossibilities.choices;
for (var i = 0; i < possibilities.length; i++) {
boardArray[nextUnsolvedCellIndex] = possibilities[i];
var solvedBoard = recursiveSolve(boardArray.join(""));
if (solvedBoard) {
return solvedBoard;
return false;
function boardIsInvalid(boardArray) {
return !boardIsValid(boardArray);
function boardIsValid(boardArray) {
return allRowsValid(boardArray) && allColumnsValid(boardArray) &&

allBoxesValid(boardArray);
function boardIsSolved(boardArray) {
for (var i = 0; i < boardArray.length; i++) {
if (boardArray[i] === "-") {
return false;
return true;
}
function getNextCellAndPossibilities(boardArray) {
for (var i = 0; i < boardArray.length; i++) {
if (boardArray[i] === "-") {
var existingValues = getAllIntersections(boardArray, i);
var choices = ["1", "2", "3", "4", "5", "6", "7", "8", "9"].filter(function (num)
{
return existingValues.indexOf(num) < 0;
});
return { index: i, choices: choices };
function getAllIntersections(boardArray, i) {
return getRow(boardArray, i).concat(getColumn(boardArray,

i)).concat(getBox(boardArray, i));
function allRowsValid(boardArray) {
return [0, 9, 18, 27, 36, 45, 54, 63, 72].map(function (i) {
return getRow(boardArray, i);
}).reduce(function (validity, row) {
return collectionIsValid(row) && validity;
}, true);
}
function getRow(boardArray, i) {
var startingEl = Math.floor(i / 9) * 9;
return boardArray.slice(startingEl, startingEl + 9);
function allColumnsValid(boardArray) {
return getColumn(boardArray, i);
}, true);
function getColumn(boardArray, i) {
var startingEl = Math.floor(i % 9);
return [0, 1, 2, 3, 4, 5, 6, 7, 8].map(function (num) {
return boardArray[startingEl + num * 9];
});
function allBoxesValid(boardArray) {
return getBox(boardArray, i);
}, true);
}
function getBox(boardArray, i) {
var boxCol = Math.floor(i / 3) % 3;
var boxRow = Math.floor(i / 27);
var startingIndex = boxCol * 3 + boxRow * 27;
return [0, 1, 2, 9, 10, 11, 18, 19, 20].map(function (num) {
return boardArray[startingIndex + num];
});
function collectionIsValid(collection) {
var numCounts = {};
for(var i = 0; i < collection.length; i++) {
if (collection[i] != "-") {
if (numCounts[collection[i]] === undefined) {
numCounts[collection[i]] = 1;
} else {
return false;
return true;
function toString(boardArray) {
return getRow(boardArray, i).join(" ");
}).join("\n");
if (testable) {
solver = {
solve: solve,
solveAndPrint: solveAndPrint,
recursiveSolve: recursiveSolve,
boardIsInvalid: boardIsInvalid,
boardIsValid: boardIsValid,
boardIsSolved: boardIsSolved,
getNextCellAndPossibilities: getNextCellAndPossibilities,
getAllIntersections: getAllIntersections,
allRowsValid: allRowsValid,
getRow: getRow,
allColumnsValid: allColumnsValid,
getColumn: getColumn,
allBoxesValid: allBoxesValid,
getBox: getBox,
collectionIsValid: collectionIsValid,
toString: toString };
} else {
solver = { solve: solve,

solveAndPrint: solveAndPrint };
return solver;
}(TESTABLE);
Learning Outcomes
Programming is all about data structures and algorithms. Data structures are used to hold
data while algorithms are used to solve the problem using that data.
Data structures and algorithms (DSA) goes through solutions to standard problems in
detail and gives you an insight into how efficient it is to use each one of them. It also
teaches you the science of evaluating the efficiency of an algorithm. This enables you to
choose the best of various choices.
For example, you want to search your roll number in 30000 pages of documents, for that
you have choices like Linear search, Binary search, etc.
So, the more efficient way will be Binary search for searching something in a huge number
of data. So, if you know the DSA, you can solve any problem efficiently.
GITHUB LINK :
https://github.com/aravindanaswar/SUDOKO-SOLVER.git
Bibliography
• Google
• GeeksforGeeks
• YouTube

Final Report 1

Uploaded by

Copyright:

Available Formats

Final Report 1

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Final Report 1

Uploaded by

Copyright:

Available Formats

SIX WEEKS SUMMER TRAINING REPORT

Registration No. 12205985

Program Name: B-Tech CSE

Under the Guidance of

Mr. Sandeep Jain

School of Computer Science & Engineering

Registration no: 12205985

Date: 25th Aug, 2024

Training certificate from organization

7. Importance and Applicability

An algorithm is a finite set of instructions or logic, written in order, to accomplish a

Asymptotic notations are mathematical tools to represent the time complexity

• Worst, Average and Best-Case Time Complexities

When it comes to analysing algorithms, the asymptotic analysis seems to be

Objective: The objective of this track is to familiarize the learners with

Reason for choosing this technology

it easy to understand faster as we are involved Practically.

2. It has 200+ algorithmic coding problems with video explained solutions.

3. It has track based learning and weekly assessment to test my skills.

Profile of the Problem

 Objective of the Solution:

3. Constraints and Requirements:

 Backtracking Algorithm: The primary approach used is backtracking, a depth-first

o The code should be well-documented and organized, making it easy to

4. Assumptions and Constraints:

o Users are familiar with basic Sudoku rules and conventions.

4. Foundation for Advanced Features:

 Algorithm Design and Implementation:

 User Interface Development:

 Code Optimization and Testing:

 Problem Solving and Debugging:

I addressed issues that arose during the development process, including

 Proficiency in JavaScript: I utilized my skills in JavaScript to implement the

 Knowledge of Algorithms: I applied my understanding of backtracking and

 Web Development: I leveraged my experience in HTML and CSS to create a

 Problem-Solving: I addressed challenges that arose during the development

 Experience: I drew on my background in computer science and software

 Interests: My work on this project reflects my interest in puzzles, problem-

 Tools and Technologies: I utilized web development tools and environments, as

<script type="text/javascript" src="sudoku.js"></script>

<script type="text/javascript" src="analytics.js"></script>

body { font-family: Calibri, sans-serif; }

#container { text-align: center }

table { border-collapse: collapse; font-size: 2em; margin: 0 auto; }

colgroup, tbody { border: solid medium; }

button { margin-top: 15px; font-size: 1.5em; }

<h1 class = "padd">Sudoku Solver</h1>

<tr> <td contenteditable="true"></td> <td contenteditable="true"></td> <td

<tr> <td contenteditable="true"></td> <td contenteditable="true"></td> <td

<tr> <td contenteditable="true"></td> <td contenteditable="true"></td> <td

<tr> <td contenteditable="true"></td> <td contenteditable="true"></td> <td

<tr> <td contenteditable="true"></td> <td contenteditable="true"></td> <td

<tr> <td contenteditable="true"></td> <td contenteditable="true"></td> <td

<tr> <td contenteditable="true"></td> <td contenteditable="true"></td> <td

<tr> <td contenteditable="true"></td> <td contenteditable="true"></td> <td

<button id="clear-button">Clear board</button>

if(event.target && event.target.nodeName == "TD") {

var validNum = /[1-9]/;

var tdEl = event.target;