Implement A Sudoku Solver - Sudoku Solving Backtracking Algorithm ("Sudoku Solver" on LeetCode)

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
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: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 16.9 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

[@BackToBackSWE]

Table of Contents: The Problem Introduction 0:00 - 0:44 More Information On The Problem 0:44 - 1:52 The Brute Force Approach (Complete Search) 1:52 - 3:09 The Backtracking Approach (3 Keys To Backtracking) 3:09 - 3:30 Our Choice 3:30 - 4:18 Our Constraints 4:18 - 6:28 Our Goal 6:28 - 7:41 Time & Space Complexity 7:41 - 9:11 Conclusion 9:11 - 9:34 The code for this problem is in the description (with many comments for teaching purposes).

[@raghavkakar8092]

Where is the code in the desc?

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@farahalaa2362]

Hello, why the filling in empty spaces is row by row ?

[@ostapo2888]

​@@raghavkakar8092 here is the simplest solution using the approach from the video if you really need it - github.com/orishko-py/codewars/blob/master/sudoku-solver.py

[@tanaygupta632]

Where the fuck is code in description?

[@lilzjay9732]

Hey bro, you are not yelling. I can feel a strong passion from your voice!

[@BackToBackSWE]

Nah...I'm yelling haha

[@aayushsharma1452]

@@BackToBackSWE no you are not

[@bisann2441]

thank u so much!! but where's the code exactly?

[@johnskeff9617]

Where is the code?? There is NO code in the description!

[@xinzhang5877]

very clear to illustrate the hard part of this problem. Great job man, you deserve more subs, and keep going!

[@BackToBackSWE]

thx

[@sobowaleolamide4177]

Nice solution. I followed your approach but I did a bit of an update on it. Instead of checking everytime if a character can be placed in row or column or region at O(n^2) runtime, you can do that in constant time by saving keeping track of the content of each region, each row, and each column, then you can backtrack on it. after trying any character.

[@BackToBackSWE]

nice

[@anshulabhinav13]

I was hoping you would do a dry run on the example input board, just like you do for most of your other videos. That really helps in firming the understanding, more than the code.

[@BackToBackSWE]

yeah

[@vibhoresrivastava6087]

Great explanation. I've checked out a lot of your videos past few days. You are doing a great job. Wish my algorithms professor was like this.

[@BackToBackSWE]

thanks

[@algorithmimplementer415]

If you keep this up, as you started at the very young age at college, I am sure you will go very far. :)

[@BackToBackSWE]

I will haha, this is the next launch twitter.com/thebigoguide, then I'll be back to tend to this channel

[@shuaisun1831]

I love your videos. They are very helpful and you explain each problem clearly. Thanks

[@BackToBackSWE]

I love u

[@somerandomguy000]

I actually prefer the yelling and passionate approach. You’re the best!

[@alzaeem79]

Thanks a lot man, you're helping tons of people. Hope you have a great day

[@shivankchaturvedi4817]

U aren't yelling this shows ur passion towards the problem don't change the tone

[@BackToBackSWE]

thanks haha

[@ankuragarwal4014]

Excellent Explanation and it can be easily seen , the amount of effort you have done thanks a lot for this video

[@BackToBackSWE]

sure

[@aidandanielski]

I love your video. It's one half Sudoku tutorial and one half inspirational speech. Backtracking can solve many problems.

[@BackToBackSWE]

lmao, old video, apologies

[@aidandanielski]

@@BackToBackSWE Quality trumps age. (You know what I mean...) ;)

[@xiuwenzhong7375]

cannot believe it, I first search Sudoku Solver in youtube, I did not found your video. Then I watch other guys video which make me confused but I saw a leetcode link under that video comments. Then in the leetcode discuss, I saw your video link, that's how I found it.

[@BackToBackSWE]

hahahahahaha, yeah, this channel is new and KZbin thinks it sucks ass

[@Maen963]

U R A LEGEND ! KEEP IT UP 💪

[@BackToBackSWE]

no u

[@muj99ali]

I got this same question in an interview, and the problem I faced was in checking if placing an element breaks a sub grid or not (It's relatively easy to check rows and columns). I believe that's the only important thing missing in this video. Otherwise I'm a huge fan of your channel ❤️

[@BackToBackSWE]

thx

[@ptronic]

It's not hard if row between 1 and 3 and column between 1 and 3 subsection 1 etc

[@prakhargupta7125]

bro you deserve million views and subscribers.thnk u!!

[@BackToBackSWE]

haha thanks

[@lizziedaffofil6064]

Loved it more when you are loud:) such energy is contagious!

