1:38 wow he was able to say "recursion" without even moving his mouth, that's the real trick

@jojosoni6355

4 жыл бұрын

It's easy if you try it.

@DarshanSenTheComposer

4 жыл бұрын

now everyone is trying it out

@qcdiamond8292

4 жыл бұрын

I've literally watched it 10 times now and I'm still amazed.

@vadiimt

4 жыл бұрын

His lips utilize a very efficient algorithm

@NicosLeben

4 жыл бұрын

That comment made me laugh so hard. xD

Once you understand recursion you can understand recursion

@ishaanvatus3536

4 жыл бұрын

I see what you did there I see what you did there

@vandelayindustries2971

4 жыл бұрын

@@violet_flower Yeah sure I'll explain deadlocks to you right after I've explained deadlocks to you

@harbl2479

4 жыл бұрын

But where is the edge case?

@mekkler

4 жыл бұрын

@@harbl2479 I was thinking that too. It seems like it's taken care of by simply working through the nested for loops, which continues even after it found a solution. This has the advantage of finding all solutions if there are any, which there shouldn't be if the puzzle was constructed properly.

@albertbatfinder5240

4 жыл бұрын

You make it sound straightforward, but in ORDER to understand recursion, you need to understand recursion.

It must ba a joy having him as teacher, he is so chill and methodical.

@RobertMilesAI

4 жыл бұрын

When he's your teacher you don't get subtitles, so it can be tricky

@MatthewSmith-wh5dr

4 жыл бұрын

Amen

@wakinglife7355

4 жыл бұрын

I'm sad

@hamiltonianpathondodecahed5236

4 жыл бұрын

@@RobertMilesAI exactly

@toddbod94

4 жыл бұрын

Robert Miles he's perfectly understandable without subtitles imo

I really like Thorsten, he seems like a good guy.

@Gooberpatrol66

4 жыл бұрын

eh kills sodukus and doesnt afraid of anything

@stoneskull

4 жыл бұрын

he's awesome. he has that excitement for maths like a young person, and explains in a way to help others.

@ASCENDANTGAMERSAGE

4 жыл бұрын

Yeah I love this guy.

@user-zu6ts5fb6g

4 жыл бұрын

he ist verry deutsch

@bryphi77

4 жыл бұрын

Kinda reminds me of a bond villain.

It's more fun to write a solver/ generator than it is to do the puzzles by hand

@recklessroges

4 жыл бұрын

A+ (now write it in Rust ;-) )

@garethevans9789

4 жыл бұрын

