Stanford Lecture: Donald Knuth - "Dancing Links" (February 22, 2000)

OK, that's number one. Is this working? I think it's working OK. OK. So here I am, my computer musings for the first time in several months because I was away at M.I.T. last fall and I'm planning another one in April. Which which, you know, if you like this one. You might come back in April if you don't like this one. It's one April to me, completely different. So you might like that one anyway. Today, I'm talking about some dancing links, and it's different from the one in April in in in in Apr

il. The title is going to be the joys of art and Politics. And and it's only about mathematics. Today, I'm talking about something that's extremely simple and amazingly simple fact. You might say. It's so simple. Why is he talking about it? But the reason is that I'm responding to this cartoon that I tell you might have seen that there's a lot of practical examples you can use. No theoretical stuff. And that's that's today's the actually put these lectures. And I, I prepared this thought for in

honor of Tony Hall, professor of law at Oxford, whose retirement last last December and on. And Tony was the person who. Wonderful. Thank you. Tony was the person who taught me a lot about data structure. That's what he, I think is largely responsible for the ideas that we have now in high level languages for good ways of having links between, you know, pointers between different parts of data structure and on. And so naturally, that was that was the topic that I would that I would choose when I

had to give a talk in his honor. So here I of course, I have to tell you about the old days, because I'm I'm an old perving, a little timer nine. And one of the things that was important with that, and I prepared this stuff for Oxford technology. Neistat for technology. So, I mean, I had I had overhead transparency at Stanford. It works much better if you if you do it just on paper. And I had. And so, like, I should really go back to, you know, I had to work so hard to get these guys. But it is

much easier to just you know, I could just bring the book here in and talk to you about that. But this was a famous book that really changed the world. I came out about 1970, 71, and it would end the horror with that one that one of the one of the authors. And as good [INAUDIBLE] to handle, all of them were there at a conference where we where we presented this paper. And so also I wanted to mention as many names of people in the conference as I could. So I started out with, you know, showing t

his book, which is which taught us a lot about about data structures. And then, in fact, Tony, Tony contributed the middle chapter to that book and also the third chapter book, which goes north on data structuring. How but actually, I wasn't going to talk about that chapter. I'm talking about the last page of the previous chapter, which was by Gary. Not not as good [INAUDIBLE] to have this masterful chapter about how to how to write programs, you know, in a way that helps you get them right. And

and also, you got to get all good, all kind of characters. It's a good program. So what they meant by a structured program, and that's his main example at the end of his paper was the eight Queens problem. The problem of putting, well, a generalized N take a chessboard and place that in by an eight by eight and you place the end queens or N objects so that there's no two in the same column, in the same role in the thing diagonal. So it's sort of like the queens can't attack each other. And this

this was a I think it still is a fairly a fairly standard problem used for teaching people about program, because it because it has some interesting issues occur. And so here was this program sort of at the at the climax of his of his chapter there. Now, a few years later in this trial, all information processing letters, this is nineteen seventy nine. There was an interesting article by two Japanese authors who who gerb to go back to Dykstra's. A queen's problem, and they rewrote it and and th

ey made a change that made it run more than twice as fast. And it's it's it's it's a nice idea. That's the main idea that I'm going to talk about today. I'm going to call it Dancing Link. And they and so with the program about the same length of time as they were able to change the data structure in a way that would actually speed things up. And even on a bike, you're not a small, small, small one. It would speed it up by a factor, too, on a larger run to do that by a larger factor further. This

was hit tomorrow and not no off. I know Professor Noji ties very famous. I think that he's leading his project for the best computer girl, playing, you know, wins tournaments in Japan for many years. I'm not letting go. This was, you know, at the end of the 70s. What was this great idea that they had in the paper? Well, it's still, as I said, it was it was extremely, really simple. And it applies to any any programing language. And and when you're using the leaflet. So, Sara, one of the main ma

in ideas in this processing of any kind is to have pointers to everything from every note, a record X, you have a pointer, l think to the to the notice on your left and the pointer arc to the note that's on your right. And so if you want to delete X from the list, you have to change two pointer. You have to, you have to take the thing that was to the right of X. You have to change its left pointer so that if it goes to the left of X, it's not point X anymore. And you have to. And similarly, the

guy who is on the left has to now point on the right to the guy who's on the right of it. So for every programmer who's ever done list, make list knows how to meet. An element from the daily link list is one of the main main advantages of a W like list is that you can delete something without knowing who's pointing to it, because the L l exactly who's pointing to you from one side of I'll tells you who's pointing from the other side. Just make me few changes and X is out of the list. Now the the

simple idea that I want to dwell on for the next hour is that you can undo this operation and put X back in the list again very, very easily, just knowing X. And if you don't change that, the memory of who who worry is right and left neighbors at the moment. I left the list. So if you do these two operations, you get these both. And if you do these two operations, they undo the things at the top. I'm not sorry, TV people. We've got to have got to be able to do the right thing here because. See

both of them. Really? What do you like this here? Go go ahead. So these two simple operations put us back in the list again, provided that, you know, that everything else is nothing else is intervening. In the meantime. So now, in a way, as I say, this completely trivial. All you have to do is restore the the left pointer on the right, namely back to X again and so on. But the but the beauty of it really comes to you. The more the more you look at it, the more you see that it's great that you th

at you didn't have to remember very much about. About all you had to know is X. And you can put X back in again. A lot of times when you're when you're trying to undo a sequence of operations, you have to remember the previous state. You see like you if your story, if you if you're trying to undo an assignment statement, the sign the statement is replaced A by B. You have to you have to save on some stack. You have to save the previous value of a. And then you have to also stick to save the the

address of a. In this case, you don't have to. You don't have to do that. Usually you don't. You have to save the value of X because your algorithm will know what X was, because X, X occurred in some because of some process. So all of the examples that I'm going to show you explain how how this is a great idea for undoing things where you have a computation, where data structures are changing a lot. And you can you make some changes to but you want to take back those changes again, and that's wh

at the end in that end, the end when you start looking at the way algorithms work when you're doing this operation. These links seem to be dancing around and around in some glorious choreography. And that's why I decided to call is just dancing linked the fact that I'm writing volume four of our computer programing? I hope I find that that this is a technique that uses so in lots and lots of programs. So I figure I better start talking about it. So I thought if anybody else finds new stuff about

it, then I'll then I'll, you know, it'll it'll be in a mature state by the time I'm finally ready to publish that the the the by now. In a way it's bad programing practice though. I mean some people frown on this idea of when you delete X from the list. The traditional wisdom says that you better clean something. You better clean yourself and reset the length of X next and I'll back to zero or something because it's dangerous to have a pointer into the middle of a list. If you think about it, t

he reason that this sort of blows your mind that the reason is it. The reason I said aha. When I looked at this Japanese paper and saw that they were doing it was because there is no elevation of X don't don't have the semantics. But, you know, what is the meaning of elevation of X when X is a member of a list. You know, elev X is which is the pointer to the person on your left are X is point of person. You're right that X is out of the list. What elevates and I mean. Well, it means that this is

