C++ Sudoku Solver in 7 minutes using Recursive Backtracking

C++ implementation of a Sudoku solver.
We use a recursive backtracking algorithm and the bitset data structure.
― mCoding with James Murphy (mcoding.io)
Source code: github.com/mCo...
SUPPORT ME ⭐
---------------------------------------------------
Patreon: / mcoding
Paypal: www.paypal.com...
Other donations: mcoding.io/donate
BE ACTIVE IN MY COMMUNITY 😄
---------------------------------------------------
Discord: / discord
Github: github.com/mCo...
Reddit: / mcoding
Facebook: / james.mcoding

[@luziferius3687]

“Slap that like button an odd number of times.”. Nice! 😂

[@Swedishnbkongu]

if you click dislike though, it unlikes, so that strategy is not enough!

[@A1rPun]

@@Swedishnbkongu he didn't ask for a dislike though.

[@Swedishnbkongu]

@@A1rPun he said to slap like but didn't say not to slap dislike, so slapping like an odd number of times does not guarantee i leave with a like on the video

[@hamhampangpang_customer]

@@Swedishnbkongu he also didn't said not to not slap dislike so a win

[@dimaryk11]

@@Swedishnbkongu The two actions revert each other. The desired and implied result of the statement is to like the video, hitting dislike won't achieve the like state, thus you're not supposed to

[@Bananaa511]

This was very close to a Java programming assignment at my university, going back and looking at the problem again feels refreshing. At the time I remember looking at some bit operations that had optimised peoples algorithms quite heavily and I brushed it off as too complicated for me at the time haha. Really helpful video.

[@mCoding]

Welcome!

[@gravysnake78]

you know there a good programmer when you can see eyebags

[@Zack_Taylor]

they're

[@Zack_Taylor]

or maybe "there's"?

[@WysockiD]

This channel is about to 10x, grateful to have found you early. youtube algo is on your side, ride this momentum and pump out the quality content, all the best man.

[@mCoding]

Much appreciated!

[@nicke20686]

Took me 2 min to realize I wasn't looking at Python and was wondering why none it looked right to me..

[@mCoding]

I use many languages! Even if you dont know c++ the ideas are still clear!

[@nicke20686]

@@mCoding yep I could follow it pretty easily was just thrown off by the syntax for a while

[@cipherxen2]

@@nicke20686 usually python's syntax throws me off

[@egehurturk6209]

This channel is 🔥

[@mCoding]

This CHANNEL's on FIYAAAA

[@primeprover]

Would love to see a video showing the construction of a solver for a 16x16 sudoku. A little more thought is needed as brute force recursion is too slow.

[@xenicat]

I was surprised that this performed pretty good I would have expected brute force to be to slow even for 9x9. For 16x16 it might be enough to not start guessing with the first empty space and instead go through all spaces first and check how many possibilities are left and then make a guess for the space with the least.

[@primeprover]

@@xenicat I think this is because incorrect guesses generally provide a wrong solution very quickly. This happens less in a 16x16 sudoku.

[@Julian-vi4vl]

Nice, I wrote a similar sudoku solver a couple days ago and its a really fun problem would recommend it to others.

[@mCoding]

It was surprisingly fun after I remembered that bitset exists!

[@vorpal22]

For a much more efficient (but programmer time consuming) approach to solving Sudoku using backtracking, look up Donald Knuth's DLX (dancing links) algorithm. It's a really interesting algorithm that can be used to solve a number of puzzles, and uses a linked "grid." I'm addicted to solving Sudoku (just not by hand, but algorithmically)... constraint programming is another fun one to try: choco-solver in Java is a great library and it gives you a very nice taste of how constraint programming works, which is something that you could find useful in your code.

[@john_critchley]

Hm... I wrote a sudoku solver over Christmas... took me just less than 3 weeks... but I did do it in Z80 assembler; I was thinking of adding a similar bitmap mechanism across rows, columns and "blocks" but there are only 8 bits in the byte, so that would make doing 9 fiddly ... and I didn't bother doing further work on it as just checking across the locations was fast enough. I generate a lookup table for the cells in the "block" which are not covered by the row and column checks, so it only needs to check 4 cells per block. It now runs on a Z80 emulator _and_ on a RC2014 (real Z80 based retrocomputer). Perhaps I should do a video on how I wrote it.

[@TheJaguar1983]

