Python Sudoku Solver Tutorial with Backtracking p.1

แชร์
ฝัง
  • เผยแพร่เมื่อ 21 พ.ย. 2024

ความคิดเห็น • 255

  • @edwardwong654
    @edwardwong654 ปีที่แล้ว +7

    Tim explains the backtrack algo really well, and I give him credit for writing the code on the fly instead of having it pre-canned. He is a real programmer's programmer. I am going to follow alone but I want to tweak it a bit and use a RANDOM function to pick the an empty square. And then do a monte carlo simulaton with time lapse to compare. I am going to make my CPU work! Good job.

  • @ninesquared81
    @ninesquared81 4 ปีที่แล้ว +36

    You could avoid having things like 'range(len(bo[0]))' and 'bo[i][j]' by using the enumerate() function, which takes an iterable (in this case bo) and returns an enumerate object which can be iterated over for index- value pairs. In code you'd write:
    for i, row in enumerate(bo):
    for j, val in enumerate(row):
    if val == 0:
    return (i, j)
    It's a very useful function if you need to iterate over both the index and the value at that index.

  • @BigFatSandwitch
    @BigFatSandwitch 4 ปีที่แล้ว +12

    Dude I have been struggling to understand backtracking for a long time now. You just made it so simple to understand. Thanks for the video

  • @oneeyedjack2404
    @oneeyedjack2404 5 ปีที่แล้ว +108

    By the way, 9^81 is very much above trillions (10^12). In fact, it is nine hundred quinvigintillion

    • @TechWithTim
      @TechWithTim  5 ปีที่แล้ว +24

      😮

    • @yashkhurana9170
      @yashkhurana9170 5 ปีที่แล้ว +7

      'quinvingintillion' hahahahahhahaha

    • @WWFYMN
      @WWFYMN 4 ปีที่แล้ว +8

      it is 196627050475552913618075908526912116283103450944214766927315415537966391196809

    • @tatwiksai9052
      @tatwiksai9052 4 ปีที่แล้ว

      196627050475552913618075908526912116283103450944214766927315415537966391196809

    • @arjunmohammad1729
      @arjunmohammad1729 3 ปีที่แล้ว

      Pro tip : you can watch series on KaldroStream. I've been using them for watching a lot of movies lately.

  • @Krie7ananas
    @Krie7ananas 3 ปีที่แล้ว +3

    I survived my BSc thanks to this chanell, now it's saving my life in masters, Thank you!

  • @user-hd6xc1xn9d
    @user-hd6xc1xn9d 4 ปีที่แล้ว +12

    Thank you so much for this series, I will definitely finish it. I have always been intimidated by algorithms and AI-related topics, but this video helped me become more comfortable with that.

  • @dylanroberts6217
    @dylanroberts6217 4 ปีที่แล้ว +8

    Great video! 9^81 assumes every square has 9 options but every correctly placed number significantly decreases the number of possible numbers. The actual number is surprisingly not as big as you would expect. Nevertheless it is much better to use the backtracking approach.

  • @melbbb5673
    @melbbb5673 3 ปีที่แล้ว +1

    Thank you for putting the mistakes in, it helps a new learner like me!

  • @Plengueiraa
    @Plengueiraa 5 ปีที่แล้ว +10

    Hey Tim! I'm Brasilian but i love ur videos. I'm starting now at python.

    • @TechWithTim
      @TechWithTim  5 ปีที่แล้ว +2

      Hey! Glad you like them

    • @Plengueiraa
      @Plengueiraa 4 ปีที่แล้ว

      @@bulletprooftrading no, the way I said this is because the videos are not in portuguese.

    • @Plengueiraa
      @Plengueiraa 4 ปีที่แล้ว +1

      @@bulletprooftrading ow, it was good, I evolved a lot. I`ve been learning Pyside, Pygame, and other tools . Was very cool.

  • @zaidabraham7310
    @zaidabraham7310 4 ปีที่แล้ว +55

    9^81 is way, way more than a value in the trillions. It's 2 x 10^77.

  • @ramizquliyev394
    @ramizquliyev394 3 ปีที่แล้ว +2

    Mannnnn, You are killing it. Really you are inspiring me to learn programming. Maybe this isn't the vauu thing to learn but I fell that I am learning something. ( Not wasting time ) Thanks a lot

  • @42mix22
    @42mix22 5 ปีที่แล้ว +3

    Wow, me and my classmates were bored at school today, we tried making a sudoku solver, and woah, I didn’t think we would make efficient logic, we actually managed to make logic similar to the backtracking method, only we didn’t have enough skill to be able to code it

  • @muabyt7333
    @muabyt7333 5 ปีที่แล้ว +154

    2:28 two 8s in one row... seems legit

    • @Rej-dx8um
      @Rej-dx8um 4 ปีที่แล้ว +5

      i was just about to say that lol

    • @things990
      @things990 4 ปีที่แล้ว

      MuabYT that’s a column not row

    • @muabyt7333
      @muabyt7333 4 ปีที่แล้ว +19

      Thing S
      Google “column row”. When I was young, I also got that wrong a lot. But if you practice your english will get better.

    • @chantelsopio5826
      @chantelsopio5826 4 ปีที่แล้ว +7

      ​@@things990 What do you smoke and where can I get some?

    • @infinite_xiao5483
      @infinite_xiao5483 4 ปีที่แล้ว +1

      @@muabyt7333 I like calling it x y, x for horizontal, y for the vertical

  • @flamexc
    @flamexc ปีที่แล้ว

    I found your explanation on backtracking really useful!

  • @mortenb3606
    @mortenb3606 ปีที่แล้ว

    Just the series I've been looking for man!
    Thanku

  • @a.m2053
    @a.m2053 4 ปีที่แล้ว

    Nice explanation. One of the clearest videos on the network.

  • @sebastiannrregaard5849
    @sebastiannrregaard5849 5 ปีที่แล้ว +3

    Hi Tim! I'm very exited for this series, i just started out with python and i'm learning a great deal of your videos!
    i wanted to ask why this dosn't work?
    i = 100
    while True:
    if len(str(i)) == 1:
    print(i)
    break
    else:
    i = (i / 2)
    print(i)
    i have also tried to set the condition for the while loop to
    while len(str(i)) > 1:

    • @TechWithTim
      @TechWithTim  5 ปีที่แล้ว

      Aha because when you divide you get a float which has a length of 3 because it counts the “.0” . Try checking if i//10 < 1

  • @officesuperhero9611
    @officesuperhero9611 5 ปีที่แล้ว +5

    very interesting. Will be a good series. Thanks Tim.

  • @LawZist
    @LawZist 5 ปีที่แล้ว +7

    Great video! keep upload more code using different algorithms :)

  • @robertr7923
    @robertr7923 ปีที่แล้ว

    The magnitude of 9^81 is mind-bogglingly vast, making a trillion seem like a mere drop in the ocean. To put it into perspective, a trillion, which is 10^12, is dwarfed by 9^81, which is an incomprehensible 2*10^77. Just think about that for a moment: 2 followed by 77 zeros. That's an astronomical number that's hard to fathom.
    To drive the point home, consider this: a trillion times a trillion is "just" 10^24, which is barely a blip on the radar compared to 9^81. As the exponent increases by just 1, the number multiplies by a factor of 10. So, even a million of these trillion-to-the-trillionth-power calculations is a paltry 10^27.
    Now, imagine multiplying trillions together six times and then multiplying that by a million. That's what it would take to reach 9^81. This number is so unimaginably large that it's comparable to the estimated number of atoms in the universe. Yes, you read that right: the number of atoms in the universe.
    It's difficult to wrap one's head around just how staggeringly large 9^81 is. Suffice it to say, it's a number that's beyond our comprehension, a true testament to the incomprehensible vastness of mathematics.

  • @repudiation230
    @repudiation230 5 ปีที่แล้ว +3

    This is very strange. Yesterday I finished a sudoku solver- what a wonderful coincidence.

    • @TechWithTim
      @TechWithTim  5 ปีที่แล้ว +1

      Is it similar to mine?

    • @repudiation230
      @repudiation230 5 ปีที่แล้ว +1

      @@TechWithTim Yes, it uses the backtracking algorithm although I modified it slightly.
      Before running the backtracking algorithm, the program runs a method on the 'Sudoku board' which checks which numbers already appear within each row. The function then returns a 2D array, where each child array corresponds to a row on the Sudoku board and contains the numbers which do not appear within the given row.
      The program then runs the backtracking algorithm as standard, but rather than potentially checking each number 1-9 for each empty square, it iterates through the numbers which are not already found in the row. This method ensures that time is not wasted checking trivial cases.
      I wrote it in JS hoping to implement it within a profile/portfolio website for colleges to view.

  • @avvn9331
    @avvn9331 5 ปีที่แล้ว +2

    You make really awesome and interesting and useful videos sir

  • @mathisalwaysright4048
    @mathisalwaysright4048 ปีที่แล้ว

    9**81 is actually so high, that I believe that no computer would be ever able to solve it.

  • @poojasrinivasan2727
    @poojasrinivasan2727 4 ปีที่แล้ว

    thank you so much Tim for this code and for making us understand so clearly . just coding isn't effective explaining the concept is so great .

  • @diego56780
    @diego56780 5 ปีที่แล้ว +1

    thks man, i needed this for a homework and i didnt understand how to do it, you saved me man. Keep going with this kind of examples i enjoyed how you teach us.
    More baktracking examples please, like the 4 queen s chess table .

  • @BorrowedAtoms
    @BorrowedAtoms 4 ปีที่แล้ว +1

    The biggest puzzle was foguring out what the top right corner was :D

  • @estevanmaidaa8213
    @estevanmaidaa8213 5 ปีที่แล้ว +5

    thanks Tim it's the best one I saw

  • @pragyan394
    @pragyan394 5 ปีที่แล้ว +4

    Thanks, I feel like I understand recursion a little bit better now.

    • @TechWithTim
      @TechWithTim  5 ปีที่แล้ว

      Awesome! Try watching the next video where I implement it

  • @shockbladezed2352
    @shockbladezed2352 3 ปีที่แล้ว

    9^81 power is 3^162. We know, that 2^20 is a bit bigger than a million, hence 2^40 is a bit bigger than a trillion. Imagine what's left for 3^162. Another way to visualize it is, that 3^2 ~=10. 3^42 is a bit (in percent) bigger than 10^20. 3^162 is a bit (in percent) bigger than the forth power of 3^42. In fact, it's 3^168/729. So we know, that 3^162 ~~ 10^77, so we can safely assume 3^162 has around 78 digits. (Just checked the calculator - it's around 1.966×10^77. Can't believe how close I was).
    Edit: 9^81 is only if you literally have no digits on the board or rules about how to position them on it.

  • @willforrhall
    @willforrhall 2 ปีที่แล้ว

    Make a video on algorithms and data types

  • @сойка-и8й
    @сойка-и8й 5 ปีที่แล้ว +4

    Thanks Tim you are the best

  • @adityad8929
    @adityad8929 10 หลายเดือนก่อน

    Thankss for this amazing tutorial Tim

  • @220SouthlandAve
    @220SouthlandAve 6 หลายเดือนก่อน

    Tim is my hero!

  • @mehdiSupp
    @mehdiSupp 5 ปีที่แล้ว +2

    Looking forward for the next video

  • @ramlabasharat4334
    @ramlabasharat4334 4 ปีที่แล้ว

    Amazing... can you give me a solution to the Ubongo puzzle?

  • @maxwellhouse8inator
    @maxwellhouse8inator 3 ปีที่แล้ว

    9^81 is roughly equivalent to the amount of atoms in the universe to put that into perspective

  • @yassernadir2947
    @yassernadir2947 5 ปีที่แล้ว +2

    You are a genius 👍🏻

  • @rock53355
    @rock53355 3 ปีที่แล้ว

    Thank you Tim! I finally understood it! :D

  • @androsio7ja865
    @androsio7ja865 3 ปีที่แล้ว

    finally i understand it!! ur the best

  • @gniewo6
    @gniewo6 5 ปีที่แล้ว

    very good now i go to next one

  • @stuartjacobs
    @stuartjacobs 5 ปีที่แล้ว +1

    That was fun. On to the next one. Cool vid. Thx

  • @adithyasapalya634
    @adithyasapalya634 2 หลายเดือนก่อน +1

    in the source code provided by, the GUI isn't working in website

  • @AlexWardi
    @AlexWardi 4 ปีที่แล้ว +2

    13:17 the "up thing" is called a pipe...

  • @trenttagestad5282
    @trenttagestad5282 4 ปีที่แล้ว

    Hey Tim, love your videos! Thanks for making them. What would be the best way to randomly generate a partially solved Sudoku puzzle as an array of lists like you have in this video?

  • @ThePzr
    @ThePzr 4 ปีที่แล้ว

    Lovely bro !
    Thanks a lot for your donations for others.

  • @matthewferguson8369
    @matthewferguson8369 2 ปีที่แล้ว +1

    why in the second for loop is there an [0], wouldn't you want to use [i] ? To refer to the current array?

  • @solve64
    @solve64 2 ปีที่แล้ว

    Nice, I did something similar in PHP.

  • @paclifac7730
    @paclifac7730 5 ปีที่แล้ว

    Thanks so much dude, this code Will be use from Argentina ♥

  • @kubogi
    @kubogi 4 ปีที่แล้ว

    I tried backtracking by hand... it worked and I got my new best! (2m46s)

  • @loveyou4676
    @loveyou4676 2 ปีที่แล้ว

    Coding starts at 11:27

  • @brucebane7401
    @brucebane7401 4 ปีที่แล้ว

    tim is the best

  • @castormann
    @castormann 5 ปีที่แล้ว +94

    ”9^81 is probably like in the trillions or something”... not even close lmao

    • @VivekYadav-ds8oz
      @VivekYadav-ds8oz 4 ปีที่แล้ว +4

      9.something * 10^77 LMAO

    • @leventegyorgydeak1300
      @leventegyorgydeak1300 4 ปีที่แล้ว +14

      it is more than the number of atoms in the observable universe

    • @ongp793
      @ongp793 4 ปีที่แล้ว +1

      @@leventegyorgydeak1300 it isnt

    • @rafvissersraf
      @rafvissersraf 4 ปีที่แล้ว

      @@leventegyorgydeak1300 you're stupid, only our own sun is 10^57 already smh, and all of the atoms in body masses in space are a small fraction of all the space dust atoms

    • @leventegyorgydeak1300
      @leventegyorgydeak1300 4 ปีที่แล้ว +2

      @@rafvissersraf do you realise that 10^77 is 10^20 times more than 10^57? that is an insanely huge number, and you have to multiply by that. Maybe 10^77 is not more than the atoms in the universe, but it is 10^80-something

  • @gigachadkartik
    @gigachadkartik 4 ปีที่แล้ว +1

    9^81 is when all the boxes are empty which essentially never happens, about 20 boxes in typical sudoku are filled so we have about 9^60, that's still an ultra-massive number.

  • @rylan8092
    @rylan8092 3 ปีที่แล้ว

    Great content! Keep up the work!!

  • @mpricop
    @mpricop 5 ปีที่แล้ว +1

    At the end, in the last loop it should be `len(bo[i])`, as currently you are looping only over the first row :)

    • @TechWithTim
      @TechWithTim  5 ปีที่แล้ว

      I see what you mean but it’s actually fine. Since we known the length of each row is the same we can do that.

    • @mpricop
      @mpricop 5 ปีที่แล้ว

      @@TechWithTim true

  • @moesparc
    @moesparc 2 ปีที่แล้ว

    12:46 you explain how you are creating the verticle lines but you say horizontal instead. im not that great at python yet so i was trying to understand how the code would create horizontal lines until i finally realized you meant vertical. this was a headache lol

  • @roshanloke9423
    @roshanloke9423 4 ปีที่แล้ว

    Please explain why we use( if i ==08)

  • @pallepuaruna6970
    @pallepuaruna6970 4 ปีที่แล้ว

    Absolutely amazing of u

  • @peterball3289
    @peterball3289 4 ปีที่แล้ว

    Thanks nicely presented.

  • @Uriakatos
    @Uriakatos 4 ปีที่แล้ว

    Dude, why couldnt you have made this video when I was in uni and smashed my face into my keyboard when my teacher assigned this as hw lol.

  • @WarlikeSRK
    @WarlikeSRK 4 ปีที่แล้ว

    hey Tim,
    Thanks for the great tutorial. Im totally new to programming so I guess this is still a little too advanced for me because I'm already having trouble understanding what is you do exactly when defining the print_board function (the range and Len stuff) :(

    • @Alan-pi1vn
      @Alan-pi1vn 4 ปีที่แล้ว

      For i in range(len(bo)) just creates a list which is as long as the amount of rows on the board and the loops over all the items in that list. for example For i in range(2): print(i) would print out 0 and 1.

    • @confidential303
      @confidential303 4 ปีที่แล้ว

      @@Alan-pi1vn you making it more confusing

    • @AI-DM
      @AI-DM 4 ปีที่แล้ว

      @@confidential303 Let me take a crack at explaining if u still need it. Parentheses like these work like the ones from math. So it looks at the inner most then works out. So it start at (bo), then it looks at (len(bo)) which gives an answer, 9 in this case. So range(9) then happens. I hope this helped

  • @davideettori3226
    @davideettori3226 5 ปีที่แล้ว +1

    Amazing video

  • @modaryaghi
    @modaryaghi 4 ปีที่แล้ว

    Thanks Tim.

  • @sora6430
    @sora6430 4 ปีที่แล้ว

    which is the best database to work with python?

  • @sarvanik4802
    @sarvanik4802 4 ปีที่แล้ว

    can you tell me whether you are coding in pycharm?

  • @yoyoyuan
    @yoyoyuan 5 ปีที่แล้ว

    Can you do a video on killer sudokus?

  • @jakubucinski
    @jakubucinski 5 ปีที่แล้ว +3

    Good one !

  • @captaincodm7527
    @captaincodm7527 4 ปีที่แล้ว +1

    Hey man Tim how can we type a modulus please answer

  • @adriandiaz1072
    @adriandiaz1072 4 ปีที่แล้ว

    Is this the best way to make a sudoku board?

  • @pratyushvatsa7490
    @pratyushvatsa7490 3 ปีที่แล้ว +1

    What if the puzzle given by user is not solvable?

  • @PetersFXfilms
    @PetersFXfilms 4 ปีที่แล้ว +1

    3:25 "9^81 is probably in the trillions" I facepalmed to hard at that. Come on Tim.

  • @AlexandrBorschchev
    @AlexandrBorschchev 4 ปีที่แล้ว

    Theres a video in computerphile about this, i also recommend everyone to watch it.

    • @gmc9753
      @gmc9753 4 ปีที่แล้ว

      That video doesn't explain the backtracking as well as this one.

  • @sainco3036
    @sainco3036 5 ปีที่แล้ว +2

    thanks.

  • @TriThucMoiNqk
    @TriThucMoiNqk 3 ปีที่แล้ว

    RecursionError: maximum recursion depth exceeded while calling a Python object! help me

  • @jessicavo695
    @jessicavo695 5 ปีที่แล้ว

    Hey Tim! I am really in need of your help with the natural solver. Is it possible to make a video about the natural solver as soon as possible? greetings from Zurich

  • @pranav2423
    @pranav2423 2 ปีที่แล้ว

    How might you analyze the runtime/spacetime of this? I see n^2 work done and then there's a recursive call, but I'm not sure how the recurrence relation would look.

  • @CollosalTrollge
    @CollosalTrollge 3 ปีที่แล้ว

    hey man, what keyboard do you use, i cant stand mine. I use wireless Logitech K270 its decent but i am tempted to get a better keyboard with buttons that feel good and a proper space bar , all these space bars on most keyboards are so bloody rattly , i mean u get used to it, but im sure i can find a good keyboard

  • @David-gr9nr
    @David-gr9nr 3 ปีที่แล้ว

    Wouldn't saving all possible options for the empty positions and then eliminating them one by one be faster? Once there is a single option then we fill in the position.
    The way I'd do it would involve different steps at first the most efficient option, looking for places a number can already be placed with 100% certainty, if no success then the next step. Like a human (who knows how to play) would play it.

  • @ahammadshawki8
    @ahammadshawki8 4 ปีที่แล้ว

    it will be 81^9

  • @bianchialex
    @bianchialex 3 ปีที่แล้ว

    I really want to do this in a pandas array. And make a sudoku puxxle creator.

  • @maava
    @maava 5 ปีที่แล้ว

    What would the 6x6 box loop look like? Having troubles with it

  • @TheUndulyNoted
    @TheUndulyNoted 4 ปีที่แล้ว +6

    why are you writing len(bo) and len(bo)[0] in the for loops when you could just write range(9), sudoku grids are always 9x9 so you shouldn't complicate the code accounting for an impossibility. You're sacrificing readability for no reason.

  • @user-hd6xc1xn9d
    @user-hd6xc1xn9d 4 ปีที่แล้ว +1

    I am confused about the printBoard() function.. %? Modulous?? what is that?

  • @marshalljamieson231
    @marshalljamieson231 3 ปีที่แล้ว +2

    The way he says sudoku doesn’t hit my ear right

  • @siamahmed8287
    @siamahmed8287 3 ปีที่แล้ว

    What application do you use to record your screen and edit it?

  • @maava
    @maava 5 ปีที่แล้ว

    Can you do a video for 6x6 sudoku instead of 9x9?

    • @Kyrelel
      @Kyrelel 4 ปีที่แล้ว

      The code would be identical except for board[] and the upper limit of the loop increments

  • @abhisheksarkar4897
    @abhisheksarkar4897 3 ปีที่แล้ว

    Hey can u clear doubt which is isn't there 11 rows( a single line takes one row right?)so how u set logic for printing horizontal lines after 3 row

  • @anaiscarrichon6409
    @anaiscarrichon6409 4 ปีที่แล้ว

    where did you find sudoku boards ? I'm looking for CSV exportable boards

  • @yididyakediryasin2886
    @yididyakediryasin2886 2 ปีที่แล้ว

    Hey, Can we use A* Search to solve Sudoku?

  • @sankethb.k642
    @sankethb.k642 5 ปีที่แล้ว +3

    I love it

  • @domingo2977
    @domingo2977 4 ปีที่แล้ว

    Can you make the same sudoku solver with tkinter?

  • @Munax.
    @Munax. 4 ปีที่แล้ว +6

    3:31 I'm sorry but I laughed with loud when you said at 9^81 is in the trillions. I'm super rusty at math but I'm sure it's way beyond trillion trillions.

  • @aryanbhatia6992
    @aryanbhatia6992 5 ปีที่แล้ว

    When is the next tutorial on PyOpenGl coming ??
    And what will it be about ??

    • @andrewm6788
      @andrewm6788 5 ปีที่แล้ว

      Just watch sendex videos on it if u cant wait

    • @TechWithTim
      @TechWithTim  5 ปีที่แล้ว

      I’m trying to create an FPS camera but it’s pretty difficult so no estimate atm

  • @markosmuche4193
    @markosmuche4193 5 ปีที่แล้ว

    was great. thanks

  • @just_an_ordinary_being
    @just_an_ordinary_being ปีที่แล้ว

    What software did you use to type in the codes?

  • @alexanderreiner7694
    @alexanderreiner7694 3 ปีที่แล้ว

    I am in 11th Grade and I need this for my Skilled Work or how thats called in english. In germany we say: "Facharbeit"

  • @namanagarwal115
    @namanagarwal115 5 ปีที่แล้ว +1

    I don't understand the line j == 8

  • @siddhantagarwal6885
    @siddhantagarwal6885 3 ปีที่แล้ว

    hi just wanted to understand how will it be 9 raise to the power 81 possibilities , i think there will be only 729 possibilities right ?

  • @lazar87022
    @lazar87022 3 ปีที่แล้ว

    how does one return the grid when its solved instead of returning True/False values ?

  • @user-hd6xc1xn9d
    @user-hd6xc1xn9d 4 ปีที่แล้ว +1

    I dont understand how for loops work or anything.. also what is print([i][j])

    • @krisikris7316
      @krisikris7316 4 ปีที่แล้ว

      @@Pranav-x8q Why should we do that?