@@recklessroges Now Brainf*ck 😉 (It's is a real programming language)

@quintrankid8045

4 жыл бұрын

@@garethevans9789 Piet?

@sabouma

4 жыл бұрын

Making a solver is also kind of a puzzle :p

@imveryangryitsnotbutter

4 жыл бұрын

@@garethevans9789 I refuse to believe anyone is so masochistic as to write a program for extensively handling a two-dimension array in Brainfuck. Like, I'm sure one exists somewhere, but it was almost certainly written in C and then run through a converter.

This is O(scary)

@nikolasscholz7983

4 жыл бұрын

I'm literally crying from seeing this approach

@aevus

4 жыл бұрын

i mean this aproach is almost brute force

@SimonTiger

4 жыл бұрын

Not for a normal 9x9 sudoku. NP-hard means it gets way harder once you _increase_ the size. For example, 16x16 sudoku would probably take longer to solve, but a 9x9 should be doable in just a few milliseconds.

@TaylorLopez412

4 жыл бұрын

How did this not hit the recursion depth limit?

@incription

4 жыл бұрын

@@TaylorLopez412 you can set the recursion limit iirc

1:12 - "vot do vee do?"

@hemaangs3024

4 жыл бұрын

SILENCE! VEE VIL AASK D'KVESHCHUNS!

@narcosblacksquad2524

3 жыл бұрын

Scooby dooby doo

@stefaniapozzi2296

3 жыл бұрын

haha

Does he have his own KZread channel? I really enjoy the way he talks about problems. Makes them seem much easier than they really are.

aaaaa the spaces before the colons

@ekremdincel1505

4 жыл бұрын

And this nested loops...

@OrgBrent

3 жыл бұрын

It hurts

@seftondepledge3658

3 жыл бұрын

@@OrgBrent And not having a space after commas. Not very pythonic

@rudyorre

3 жыл бұрын

@@ekremdincel1505 I get the spaces thing, but how else would you write the nested loops?

@ekremdincel1505

3 жыл бұрын

@@rudyorre you should find a better algorithm if possible.

The Dancing Links algorithm, by Knuth, is one of the most beautiful algos I have ever seen. It works by abstracting away from the sudoku itself, and translating all the constraints into a matrix form, on witch you can apply a backtracking algorithm, in order to find a subset of lines with exactly one non-zero value in each column. The advantage is that it treats all constraints as equal. You should absolutely do a video on solving Sudoku with Dancing Links. Moreover, you can show that by generalizing a problem, you can use exactly the same algorithm for Sudoku, Pentominos, Soma cube and many others.

Dear Thorsten, I was your student and enjoy this video. As a Chinese, I want to tell that the later game is called Huarongdao. (华容道), The story is about a general of a kingdom escaping from a losing battle. I have some fun when I was a child with it.

6:45 that keyboard has seen war

@NoHandleToSpeakOf

4 жыл бұрын

Space bar certainly did

@choOz

3 жыл бұрын

what about his whiteboard shits scarred for life

I was actually contemplating on making a sudoku solver myself as practice or not, but then seeing how it's done is just way too fun.

For those who wanted to learn more about this. The problem of solving sudoku can be generalized to a problem called Constraint Satisfaction Problem (CSP), CSP includes things from puzzle solving to real world problem like planning and scheduling.

@codemaster1768

2 жыл бұрын

True. It mostly uses AllDiff constraints to solve the problem.Which states that all the variables must have different values.

As someone who's learning Python I'm excited to try this project. I've learned to build my first LogisticRegression model, so I'm excited to to continue making progress.

The time when Targaryens not using Dragons anymore, They are using Python..

He has so much more enthusiasm for computer science than 90% of my professors in the department. Lol.

I remember i made my own sudoku solver in my late teens. I don't remember much but i remember part of it would track POSSIBLE numbers for each square. This video brought back a bit of my memory when i saw "possible" in the code.

I would smoke weed with this guy

@francescodiniccolo

4 жыл бұрын

Teo Ionut me too, and I don’t even smoke

@evolutionsimplified

4 жыл бұрын

Teo where do you find weed in Bucharest?

@uwu-zl6tq

4 жыл бұрын

@@evolutionsimplified noapte buna

@mayursaroj4360

4 жыл бұрын

He lowkey looks like a gangsta or a drug lord turned programmer 😂

@johnjacobjinglehimerschmid3555

4 жыл бұрын

I think I'd have to have smoked weed to understand this guy!

Great teacher, fun and entertaining for super tough concepts. Such an elegant solution too.

This is really a clever little algorith for the problem. It's a bit too simple for my taste because it only prints out the solution while the solve() recursion is still running. After solve() is completed, the grid is in the state from the beginning again and the solution is lost. I slightly modified it by adding a returnvalue to solve() and some evaluation to keep the final result in the variable grid[ ][ ]. A while back I began programming a sudoku solver that should replicate the exact way I solve a sudoku on paper. It's still not finished because it struggles with the extra hard Sudokus. I like these Computerphile videos.

You can use the built-in pprint function (from pprint import pprint) to pretty print data

@rucker69

4 жыл бұрын

That is a separate library in the deployments I'm familiar with.

@Kuchenrolle

4 жыл бұрын

@@rucker69 I guess he means it's part of the standard library.

@rucker69

4 жыл бұрын

@@Kuchenrolle it looks like the original was edited

Wow. I really want to learn more under him. Beautifully explained everything. ❤️

At one time I wanted to learn java, so I wrote a sudoku solver in Java, with a gui to input the puzzle. The principles of solving were basically the same as the python version, but Thorstens version were more elegantly written.

4:02 smooth af

I would like to watch your follow-up video about Knuth’s algorithm x and dancing links, considering a sudoku solver as a constraint satisfaction problem :)