these are the people who used to be. Usually they're. But they're. But but, you know, the algorithm has gone on, made other changes to the list. And and so l l our X sort of have a historical interpretation. But but they don't have an interpretation in terms of really the present state of things. You're a provocative example, and the first one of the other people in the audience that day was Dana Scott. So I showed a report that he wrote when he was a graduate student at Princeton in the 70s. I

I gave this talk at M.I.T. in November and half the people didn't know who Dana Scott was, which I thought was rather surprising anyway. Speaking of semantic standards, one of the people who who did a lot of the pioneering work on what computer programs mean in so many ways, he's an he's a professor at MIT. Sometimes the tax burden, Carnegie and so on. But when he was a grad student, he wrote this this report called programing a combinatorial puzzle. And the puzzle that he worked on was called

pen terminals. And that was another thing I found out at M.I.T., half the people. Can you zoom back? I want to see people on TV. Can you. Yeah. Good. That's good. That's a lot of people had never heard of Pentagonal before. I'd like to take a poll here. How many in the audience are familiar with Penn Terminal? I'm not familiar with, what, 130? I see. This was all the rage for so long. It was one of the most popular toys. I mean, so many hours of pleasant recreation going on with twelve pieces of

colored pieces here. There are the twelve ways to take five squares and put them together. And you know, dominoes have two squares and dominoes have three and so on. And dominoes have pie. And in it in the 50s when when Dana Scott wrote this this report. People have found, I don't know, 20 or 30 ways to to put them into a into a chessboard, leaving the center hole open. You see, I had 12, 10 dominoes that covers 60 cells and you got 64 all together. So it's gonna be four that are uncovered. And

it and it's once you see a solution like this, it looks easy. But you can you can work a lot for a long time. And if not if not coming out. And so the people we're finding solutions and they would write it down in a book. And, you know, and then somebody say, oh, here's another one. And so, you know, there was a it was a pretty good exercise for the computer at Princeton in the 50s, which was called a maniac. Well, that actually wasn't called a maniac. I mean, it was at Los Alamos, but they and

they had a similar machine. But all the grad students call it the maniac. But the let the people at Los Alamos really. So they had the only real maniac. But anyway, it was it was it was a little machine. Quite interesting. I gave you my paper. I see exactly how many. I think it was 10 K plates of memory or something like this. And 40 bit words. And it was not at all obvious how they were going to solve this problem on a little machine like that. And Scott was very proud of himself, actually, th

at he could that he could find all the solutions in something like three and a half hours. I believe it was on on the maniac. So so he wrote this report now. Now, if you understand that the quote like a phenomenal problem is that he worked on trying to get these twelve pieces into the into every further system. OK. Now, let me let me show you another way to state that problem, and that is I can way to present the solution to that problem would be would be these are these numbers. So the dominoes

have the fall and dominoes have have names from letters. They look like like this the kind of here. It is called an eye. This one here is called X. This one is called the U. In fact, I have all the letters at the end of the alphabet seems to work out. You've got a p q r s t u v w, x, y and Z content dominoes and then had to have iron and then a couple others thrown in. But here's the P and then the Q. Well you to be a little bit creative. I think this is a is slightly higher than ours. Is this

guy here upside down. And but the others are, are pretty, pretty obvious to F. S. Right. And then a t, of course, is this guy. And you I showed you in the V is also obvious. This is the blue V w it's green here. X is the one I showed you. And Y and Z is. That would be not compute with us. Okay. Maybe s is a little tricky, I guess this one, they call it. OK, whatever. You had to have names for personal in this case. I said when I say I 11, 12, 30, 40, 50, that means that that position one one one

two one three one four one five are filled by the. I can't comment on anything common. Similarly. Here's the end. Then they call this an innocent 16. Twenty six. Twenty seven. Thirty seven point seven. Can get the idea that this is this. These are numbers also reflect the idea of of this diagram and what you can. The point is, is that what we have here is an example of an exact cover problem, meaning that all of the are part of the letters occur. Exactly one. And all of the all of the places in

the chessboard, except for the holes in the middle occur. Exactly one. So the one one one two up to one eight two one to two up to eight and so on and before one, four, two, four, three or six, seven and eight. All of those two numbers occur here. Exactly one. And all of the twelve letters occur. Exactly one. Now if you if you so you can make up a gigantic matrix of zeros and one that has twelve plus sixty columns to it. Seventy two columns, one column for the letter I, one con four letter and

it's all in column for six to twenty six. All these things. Seventy two columns. And then the rows will each have six ones in row six. Say which columns are being covered by that row. For example. There'll be one of the rows would be I. Eleven, twelve, thirteen, fourteen and fifteen. You would have ones in those six columns and zeros in the other fifty six columns and so on that. So I think I forget the exact number of rows. It's I've got it in the paper. It's twelve times. I don't know if it's,

I don't know, 400 million or something like this. Each row has six ones in it corresponding to which columns are covered by that row. So the exact cover problem is a problem of taking a huge matrix of zeros and ones and selecting a bunch of rows so that every column is in exactly one one row. Now, if you add up the rows that you've selected and you get one one one one one, one one. That's the exact cover problem. And so the pen Parmeno problem is a special case of this exact quote is a special

case of this exact cover problem. And it has has a genetical structure, too, which is with a lot of things that most of that cover problems don't have a nice geometrical structure that would say that, you know, that the that you can slide a piece to the right knee and there's much more there's much more structure in this problem than there is to the general. Over. But I'm going to talk about the impact of the damage. Now, this. But here is only one. As far as I know, there's only one way to do a

n exact color problem, and that is by trial and error. You try to choose a block by some means or other. Some rows are more are more useful choices than others. But you actually have to choose some road that, you know, that has a one in the first column. You got to cover that counts done also. So you have got to choose the road by some means or other. And then and then that covered a few columns. And that allows you to reduce the matrix. You say, OK. Those cons are covered. So I don't need I don

't need to I need to worry about them anymore. And then I'll have a smart problem covering the remaining columns and continue until all the columns are covered and keep out. Keep on going by trial and error. No trial and error mean doing an exhaustive search process. And I. I'm so happy not to have to have had postscripts that I can actually look at at three of trial and error. I you I program these things as a some of the first computer programs I ever wrote were to do a search through all thro

ugh all through a whole bunch of possibilities. But I never was able to visualize it until this year, until now, because we know it's OK. Just tell the tell the computer to draw the black tree with with how many ever tens of thousands of branches. And here you start out with having made no decisions and you have this case. That's a two way to proceed. I think this corresponds to to taking the putting the X in this position. And then you have to then you have only two ways to to feel some others,