When I did this for Codingame, I used a hybrid approach: use rules to solve until you can't, then choose a possible number to insert into a blank and use rules until it solves or breaks.

[@etmax1]

finally someone who indents and brackets properly 👍

[@Kornchipzzz]

Subbed. Excited to see where this channel will go!

[@mCoding]

Much appreciated!

[@MatheusAugustoGames]

Very nice! I once used the same concept to solve the eight queens puzzle, it was very entertaining! I might try doing it in C++ now that I know bitsets are a thing :P

[@mCoding]

Go for it!

[@JustinRiedyk]

Took me a second to work out why the Python code looked so bananas.

[@mCoding]

I have done this too! :) Cheers

[@irapk79]

@@mCoding can you make a video for python version too ?

[@kasparpoland9803]

this a great video. youtube knows it too bc i watched it when it dropped but it just got recommended it to me again.

[@kylefluto5384]

James, could you do a video showing a formal proof and (hopefully) the intuition behind detecting the start of a cycle in a singly-linked list?

[@qnn130]

Amazing video, your coding style is so clean!

[@cameronguilbeau5888]

Really enjoy this content, keep it up.

[@lukerichards22]

I slapped the like button 88 mod 9 times for you.

[@JohnZakaria]

How about solving it as an integer optimization problem using pulp. There is a medium article about it. It uses the same one hot encoding idea like yours. Then it solves the problem using the simplex algorithm.

[@mCoding]

Cool idea!

[@Tedisdeaad]

A demonstration on a board would have been helpful. Putting a number in that isn't currently contradicting the board state does not work on it's own. Surely you can't recursively undo that over and over in such short time?

[@mCoding]

"Putting a number in that isn't currently contradicting the board state does not work on it's own" Actually it does! Computing what would be the best place to recurse takes time, so sometimes it's ok to just recurse as fast as possible. Also bitsets give an insane speedup here!

[@usharma1624]

Great video! As always.

[@mCoding]

Thank you! Cheers!

[@abdullahkarolia3418]

Heyyy, I actually reaaaaally hope I can get a response to this🤞🏻. Firstly, I ABSOLUTELY LOVED THIS VIDEO, and your channel in general is amazing! I've actually tinkered a little with the code to make it work my use case, and it works brilliantly for a 9x9, but do you have any tips for modifying it for a 16x16 grid (currently I'm sitting at abt a 10min solve time), I'm fairly new to coding in general, but I'm a quick study, so even a nudge in the right direction will be higgghhly appreciated

[@mCoding]

Definitely! For a larger board size be smart about the recursion order. Instead of just blindly recursing left to right top to bottom, compute the square that has the least remaining possibilities and recurse on that one.

[@abdullahkarolia3418]

That helps a tonne! Thank you

[@rayhaanhanslod4792]

@@abdullahkarolia3418 dont lie you lazy to code it lmao

[@BboyKeny]

LeetCode sounds like fun

[@mCoding]

Sometimes yes, sometimes noooooo.

[@vishrutbansal2535]

I get that this might be out of the scope of your channel but I'm new to both Python and your channel so I'm asking: How about some beginner concepts? Anything that you found tricky when you started coding should qualify! Thanks :)

[@mCoding]

How beginner are we talking? Many of my earlier vids are primarily for beginners, excluding leetcode problems.

[@vishrutbansal2535]

@@mCoding They really are, I've been binging and I love them though I must say a few are beyond my level still. Which is to be expected, I've only been at this for a week. And it's the kind of stuff I haven't seen covered elsewhere so I really appreciate it. I suppose I'm mostly curious what caused you pain when you first started. The justification I'm going to go with for why you should spend your time re-thinking basics when you've done it once already is that COVID seems to be reappearing and as we go back into lockdowns, more people may turn to coding for the first time and python is among the top choices for beginners. Either way, I'm looking forward to learning more so I can fully utilise the knowledge you share. Thanks a bunch.

[@ikositetrachoir958]

I made a sudoku generator and cut the cells is hardest sh. Now, I tried to reverse your algorithm

[@syndicatedpuzzles]

Not 100% sure why you need to reset the digit when backing out of the recursion. Since you're passing everything in through the main function the stack will make copies. Previous ones will be untouched. Unless that's not how the stack works in this implementation.

[@BradenBest]