I built a sudoku solver in PowerShell, python and C++. But it couldn't solve the harder problems. Awesome video.

Wow, it's not teaching, it's gossiping, motivating, soothing, relaxing.

a function that calls itself? THIS CHANGES EVERYTHING

I’ve tried to code it myself using my own logic on solving sudokus. It is far more complicated and frustrating to code, and this is where the beauty of his method resides.

@ziga1122

Жыл бұрын

I feel you, after 5 attempts i finally succeeded using logic, i spent way too much time on it though

Love yt recommendations. I have been watching for 1 min and was subscribed already.

Is it possible for you to enable automatically generated captions? They work perfectly on Numberphile channel! I am convinced I am not the only one who would appreciate this. I often watch your videos at night and I cannot enable sound because that would disturb my roommates :( btw. I love your videos. Great content as always!

For my final project in pic10C (programming in computing) at Uni, I tried to finally write a program in c++ to generate Sudokus using specified seeds. I had tried to write this program three times previously: once in c++, then in python, then again in c++ and of course the last attempt in c++. It's amazing just how complicated it becomes trying to generate Sudokus. You'd think the logic would be simple enough: put a number there if it can go there; but the issue is the framework you have to move in: columns, rows, and blocks. You find that numbers being in cells is only a suffucient condition to block a number from potentially going in a cell. In fact, potential numbers in potential cells can affect OTHER cells potential numbers, and the issue just compounds from there!

@Henrix1998

4 жыл бұрын

I have couple ideas, I'll try to remember to test them

@cody5535

4 жыл бұрын

@@Henrix1998 One of the ideas I came up with (which was ultimately insufficient but which might be improvable though I've not worked on this project for about a year) to surmount this problem was this concept of cell "families" which were empty cells in a block, row, or column whose mutual potentials were the source of the exclusion of those numbers outside the family in that block, row, or column. I remember getting the first layer of this idea working but it needed to "shrink" as cells in families were assigned numbers which I never solved in time. Typing this out it reads like a non-issue but for whatever reason the difficulty of doing what I was doing shot up.

@aevus

4 жыл бұрын

i also wrote a sudoku generator. my approach was to first: generate a list of the most "primitive" sudokus possible and store that list, then use that list to create the sudokus. with "primitive" sudoku i mean a special set of sudokus with which i can create any legal sudoku. i create a new sudoku out of a primitive by several transformations like: flipping, rotating, switching numbers with each other (like switching all 1s to 2s, all 2s to 5s and all 5s to 1s) switching rows within blocks switching rows of blocks and more. the important thing is doing any of the transformations on a valid sudoku will give a new valid sudoku. and to get that list of the most primitive sudoku i basically just brute-forced all sudokus, checked if they were legal, then check if i already stored this sudoku or any of its transformations, if not then store this as a new primitive sudoku. you only have to generate that list once on your computer, then you can use that to generate new sudokus really fast on any machine.

@vandelayindustries2971

4 жыл бұрын

Wouldn't it be exactly the same as solving a sudoku, with the only two key differences being that 1) you start with an empty board, and 2) you don't check whether 1-9 can fit in a cell in numerical order, but random

@philrod1

4 жыл бұрын

How about this for generation: Create a complete and legal board Remove a number and solve() Keep repeating until the board has more than one solution Put back the last removed number I'm not sure if this would make for nice puzzles, though. It will probably _depend_ on backtracking, which humans don't really like. I prefer to deduce or infer solutions.

_cries in PEP8_

@ekremdincel1505

4 жыл бұрын

Lol

@SSJ3Tim

4 жыл бұрын

Every video with this guy

@pitrk

4 жыл бұрын

Searched through the comments for this before starting the video.

@proud22beme

4 жыл бұрын

the think that hurts me the most is not using numpy's nicer features, for ex, the possible() function could have been this: def possible(x, y, value): return np.all((grid[y, ...] != value) + (grid[..., x] != value))

@JNCressey

4 жыл бұрын

@@proud22beme, looks like that's only the column and row rules, you missed the 3x3 square rule.

Simple and elegant solution. I love it!

I did one years ago, I made a 3 dimesional array, 10 values for each square (10th value holds the solved value). The user could enter numbers interactively. When a number was inserted it registered the number across the row, column and block, thus reducing the possibilities in each square. Then it checked the whole grid, and if there was only one possibility in a particular square, it got filled in. Then it recursed. If it failed to fill in another square, it went back to waiting for the user to fill in another number. It would normally reach a tipping point where all the numbers got filled in.

Some time ago I was making a sudoku solver for fun. But I did the "like human" approach. Specifically, I made it try various techniques. This also nicely doubled as a puzzle difficulty checker. Instead of just looking at how many cells were pre-filled (most of publications I checked do that), it checked what techniques were required to progress. But I got bored before I could finish it so it would solve the "hardest sudoku puzzle" without guessing.

Prof: This is my sudoku solution. Interviewer: Now do it in O(-1) complexity Prof:

@henrysiau2695

3 жыл бұрын

Vstro its O(1) because the n is always 9

Many years ago now, i.e. very shortly after Sudoku arrived in Norway, I wrote a solver for it. For a quick & dirty program like this I used Perl. The obvious method was to use recursion with pruning and backtracking since a brute force approach would be far too slow. My solver sorts all the open cells by the number of possible numbers to put there, this means that I always enter any forced values first, then when I can't see any more of these I will try the cells with two possible values, then 3, 4 etc. The key to make it fast was to have a compact grid representation so that I could pass it along on the recursive calls, I used a 9-bit bitmap for each cell, so each time I place a digit I also cross out that bit from cells in the same column or row. The alternative is to clean up during backtracking but in that case the bitmap updates take a lot of time so it is better to simply make a local copy for each call. The obvious next stage was to use the solver to evaluate the difficulty of randomly generated sudokus, I gave this program to my parents for Christmas so that they could print out a pair of new puzzles each time they wanted to have a solving race. I used the number and size of the N-way splits needed in the solver as a proxy for difficulty and this worked very well.

Worth mentioning is that sudoku is part of a family of problems called 'exact cover' problems which are NP hard. In the family are problems such as nonograms and the eight queens problem. Would be cool to see sudoku generalized as an exact cover problem and solved that way.

i'm so intimidated by the ease he's talking about those hellish loops.

This is the kind of guy who teaches by doing My favorite kind of teacher

This video helped me a lot understand a different way of using recursion

This guy is off the hook! Spectacular!

I can just imagine this guy as Hitchhiker's Guide to the Galaxy character.

@Nilslos

4 жыл бұрын

I like your comment, but at this moment it has 42 likes, so I won't put another one there, it would ruin the "answer".

@deveshmungad7900

4 жыл бұрын

@@Nilslos can't help it now

@naommalotane7444

3 жыл бұрын

President Zaphod

I dig this speaker. Pretty chill one. And interesting topics too :)

I'm hobby Python programer and Sudoku solver was my first "real" project fee months ago. I really love Python!!! :)

I tried copying this with a blank starting grid with all zeros and thought it wasn't working, but then realized it was just taking forever to loop through everything! Great video, got me thinking.

@wildthing72

2 жыл бұрын

😆😆😆

The cooking animation was amazing ... and made me laugh^^

@ekremdincel1505

4 жыл бұрын

Haha yes

He explains everything well, except for the part "grid [y] [x] = 0". I had to take some time to realize that this part is actually connected to the input part where the program stops and not just sets the cell value back to zero right after finding the answer)