some other square I get with you. So once you've done that and you have a few more checks of possibilities and two more female more and so on. And finally down here, there are 19 little thin lines at the bottom. Of course, line two solutions. You've actually. They're actually 19 solutions to this part of the placing the domino in this particular place. I think that had 19 solutions. And so this is what what it looks like when you're when you're doing a trial and error calculation like this and

a three and a half. The standard way to do this is called backtracking. So you go here and you go down here and you try always to get stuck. You go back up again. So here we didn't get a solution. We have to try again. And going back up again, make it choose another thing. And and the dancing comes into it because I have data structure representing the current state of the exact other problem after I've covered a certain number of wrote a certain number of columns. Then I have to delete certain

rows that I can't use anymore because they would double cover something and I have to then have to have some structure. Tell me what would be a good of a good rotu to choose next. And so I need data structures to keep track of this process. I'm going back and forth. But, um, but in the end, I think it is better I have to unfavorite again when I decided that, you know, when I decided that I that I'm done with the with one choice, I have to go back to go to another. So this is that this is a compa

ratively small for for for a 21st century. But in the in the fifties a search like this would take would take more than an hour. Let the search still take a microscopic search like this will take a microsecond in the 50s. Here. No, if it's less than that right now, my my programs look, for example, on my on my opinion, most theories. Which is five hundred megahertz. We'll do 10 million of these. Dancing link operations for. OK. I'll call an update to the data structure which which really means t

o take something out of a list. And then later on put it put it back in again. And it's something and it is sort of I think it with something like 70 memory references altogether or something like that. I'll call it an update on the job, because I, I have a I have a four way link data structure here. I'll explain it to you, but I have to take something out of TULIS. I have to take my leave. Something I could lead out of a horizontal lift and I have to do a vertical lift and up and then I have to

put it back in again and and I have to change the account that I'll tell you about here. So the total number of memory references, John, is the there's something I forget the exact number. Some like 17 memory represents an update. And I and my opinion was doing 10 million updates per second. So that was even today, it was, you know, one tenth of a microsecond for for these 17 memory. It was it was it did seem to work well with the with respect to the cash and stuff, too. Now, let me let me show

you this data structure as an example of where you can get the idea that dancing weeks isn't only for a small list with Eleanor, but it actually applies when you head into the middle of a complex data structure. We have lots of W links. And here's an example where we have an exact, very simple exact cover problem has one, two, three, four, five, six, seven columns, one, two, three, four, five, six rows. And the idea and the place where you have all the all the activity here, this corresponds to

a one in that matrix of zeros and ones and where you have just to pass through those are zeros. So so far, you haven't put together with three each row. You have a list, a doubly linked list of all the what are all the columns in a row that have one thing. This this points to the right. This points to the right. To this guy just points to the right. So this guy walks around at the end. Can the TV man zoom up close on UNEF? Can you zoom in? Yeah. Good. Let me even close the way up, you go to the

max. That's your that's your best. OK, so you've got four. You've got four pointers in a. What one is to the right. One is to the left. Then there's one up and one down. So similarly for each column, you have a list of all all the growth that they have, a one in that car. Then there's a header. There's header columns. There's a hetero at the top. These are these are this Padstow, not part of The Matrix, but it tells you the name of the column. And it tells you how many entries there are in the

column at the moment. And so these headers are also listed together. These are things that we have to cover. And there's one more note out here which which is a header for the whole homemaker's. So this is the quadruply leaf list in a sense of the deviling for the left and right, deviling for up and down. Now, suppose that I that I have and I have two ways to cover column one. So in order in order to do the after one, I'm going to do is the effort covering it. I want to take this this column out

of this list. And so I'm going to do dancing link operation. I'm going to do a removal operation on this on this element. So if you look if you can see the Red Hook red, there is this zoomed up the map. OK. So these these are short circuit link. Here is new situation after a has been taken out of that list. So, you know, we just changed to link. We changed the link and Visa jumps around a link from his head and also jumps. Right. And no matter which of these two roles I choose in order to cover

, really, I'm going to have to take this guy out of the list. Now, I suppose I suppose I choose the suit. Now I can march down this road a and and see all the choices and I'll try this role. And after I and after I try this or I'm going to try this. But first of Alesi, if I try this, will that means that I'm not only covering relay, but I'm also covering roadies and I'm also covering real G. So now I'm going to have. So now I'm going to remove this from the from the Matrix from column B. I'm sor

ry. I'm going to I'm going to remove. This from The Matrix. And the. We. OK. And so. Why am I confused here? And I'm going to. Clearly had deleted this note and this note, and I'm all for deleted this no delete every square which is covered by. I. OK, so I deleted bith and I deleted this now. But why am I so scared me? I believe that's right. So I've only I'm only in the middle of an out of of of an operation here. Here I've gone the next step and I've deleted Colin V as well as well. But I don'

t understand what I did, why I didn't do this. Eliminate the bottom here. I didn't believe this day. Why am I doing this? This is Filii. I thought this was this was so easy that I didn't bother preparing. Know nothing about you. Okay, so this is this is American. But let me let me just go back to my notes here, so. OK. So first of all, I did was to move from the draft. Well, what in the heck? This is an old graph. There you. All right. OK. Now, this one fell after. After Column A has been covere

d. Oh, I see. So. So I am a matter which element I thought it was so obvious, but I'm going to cover Colony and there's going to be two ways to do it. But before I decide which of those two to use, no matter which of these two I have to do, I'm gonna have to remove them. I will use them more than once. And so I'm going to have to remove all of their entries from the from the Matrix. And so so this guy also had had had had these two in The Matrix, just they also had this one in The Matrix. So I'm

taking these. No doubt. And then, you know, because no matter which row of those two I choose. I won't be able to use the other. I won't be on the cover column in a while. So I take out these these three things in order to take these three things out, and I have to remove them from the vertical if. And now then when I go to this illustration, we have we have Luling. Then I decided that column's DNG are now are not to be covered because I'm choosing this one for want to cover columns. DNG. And i

n that case, I take DNG out of the top out of the topless light. So I believe in the lifting. And I also and I also then March, march down D and everything like here here's something that's still in this deep thought. So I have to take out these, these two elements because, because these two can't be used anymore. I'm never gonna use this guy. And similarly, Angie, I have to take out. I have to go and see if there's anybody left in G. To D and you have been covered. Well. I'm not sure why I didn

't do anything to that guy. I have to think about. But the main point is that, Mike, my algorithm, in order to do this exact cover problem is, is walking is walking down the list. Walk down this list and find this note and it goes to the right and delete these. And then it goes down here and it goes to the right and left. So. So the algorithm, which, as you know, is written down in the in the in the in the paper in detail. Here's the order to look something like this. For each user. So they walk

down a list and you do these these changes and and these are just the operations of removing things from the list up of down, set up and down. This is the the the idea of removing all of the list. Then of undoing it is the opposite. And you go in the up and you walk through the data structure and the other order. So after F f you want to restore the original original thing, whatever you did when you were marching down this way and then and then marching to the right. Instead you marched down th