[@umber3117]

Thanks for the great explanation and clean code.You made my day.

[@BackToBackSWE]

nah, you made my day for watching

[@sahiljindal3202]

Mr. Nobody provide code to me too

[@steelcube]

What happen when the program has picked a number for a cell and later needs to change it due to other cells constrains? I mean it could be valid at the time it picks a number but may need to be changed later?

[@BackToBackSWE]

Yes, if that is the case that choice will take us down a path that will hit a "dead end". We will backtrack to the same decision point and make the next decision from that same cell into a new path of exploration.

[@matejriha4128]

@@BackToBackSWE How do I locate the number which caused the problem?

[@JH-dg9kl]

I don't understand whats all the dislike..what amazing explanation. he basically told you the approach. the coding part is easy. the check if can place part is basically the previous question ValidSudoku. I actually prefer this kind tutorial rather that just given me the code upfront.

[@BackToBackSWE]

Hahah, the video's quality is kinda bad.

[@airysm]

Hey thanks for the vid! I was looking over the code and the comments really help make everything clear but the one thing I didn’t get was in the valid char placement method when you check if its a valid placement in the region, the formula for int I,J and topLeftOfRow,Col how did you derive those?

[@BackToBackSWE]

int regionSize = (int) Math.sqrt(board.length); // gives us the size of a sub-box In a 9 x 9 board, we will have 9 sub boxes (3 rows of 3 sub-boxes). int I = row / regionSize; int J = col / regionSize; The "I" tells us that we are in the Ith sub-box row. (there are 3 sub-box rows) The "J" tells us that we are in the Jth sub-box column. (there are 3 sub-box columns) Integer properties will truncate the decimal place so we just know the sub-box number we are in. int topLeftOfBlockRow = regionSize * I; // the row of the top left of the block int topLeftOfBlockCol = regionSize * J; // the column of the tol left of the block That multiplication takes us to the EXACT top left of the sub-box. We keep the (row, col) of these values because it is important. It lets us traverse the sub-box with our double for loop. Each coordinate we touch will be found by an offset from topLeftOfBlockRow and topLeftOfBlockCol. For 20 minutes I debated what to name these things and I literally couldn't think of a very clear name so left them alone. The fact you had to ask this means the code is too opaque. It is my fault and I will rename things to make things more clear.

[@airysm]

Back To Back SWE no worries! Thanks for the explanation

[@mihailovasic4623]

Hey mate, love your videos, but I have a question about the line 35: board[row][col] = EMPTY_ENTRY; why does it work with it and why doesn't it work without it? I mean, you set a value for a cell, and then you set it to EMPTY_ENTRY, why?

[@BackToBackSWE]

Imagine what is really happening. It doesn't matter if clear it or not. The cell gets overwritten.

[@samwenda3261]

Thanks for the video, it's good explanation. Can you make a video about 8 puzzle problems using backtracking, I really hope for it?

[@BackToBackSWE]

maybe? Technically I can only directly make videos requested by patrons but I'll consider it. (if someone sees this comment in 1-3 years and the Patreon doesn't exist ignore this)

[@beteltadesse9803]

Great Explanation! Thank you Brother!

[@anushkachakraborty8635]

This is the third succesful classic algorithm I learnt from you. Absolutely love your way of teaching ^_^

[@BackToBackSWE]

great and thanks

[@CodingWithPrakash_]

kzbin.info/www/bejne/qHucf3mBbtiSo6s Valid Suduko (Explained like a champ)

[@roshanpandey5357]

It's always safe to like your video at the very start.

[@BackToBackSWE]

lol

[@mallikarjunpidaparthi]

Wow.. brother thank you... You made this really easy

[@BackToBackSWE]

sure

[@ImpactfulEASON]

Nice explanation, I find easier to understand the reasoning behind the approach

[@BackToBackSWE]

nice

[@gurtagel]

One question I have is how we can figure out which valid value to use. For example, when we are looking at the second blank spot, you put a 2 there and proceed with the assumption that it is valid. However, how did you know that the second blank could not be a 6 instead. There are no 6's in that row, column, or sub-matrix?

[@BackToBackSWE]