@weejohntee

3 жыл бұрын

I still struggle to understand that part

@Anaximander29A

2 жыл бұрын

@@weejohntee this took me a while. Thing is solve() has 3 different outcomes: 1. No empty cell found (the sudoku is solved) -> before the function finishes (and leads to grid[y][x] = 0) it prints the array. 2. The possible() function returns false and not all numbers (1-9) were tried already OR the possible() function returns false and no number fits in the cell. In the first case it checks possible() with the next number, in the second case (3) it returns the solve() function before the the whole sudoku was finished and sets no number for this cell. The previous solve() call in the recursion now finishes its own solve call, and sets the cell before also 0. BUT in this case maybe not all numbers(1-9) were tried so it could try again with another. Only when all numbers were tried, the solve() returns and then checks the previous solve() call (bottom up in the recursion). But maybe in the end the solve() function can't find an empty cell anymore. Then the whole thing gets printed before all the recursions collapse and go bottom up (--> clear the array) again.

@niranjanshankaran3493

2 жыл бұрын

@@Anaximander29A thanks for the explanation

I did something similar in python last year (as a college freshman). It's really cool seeing how my sloppy self taught code/sudoku logic (not using brute force/guess and check) compares to a legitimate build.

Am I the only viewer who can't get enough of the Professor's videos but quickly gets bored or irritated at other Computerphile presenters - and stops watching them? Why? Because the Professor is the antidote to the computer science lectures I attended in College where the lecturers took themselves and/or the subject matter too seriously.