e list upwards and go along to the left and put things back again and and magically all of these pointers that you haven't cleared to zero are just set to the exactly the the data that you need to to to put them back into the list the way they were before again. So so that the point is that I can make all these changes to the data structure. Only remembering one, not one one node. And from that one node, I can follow its links and and that and it will the list will continue, will start to regene

rated itself again without. And just just before I leave, just in time for me to conceive another link in order to continue on doing that link has popped into place. So if I just if I just run my album sort of backwards, even though I have no idea what the semantics is of the Elna and you and the pointers in these in these lists anymore, I don't know what they mean. But I do know that if I if I, if I if I do the dancing linked algorithm in the opposite order from the way I do for undoing as I di

d doing, I'm guaranteed that it will actually restore the thing. Well, the interesting thing with the point of view of people of approving computer programs. Correct. Is that the traditional idea is if it is that you you have an invariant that describes the meaning of of all the of all of the players in your you function. And then you you prove that this this remains invariant. But here I don't know how to write down that ingrains too complicated. But I don't bother with it. I just say I don't k

now. I'm not going to tell you what these pointers mean. I'm just going to tell you that it is clear that if we write that whatever they whatever they do, which if you do this, operate this operation is the inverse of the other one. And so so if you have a sequence of of operations one, two, three, four, five, six, seven, eight, nine. And then you. And then you go do nine inverse. Agent first seven inverse. What are you going to get back to the beginning. But I don't. But the actual mathematical

writing down of what the of what the relation is on these pointers. That that seems hopelessly complicated. And in the end, it's actually better to have this operational definition rather than explicit. Going through what the what the meaning is. Well, let me show you some examples. Now, the f the next slide is it is for nostalgia for the evil people in the audience. Remember when the communications of the ACM was? It was an interesting journal to read. And back in the 60s was one of the glory

days of the cover. In October, 66 was about 10 dominoes. And how many would you know? And John Fletcher at Livermore as probably the champion program of all time as far as the fewest machine cycles, to find all the solutions of packing this whole phenomenas into like here's a six by six by ten array. And and he did this by by are writing some very interesting recursive macros in assembly language that would expand into an inner loop that had a hundred instructions in it, but they would use the m

achine very efficiently. And if you if you study the way, then it starts out as. Maniac in the 50s. And then you study the way Fletcher saw this problem on I.B.M. 70, 94. In the 60s, he tried to say how wrong with their programs. Take a you know, on a machine that we have right now. I would say that it's that they put their programs probably run five times faster than my my dancing length program. However, it's because of the phenomenal problem has a very special kind of a cover problem. You can

you can exploit the geometry of the of of of the situation and there and, you know, and simplify it. But when it comes to the exact cover, problems cover lots and lots of different things. And when it comes to these things, the program actually starts to win big. And it's also because as the size of the problem gets larger there, their method was not it didn't use any any tree pruning technique. That would be based on a number of choices available. You see, if you're doing an exact cover proble

m, if there's some column has only one way to be covered, then my guess what then you know, then you better choose that row. You're forced to do that. But but the methods used in these programs would always say, well, just find the the first fell from the top to the bottom. That isn't covered so far. And then and try to feel that in all the away. And it's a fairly good heuristic better. But it it doesn't use it doesn't use the the symmetry between pieces and position. If you if you remember this

this slide, if the job was to was to find some ways to say that you had all twelve of the letters and all 60 of the positions, but there's no real difference between letters and positions in the exact cover problem. So so if you look at literature on on on people who have who have been who studied way through, who solved different kind of battalino problems and there's a large literature about it, though, they'll often have two kinds of arguments. One is to say, well, there's there's only five

ways to fill it to fill a certain cell on the diagram, or they'll say there's only two ways to place the IPN, Tommy. Those are when you look at them as if they're cover from. Those arguments are both the same. They're saying that there's only a certain number of ways to cover a certain column of this of this thing. So of the duality. So so what? So sometimes the next branch should be not on how to fill a position, but it should be on how to use a piece. And those are exactly the same things. So

when we get to larger and larger problems, the technique of dancing length begins to win because of these little numbers in the top here, which is how many things are left in the column. This number drops to zero. You're dead and you might well stop, by the way, if one gets a false move. And so I thought if if that's true to Branch on a column that has the smallest number of ways of of continuing that that effect of branching doesn't doesn't show up on small problems. It starts to show up. Well,

I'm Marsha. OK. And I know I wanted to try this out on some on some other times. Once I hadn't, I wrote a general a little program that just does a general exact cover problem with dancing length and. And you can download this if you're interested. Just go to my home page and then go under downloadable programs. And then one of them is called Dancing Links. And there you can download a general thing that, you know, that reads in a exact cover problem. Good reason, a whole whole list of possible

uses for sort of one line, many, many lines like this in and out of all possible worlds. And then in the first, the date is list of all the columns. And then after that, one wrote a time. And then it'll it'll tell you it'll solve the exact outcome, all the solution. And for the first, I wanted to try it out on another kind of thing. Lether called hex diamonds. It turns out there's off to twelve of those. If you take six triangles and put them together the way in pendent control, you had five sq

uares and put them together in hex diamonds based on the idea that a diamond has two triangles put together. I thought, OK, here's a nice rhombus. And and and so I put it into my into my general program. And I'll also drivers for this. By the way, you can download photos for Hech time and you specify a broad shapes and you specify which which of Simon's you want and it will generate. It will generate the input to the Dancing Lengths program and and you can pipe these together in one want to use

command and get the solutions to things like that. And I was going to make some kind of arrows to see how many solutions this will give, particularly. There was no way to do it. But here, if you look at the fine print, it says thirty seven million three hundred three three hundred thirteen thousand four and five updates and update is the operation of taking something out of out of my 01 matrix, taking out of the data structure and then putting it back in again later. So there is everything I do.

I also I also undo breaking symmetry. There is that if if there was an interesting asymmetry that reflects the history of it and if you look up close that this@, for example, at this look at these Rosevear, I deleted this guy before I deleted this guy. So now there's a red pointer from here going up to here. It's different. So this has a red point of doing it. This is not symmetrical to this. So if I tried to insert not again in the same order, it would the algorithm wouldn't work. But if I ins

ert this one, if I undo this one under this one. If you look at the actual way these two these things are said afterwards. Although the things I deleted two things out of the list at the Philly symmetrical. But that's not the question you ask nicely in order to in order to take the right take for symmetry on a problem like this. It's very simple. I take the hexagon piece and I say it's going to come up here and only one one fourth of the diagram because it forced him to create every every other

round. This has hostilities. You can flip it this way. You can flip it that way. And so in order to you order to say that I don't get the same solution twice, I just insist that one of the one of the pieces be in a certain part of the diagram. But also, there's the. Does have other interesting thinking now that the the the the big famous problems on excitement's of those was invented by by Thomas Walburn, who wrote about them in a New Scientist magazine in the early 60s. And he said, this is thi