When I place the 2 I just randomly choose that number, no methodology behind it. Check out the code in the description. What really happens is that we try numbers 1 to 9 using a for loop and if a placement ends up not working we backtrack and remove it from the board.

[@MuhammadFarooq-wi7vl]

Such a simpler and great explaination....and u are not yelling man😆....thanks it was very helpful...👍

[@BackToBackSWE]

thanks, ok, and great

[@practice8844]

your explanation is best ,best teacher ever

[@BackToBackSWE]

thx

[@andresabello5639]

yeees, I am not a better person but I love your energy and now I know how to solve and that makes me a better engineer. Thank you! And please don't change your style.

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@ranjeetgaikwad4786]

thank you very much sir, very helpful

[@gowrivinaykamalakars7818]

Thanks for your wonderful explanation sir..

[@yashmistry61]

Thank you guys this video helped me in my assignment Thank you again Where are you from guys?

[@BackToBackSWE]

maryland usa

[@joshstafford9353]

When did you actually explain backtracking though...

[@BackToBackSWE]

dont remeber this vid

[@sharpnova2]

he didn't at all. kind of weird. i clearly see how to solve this problem from what he did say but only because of my background

[@awsomecrossing]

What if in the middle of the grid validation check fails? What do you do then?

[@subratrai1146]

love you man!!

[@BackToBackSWE]

u 2

[@vanyastaleva415]

Hmmm, am I the only one who can't find the code? He said that in the description box there is a link to the code

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@SunFoxPL1]

@@BackToBackSWE So if we want to see the code we need to pay? That's... really ugly. I mean it's really ugly marketing move.

[@mangekostorm9211]

@@SunFoxPL1 It's still on his github though it is no longer maintained. The solution is also available on a variety of other websites. It makes sense that you should pay for new content (and it's much cheaper compared to other coding schools) since he is taking so much time to prepare and constantly update the materials when he could be working a SWE job and making a SWE salary. We should be thankful that he still has his original videos up.

[@SunFoxPL1]

@@mangekostorm9211 Oh I don't mind him getting money for what he is doing, just the fact that he posts video on youtube which is just half done (there is no code, and when someone asks about the code he just says that you need to go to the webpage and pay) is very unprofessional.

[@prinzuchoudhury6920]

github.com/bephrem1/backtobackswe/blob/master/Dynamic%20Programming%2C%20Recursion%2C%20%26%20Backtracking/SudokuSolver/SudokuSolver.java

[@VinaySachdevaK-EE-]

Great Video, Was just wondering where is the code...

[@BackToBackSWE]

thanks and the repository is deprecated - we only maintain backtobackswe.com now.

[@0saptarshi]

Hi Sri,I couldnt find your code in the description below.

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@willturner3440]

I am addicted to your teaching style, I can watch your lecture whole day 😄

[@abhyasood4198]

absolutely love the way you explain everything... has helped me a lot.

[@BackToBackSWE]

great!

[@vishaldobariya]

Why you have two 9s in ROW number 3? Is that correct?

[@rajakumar-eg7dl]

How i can apply vanilla backtracking on this problem for at-least 10 iterations

[@BackToBackSWE]

not sure

[@eltonli8458]

Great! Thank you!

[@BackToBackSWE]

glad it helped

[@mohamedarshathn7768]

Thanks for leetcode discuss 😇. Finally, found a great channel.

[@BackToBackSWE]

hahaha

[@salmankhurshid4410]

Nice video and great explanation. I have brought our course but all videos are not there, what I meant is that some videos that are there on youtube are not in the course. why so?

[@BackToBackSWE]

Hi! The intention is that some videos here are lower quality and don't explain the problem how I see it best explained. Also bad gear like microphone kept some videos out of the service as well tabled for a reshoot.

[@rishabkumar4940]

Man you are amazing!!

[@BackToBackSWE]

thanks - im normal

[@CodingWithPrakash_]

kzbin.info/www/bejne/qHucf3mBbtiSo6s Valid Suduko (Explained like a champ)

[@charlesliu1439]

Very clear.

[@swatirauniyar9062]

In the description box above I can't find the link of your code.

[@BackToBackSWE]

The repository is deprecated and we only maintain backtobackswe.com now.

[@NeerajSharma-oz1mm]

Bro.. Please be loud Excited teacher is effective teacher. :)

[@sankarprasadpanda9431]

