Transcripts
1. Introduction: welcome to this course and how to crew eight on DSO solve your own Sudoku puzzle using Beytin. Don't forget to follow me on Social Media, Azmath a second language and Facebook on David Letterman that it's been in instagram. What are we going to do in this course? We're going to learn how to generate a sudoku board in a naive way using Bytom When I say and I have way, I want to say the most intuitive way too great a Sudoku board. However, this may not be the most efficient want. In Google, you can find lots of academic papers where it explains how to grade sudoku boards in more efficient ways than what we're going to do here. But well, after grade in our native Sudoku board, we're going to learn how to solve it with integer linear programming, using by thing again with this library called BU L P. I hope you enjoy this course on that you can create lots off the local boards
2. Explaining the approach to generate a sudoku puzzle: So what exactly is a naive approach to create this possible? These are the five steps we're going to follow to creature naive Sudoku puzzle. The first step is to randomly generate a number between one and nine. The second step is to check if it is safe to put it in the cell with coordinates. I come a day where I n j r in these set. Remember that in python in Texas, start at zero. That's why I and J are going to start at zero as well. If it is safe to place these randomly generated number than we're going to place it in sale I kamajii on increments. Next location on. Go back to step one. If it is not safe, then without increments, who are going back to step one? The last step is once a matric is fully field. We're going to remove K number of elements randomly to complete the game. Okay, so this is how our matrix is gonna look like in python here. I have written some coordinates of some cells. For example, the first cell is going to have co ordinates. Zero comma zero, these cells going to have coordinates three comma one on these cells going to have coordinates. Six. Come on. Three. Okay, so now we're going to buy thumb. And the first thing we're going to do is to import the function. Ran in from the package. Random. So from random Import, Brendan's And these will allow us to generate random numbers between one. And nine. The second thing we're going to import is the famous package Numb Pie As MP as it is conventional to do So Okay, so I'm going to now to find a function. I'm going to name this function. BC column I need is going to accept these parameters. I day and s I is the number off Row day is a number off color and s is that sudoku? Okay, so this function busy column is going to check ive There is a repeated value in the column where we're placing our randomly generated number. So we have placed these random number in cell icom Ajay on dso in column in the Jay's column. We're going to check if there is a repeated value. So we're going to eat e trade through the elements in that fixed Come to do this we're going to create the for loop for em in a range zero comma nine. If em is equal to I, we're going to continue. We're not interested in checking and what happens in when em is equal to I. But if it s m, we're going to fix the column is equal to s I day. So if we found a cell with coordinates and come a day where the value is equal to what we have already placed in cell icom Ajay and we're going to return truth true means that the column is BC or that there is a repeated value in that fixed column. If we don't return true, we're going to return false meaning that the column is not BC, or there is no repeated value in that column. We're going to define also the function b zero. It is going to affect the same parameters i j E n s. And now we're going to fix the row and check. And even that fixed row there is a repeated values. So for an in range zero comma nine, remember that range? The last element of range is not included. So here are numbers from Syria to eight only if any sequel to J. We're not interested in what happens there. But if s I come in is equal toe s I j and we're going to return True, that road is BC or it contains a repeated about you. Otherwise, we're going to return fools if Juries never returned and then we're going to return False. Okay, So now we have checked two important rules from the Sudoku game that we have to check if there are no repeated values in a column or in a row. Now we have to deal with the last rule. We have to check if, in that sub matrix with Dimension three by three, there are some repeated values. So we're going to define dysfunction. BC box But refer to the boxes. The three by three sub matrices formed in these Sadako Bug. So first we're going to check. Suppose we we are in. So I m a J on ICOM. Ajay is contained in the first sub matrix. So I'm saying that for example, we are in here in cell one cannot zero. So this is contained in these first sub matrix on these firsts of matrix contains elements that the row is from 0 to 2 on. The column is from Syria to two as well. So if I is greater than or equal to zero and I is less than or equal to two, NJ is greater than or equal to zero, and J is less than or equal to two. That means we are in the first box or the first sub matrix. So we're going to eat right through all the elements in these box through all the elements in this box and to check if there is some repeated value. So for aiming range from Syria to three, remember, three is not included for an ranged from 0 to 3. So if em is equal to I on any sequel to J, we're going to skip this situation now. If if and and is equal to s I J, then we have found a repeated value in that book. So we're going to return true. If we never return true, then we're going to return faults inside these Eva statement. Okay, so this is a scene now we're going to deal with the second box. So these he's going to be called the second box and note that the rose school from 0 to 2 on the columns go from tree to five. So we're going to based this gold. But here, we're going to modify this. Jay's going to three on the five. And this is going from tree 26 Remember, six is not included. Three is included. So we're going to have here 345 Now we're going to do the same thing with these third bucks . The columns go from 0 to 3 to two and the columns go from 6 to 8. So we're going to copy and paste thes piece of code. This is going from six 28 and these is going from six tonight. Okay, Now I'm going to paced all of these code. So from here toe here we are referring to the 1st 3 boxes in these, like, sup, bro, if we can call it like that now, we're going to deal with these three boxes from here. Know that we only have to change where the column the rows are going. So here the roads go from 3 to 5. So let me identify this. So here I goes from 3 to 5 and here goes from 3 to 6. Here it goes from 3 to 5. 3 to 6 Here, 3 to 5, 3 to 6. So we have dealed dealt with these three boxes here. Now, we're going to deal with these three boxes here, so I'm going to based this gold again, but no. OK, but now I goes from 6 to 8. So here, 6 to 8 here 6 to 9, six eight, 6 to 9. Thanks to eight on six tonight. Okay, so we have created our three functions that are going to tell us ive there is a repeated value in a column. If there's a repeated value in the row or if there is a repeated value in this of matrix we're in in the next video we're going to create now that pseudo query on eater it through the locations in order two great are Sudoku Buffels. So I hope you enjoyed. And what's the next video
3. Creating the function to generate the sudoku: Okay, Now we're going to define a function name Sudoku, and it will receive as arguments and the number of elements we want to remove after we have field all the end times and matrix on. Okay, so the first thing we're going to do used to create an array field with zeros, we're going to bother them. The dimension. It's nine times nine, and we're going to specify that those zeros are indigenous. Otherwise the matrix will be field with zeros as floats. Okay, so we're going to e trade through all of this through all the locations or through all the cells. So well, true, we're going to say conditional one will be If there is any repeated value in the column, we are placing our random integer. First, we're going to the find a random integer. It's an integer between one of nine. So we're going to set the value off the cell. I gotta j to K. And now we're going to set the conditions so conditional on, as I was telling you, will be if there is any repeated values in the column we are in. So we're going to plus his arguments condition, too will be if there is any repeated value in the row. We are in on condition three will be if there is any repeated value being the sub hatreds were in. So only if condition 12 and three are false. That means that it is safe to place the this random number in cell I come a day so you've gone to warn is false and come to is false on on three piece falls on In this case, we're going to break these while. Okay, so we are good to go. We haven't used yet these arguments And I'm going to execute this script with F five. If you're in the deadly off python, I'm going to called these function and there will be a never I know there will be a never You see, I wanted as to be print, but it is not spring. So there is an error. Andi, as ah, question off your class project. I want you to tell me what is the error. So I will give you a hint. These are loops that have ah finish, stop. But this while doesn't have a stop. If this condition, if these conditions are not met. So we're in an infinite Why loop This is the while of I want you to tell me why this is not a work. Okay, so, control, see? Keyboard interrupt. And it says, Well, it's stopped when ever waiting. Condition one. Okay, so this is not a word. So we're going to set a maximum number of situation, so my future will be, for example, and 100. So we're going to include another while So all of this has to be indented break points. No, no break points. And I'm going to define, like, one which will be false on flack to which will also be forced. Okay, So also here in a range after this line, I'm going to set our counter on going to say, instead of saying, Well, true, while count is less than my maximum number off reiterations, I'm going to do all of this. And if this condition is not the mad, I'm going to increase the counter by one. So these while is going to execute until we reach the maximum number off. It'll Asians. So if we have, the discount is equal to the maximum number of situations. So if we're reached, the maximum number of iterations were going to say flag one equals true. And we're going to break, um, this firm from this war also like one. Um, you see, Cook? I mean, I want to say if, like one is equal to true, then flag to will be also called true on. I'm going to break from these 1st 4 So I I broke out from this four and now I'm going to say if, like two is equal to true, then what I'm going to do? I am going to set the ray. That's a dog west again to Syria, and I'm going to start over. Why? I want you to tell me why I am doing this. If not, I'm going to break and then I'm going to print s so I'm going to run this script so we haven't used and yet on. See, Well, it is a little slow, but not that slow because it generated within a few seconds. So, for example, let's see this first row we have 12345678 and nine. There is no repeated value. Let's see, For example, in these first square we have 12345678 a nine. So no riveted value in thes square. Let's CBC score. Here we have 12345 6789 So no repeated by the here. Let's take, for example, these row 1234 5678 and nine. No repeated value. And you can take that. This is a legitimate sudoku puzzle. So this is not that efficient, but it works well, Have, Ah, a gigabyte ram computer. So that's pretty normal. It executed within a few circum. So it's inefficient, theoretically. But in practice it is not that that inefficient in terms of time. So this is the local bustle, uh, solved. Now we're going to had some elements off these off this puzzle. So we're going to set Gantt, you go through wrong again. It's the way account. He's less than or equal twin. I'm going to generate random coordinates so coordinates can go from zero to eggs, so syrup plague, so coordinates that are going to be hidden. I'm going to set them to zero. So if if we have already a coordinate that is equal to zero, we're going to continue. But if not, we're going to set that coordinate 20 on. I'm going to increment the count. Um, on Lastly, I'm going to bring my the D teammates, so I want 15 elements to be hidden. So let's see, Here is the complete sudoku on here Is that Sadako? With some elements hidden. So the Hayden elements are these that are said with zero. So now we have a legitimate sudoku puzzle on the next video in the next video, we're going to solve it, not just by seeing the solution, but with integer linear programming.
4. Explaining the integer lineal programming solution: So now we're going to use integer linear programming in order to solve our sudoku puzzle we have already generated. So we'll create this model for a model when invariable. So we'll create a variable x of I Gay Cade that assumes the value of one. If the cell with coordinates ICOM Ajay contains the number Kate on zero. Otherwise I, J and K can take bodies from 1 to 9. This time, we're going to change in excess. Indexes will start on one at one on well and a nine so we'll have nine times nine times nine. That is 729 variables, integer or binary variables that can only take zero or one as values. So the first constraint is under columns and can be expressed as the following sung these Some is telling us that, for example, if we have already placed the number seven in sale with coordinates ICOM Ajay, then nothing else can be put on the other column on the other ourselves. Of the same column on the second constraint is on, the roads can be expressed at the following some. This is the same thing is, for example, we put the value of two in sale with co ordinates icom Ajay. Then we can't put anything else on that road. Okay, let's see the other constraints. So the third constraint is on the boxes and can be expresses the following double. Some is the same thing as the column on the roads. But now for the sub matrices or the boxes, as we call it, the fourth constraint weren't is that every position in the Matrix is field. So we can't lead any Selby empty. Everything has to be field. Okay, so last but not least, the positions we already know must be one. So, for example, if we have one in sale with coordinates four come on, five, then x 451 must be equal to one. Okay, So for a linear programming problem, we need to optimize and function. But what do we optimize here? Well, the answer is nothing. We just want the restrictions to be satisfied. So our objective function will be anything will be. Zero could be one. But we'll set that at zero, and we can maximize or we can minimize. So after you have understood, all of these were going to the actual cold Inp item
5. Using Pulp to solve the puzzle: So now we're going to actually solve or generated pseudo proposal. So first, I'm going to generate some random bustle here, and I'm going to say I want 20 elements removed randomly. So these will be my sudoku puzzle with training elements hidden. Okay, so now I'm going to grate on your script. I have already won here, and the first thing I'm gonna do is to import B u l b He's library for in your optimization . If you don't have that, you go on search for CMD on. Go on, say it installed B U L b you wait a few seconds and as I already have these package installed, so these will be the message requirement already satisfied. But if you don't have these package, then it will be installed for you easily using big. Okay, so now I'm going to need a least that contains numbers thrown one tonight. So remember, when you use range, these last number is not included, but this one is included, so numbers will be simply a least containing number from 1 to 9 as the strings. The second thing will we're going to do is to say, well, Rose sequel to numbers, calls, people numbers on values equal to numbers. Okay, so now I'm going to create an empty list. Boxes. Boxes will actually be at least off lists. Each subleased will contain doubles, and these doubles will contain the coordinates off each box. Remember the boxes And where These ones. So let's see how to how we can generate this. So, first for I in range from Syria to three for James range from Syria to three boxes. I will add a new subleased Row three. This will be the the row coordinates on the column. Coordinate will be this one. This isn't now four k in a range three for l in range three. So this is least comprehension. If you don't know that you can search in. I think the commendation how to create least like this. Okay, so now I'm going to execute boxes. For example. Boxes here will be at least that's why I told you boxes is a list of lists on this list. Contains doubles and doubles contains the coordinates off the cells in these books. So remember now we're changing. Um, we're changing the coordinates so in excess will start at one now? No, not a zero. And we'll end up nine. Not at eight. So boxes here contain those card in its boxes. One will contain the coordinates off these books here. Okay, so now we're going to actually create the problem. So to create a linear programming problem, we use lp problem and we give it a name, for example. Sudoku problem. And we specify if we want to minimize or we want to maximize. So it doesn't matter. Here, we can minimize or we can maximize. We don't occur. Uh, in this case, now we're going to great the variables we use these with. I'll be viable that dicks, we give it the name. These double well say to these functions. So x will be older combinations of values rose and cold. So remembered around nine elements here and then elements here and then elements here. So there will be nine times nine times nine, 729 and valuables. We say that they can only take the value zero or one at that. They are into yours. So let's see what happens if we want to see these variable X. So it's this quist, and it's a Dictionary of Dictionary of Dictionary. So these first variable x of want, want want is saying, um in the cell with coordinates one comma, one the value off one. So it can be one if we place one in the in the cell or will be zero if we don't put one in the cell, for example, let's take this eggs said 154 So this is telling us that four is in the cell with coordinates one. Come on, five. So if these variable is equal to wonder for displaced in that cell on, if this variable is equal to zero than four is not placed in that cell. So there are a lot of marbles here. Sure she'll be 729 valuables. Okay, okay, so now we're going to at a new objective function is will be zero. We're going to say arbitrary, objective, objective function. It's every trying. So I'm going to bring to rob. It has the titles. The local problem. It is of the type mini Mice on. We're going to meet my zero Onda. We have to specify the gun strengths. So that's what we're going to do now. So we're going to beat rate through the values. Um, these four will give us all the constraints of the second type. So maybe we shall start with the 1st 1 with go strains on the columns. So I'm going to start that for Gaitan calls. So what we're going to do is the full we're going to add constraints will be some off xk I and J for I in Roath will be equal to one, and we're not going to give it an a special name. Now we're going on these second constraint, so we're going to add look more of constraints sk I and J or Jake ghosts. It's going to be equal to one, and we don't give it a special name. Lastly, we're going with the third constraint these these one. So for being boxes. So that's why we defined that least of let's called boxes, because it will be easier. And we won't need a double somebody who need only a single some So x. Okay, I m j for the stubble. I come a game, you be. So this has to be actually at least, and this has to be called one, and we won't give it a special name. So we're going now with 1/4 constraint. So for I in rows for J in Gulf, we're going to add these comes strength X. Okay. I am Jay. Working values is equal to one. Okay, so now we have these fourth going straight for constrains. We need now these these constraints here. So, for example, we're going to see where is my at bustle? Here's my puzzles. So, for example, here we have, um this is cell with coordinates. One Come on, one And we don't I mean, here we have here. This is sale with coordinates. One come for and it has the number six in it. So x off, one off six. Come on, one come before. Because that's how we define the verbal is going to be equal to one. So what I want to do is I want to add this country, rob eggs of six. Uh, one. My four will be equal to one. So as you may guess, we have lots off constraints here. So for example, now we have to adhere that for example, these will be eggs off eight off. One off five is equal to one. So I have to add eggs of AIDS. One five is equal to one. So and we have to do this for all off these numbers that we already know. So that's very manual work. So I'll pause the video here. How finished a better here and in the next video you will encounter with all of these constraints added, and we'll see how to solve that Sadako possible and write it on a txt file.
6. Writing the solution to a file: Okay, so now I have added older remaining constraints. As you can see, there are lots of them. That's maybe because we didn't hit a sufficient elements in our original Sudoku puzzles, so we must heed more of them. But that's okay. Once you master the art of copy and pasting and Onley changing values, then you can do these within five means. So the next step is to actually solve this so we can call on the function self abrupt. And then we want to see the status if it was optimal or if it was invisible. So let's see. We call hell be establish rob status. So let's see. Well, I have already executed these two times on yet it was optimal. So we're good to go. The next thing we have to do here is to write the solution in a txt file. So first, I'm going to create that txt file by calling the function open. So look wild. The T X team. We're going to open it in write mode, the w means right mode. So we're going to write in it. So first, I'm going to eat the rate through the rose. I'm going to add a nice little format. I'm going to say that when I is equal to one or when I is equal to four or when I is equal to seven, we're going to write these like horizontal bar. We have to copy and paste this on this we add in your life. So how many dashes are there? 367 Okay, and then I'm going to eat rate through the columns on, then through the values. Okay, So if I know that the value off these binary bearable is equal to one, then we should bring K in the board. Escape is the number that is placed in sale with coordinates. I m. A. J. So first we're going to add a format. If gays equal to one or J is equal to four or J is equal to seven, we're going to write very cool bar on a space, and then we're going to right the value of gay less in the space. Then, if Jay's equal to nine, I have to write again the medical bar, but with the new lines. So vertical Bora with new line. Lastly, if we're going to write a very I a horizontal bar like this one. So this is the art of Kabi basting. I'm going to so right here. I'm going to close this fire so the watch don't go out that close. So let's see what happens. Hope I don't have any errors, No errors. And as you'll have here, the solution of my sudoku puzzle. So let's see here. This is the solution on this is dissolution with integer linear programming. So you can see here there's a 719 years of 71 and nine, for example. Here she'll be a four. There's a four here on. That's the solution we have here. But we didn't on the sea the solution. We created the solution with integer linear programming. So that's all I have to teach to you. I hope you enjoy this course on. Don't forget to do that class project