"slap that like button an odd number of times" _slaps the like button 2^32-1 times resulting in youtube rate-limiting and ultimately "losing" the like, trying to compensate and somehow ending up with a like count in the negative billions, whole site breaks and goes down for 8 hours again_

[@mCoding]

I still appreciate the attempt :)

[@MrWabouz]

Your youtube channel is awesome!

[@mCoding]

Thanks! 😃

[@jacasch3164]

would it be faster if you always evaluate the empty field which has the lowest entropy? (the one where the least ampunt of digits are possible)

[@mCoding]

That would involve computing the lowest entropy field at each step, so I'm not sure. There is probably some balance where this wins.

[@yehoshuas.6917]

Huh, I originally thought this question would be much harder since I'm pretty familiar at playing sudoku. A human playing sudoku basically does the OPPOSITE of this algorithm; guess and check takes way too long in my experience (humans kinda suck at backtracking). Instead we use elimination tactics, finding a specific part we know the answer to, filling it in, and then recursing on the new board (we're very good at pattern recognition, so the search is shorter than a computer probably). I figured this would be faster for a computer to do as well, since you're limiting the amount of future possibilities by guessing right from the start. I suppose the trade-off is that with guess-and-check you don't have to spend all that time trying to find which space is knowable, but you have more future possibilities. What I hadn't considered originally as a plus for guess-and-check is that the future paths aren't nearly as long as you might think. After trying some guess-and-check in actual play, I found that wrong guesses become impossible pretty quickly (especially if you're going to guess in order row by row, and then column by column). This is probably because there's a lot of interdependence in Sudoku, having to match row, column, and box. Great video, will definitely be giving it another go.

[@mCoding]

Thanks! It reminds me of this lecture from R. Feynman about how computers are excel at being dumb but very fast. kzbin.info/www/bejne/e3y6eHp6jcpog6M

[@yehoshuas.6917]

@@mCoding What a great lecture! The man is hilarious

[@lupomikti]

Had this as an assignment but in Prolog. I remember how the goal was just to program the brute force method and make sure it could solve hard ones in less than 5 minutes, but we could earn extra points if I made it more efficient with heuristics and movement through the board. Everyone was so shocked when I presented my solution and said it could solve all 5 of the given boards in less than a second haha xD Was the most fun assignment I had at uni.

[@mCoding]

Nice!

[@ivand8393]

How about to code it in Python ? :-) ... Probably it will be faster (the codding, not the execution)?

[@mCoding]

Would be similar,, pretty straightforward to translate, except bitset -> set

[@shmydo-derp8006]

That new mic is crispy

[@mCoding]

Like bacon or like sunburn?

[@johnydl]