Where i can find the code!! Not finding in description.

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com

[@interviewprep6259]

This is brilliant. Thank you!

[@BackToBackSWE]

sure

[@ASASAN]

1:04 Double "Our Choice" on screen ? :))

[@BackToBackSWE]

OOPSIE!

[@lomeshdaheria9960]

Can someone tell me where is the code I can't find it in the description

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@xxbighotshotxx]

Awesome explanation. Backtracking makes sense now. Thank you

[@BackToBackSWE]

great

[@farahalaa2362]

Hello, why filling in empty spaces is row by row ?

[@BackToBackSWE]

wym

[@kaushiquedhrubo908]

how do you learn all these difficult algos for yourself.....

[@BackToBackSWE]

I'm a student and I just use the internets.

[@amirtv106]

Reading

[@dbldzo]

Hey man, this was probably the best coding explanation, so glad I've found this video because I have the same problem waiting to be solved. The only difference is that the given board (also 9x9) is completely empty, no placement of any number whatsoever. Is there any change in the "choice" part? P.S. The code is not here anymore, any information on that? P.P.S. Keep it up, don't stop whatever you are doing!

[@BackToBackSWE]

Is there any change in the "choice" part? No P.S. The code is not here anymore, any information on that? The repository is deprecated - we only maintain backtobackswe.com. P.P.S. Keep it up, don't stop whatever you are doing! Thanks.

[@newtonpermetersquared]

@@BackToBackSWE It would be helpful if you put note about the deprecated repo in the description. But thanks for the video though 👌🏾

[@chetthejet3896]

Being you answered all of the questions asked of you, I would like to know if I use a blank board how many different puzzles can I create? Your video is far beyond my comprehension so I will not say you are a poor teacher, but you are the first person to answer all of the questions on your site. I asked a relative that question (he had a doctors degree in math) and he did not or could not answer my question. I enjoy the puzzles but not as a math problem. For me that takes the fun out of the hobby.

[@BackToBackSWE]

How many different sudoku boards? Well, that's hard. The total invalid boards is 9*9*9*9*9*9*9*9*9*9*9...basically n^n which is 9^9 which is 387,420,489 boards. Valid boards? That is harder to count.

[@chetthejet3896]

​@@BackToBackSWE Thank you Bro. I figured you would give me a good answer.

[@BackToBackSWE]

@@chetthejet3896 lol, I try

[@karljay7473]

One of the problems I'd have with this is that the 1 at the start might not be the correct answer. The first empty cell could be 1,2 or 4. You don't know which it will be until you solved a certain number of the rest of the puzzle. I'm guessing the code keeps passing thru, but while you're there you could just find ALL the answers the position could be before you move on. I get that 1 has a 1 in 3 chance of being correct, but I'm not sure if that's the best approach.

[@BackToBackSWE]

The backtracking does that right? Makes a choice, goes deep into it, comes back if infeasible.

[@karljay7473]

@@BackToBackSWE I haven't written any code for Sudoku puzzles, but it seems that having info on what a given cell can and can't be, helps to eliminate other paths so that you don't have to do a full check. In other words, knowing that a given cell can only be 1,2,4 you can use that knowledge to reduce the number of checks in the 3 sections (horizontal, vertical, 3x3 local grid). That should narrow down what the other one can be. I'd have to run thru your code, but seems like it's not taking advantage of complete knowledge of all paths. In other words, if you have 6 paths and you reduce that to 3 paths, you cut the amount of time needed to find the final solution. Much like the "find the hidden word" puzzle. If you see "Applz" you don't have to check it again, you know it's not a word, it can't make a word, you can mark that branch as a dead end branch using DP. I'd have to write the code to see if it's any better or doing the same thing.

[@rathan235]

Good job, but where's the code?

[@yicai7]

Feel like a backtracking pro

[@kristianusifoh9307]

Hey bro thank you for your video. I couldn't get the code to look at how it was implemented

[@BackToBackSWE]

It is on my github but the repsoitory is deprecated

[@kristianusifoh9307]

Back To Back SWE ok thank you.

[@caretakerrandom8818]

where is the code??????????

[@BackToBackSWE]

depdeceted repo, no longer used

[@littlboz]

This video is much better. I like the toned down style. Good job.

[@BackToBackSWE]

I like toned down too :)

[@azadalishah2966]

Where is the code link? I don’t see in description

[@BackToBackSWE]