I really like the, "and my challenge to you is to write...".

@runrickyrun157

4 жыл бұрын

"The proof is left as an exercise to the reader"

Really liked this one, the solution is so elegant

@bugodi327

4 жыл бұрын

not really its about as brute force as it gets

@mayursaroj4360

4 жыл бұрын

why does it continue to print other solutions, even after its out of loop? plz help

@lesa251

3 жыл бұрын

@@bugodi327 No it's not as brute force as it gets. The as brute force as it gets would be to generate all the possible sudokus and check for each one if it was vaild.

Thank you for the efficient explanation! Does Thorsten Altenkirch’s name appear in the description notes? I am looking forward to reading the book he alludes to: Conceptual Programming with Python.

For anyone interested: If you want an easy way to go the constraint solving route, for example because you want to solve this for larger N where the running time becomes restrictive, you can model your sudoku problem in a constraint programming language such as MiniZinc and solve it using a constraint solver. Sudoku is actually part of the MiniZinc tutorial

@es68951

Жыл бұрын

Constraint programming is the way to solve this without reinventing the wheel 😄

I wrote a similar solver in MATLAB using recursion but I searched through the puzzle to find the element with the least number of possible values which minimises the number of calls to the function.

REALLY be wanting to fix that phone cord.

@Diachron

4 жыл бұрын

Glad I'm not the only one. 👍

@lisatorres2377

3 жыл бұрын

Ur so funny guy

Recursion is easy to understand at high level but hard if you actually think in detail. When I wrote a Sudoku solver I used a more human approach. I first added those that were certain and used recursion only when there were alternatives,

My job is in the health industry and I have very little idea about other domains. I've recently just been looking at computer science online. This is insane for me. There are universes of things in life I have no idea existed.

LEGEND! 10 minutes on this and was able to understand backtracking...

@akywongster

3 жыл бұрын

Dude ur profile pic made me throw my phone against the wall

The homework is to create a python script using that solver and "back tracking" to generate new "1 possibility" sudoku grids.

there is one little trick to improve the the solver by magnitudes, iterate over all fields and find the one with the least possible values according to the 3 constraints (row, colom, box) if you feel fance only try those values (but it just reduces runtime costs by some small amount) that way you have much less guessing and the search tree almost collapses to a list

@jan861

Жыл бұрын

could you elaborate, please?

This beautifull man just made me understand backtracking... Thank you!

"Once you understand it, it's quite simple"....That is the beauty of computer science

Please do a follow up on Knuth's dancing links algo.

Woah, there has to be more such videos!

I didnt do it this. But I did a sudoku verifier in C instead. It was quite interesting because you can use threads to check the puzzle from rows, columns, and each individual square.

I didn't understand what for the line after the call for the recursion func? the line grid[y][x] = 0? because, if i call the function, it will start over, and if i finished, i will not enter the if statement..

@entivreality

4 жыл бұрын