s is actually a ticket. Can you zoom back out? Can you zoom back a little bit? This is signed by him on Jack. This is his, you know, one of his first solution. This is this was a historic piece of paper from him. And and he noticed that if you take the 12 hex diamonds, some of them are are one sided and some are two sided in the sense that some of them, when you flip them over art, are different. And so if you make two copies of the two sided one, then you have to have the one sided hexameter, e

xactly 19 of those. And it was just the right number to make a diagram like this. And and so he he wondered if he could fill that diagram with the 19 one side effects diamond. And he spent months on this until he got his first solution in November of fifty nine. And then he showed this solution to Richard Guy in London in 16, which would save this piece of paper, which is where this came just came from. And Phil and Richard told me that he wrote about it. He said that the guy family didn't get a

ny sleep the next 48 hours trying to find solutions to this to this problem. Now, the 19 states decision problem is, is fairly, fairly tough search. And it took them and it took a long time to find one solution. And up and out for many years, the Richard guy had notebooks where he would record more and more solutions all the time. So I thought this was a natural thing for me to do, to work on with my program. And because it was you know, it was a much larger problem. So the advantages of my gene

ral sensing link approach would would begin to show up. And so I so I counted the total number of solutions in here in order to do the symmetry breaking. You take this black piece and you kick in and you can either place it in the center or you can place it slightly farther from the center, slightly five, either zero, the possible seven positions where the black piece could be in order to get rid of the symmetry. And then here, for example, I have two billion updates, 11 billion updates. In orde

r to in order to do this. And at this point is when I actually got my new computer upstairs. That was ten times faster than my part, too. And so I decided I better get a new machine at home. But but I finally, you know, so. So first, when I ran it, it took two days. But then when I did on this other computer, it's a three hour, but I got all the solutions. And so I think I thought, okay, great. And I wrote to Richard Guy code telling him the total number of solutions. And he said, that's very in

teresting. He had a student who two years ago had also written a computer program for this, and he had worked on it for, you know, and had run for some time, for week. And the student actually set up a Web page, the heck Diamond Home Page. And and so great. I look at the home page and I found out that I had one more solution than he did. And so I left. And so I didn't know what. Just one. Yeah. Get off I went. And the value jeopardy. But you can you can click on. You can you can search for him.

You can say you'll find you'll find the all the solutions that have the effect that have to have this black piece in a certain place. And another thing, another place. And I wasn't about, you know, one hundred twenty seven thousand solutions to someone. I want to find out which one he missed. You know what? But I sent him a lot of printouts so that he could figure out that, you know, which were you. There was a discrepancy between our between our two our two things. Well, the student was on vaca

tion and I had to finish this paper for a deadline. So I'm still up in the air for a little while, but. But after two weeks, the students came back and. And. And he he he he he told me why we ran this program. And this time he found the same number solutions that I did. And and he showed me the solution that he had been missing. The idea that this database that's on the web now. But this was a. Who is this? This is who is sort of one of the one of the classic problems of reading, even though the

re's a hundred twenty five thousand solutions. It seems to take a long, long time. If you have the other 19 pieces to actually find any of them and that there is a question of what's the most symmetrical solution of all? Because I have a complete list of all of them. You know, like there are some conjectures about what are the most symmetrical solutions. And so now how do you define symmetry? There's there's two ways. One by pieces, one by edges. I chose edges. And so I say that if you take us i

f you take this solution and you flip it left, right, and then you say, how many edges? Ah ah ah ah. Still edges. And call it the horizontal symmetry of the solution. So, for example, if you had any edge in the middle will count. And then if there's an edge here. Also these these diagonal edges on the hexagon, of course. So this one has to. It turns out that by that measure, I don't count edges on the ed on the on the outside. So this one has a horizontal symmetry score of fifty one vertical sym

metry score of 24. You flip it up top to bottom. You get twenty four. Now I would say that the most symmetrical solution is the one where you know where you have had the maximum number of edges. Net net shape here. And that was. So I had this one with 50 to score, 52 and 27 in the other direction. So I consider that the most symmetrical solution of all. That's kind of pretty to have to have a symmetry in there. And so that that solved it. It's the third act that the conjecture, the one wasn't Wi

ckland. You could do a little better than the one that that people had found by hand. Well, is a long history to that. But I want to get on to two more thing. This was this was a fun puzzle that I got. I got this made in Taiwan. It has it has a. I forget how many pieces in it, but these are are now called Tetris sticks. You have I remember we had the PIN terminals, which were five Aminals and then Hech diamonds, which was six. I'm six diamond. Well, these are sticks with four sticks and 30. So e

ach each piece covers four, four edges of the square. And each of these is a different way to to do that. Well. The total number of Tetris sticks is, is fifteen I believe. And let me show you. No idea where he might have it here, I guess. OK. Yeah. Get this picture shown. This is not the color version, but we get a close up. Zoom in on this. It'll be better. Good. Yeah, so. So here we have to take one of the terrorists out and then you can fit the others, for example, into this terror. This this

this Taiwanese father was called the eight hundred forty five. Interestingly, combination's and and, you know, he had told him a solution was something like seventy nine. This number eight forty five was completely Hokie with that. But if it, if it, it's a beautifully made puzzle and and and it turned out to be a very good thing because it's not exactly an exact terror problem. The point is with the sticks, you're not allowed to. You have to cover all of the all of the edges. But you can't do i

t this way where two things are crossing. I would get a picture that would close the Pixar movie. So if you saw here, for example, I have the zie Tetris stick and and the V that the stick and and you know that they would cross you can you can film together like that. So the corresponding thing in the in the cover problem, I have to I have to cover Zano segments from two to three Tetris stickers is covering horizontal two to three, horizontal three three and vertical for three vertical forfour th

at would correspond to these two verticals and two horizontal. And then I also have the Z code, but then I have intermediate points. Intermediate three three, intermediate four for intermediate three, three and sort of intermediate point is common to the two and that means that I'm not allowed to use it. So here what I do in this, I generalize the that cover problem to a lot. Who has a saying that some of the columns are don't care. I don't I don't have to cover. I don't have to cover all of the

cards. I just have to cover the designated column. But I'm not allowed to use the these other are not allowed to you to cover the more than one. So I have to get a solution in which I choose enough growth to cover all the designated columns. Exactly one all the other columns that most one. And so here are the I thirty three intermediate position saying no to things allowed to go in, in that attack. So are the beaute. The nice thing is that the same, the same computer program work, you just init

ialize it differently at the top. You linked together only the columns that are only the designated com that have to be covered and all of the optional columns you just leave out. But then you use the exact same algorithm and it just solves the generalized cover problem. So. So. So I could apply it to terroristic and. And the the interesting thing is that you could also apply that to the eight Queens problem. So let me show you that. Here is the head of the path look that suppose we have a forkl