Hi, the repository is deprecated - we only maintain backtobackswe.com now

[@cleolin5679]

Where can I find the code?

[@masc0648]

Can some one point we to the link of the code ?

[@lomeshdaheria9960]

Thank you 😊😊😊 ben

[@BackToBackSWE]

sure

[@bru9jat]

Where is the link to the code?

[@BackToBackSWE]

The respository is deprecated - we only maintain backtobackswe.com

[@Neo_Nkosi]

I can't see the coded solution in your description😢

[@ayyubshaffy3612]

yo I dont see the code in the description anyways nice video :)

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now. and thx

[@aiman1562]

@@BackToBackSWE how can i get the code if that's possible?

[@tejenderjeetsohi2128]

Where is the code?

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com

[@adamr-personal8035]

Is this solution supposed to be working for any Sudoku Grid?

[@adamr-personal8035]

Besides that - this is great channel - I am just preparing for the coding interview at Facebook, as a VR dev- and you're helping me a lot! Thanks!!!

[@BackToBackSWE]

Yes, it can easily be generalized to any Sudoku grid (forgot the exact dimensions though).

[@BackToBackSWE]

Nice, sure no problem.

[@tomeve4823]

Sorry i cant find your code could u give me the link to the code please？thank you ！

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@sharpnova2]

@@BackToBackSWE fuck you.

[@vaishnavism5110]

um hey where is the code??

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@SC2BuildOrder]

i love this man so goddamn much holy shit

[@BackToBackSWE]

no u

[@sharpnova2]

why? he left out the most important part of the algorithm and then pulled the code. he's trash.

[@sakshigupta9111]

where is the code for this problem??

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now

[@prinzuchoudhury6920]

github.com/bephrem1/backtobackswe/blob/master/Dynamic%20Programming%2C%20Recursion%2C%20%26%20Backtracking/SudokuSolver/SudokuSolver.java

[@MegaWindow8]

Code in the description?

[@user-sm1xs2ww9m]

3:50 row, column traversal 4:40 we cannot break the board (dont do an n^2 check) 6:30 how do i know im finished

[@jayavardhan430]

Excuse me anyone please tell me where is the code

[@Official_Southpaw]

Can you be my Algorithms professor? Lol great video! I can get my assignment done and sleep now.

[@BackToBackSWE]

I would be a professor if I had the interest but I think in this lifetime I probably won't be one.

[@bishwhat6554]

why am i watching this im still doing intro c++ lol

[@BackToBackSWE]

hahahahahahahaha no idea

[@bishwhat6554]

@@BackToBackSWE if you had to guess, what year of computing science is this?

[@BackToBackSWE]

@@bishwhat6554 I understand the intent of this question but I don't think it has an answer. It is...any year? You'd just understand this when you understand it? A 10 year old could understand this if they had proper precontext....it just happens that age brings such precontext.

[@sophiehall38]

I don't think you are yelling either. Good job

[@BackToBackSWE]

aw

[@devalmodi5350]

where is the code?

[@BackToBackSWE]

The repository is deprecated, it is on my github but no longer maintained

[@jibxjib]

I love you so much

[@BackToBackSWE]

thx

[@sameerranjan2039]

inspiring ! (you compelled me to comment :)

[@BackToBackSWE]

nice

[@yashsrivastava9541]

I could not find the code.please help

[@BackToBackSWE]

THe repository is deprecated but stil on my gituhb

[@hakoHiyo271]

I was interested in hearing about backtracking part which is not there in this video.

[@ranajitmukherjee9789]

Can u please provide the code?

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@venvanman]

co-pilot sent me here for some reason lmaoooo

[@navyananjala5012]

Can u have a code for tentaizu game

[@BackToBackSWE]

yes and yes

[@kabooby0]

Go back to yelling please : ) Now - what about an algo which traverses every square and adds in the correct number only for those squares which have 1 possible entry. That loop runs continuously on the same grid until it stops making additions to the grid. At this point the grid is either solved or we use the recursive backtracking algorithm to produce the solved grid(s). Would doing that be faster?

[@BackToBackSWE]

Ok. and not sure, that is an idea. it could come to a lock where no cells are single possibility so you'd have to prove the algorithm terminates.

[@kvantro7909]

I can't find the codeee

[@navyananjala5012]

Can u have a code for tenutio game

[@BackToBackSWE]

yes