as i understand it, it goes like this: find a number that is possible in the next empty position (on the first call, this will be the first empty position). now taking the position as filled with that chosen number, again find a number that is possible in the next empty position. repeat this process until all positions are filled. if we can’t find a possible number for a given position we made a mistake somewhere and the lowest recursive call returns. this return within the lowest recursive call will lead the next higher call to reset its position as empty and loop to the next value between 1 and 9, repeating the process. if the loop can’t find a possible value for the empty position, it too will return, leading the next higher call to reset its position as empty. repeat for each layer.

This guy wants to save me 15% on my car insurance.

Beautiful solution. Bravo!

I programmed my own sudoku solver last week, was fun.

He makes coding on light mode less weird

hay everyone 2d list output easy mode -> print(*listvar, sep=' ') !!!best thing EVER changed my life

@rishavmitra5732

3 жыл бұрын

Another one from pprint import pprint pprint (grid)

Great video! Worth mentioning that after all solutions are found grid will return to its original form as a side effect of grid[y][x]=0 (which can also be a feature).

@elhartzer1639

2 жыл бұрын

If i dont want this, how can i prevent it? An idea was to put it in an if statement, that checks if all rows sum to 45 and then not execute grid[x][y] = 0. Or maybe use numpy to check if there are any zeroes left? Would there be a more elegant solution?

I wrote a sudoku solver that ran on an arduino spitting each new addition to the grid as a load of serial prints. I didn’t use the brute force recursive approach but instead tried to replicate the methods I found on a website devoted to solving sudoku. I think it taught me allot

@nunoricardoserafim3187

3 жыл бұрын

Why did you run on an arduino? I'm just curious

@letsgocamping88

3 жыл бұрын

Nuno Ricardo Serafim because at the time it was the only programming language / environment that I was familiar with!

I was reading Steven Skiena's "Algorithm Design Manual" and according to him, this kind of sudoku solution for backtracking suffers from choosing the empty squares suboptimally. It seems like the best way would be to try the most-constrained-empty-squares first, rather than simply looping empty squares from top left corner to the bottom right corner. Most constrained empty square is those squares on the board which have the least possible (guessable) values in them. So instead of recursing from a square which has [1,2,4,6] as possible guessses, focus on starting from a square which has only two possible if that is available on the board. It makes it a bit tricky to code the backtracking but it seems in principle it should prune the search tree quite a bit.

@QContinuuum

3 жыл бұрын

Of course the purpose of this video was not to present an efficient algorithm, but to explain recursion/backtracking on an example. I doubt an efficient algorithm would use recursion or backtracking... I guess it would solve the constraint problem. But on topic: The tricky part in the code comes after you invoke solve()... when you return ,where are you in the tree of all possibilities? What to do next? That's what makes this video so valuable. Thanks a lot....

@steelpanther88

3 жыл бұрын

@@QContinuuum I'm not disagreeing in principle but I just wanted to point it out for benefit of all viewers. I reckon that DFS brute force with backtrack would still be effective for regular sudokus. Assuming properly formed sudokus with 17 or more clues (with singular answer). There are allegedly some other type of methods like simulated annnealing which use random guessing somehow to solve the sudoku fast. But in principle DFS brute force with backtracking will always succeed in solving sudoku given enough time. In terms of other known sudoku algorithms there is dancing links/algorithm X by Donald Knuth, but I'm not too familiar with its time complexity or how efficient it supposedly is.

That puzzle is called The Setting Sun, its on my list for VB

Pure brute force 🙂 never stops to amaze me, how far brute force can get you.

Try building a MILP solver. Really quite interesting, particularly to extend it for other variants.

So this is what Steve Wozniak do after leaving Apple

From the notes on his whiteboard it seems he is taking the MIT Programming with Categories course :)))

@Evan490BC

4 жыл бұрын

Are you kidding me? Altenkirch does research on Homotopy Type Theory, he doesn't need to take any course. He eats Category Theory for breakfast.

@carlosarchable

4 жыл бұрын

In any case he'd be giving the course...