I recently coded my own solver (for different types of boards with different rule sets, looking for all possible solve states where I don't know if something is unique) first in JS then converted to python (while learning Python for the first time) and after watching your video I think I'm spending far too much time recursing arrays of options (I've been naively going "is X in Array, Remove X" multiply that by sometimes hundreds of cells), it's taking me weeks to chug through some rules to determine if/when there are no actual solutions to a ruleset. I think your code is C but can I do the std::bitset stuff in python, if so how? I think I can manage to make my code work with that now I understand the principle but I'm not sure how to start using bitset things, or C in Python (I use basic install of PyCharm) I'd would be delighted with just a pointer to relevant documentation I'm really not sure where to start looking. Thanks for the help

[@mustafamotiwala2335]

Doing some cursory research, it doesn't look like there is anything in the standard library. However, it is pretty easy to implement yourself. Heres a link to a post on stackoverflow that contains an example implementation. Obviously it'll be a lot slower than std::bitset but that's a given in python anyways. You might try looking into libraries like numpy or numba also. stackoverflow.com/questions/3946086/python-equivalent-to-javas-bitset

[@johnydl]

Thanks a bunch, I know there are ways to get some stuff in Python to run in the C environment (I recall something from some tutorial I watched this month) but if bitset isn't one of them that's okay, it doesn't have to be that much faster but right now it's stupidly slow, If I get a 10x boost that'd be great... Even without a bitset I think I could probably make it happen with a "for a, b in zip (my_true_false_array, my_mask):" kinda loop Done lots of research myself the past day or so thanks to the inspiration ;) but I didn't find the stackoverflow Q&A so double thanks for that too

[@ChasmChaos]

@@johnydl Have you tried using numpy vectors rather than Python Lists? For anything that needs performance, numpy vectors + methods are essential.

[@Daveed]

nice

[@danjohnson6800]

Great content and explanation! I'm on win10 vs 2022. the line: auto [row, col] = next_empty_position(board, row_start, col_start); won't compile. I spent 2 decades in C/C++ into mfc, but this newer wrinkle eludes me. What should this be to work in MS VS 2022? Thanks and keep up the great work!

[@danjohnson6800]

Found it: switch setting in Project Settings. use C++ language c++17 or later. foray into tuples, structured bindings. well worth the journey!

[@kocraft137]

Is it possible to make a renderer I C++ and control it from Python. Imagine having a Player class in Python that has a position attribute and a scale attribute. Would it be possible to send information between these two languages at the same time?

[@lokeshchandak3660]

Python has C extensions if you want to look into it. Most of the major python libraries use C underneath, for performance.

[@laurinneff4304]

I never heard of recursive backtracking before. I'd write a sudoku solver like this: loop over every square, for each of them find all possible solutions. If there's just one solution, fill it in, else don't do anything. Repeat until there are no squares left

[@mCoding]

This solution is great for easy sudokus. However, it is possible that it is required that you make a guess at some point. For hard sudokus there may not be any square that you can fill in that has only one possibility. This can happen even if there is only one solution.

[@pancreasdragonheart9765]

Silly question, but can this bitset hold any number? For example, what if there're 255 unique numbers and not 9.

[@mCoding]

Yes you can have any number of bits (until you run out of memory). The typical implementation of bitset holds an array of unsigned longs (of size=ceiling of how many bits you want/8) that it accesses by calculating offsets and masking.

[@anonymoussloth6687]

I don't understand what cell_contains is. There r 9 rows and columns and each one can only contain 1 number out of 9 so that makes sense. But there are 9x9=81 cellls, each with a possible value of 1 to 9 right? So why is it only and array of size 9?

[@mCoding]

By cell I mean a 3x3 block. In sudoku, every row must contain 1 to 9, every column must contain 1 to 9, and each of the 3x3 blocks must contain 1 to 9, I'm just using the word 'cell' for one of those 3x3 blocks.

[@anonymoussloth6687]

@@mCoding oh i see. That makes sense now. Thanks!

[@lizard450]

I already liked the video before you told me to slap it an odd number of times... Why do you want me to unlike it?

[@mCoding]

*shock*

[@Cucuska2]

Bitset - great thing! I would really like some memes, but stellar video, thank you!

[@mCoding]

Noted!

[@sebastianjost]

I don't have much experience with c++: What does the "std::" do? Why is it used so often?

[@mCoding]

"std::" tells the compiler to look in the standard library namespace ("std" is "standard"). i.e. use builtin functions/types. unlike python, e.g. min, max, zip, etc., C++ does not put many builtins in the global namespace.

[@keyshots294]

I'm struggling with the constexpr type function coz I have cpp11, is a way to go around this?

[@doron910]

Can someone explain the SIZE_T thing please? why not just using an int...?

[@anonymoussloth6687]

Size_t is an unsigned int basically. It means it is always positive. So that increases the range of numbers it can store since it doesn't worry about negatives. The standard template library uses it to represent the size of its data structures

[@doron910]

@@anonymoussloth6687 much thanks, how is it preferred over using an int in this case?

[@anonymoussloth6687]

@@doron910 because the size of anything cannot be negative. Both unsigned int and int have same memory size of 32 bits or 4 bytes. That means both can store the amount of information which is 2^32. But because an int can be negative, it has to use one bit for the sign of the number (pos/neg). But an unsigned int doesn't need to worry about that because u r telling the compiler that this is a unsigned number aka a positive number Ps. In reality, an integer doesn't use one bit for a sign because there is another better way which is called 2's complement of a number to represent negative numbers but the concept is the same. The postive range decrease because we have to account for negative numbers also using the same amount of bits

[@doron910]

@@anonymoussloth6687 Yes but he is not dealing with large numbers here so signed is sufficient and also why not using just unsigned int instead of size_t

[@anonymoussloth6687]

@@doron910 it's has to do with coding practice. U can also see he is using std:: everywhere instead of writing using namespace std because it's best practice to do so.

[@prawnydagrate]

genius

[@iamseth5253]

is he the brother of nullbyte?

[@MD-vs9ff]

Seeing all those raw 9s triggers me. That should be a defined constant somewhere, and those bitsets and bitset arrays should be typedeffed. No example is too trivial to show good practices on.

[@branthebrave]

Or use... deduction. There are complicated sudoku techniques you can use like xwing and swordfish that people use, but computers can find even harder patterns better than us

[@ChasmChaos]

Yes, but implementing "deduction" is not as straightforward since you need to be smart enough to implement a smart algorithm. :) Unless you take a reinforcement-learning approach (generate thousands of sudoku problems and let an RL agent solve it, giving a reward for solving). Constraint programming approaches can come in handy here. Of course, implementing a CP engine is hard, but using an off-the-shelf one is easy.

[@michaelmartiarena625]

your code doesn't work on my computer :( it just gives me compiling errors, nice video tho!

[@mCoding]

Make sure to compile with -std=c++20

[@christophergreeley4880]

Cool doing a video in C++ :D

[@mCoding]

Glad you liked it!

[@christophergreeley4880]

@@mCoding 😊👍

[@verainsardana]

Do a sudoku creator. I tried making but wasn't that successful (I have a working prototype though)

[@ypaut]

Awesome

[@mCoding]

Thanks!

[@wafflescripter9051]

made it odd, nobody mess it up.

[@kishiro8036]

when i see the title, I be like " meh, this code is so bad, why the code take 7 minute to solve sudoku?? " and when i opened the video, i realized that he do it in 7 minute.. and i feel so dumb.

[@rayhaanhanslod4792]

hello to all the wits students here this weekend

[@mCoding]

Welcome, make good choices!

[@jawadch8723]

bruh. I made one without recursive back-tracking

[@mCoding]

If you use domain knowledge of the problem you can usually do better than a simple recursive backtracking approach!

[@jawadch8723]

​@@mCoding Need the source code?

[@mCoding]

Feel free to post it!

[@jawadch8723]

@@mCoding github.com/M-Jawad-Ch/Mathematics/blob/Projects/Sudoku_Solver.cpp I am currently a student so it might not be the best. It certainly doesn't use backtracking.

[@lonnybulldozer8426]

You should have thrown threads at it for a real speed boost.

[@callowaysutton]

recursion doesn't really parallelize well

[@lonnybulldozer8426]

@@callowaysutton Yeah it does.

[@mCoding]

Getting threads to work on leetcode sounds like not a good idea :)

