Implement A Sudoku Solver - Sudoku Solving Backtracking Algorithm ("Sudoku Solver" on LeetCode)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
Question: Implement a Sudoku solver. (a classic Sudoku board is 9x9)
The Rules of Sudoku:
We are working with numbers 1 thorugh 9.
Each number can only appear once in a:
Row
Column
And one of the 3 x 3 subboxes
Approach 1 (Brute Force)
Try every possible assignment to empty entries and then at the end validate if the sudoku board is valid or not.
With no constraints, given a 9x9 board we have at max 81 spaces where in each space we can place the number 1-9 (but on a normal board many spaces will already have a number before we even start solving)
This means that there are 9^81 total arrangements of the board (as a loose upper bound). This is 1.9662705 * 10 ^ 77 boards just for a 9 x 9 board.
This would take too long.
Approach 2 (Apply The Constraints)
The backtracking approach.
We can traverse and place an entry in empty cells one by one.
We then check the whole board to see if it is still valid.
If it is we continue our recursion.
If it is not we do not even follow that path.
When all entries have been filled, we are finished.
The 3 Keys To Backtracking:
Our Choice
What we place in an empty cell that we see.
Our Constraints
Standard Sudoku constraints. We cannot make a placement that will break the board.
Our Goal
Place all empty spaces on the board. We will know we have done this when we have placed a valid value in the last cell in our search which programmatically will be the bottom right cell in the 2D matrix.
Validating Placements Before We Place Them
INSIGHT: We could traverse every row, column, and 3x3 subgrid to perform validation but at every decision point we know that we are adding onto a grid that is already valid.
So we just check the row, column, and subgrid of the item that has been added.
Whenever backtracking we know that every decision that we made stayed within the constraint that we started with being that the board was valid.
Complexities
Since Sudoku is traditionally 9x9 we can't really discuss complexities because nothing can scale.
Solving Sudoku generalized to n x n boards is a NP-Complete problem so we know for sure that our time complexity is exponential at the very least.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 16.9 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Видео Implement A Sudoku Solver - Sudoku Solving Backtracking Algorithm ("Sudoku Solver" on LeetCode) канала Back To Back SWE
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
Question: Implement a Sudoku solver. (a classic Sudoku board is 9x9)
The Rules of Sudoku:
We are working with numbers 1 thorugh 9.
Each number can only appear once in a:
Row
Column
And one of the 3 x 3 subboxes
Approach 1 (Brute Force)
Try every possible assignment to empty entries and then at the end validate if the sudoku board is valid or not.
With no constraints, given a 9x9 board we have at max 81 spaces where in each space we can place the number 1-9 (but on a normal board many spaces will already have a number before we even start solving)
This means that there are 9^81 total arrangements of the board (as a loose upper bound). This is 1.9662705 * 10 ^ 77 boards just for a 9 x 9 board.
This would take too long.
Approach 2 (Apply The Constraints)
The backtracking approach.
We can traverse and place an entry in empty cells one by one.
We then check the whole board to see if it is still valid.
If it is we continue our recursion.
If it is not we do not even follow that path.
When all entries have been filled, we are finished.
The 3 Keys To Backtracking:
Our Choice
What we place in an empty cell that we see.
Our Constraints
Standard Sudoku constraints. We cannot make a placement that will break the board.
Our Goal
Place all empty spaces on the board. We will know we have done this when we have placed a valid value in the last cell in our search which programmatically will be the bottom right cell in the 2D matrix.
Validating Placements Before We Place Them
INSIGHT: We could traverse every row, column, and 3x3 subgrid to perform validation but at every decision point we know that we are adding onto a grid that is already valid.
So we just check the row, column, and subgrid of the item that has been added.
Whenever backtracking we know that every decision that we made stayed within the constraint that we started with being that the board was valid.
Complexities
Since Sudoku is traditionally 9x9 we can't really discuss complexities because nothing can scale.
Solving Sudoku generalized to n x n boards is a NP-Complete problem so we know for sure that our time complexity is exponential at the very least.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 16.9 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Видео Implement A Sudoku Solver - Sudoku Solving Backtracking Algorithm ("Sudoku Solver" on LeetCode) канала Back To Back SWE
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Create a Sudoku Solver In Java In 20 Minutes - Full TutorialThe N Queens Placement Problem Clear Explanation (Backtracking/Recursion)How To Do Hard Sudokus In 10 MinutesPython Sudoku Solver Tutorial with Backtracking p.16 Introduction to Backtracking - Brute Force ApproachHow to Solve Sudoku using Backtracking | RecursionValid Sudoku - Amazon Interview Question - Leetcode 36 - PythonThe Quicksort Sorting Algorithm: Pick A Pivot, Partition, & RecurseThe Sudoku Trick All Expert Solvers KnowDeeply Understanding Logarithms In Time Complexities & Their Role In Computer SciencePython Sudoku Solver - ComputerphileImplement An LRU Cache - The LRU Cache Eviction Policy ("LRU Cache" on LeetCode)L15. Sudoko Solver | BacktrackingCoding a Sudoku solver in Python using recursion/backtrackingPuzzle 8: You Won't Want to Play Sudoku AgainThe 10 Most Important Concepts For Coding Interviews (algorithms and data structures)C++ Sudoku Solver in 7 minutes using Recursive BacktrackingThe Backtracking Blueprint: The Legendary 3 Keys To Backtracking Algorithms6.1 N Queens Problem using Backtracking