ift problem I'm only doing for roads and for cars, a four by four chessboard. Well, then then there are 60 places to put a queen. And. And I'll say that, for example, this has been rank zero, file zero and column a diagonal column in one direction, a zero and a diagonal cone in the other direction, B three on the second. If if I put a queen in row in rank zero, file one and I'm covering diagonal one, a one and before and so the ways to put a put a queen on a four by four board. Each one of them

covers one rank and file, one one diagonal going this way, one diagonally this way. And so the generalized cover problem is, two, to find a way to choose four of these rows so that each of the rank is covered exactly what each of the houses cover. And and no diagonal is covered more than one. But you don't have to cover each diagonal. There's there's a seven seven diagonals each direction. So so this is a this is a generalized cover problem. And we can use the dancing linked the the general algo

rithm based on these four way length to solve the facade of the queen's problem. And the clues by something like this turns out to be best to start. Start here, the middle of the board. So, first of all, I'm going to try to say put something in rank for us. So I have to choose one of these eight places. Will perhaps I put the queen here. Let us zoom you zoom in on this type. So, so familiar with the queen here. So that so that that means that all the places I got access here now are are forbidde

n. And those get removed from the from the cover problem. And I've got numbers here, six six six six six six six five five, five, six. These are how many possibilities. How many ways are there to fill this rank. How many possibilities are to fill the list files. So the next batch should then be on one of the files. Let's say if closer to the middle is better. So so I'll choose it for saying I have to choose one of these five places to place the second. OK, well, maybe it goes here, so then that

that gives me a lot. Now I have to cover a few more rank and file still, but four possibilities here and five here. I'll choose this one. I'll say next, just try to go into rank three. And there are four ways to choose one. I might have chosen that one. At this point, there are only two ways to choose file in file three. And and if I pick one of those already, I'll find out that just placing four queens will have been a dead end. And so this is a fast way to solve the Queens problem, catching de

ad, especially if you're altering. Sometimes you're choosing Rose. Somehow you're branching and rose. Sometimes your branching on come on file Branxton, sometimes on files while they had the way that people always do in their programing classes is always just going row by row. Instead, if you sometimes you sometimes do it by rote something because you get more effective. You don't have to have to choose as many, many branches. And so in the paper, I showed how you could count the number of solut

ions to the queen's problem up pretty high. And right now, I had a couple of open problems in my in my paper that I wasn't able to solve, that I was hoping that the other people would would be able to work on. And there is exciting news about that, at least in the setting for me. And so I'm hoping I can find the picture here. It. But maybe not. I I'm where did I make this? Okay. I'm sorry, I don't have the picture that I thought I did. I did bring some pictures here, but first of all, with one q

uestion I asked in the paper, is this a good friend here? I said, is this the most unethical way to pack one side and pin terminals into a rectangle? So zero for what we did with the hex diamonds. You know, the 19 of his assignments that are one sided. You can do the same thing with 10 terminals. There are twelve point terminals, but there are 18. If you consider if you consider it to be one sided, you know, the ones that are like the P, you have a piano and a reverse P. So that gives you 18. Bu

t what the X? There's only still one X, sir. I tried putting into a nine by 10 rectangle and it was it was unknown how many solutions there are in a nine by 10 rectangle. And and I could have a way to estimate how long it's going to take to solve these problems. Another thing that you can download in the programs that I mentioned that are on my Web site. You can say instead of finding solutions. I do a Monte Carlo test that that estimates how how long is how many updates you're going to need. An

d you can run it with different random numbers and you can generate a thousand times when you can. And then it'll tell you, you know, it's estimate based on this Monte Carlo method. And I knew that it would it would be somewhat tantalizingly beyond the capability of what I what I was doing to find all the solutions to this problem, putting the 18 terminals into a into a square grid. Right. But I tried to simplify the problem. I said, well, let's make super pieces that are symmetrical positions.

So I would have like the Z and this V, this reversely here. I wouldn't consider that to be a a you know, a 10 armano. And then I could with with a few of the 18 pieces converted into into things of size 10. I could solve an exact cover problem and I could then figure out what you want. And I would assume that that are in order for maximally symmetrical position, you would be using a lot of pieces in there. You know, in a symmetrical way. So. So that would cut down the size of the search to somet

hing that I could do. This is my conjecture for the maximum maximally symmetric thing, actually. This is this is off by the squat. Horizontal symmetry is actually seventy four to seventy two here. It should be 74 in a vertical. Forty nine. This was my thought that this would be the most symmetrical thing. Well I just got email on Friday last week from Germany, a professor in Beirut, Bygrave. Who is that actually at the University of Earth. They have a long history of of of working on an exhausti

ve search, problems like this and finding all isomorphic solutions to things. And so he found my skull with 74. He found these solutions with seventy five. So and now I have to dig exhaustively enumerated all the solutions. So they found 10 million and some solutions to this problem. And they used the cluster of Linux workstations. I don't know a dozen of them or something like that. And that worked very well for parallel processing because there you can slice each processor through a different

branch of the surgery. And they use Mike. They use my, my, my programs. And the dancing lengthened did die. It did something like four and a half trillion update. So it was about a factor of about a factor of 100 more than the ones that I had. The ones that I had done. They had. They also took this dancing thing. They also took this and played it to some of the other problems that they had, which they had been running their own their own software on that they were exact color problems. And they

found that this dancing mix was was going about three times faster, 10 times faster than than their other methods. I was glad to see that. I just like it because it's such a simple program. You got even begin to structure to save, you know, to to recreate the changes from one step to the next. But then that's not right. That was my conjecture then was 74 was going to be the best. Me got to the seventy five that. If you looked at it, I am saying that, that the score is the number of edges that ar

e preserved. If you flip it is still on edge. Now you can count exactly how the maximum possible score you could ever get because of the total number of edges inside this diagram. Is there one hundred six hundred sixty one and and the number of of the total number of Intel things inside of all of the 10 terminals is done whatever in ways, you know. If you subtract, you get a good eighty seven. So the point is, if you had a diagram that was exactly the same, it had a pentagonal and you flipped it

over. And then you still had all the edges were still edges, then your score would be eighty seven. Of course that wouldn't have that, that it's impossible to get a score of eighty seven because unlike the diagram would be would look exactly the same. And but you know there's only one X, there's only one X 10 terminals. So you can't, you know, you have to put it in the middle but then you can put everything in the middle. So eighty seven is obviously our bipeds square. Seventy five was pretty g

ood. Score 74. Was pretty good. But here they have these solutions that they found with a vertical in the Peace Corps. Eighty three. And so this means that if you take these that you feel here they had these, you flip these from top to bottom and you still have it. And only, only four of the edges change, you know, change the character. So these are really the max with the magic solutions. Now, the other the other orphan problem that I that I had was really driving up the wall with with respect

