It is quite fun to do it.

Ss of programmer computer scientists You can you can have different fun in, like writing a program which sauce it.

I mean, that doesn't mean that obviously, was a program.

If you if you if you want, it's just enjoyable.

It was a puzzle, but also fun till I support you.

Sudoku and the Number puzzle.

So here's an example.

So we see this great, and there's some numbers fit in, and the goal is to fill in all the remaining numbers every in every square.

That should be number from 1 to 9, and the rules of the game is that you cannot use the same number twice, you know, on a column on one off the squares.

So, for example, if you look in this middle square here, you cannot put a run in because there's a woman.

Here is a to hear.

If they hear four 555 is an order, actually, five would be possible.

There's a six year a seven here in eight here and nine here.

Hence, what do we do to be 55 and now we can continue this and obviously easier.

Sometimes you have to be a bit more clever.

And yet this is one of the examples for using our courts and our python book us, where we show the idea of what's called backtracking computer Science.

And actually it uses another to use a magic trick I've been talking about before.

And that means the magic trick is Kirsten.

I'm using Python here with a thing called Jupiter and I have pre cooked, but it's like the's chests and TV.

They do it like it's a little thoughts, which is too long to prepare their robbery.

Two and 1/2 Danza's First of all, I d find.

That's good.

Which is exactly the same grit as we have seen as a list of lists to the manger.

They're very basically in python, and then, actually, if you print this, it looks very ugly.

Looks like this, and that's a very readable and that's probably because we want to use this to output the solution.

Now you know our call us we actually liked Ah, Delia.

Why printer for this was a secret.

But I thought to be a bit quicker.

Today, we just shed a bit.

We employed a library quote, lumpy, numb pie and this escort definition of the Matrix.

We can just use this matrix to print this grit in the baby can actually read it now.

Another pre cooked ingredient.

It's a function which determines whether, on a certain position we can put the number so have got three perimeters by Ex N N.

So is to vie first and extent because it's the order in which T embassies appear to use this presentation.

So why exits the position and end?

It's a number, and it returns to if it's possible to put this number there, and Ford's otherwise and what it does is it.

Checks first go and then checks the column and then checks this career on the digits are not so important, especially checking this career.

It's a little bit, Yeah, Clyde's a little bit off cleverness, but that's okay.

Okay, let's tie possible.

We can, for example, ask It's a position in the middle of its chest, indexed for four, because we can't with the 01234 Is it possible to put a three on hopes, answers.

It's not possible.

No, this is possible in the same position to put a five.

It's, too.

That's what we expect.

Okay, so this is little helper function.

We won't provide so over.

So I wonder about the function.

Sort of no apparent.

Meet us because we're just working on this global great.

Maybe let's tell Python it's global and what do we do?

So how can we solve this?

My first of all, we have to find an empty position.

Which means we have to do is to loops for y in range nine.

That's Python for counting from 0 to 8, able to eight nine possibilities.

And for X, we do the same.

Okay.

And now you check if there is a zero at this position.

If great.

And here I have to save eyes of the wife.

Oh, and the x column is this zero?

OK, so he was a blank.

We found a blank.

So what do we do now?

Now I would go through all the numbers I can put their, which are the numbers from 1 to 9.

So four and in and I have to say range one comma, 10 That's always a bit funny because it comes from one tonight.

Why is it 10?

Just it counts to run before it's like if you do, loop was in less than it doesn't get to that in just that one more.

Okay, so now we have to check, if possible, in position by Kama X comma.

And so can we put the end there?

So it is possible.

What do we do?

We put it there were not.

It's possible.

So let's put it there.

Okay?

And no.

Now we have reduced the problem.

What?

We have one.

The fleece clear.

Less.

So that's a good call for Rikers in Just called the same function idea.

But you just called something.

So now, Because so often, the tie to find the next and the next and the next empty square part of kennels have happened that our choices are not really good.

We get into debt, we cannot feel the letter off the great in this case, we return.

And whatever you do go, huh?

We take this number off, we make it blink again.

It was it was a bad choice, right?

This is actually accept what's called back taking you try And if it turns out we cannot complete the solution.

If you go back, you take it out.

And you know something interesting.

If you have tried all possibilities for for empty square and none of them worked, that means via in a dead end.

But you have to Quito you go back to ever called us.

Now let's see, we have gone through the school.

Great.

We have looked at all the fields and we end up here.

Now the question is, how could we end up here?

Because whenever we find position and we go through all the numbers we return So the only way we can add up here is if there wasn't an empty space.

Well, which for you finished and we're finished.

All of you have to do.

You're finished with the settlement.

Okay?

So know what happens after after we plant return.

This would mean the the pretend.

We have failed, right?

And we look for the next solution, which is actually quite nice and means we're going to find all the solutions.

But I want us to first displays a solution before we go on.

Was a little trick here I say in court and say something like more.

It's your choice.

I mean, there, stop displaying this.

And then if you return to Prisca, turn, get more solutions.

Okay?

I don't see what happens.

It's called soil.

That's quite exciting, right?

Oh, that's the solution.

All the empty ex clears off.

It was very quick.

So we cannot say more on what's going to happen after you say more.

It terminates.

What does it mean?

It means down any other solutions.

Okay, which is a future off most good sudoku puzzles.

That there is only one solution.

It's actually interesting to see what happens if we remove some some numbers.

That's just use it as a cop.

Is this good on?

I'm going to remove these two numbers down here.

Okay, So what happens?

So here you find a different solution right here is the one down there which we couldn't put there was a seven already, And if you're not because return, you get original solution, and that's it.

So in this case, we get exactly true solutions.

If you start to remove numbers, then you give more freedom, and that would not be a good local puzzle.

this idolize me?

I mean, assistant example associate for this general approach off using backtracking.

You have a partial solution.

You try to extend it if your life it's solution.

Fine.

Otherwise you'd try to extend it.

Call yourself occurs a flea.

And if you are getting in a debt and you just return and then higher up, you try different solutions.

You undo your back like it's like if you're an amazed, you know, you go.

And you remember I was there and made a choice and I made a choice.

And now in a bag, and I go back to my previous choice anti V, as a solution.

That's exactly what you're doing here.

We're not simulating how human would solve this problem.

It would be possible to do this, using all these constraints to find possible solutions to program.

This is actually quite complicated.

So instead we d'oh is pulling a silly, stupid, basically systematically ties all possible solutions.

We're backtracking, but if you get a very business, if you could've Avis, it's very, very simple.

I got a very short suddenly it is a bit I mean, there's a bit of point.

Do you have to get your head around this leak.

Oceania, once he understands us, is really very simple.

The same idea works for lots of problems, in particular for puzzles.

And here's one puzzle, which I find any quite tricky.

It's called Club Ski, and I don't have this game, but you can obvious move one off these blocks at a time.

The goal is to be able to move out to speak block on the bottom, and you can take out any also other pieces and it seems almost impossible.

But it actually sort of Ah, and so my challenge is right.

A typhoon program which you suspect working to solve this puzzle.

And there are three places American put the disks, and the goal is to move all the disks from here from A to C, and each time you can only move one off the discs like this on the size is going to be too.