Dear Professor Thorsten Altenkirch, Thanks a lot for the video and the solution. What I don't understand is how your algorithm manages find multiple solutions for a single puzzle? What would be different for it to return just one solution? I was wondering if the looping of potential possible values in solve() creates a Tree (data structure) of potential valid solutions for solve() to recursively step through? Is that it? Sorry if the question is uber-silly.

I just recently learned python, this video was pretty fun

"you just have to understand the recursion" was basically an entire course in my uni

@lacascadaobregon

Жыл бұрын

Recursion techniques have a lot of depth, that's for sure. Consider yourself lucky for that education

7:31 Italy Map 😂

@ekremdincel1505

4 жыл бұрын

Lol

@iuppiterzeus9663

3 жыл бұрын

I don't get it

@aldison5070

3 жыл бұрын

@@iuppiterzeus9663 just look the map of italy and you will understand

@luigidabro

8 күн бұрын

Not really. Where's the upper part.

The most easy explanation for recursion trick is calculation for ! (factorial). And understanding of it is like a splash in brain! And you start to make magic, like in this video. Thanks!

Thank you for that demo

Hi! Does anyone knows why if I end the function with return(A) (I'm not using global) instead of using print(A), it delivers None? Also, why "input("More")" on the function makes it to generate other solutions? Thanks!

@Leo_banana_sky

2 жыл бұрын

To your second question: It will run through the function, and then back to the previous recursion, set that cell to 0, keep finding if another number is possible. If there is another solution eventually, then print and input(“More?”) If not, return

That's a very cool demonstration of backtracking! Thanks :) Probably incredibly inefficient though xD

@ekremdincel1505

4 жыл бұрын

Yes

@motorheadbanger90

4 жыл бұрын

i did the exact same thing he did and my script is taking forever to run...this is REALLY inefficient.

This amazing please do more videos in Python

I implemented this in C++ and found out that the easier sudoku problems are solved within seconds. But seeing that my code could solve sudoku in a matter of seconds, I became confident and googled the hardest sudoku problem and gave that for my computer to solve. It took my computer 55 minutes to solve that problem and I quickly became reminded of the limitations of my code. PS: My approach is a bit different from professor Thorsten's but it is backtracking nonetheless. I built that before watching this. My processor is an Intel Celeron R and I have 4 GB of memory, if any one is wondering.

Python Beginner: print("Hello World!") Beginner: AYE Thorsten: Let's make a Python Sudoku Solver, not a problem Beginner: ...

@dylan-j-gerrits

4 жыл бұрын

I started to learn python 3 days ago and I just finished a to create a sudoku solver yesterday, with just some basic loop and conditions. Using no import.

@skullkidn64

4 жыл бұрын

I can fluently program in python and starting to move into python but i made that joke because i have a friend who only knows the print function

@Ryan-nq3qp

4 жыл бұрын

@@dylan-j-gerrits If you are a somewhat experienced software dev, which it sounds like you are, then moving from language to language is merely a change in syntax and operation. Object oriented principles don't care about your language as long as OOP is natively supported, neither does the concept of recursion for that matter, as long as your language supports nested method calls. So yeah, I believe the OP was referring to a beginner software developer rather than just python haha.

@dylan-j-gerrits

4 жыл бұрын

@@Ryan-nq3qp : I am a beginner, not only in Python but overall. I've started to learn just a month ago, more or less, and doing a sudoku solver was the first thing I've created.

@abdullahsaid8561

3 жыл бұрын

@@dylan-j-gerrits then you're a prodigy I guess. i have 4 years experience and yet can't do this sh*t

Interesting solution. I wrote a Solver a few years ago that replicated the way that humans would attempt to solve it. It would be interesting to see a speed comparison between this method (recursion) compared to my solution. I suspect that with a simple puzzle as presented here that the recursion method would be comparable, but it would be interesting to see how it would deal with a harder puzzle.

@massimookissed1023

4 жыл бұрын

Yeah, this one looks like a brute-force try 9^81~ish possibilities until one of them doesn't fail.

@ekremdincel1505

4 жыл бұрын

Bro the code in this video is O(scary)

@band-o-lear

4 жыл бұрын

Because I didn't have anything better to do (read avoiding responsibilities), I copied the code presented here and wrapped the same timing method around the solve function. For the puzzle presented here, on the same hardware, my solver completed it in 0.003 seconds (I'm aware that there will be slop in python timing) and this recursive solution took 0.09 seconds. I then fed them both a hard puzzle (as pulled from an Australian Newspaper which had 24 values entered - compared to 29 in the video). Mine took 0.005 seconds (so not much slower compared to the easier puzzle), but the recursive solver took 0.8 seconds, so significantly slower.