to these Tetris sticks and the Tetris sticks. I, I, I found some nice solutions here with one side of Tetris sticks and. And this makes a really nice puzzle, actually were a friend of mine is helping to run the manufactory now that this uses only what we call the wellin Tetris sticks, the one that have to have joints together. The NERA, the unwealthy Tetris fix, the one that that you know, that one one piece of bent wire. And and putting the one where there are ten of the ten of the rounded ones

and 15 of the unwell ones. And I couldn't put the the are the one sided on. Well it went into a into a very symmetrical diagram. Every square thing I tried. This is the most, the most beautiful diagram it has from symmetry to it that I could get out of it. But the thing that I was would think he would take this shape. This is from an aspect diamond. And this this tape has if you count the number of edges in it, it has exactly one hundred edges. And I have twenty five Tetris sticks and one hundr

ed edges, though. So the question is, could those those all all attach to sticks. You know, fear of this. The shape. And I tried very. I know I, I ran all kinds of things. It looked like it looked like it was going to be way beyond the power of my computer by my Montecarlo test. But, you know, by by a factor of about 100 hundred or so. So I thought by heuristically heuristics, I'll put a couple of them in symmetrical position and that'll make the problem easier. And I found no solution, but I co

uldn't find a proof that it was impossible either. And I sent this test to the people in England who are the, you know, really good at puzzles. And one guy found a way to place 24 of the 25 Tetris sticks without, you know, he had this one that couldn't fit in. So it was it was it was open. But the same guy in Germany, Alfred Bozman, sent me in December. Really beautiful solution of this of this STK diamond covered with Tetris sticks. And I thought I had a flight of it that I could show, you know

, but instead, if you go to my home page and go under three prints of recent papers, then offer dancing links, you can click on the Alfred Glosserman solution to the to the tech to the Arctic diamond problem. And it's really, really a gorgeous solution. I think they found a solutions all together. And again, this cluster of like elicitation didn't do the exhaustive computation. So. So both of the main unsolved problems that I got, I had mentioned have now been cracked already. Well, any question

s? In order to summarize, then, I shouldn't. I guess I am talking more about these napoleone and opaque problems in covering problems than about the dancing link. Really, the the the idea of dancing links supplies to many, many other kind of thing, I would say. Well, one of the one of the kind of jokes is that in artificial intelligence, there's something called the Walt Filter Walt filtering algorithm for for cutting down on possibility. It turns out that wealth filter is just perfect for danci

ng length. Don't you get it? David, welcome. OK. So do I hear a waltz? OK, so, um. And, uh, but but, you know, solving many, many problems in in constraint satisfaction require this kind of undoing capability where we're the greatest. As far as I know, the techniques in the literature are typically safe. When you go to when you go in Britain and make a new branch, you sort of recopy your whole data structure to get from one state to the other. But instead of recapping the data structure, you hea

r all you remember is the one node. And from that I walk through and and undo everything and everything pops into place as I'm as I'm doing. That's the that was the beauty of it. I worked on many, many cases before wi this is the cover problem. And also, I would say like any other application where you have a lot of undoing maybe or writing a text editor or something like that. I suspect that you would find this similar kind of of economy in. Yeah. John reminds me of that program. Where you want

to be able to update and move from one position to another and also go backwards and so forth in order to preserve. Yeah. And when they had two tables, one was which gave each piece its location, had one for each square talking. Yeah. And the updating and downgrading required having both tables. So we have forward, backward linked here, but between things of a different character. Yeah, if this particular thing I'm talking about now is, is when the links are specifically in the double links of

of a of a list of 12, a linked list. And they need the novelty or the novelty of it. Is that the. It is that you don't garbage collect after you remove from the list, you keep your link still pointing into the the other elements of the thing that isn't in the list is still pointing to the two places where it was before. And if and if you if you do that, then then that's a win. It's not really it's not really saying you're avoiding garbage collecting in the garbage collector wouldn't treat it as

garbage because somewhere you are using your data structure, you still know enough to put this guy back in there. But but but it's not that the but it's something like saying that you just didn't garbage collecting the information. When you remove something, you've got to. But it doesn't. But these other you know, there's other kinds of updating that you do, you decrease by one and then later on undo that. You increased by one. You know, if you if if you're if you have a table that that that say

s for each place on the chessboard what piece is in there, then you have to have have, you know, undo that. You have to remember what piece was there before. So Butterflied wrote this paper called Nondeterministic. Algorithms in the ACM Journal in the 60s and and and gave a general procedure for four Non-Deterministic we go, you know, trying a whole bunch of things, which meant that you would execute a computation and then you would unexcused the computation again in order to go in another branc

h. For that, you needed a fairly elaborate stack mechanism that would record enough information to risk to undo every assignment. And the beauty of the dance, the length is that you don't need to stack up because the stack is this sort of implicit in the control structure of the program and not in the in the memory. Yes. So you have any obligations to reversible computing, low energy stuff? No energy, reversible computing where I is. I don't know the term rebirth of all computing to undo your ba

sic operations. And that way, you don't create increased entropy, which means there's no there's no lower bound on the amount of energy that you have to have to use. You can use sort of theoretically arbitrary. OK, well, I. Yeah, that sounds like the kind of theory that I that is that is is academic. I mean, you know, these these are these lower bounds and so on. Okay. Like nothing other. But, um, but I, I, you know, one of the talks they gave without my fee or I actually I was I was saying that

that change that got that infinity is a red herring. And and if you start if you really understand how big finite numbers can be, then you'll be quite happy to live for that many years and not insist on immortality. So your question reminds me of some of the same flavor. Were you talking about some extreme limits? Where you where that, in fact, when you when you when you know, you real realistic scale into into account? It doesn't really. But you might be able to sell it to a venture capitalist

. Yeah. Your uncertainty as to what a of the least property is. Reversibility has a very strict Catholic discipline. What did you find. Exactly. And that combined with the fact that you only track one node to unzip corporation, you think of a stack as a single place is it's not a yeah, it's not a fact. So my my mathematics is a combination of. It is a combination of some implicit dynamic, you know, operational calculus, which is where the operators are packed on a stack. And, you know, don't don

't ever appear in memory, but they appear in the invariant. So, you know, so. So you can say that I've now done, you know, my fate at a given time. Says that for. For things that are that are in the list. L means the left neighbor means the right name for things that aren't in the list are not. Could tell you that. But I'm going to tell you that I have done operations a one up to a K and now and now I'm going to play Operation K inverse and it's going to go k k minus one. And that's that. And th

at's a different kind of invariant than than people have used, including correctness of programs before. So it's a console. So it says that that's that's sometimes indirect information is better than full information. Or I can say about that one. Well, Tony. Well, you know, there's such nice people. Oh, no. Well, Esker didn't comment about he, hasn't he? He has has been more interested in mathematics than computer programing for the past 15 years. But but but Tony will say it's wonderful. But I'