[@lonnybulldozer8426]

@@mCoding Yeah it does.

[@T800-theRealOne]

The only complaint I have about the code is the std everywhere. Why don't you just declare the namespace up at the top so I don't have to keep calling std every time?

[@Tal__Shachar]

Okay stop it. You first make incredible python vids, and now you make CPP VIDEOS? Stop before I come to your house and give you a smoochie on the forehead

[@mCoding]

Thank you so much, Thanos.

[@markcuello5]

HELP

[@RoyalLXXVIII]

Man do i feel stupid

[@stilgarfifrawi7155]

James, I will pay, in cash, for you to get a new microphone. I love your content but your audio is absolutely garbage.

[@dexterovski]

James should setup a Patreon account ASAP. His content is too good.

[@mCoding]

:( This is the new microphone. What am i doing wrong?

[@stilgarfifrawi7155]

@@mCoding I was just shitposting. This sounds leagues better than before. Keep up the good work man!

[@muhammadasadhaider6893]

Why don't you use using namespace std The stds everywhere are an eye sore. (pun intended)

[@mCoding]

using namespace std is an unfortunately widespread bad idea. Please don't using namespace std in any real code-base!

[@muhammadasadhaider6893]

@@mCoding I didn't know that thanks.

[@mCoding]

No worries! I know it can be an eyesore in small codebases. But seeing std:: in a real codebase brings me great confidence that the function is doing what I expect.

[@luizchagasjardim]

"using namespace" brings everything in the namespace into scope. It greatly improves the chance of naming conflicts, so it has to be used with care. You can use "using std::vector", for example, but even then, you should not use it in headers, as you never know what code will include that header in the future. You can always use it inside a scope, though.

[@yehoshuas.6917]

@@luizchagasjardim This seems not bad; don't use 'using namespace std' for your entire codebase, just in small individual classes or functions where you're using lots of std functions and not much else.

[@markcuello5]

HELP

[@markcuello5]

HELP