@vladalgov1770

4 жыл бұрын

@@band-o-lear Code from this video can be significantly improved: when an empty cell is found Code start from the very beginning to looking for another empty cell. But if continue from the "current" position (there are no empty cells before) - it will be much faster.

@qzdl

4 жыл бұрын

who can golf the fastest solver

It's fine as a method of teaching Python, which is of course what is for. Brute force type solutions are pretty inelegant though. There are lots of algorithms that can be applied to solve Sukudu logically. The normal ones apply ever more complex ones in sequence in the same way as one does solving Sukudu manually. I once wrote one that (I think) was hugely elegant in that each square was its own object and monitored every other square (and combination of squares) that could affect it, changing its own "opinion" of what it could be as other squares did the same. It couldn't solve hugely complex puzzles (which brute force aways will) but it was fun to watch it "think" and it was very fast.

Cracking stuff. I think I understand what's happening here. I'm going to test it out!

When I originally wrote one of these, I looped through and filled in values that I knew had to be correct, because I was counting the numbers in rows, columns, and boxes and if there was only one solution, put it in. It ended up solving about 90~99% of sudoku puzzles on its own, with no further complicated logic. Just counting up what it couldn’t be, and if there is only one could be left, it knew what had to go there. This solution is pretty interesting and elegant in that it does not actually need any special constraint logic to do the solving, which is neat, but I think filling in the table with “MUST BE” values first might speed up the amount of backtracking necessary. But then, as mentioned, this way solves nearly all the puzzles I came across. But at least this would be an interesting combination solver, that only deferred this backtracking logic to get around complicated constraint heuristics.

@FADGhost70

4 жыл бұрын

puellanivis definitely a way to optimise the solving progess but i don’t think it’s necessary here. We don’t have so many combinations that the backtracking would need to go through. Any modern cpu can solve it in fractions of a second or whatever. However if we look at chess we definitely need more than plain backtracking and with example of Go to even be applicable in real time we need deep learning

How does adding the "input()" function at the end give you a different result. Wouldn't the algorithm always find the same solution? I don't get it. Someone help please

@abhishekdwivedi5208

3 жыл бұрын

@8:38 say when solve() was filling the grid cell at position (0,6)i.e 1st row and 7th col. solve() filled the 1, then recursed and filled all of the empty cells in the grid. printing happens after last cell is processed (8,8) i.e if it is empty then it is filled. and here input() function has paused the execution of the program and waits for the user to press enter. when user presses enter. it starts backtracking... It back-tracks and reaches to recursion call which filled 1at (0,6) position. it removes 1 from the cell and tries with other numbers. here when it tries with 9 it got one more solution...

@Leo-sd3jt

3 жыл бұрын

The input function is just there to give the user a pause between the possible grids. Imagine if a puzzle had 16 possible solutions. If the program printed them all out without that input function inbetween them then you would need to scroll up to see each of the solutions. The input function lets you see the solutions one at a time.

One of ze best vizeos! Further to clearify the input('More?') thing: When he prints the matrix we just end one of those recursion steps. The others a still to come. If we get a solution let's say in the n-th step we still have not evaluated N-n steps. The input('More?') just halts the process till someone presses enter. Then it is possible that none or more times in the last N-n steps we get further solutions. So the answers is, we do not initiate something when pressing 'Enter' to the question 'More?', we just proceed.

Grüße und ein Danke an dich, Thorsten :)