m not sure what he really. But I'll see them again in May. And ESCOs is retiring at age seven. His Soviet birthday is coming up in May and in Austin. And I'll be speaking at that on on a different subject in May. And Tony will be there. Also. But for me, the payoff came from the people in Germany who had been for 15 years have been working on this exact color problems of different kinds and that. And they hadn't found anything that that worked as fast as this. So that was that was the main the m

ain thing I like. I knew from my programs that it was easy to do it this way. But this was confirmation that I really, you know, made me feel especially good. I have not. There is constraint, satisfaction, there's been a there's a couple of journals just devoted to constrain satisfaction now and and I'm talking to Jean Broider and in New Hampshire about this to see to see how this. Impacts with with some of their software that they use for. For consumer satisfaction problems which are more gener

al and an exact cover problem. Well, I think my my method for the eight queens is it is the champion at the moment. Yes. Boy company, you mentioned that someone was going to construct puzzle pieces. I'm sorry, John. Your topic was going to construct some of these toys, are they? Oh, it is. Oh, no, no. That's. That's where the puzzle of the International Puzzle Party that that meets once a year. Hundred collectors make it make 100 puzzles for each other. It might take the world by storm, I don't

know, but it is fun to play with these things. Especially when they when they're well-made because of the colors and shapes in the symmetry, there's something there's something addictive about it, I don't know what it is. Yeah. About this company selling part time and with something like 200 pieces and offering a reward of 10 million. Yeah, yeah, that's right. You might download my thoughts to reply to that name of the of. What does the Web site. And clearly, clearly, penalty has the right. Whic

h is I think it's an exact cover problem. Return to Germany, where you could work for you could you could run by Monte Carlo simulation to find out what the chances are of doing this. The the Monte Carlo method is is quite interesting by itself. It works for any backtrack problem. You you sort of. Well, in the simplest case, if you have three choices to make, you write down the number three and then you you you choose between them at random. And then then maybe you have four choices to make. You

write on number four. And so maybe you have three choices that the first step. Here we go. And then you have four and then you have seven. One fourth and two or something like this. Then finally, you're stuck. Now you compute the plus three times four plus three times four times seven plus three times four times seven times one plus three times four times seven times one time two. And that. Now that's an estimate for the size of the first three. And and this is the size of estimates of the size

of the surgery at level three and so on. And you repeat this 10 times. And as you're doing it, you're also thinking of what they did, structures you would use if you program anything. But after you compute these numbers for pretend sample, run you just by hand. I have a random number generator right next to my desk, just as just this reason. And then then you can figure out how many cases it'll be was whether it's worthwhile to write the program at all. And typically, after 10 runs of this, it

gives you the order of magnitude plus the expected value. This number is is the size of the three. So this could be very neat. Yes, it could, but he cried to said out right then. And if you missed that in your search and an entry into a part of the space, that contains some very large numbers. Yes. And we know that while this process converges to the average, you can use it for a very long time. Yeah, that's right. Pessimists don't believe in it. You can. You can. You can. You can construct it.

You can construct lots of worst examples. But the amazing thing is that it that it is right on the money most of time in reasonable problems. And. And in fact, I for example, I gave a talk in at the typically EST meeting in Boston in 1976, estimating the total number of ways to go from one corner of the square to another without intersecting yourself. And it was something like ten to the twenty seven, you know, things that I and I, you know, I figured never in my lifetime I'm not going to know t

his number, but I. But I did a thousand experiments by computer and estimated how many how many ways there were going to be. And well, a few years later people found out a way to compute this. And so and so and I it's just this paper now. It was reprinted in my book, like the papers on computer science. I could add a, you know, a postscript to the to the chapter thing. Well, now we can compute this number and it turns out to be exactly this twenty seven digit number. And, you know, I was I was o

ff by two percent or something like this. And I estimated that, you know, 80 I'd guess that 83 percent of the solutions would go through the center point. And the truth was 82 percent, something like that. Now, this was based on a thousand runs of something where you can imagine you'd be way off. And, you know, I did it on a fairly large variety of things. But in the end, this problem actually, though, I did find a few cases where where my work was getting a pretty high variance. And one of them

was putting y y y in terminals into a large board. And on that one, the estimating procedure would kind of to be a bit low, maybe by a factor of 10. Almost always they get the right order of magnitude. Skeptically, you would say. You know, you can you can usually imagine I was gonna miss this stuff, but. And in fact, it blows the mind, because if you do it a thousand times, you know, maybe, maybe twice, you're gonna get a big number. And and 900 times you're getting a small number. And so it's

sort of you're throwing away all your data, almost all your data. You're just keeping to two entries out of a thousand. And yet it's worth. You had to do another nine hundred ninety eight just to prove that they were there. Those numbers are increasing, like the numbers for us. I don't know whether they go in in cases like this. Typically. I'm sorry, we are. I'm running late. But then take typically the the three if you count how how many nodes are on a three. And you write that at the rate of a

t the right it looks like a bell shaped curve. But in the end the number of digits of the tree. So I thought was a lot of what they call a lot of normal distribution means that the logarithm of of the number of nodes on levels larger than tends to be a normal thing and end up. And however, when you look at these numbers, these these numbers are always growing like this. So we're taking averages. I mean, the number of digits in these in these estimates are going up. We're not going to zero. But i

f you add it everything these out like I did a thousand runs down on the problem was on crossing night to it. And the truth was like this. And the truth is this truth is being made as an average of things like this. So I was like, yeah. Well, more linear growth. And so that would be another argument for Jones saying this is unrealistic because how are you going to get the truth out of that? But in fact, when I made it up, an average of a thousand like this, I got I got this kind of a shape. I di

dn't have the tail exactly right. And my and my student pankin thesis, I found a very nice improvement where he could where he could bias the is called stratified. It is called stratified Montecarlo where where he did get around. This is some of the other problems. In the end, he makes the variance the last more and he gets the tail. Welcome. So so I did this thing I gave you here is just the first level and there has been many improvements to this. This method, but it's not even a simple one. I

t is useful because I use it at my desk all the time and it tells me whether or not it's worthwhile writing a program, because I can get a fairly good ballpark estimate for the size of surgery before I go into the right before I had this method. I mean, I work in when I was when I was a student. There were times when I would write up a program for a backtrack application and and it would go on the machine. And even in those days, you know, the little IBM six fifty with its five milliseconds cycl

e time. And and it would I would get my answer in a minute or two. Other times it would. I don't know. One, one. Once I stayed up all night and I just I kept thinking, well, you know, it's going to give the answer. Then finally, I you know, I was it was six o'clock in the morning and I hadn't had any sleep. And I got time for somebody else to take over the machine. So I started playing out the console and looking at the memory, and it still hadn't reconsidered its first twenty two choices, you k

now, and so it was gonna go like, you know, three hundred more centuries before it was going to who's going to get to the answer. So they developed this estimation procedure so that I could tell the difference between, between one kind of problem and the other. Well, thank you.