So, you probably didn't expect me to give the Christmas lecture. [LAUGHTER] Um, but I'm glad you all came. Um, and in fact, I will not be, but I'm just here to introduce Don. I- so, it's a real honor for me, uh, you know, to have that opportunity to introduce Don. Ah, I think his accomplishments are probably well-known to the people in the audience, you know, the- the work in, uh, programming languages in computer theory algorithms, uh, on- on tech and, and many other things, you know, that extend way beyond Computer Science. I- I thought, you know, what can I say that people wouldn't know, uh, and so I thought I could talk a little about my experiences with Don over the years. And so I just, you know, just a few brief, um, mentions of- of how I've known Don, you know, through my career. So, I first met him, uh, but only virtually. Uh, when I was 20 years old and I got this book that I was supposed to read, um, on algorithms and I could not believe, uh, the, uh, the amount of material in that book and how anybody could possibly know all this stuff. And then I found out there was more than one book. [LAUGHTER] And- and that really surprised me. So, I thought I will never master all of this material. And- and, uh, [NOISE] and then eventually realized that actually probably Don is the only person who knows everything in all of those books, you know, at some point in my- in my life I realized that. And then when I came to Stanford in 2003 I actually got to meet Don in person. We may have met earlier than that. We may have cross paths, but actually when I joined the Department, um, I, you know, Don was obviously a very senior figure in the Department and always had kind wor- pep-words for-for new people, and so, um, that's where I actually got to know Don personally. And- and, you know, he did many kindnesses over the years. I just mentioned one, my kids appear in one of his books. So- so, Don used my kids as models, I- in one of his books and there are several pages of their photographs, um, and he gave us my wife and I a signed copy of that book, which we- which we treasure. Um, then there was an event may be only three or four years ago when Don came into my office and said he had read one of my papers asked this technical question. Okay? And, you know, about this paper, I'd written a couple of years before. And being a slow thinker, I think I answered it extremely poorly, uh, on the spot. Don, clea- you know, he had- he had actually studied the paper and understood the issue, um, at least as well as I did at that point in time, uh, and being very generous and didn't, uh, didn't push me too hard on that. And- and then I think, you know, in my time as chair, there's been a number of times when Don's taking me aside and just given me, you know, a sentence or two of advice about, you know, how to, you know, how to- how to, um, handle so we say some difficult situations in the department and I- I greatly appreciate that. So anyway, that's a little bit about my experience with Don. He's been, you know, a wonderful colleague, obviously, a great scientist, and, uh, and, you know, a, a beloved figure here at Stanford for a long time. It's a great pleasure to introduce him for the 24th Christmas lecture. So, Don. [APPLAUSE]. Okay, well, thank you Alex. I couldn't- I can't justify that all, but let's get- let's get on with kind of a whole bunch of stuff to say. Uh, I still see three e- empty seats up here and a nice place to sit on the floor, like, [NOISE] uh, I can't- here's another one, on the floor. So, I, you know, uh, unless you plan to leave early. [LAUGHTER] okay. So- so but the title today is Dancing Links, and, uh, uh, and I- I- I- I, I told the, um, my- my friend that I was gonna talk about dancing links, "Oh, didn't you talk about dancing links once before?" And, and, and, and sure enough, I, I'd forgotten about it, but, uh, but in, in 2000- in February of 2000, I, I gave, uh, another one of these talks, they've- before this- this particular room was, uh, was built, um, and it was called Dancing Links then. And, and, uh, uh, and well, uh, you know, an awful lot has been learned si- since then. So, uh, uh, I- I'm not gonna repeat, uh, very much what I said 18 years ago, but, uh, but you can still find it on the website of- of his ITN. Uh, you know, just it shouldn't be too hard- hard to do in, and- and then you'll see, uh, you know, what the difference was, uh, 18 years can make. Um, now, um, the next thing I wanted to show you is this, which is the co- which is, uh, the cover of a book that I was hoping to get ready for Christmas. [LAUGHTER] Uh, so- so that, you know, people could- could buy it. [LAUGHTER] However, um, uh, I I kept discovering more and more stuff about dancing links and so, you know, we've never the time to- to finally wrap it. So early next year, uh, uh, this will definitely be coming out and I have to- it's already- it's already up to 350 pages and I- uh, and I, uh, and I, I was gonna, you know, this- this little paperback first because I was entitled [NOISE] to keep the limit at- at the max of 300 pages. Um, but, but it, it, it actually comes before [LAUGHTER] this one. This was the one that I [LAUGHTER] published a couple of years ago. Um, and then, and, uh, and, and these, these are eventually gonna be, uh, this will be the middle third, and this will be the first third of- of Volume 4B of The Art of Computer Programming and it [LAUGHTER] you know, this is Volume 4A. So, o- okay. So, so I'm, you know, I'm, I'm still working on it and, uh, uh, until I go senile I I keep- intended to keep on talking about content. Uh, you know, [NOISE] and, you know, e- even though I can't [LAUGHTER] remember anymore what's all- what's in it all, uh, locally, I have- I have a good knowledge of each page of the- all this book. [LAUGHTER] Sorry. [NOISE] Now, and by the way, I- I have this other book called Selected Papers on Fun and Games, which is a really great book to give for Christmas, [LAUGHTER] and, uh, and, and in that book you can find picture not only of one but two of Alex's, uh, delightful children, so another reason to buy the book. Okay. So, so now here we have, uh, what is Dancing Links? Ah, tonight I'm gonna, uh, you know, I- I'm gonna talk about a few things that are technical, but mostly it's show-and-tell, mostly, it's things that, uh, you know, you- that- that you can look up later if you wanna- if you want to- if you want to get more information, but I- but I'm not gonna, uh, you know, I'm not gonna, uh, really dump it down either of by, by, by omitting what- what the- what the main point is. But, but, uh, firstly dancing links is, is an extremely simple idea about, about something that, you know, a way to write the- a computer program that is- that is so simple at you- at first you might, uh, you know, you might say, "How could anybody talked for more than five minutes about this- this idea?" Um, uh, however as I said, uh, I a-already 18 years ago I talked an hour and a half about it, and, and, uh, and, and tonight, uh, you know, I- I'll try to get into an hour and a half, um, and, uh, uh, and so what is it- but, but so, I got to first des- described the idea then, the-the- then so- then something about it. But then lo- lots and lots of, uh, of applications about it because it- it turns out, I, uh, the reason I haven't finished this yet is because I keep finding new. Uh, uh, is- it's like a, a Christmas time, my- I'm like, uh, I'm like a kid with a new toy because I ha- because I, I have this- this technology of dancing links that I can use to solve problems that I never thought I would solve in my lifetime. So, so, so, it doesn't solve every problem, and we need of- but [NOISE] it's completely orthogonal to deep learning. I don't think any of the things I might talk about [LAUGHTER] [APPLAUSE] [NOISE]. Okay. So, um, uh, so, so in, in the first place, uh, it- it- it relies on doubly-linked list. There's a version for- for- for singly-linked lists, but- but links and by links, I'm thinking about the, you know, the pointers between the elements to the list, and, and so, you know, we have a doubly-linked list. Let's suppose we have a doubly-linked list wi-with, uh, uh, uh, with four nodes in it. Um, uh, and we can all- uh, uh, and then I, uh, with a doubly-linked lists, we usually also ha- have a header node. So, I'll call that 01234, where 0 is the header node. And then, each, each doubly link, so zero. Uh, so, e- everything points to its, uh, uh, its- its successor. Um, and, and, uh, and the successor of the, uh, of, of the last guy is the- is the head. And then everything also points to the predecessor, which is- so these a- already- I already through that guy, and this- this comes- co- come back in here. So, so, so, uh, in, in memory, uh, then if we had, uh, uh, a locations, uh, 01234, and- and we have L link and R link. Um- Ah then a a, L link of- L link of one- of zero is one and this gives us two, this gives three, this is four, this is zero, and then going back four points; to three, to two, to one, to zero and to four. Okay. So- so, this is- this was the way it looks in memory, uh, when we have a doubly linked list. Now, uh, okay. So- so, uh, uh, one- one of the main reasons why- why it's- it's- it's nice in lots and lots of- of programs to have doubly linked list is because we- we can delete a node from the list, uh, just knowing- just knowing what node it is. We don't need to know how we got there. We can- if- if- if we- if we know the address of a node P, we can say delete P, so delete P, uh, is- is a very simple operation like I set L to L link of P, [NOISE] and R to R link of P. And then, um, and then- and then I set, uh, R link of L [NOISE] to R, and L link of- of R to L. So- so, [NOISE] that- that wipes it out, uh- uh, because the- th- L was a predecessor, R was the- the successor, and now the predecessor points its successor, the successor- the successor points the predecessor and heads it. So- so this [NOISE] was- th- this was kindergarten style. But, uh. [LAUGHTER] The- the- the thing about dancing links is that, uh- uh, for- for- I don't know, for 30 years when I brought programs that I thought okay, now the good thing is to do is- is- is, uh- uh, cleanup up and- and- and reset the links of P [NOISE] you know, P is no longer in a list so I- I return it to, uh, to the pool of available memory and-, ah, and- and clean it up. Uh, however, there's- there a lots and lots of applications where actually, uh, I know that- that eve- everything I do I- I- I'm gonna wanna- wanna undo later on. So- so, if so many interactive applications and the backtrack application like we were watching on, uh, uh, before the lecture, uh, yeah, whe- when you're backtracking you make a decision but that's a tentative decision, and then if it was a wrong decision you backtrack and you take and you undo [NOISE] and you go back to where you were before the decision. So, um, [NOISE] this was where what- where what I'm gonna tell you about really shines when when when we're undoing something. And so, uh, uh, to undo a deletion, we would insert P, um, [NOISE]. And for this, uh, we say L goes to L link of P. The ta- uh, R goes to R link of P [NOISE]. And then we say R link of L [NOISE] is P [NOISE] and wha- now, what could be simpler than this? L link of R is P so- so this obviously undo- undo- undoes what I did before. If I did this right after that one. So, uh, however, I wouldn't have been able to do this if- if I- if I had garbage collect- if I had, you know, ah, been- [NOISE] cleaned up my memory, uh, and- and- and, uh, [NOISE] so let- let's just- let's just take a look at it, uh, suppose I, ah, suppose for example, I, um, ah, [NOISE] delete three from this list. Okay. So- so, I wanna- I- I want three to go out. Uh, and so, that says that, u- um, L is two, R is four so I have to change this to four and I have to change this to two in case so three is out now. And then, an- and let's suppose I also delete one [NOISE]. And so now, I delete one, uh, so [NOISE] zero and two have to change. And so, when this guy goes out, I have to change this to two and I have to change this to zero. Um, and suppose I delete four [NOISE]. Okay. So, I- I- two and zero are the predecessor and successor. Now so, I have to change this, uh, to zero and I have to change this to zero. Okay. So, I deleted though. Now, uh, [NOISE] undo [NOISE] so now it look and say insert four. But- be- before I- we- before I insert I- I- I wanna emphasize that the- the current status of these links is really a mess. Uh, one- one of the- one of the main paradigms for- for proving that a program is correct for- for- for- knowing that- that your algorithm is working is- is to- is what we call invariants of the data structure. Wha- where we say for every part of the data structure what does it- wha- wha- what does it mean, so what does L link mean? What does R linked mean? And we give some invariant relation which is- which is supposed to stay true all the way through our computation. Um, and-, ah, and- and wh- when I do something like this, uh, the invariant becomes hopeless. It- it- you could- you could describe in logic but it doesn't correspond to anybody's intuition. It's so complicated. Nobody ever- nobody wants to bother writing down what this invariant is. Uh, so it- it- it- it- it- it opens up a whole new way of proving that programs are correct, uh, you know, I'm not saying invariants are- are bad. I'm saying that they aren't enough to prove this kind of algorithm correct in the right way because my- my proof of correctness is operational rather than through logic. Uh, I'm saying, I- I'm not gonna tell you what L link and R link mean. All I'm gonna tell you is, uh, if you do the- if you do the insertion operation in the opposite order than you did the deletions, you're gonna get back, uh, what you had. So, I'm not telling you what it means. I'm just telling you operationally what it does. And a- and that's- that's convincing but- but do- don't ever ask me to- to prove this- this method correct by- by the old- by the old style of invariant. Okay. Now so- so, if I insert four, then- then I look here at two and zero and I say, oh yeah, Okay. Uh, I- I- I, you know, I should have crossed this guide, but I- I can look at two and zero. And- and- and- and now, you see I haven't erased that, so I still remember how what- what was the predecessor and successor of four at that time so- so I can go back, uh, now to two and I can change this back to four and I can go back to zero and I can change that back to four. Okay. And- and- and, you know, I don't have time to put- but you know what? At this point I could delete two, you know, and then, ah, you know, and then I could insert two, could insert one and insert three, and I- I be back to- to my starting point. But- but the intermediate points. Don't ask me what they- what they were. Okay. So now, uh, this as I say is- is extremely good for- for, ah, well, the- the main point of it is- is undoing. And- a- a- and one of the, ah, one of the, uh, sort of, ah, corollaries is don't, ah, a- a- do- do- don't clean up your data a- all the time, you know, there- there- might be, you know, some- some people leave it in there only to see wha- a- afterward if there was some hacker attack, uh, how did it happen but- but- but, ah, here, ah, the- there's a virtue in being sloppy. So, uh. Okay. Now, um, [NOISE] take a look at the video from 18 years ago and see how I explain it that- way then. Okay. [NOISE] Now, uh- uh, [NOISE] one of the most natural application of this, ah, is for a particular kind of problem [NOISE] that's- that's called the exact cover problem. And- and- and for the- for, uh, ah, for- for ten years this was the only kind of problem that I used to use dancing links for. So, for that that cover problem is one of the- one of the traditional standard problems of computer science that- that- [NOISE] Karp showed in the 60's is NP complete. Uh, and it's, uh- it's- it's I always used to think of it this way, uh, as a- as a ever matrix of zeros and ones, uh, and here's a, ah, particular one that I've used in- in examples in- in- in my book, um. [NOISE] I'm work, I'm gonna write two more lines here. The the idea of an exact cover problem is that, we have this matrix of zeros and ones and we're gonna choose some of the rows. [NOISE] Ju- just a few of the rows in such a way that when we add those rows up, ah, we get one, one, one, one and we we get exactly one every time time we do. So, ah, ah, that's that's the goal. Like, ah, ah, you're gonna have to choose either the second row or the fourth row because I gotta have a one here. Uh, so let's suppose that I, that I tried to, ah, ah, cho- chose a second row. Okay. So so so that means I've I've covered column. Le- let me put names on these columns. A, B, C, D, E, F, G. So, I've I've covered A and I've covered D, and I've covered G. And so, ah, tha- that's just about only one decent way to solve an exact cover problem and that is to write it that is to try a trial and error. You know, try t- try some- s- something and then see then you're left with an e- exact cover problem that's that- that's simpler because you've already covered some of the stuff. So so in this case, ah, ah, we- we've we've, ah, covered, ah, ah, A and D and G and so, all we have, all I have to do is look at the other, at the remaining columns, ah, a- and the things that I haven't been, um, um, that that haven't been done. So, for example, this one. Now, ah, now I've got B, C, E, F are, is left so I have zero, one, one zero. And then, ah, ah, this guy gives me, ah, one, one, zero, one. This one I can't use because it clashes, ah, ah, i- in in in A. Ah, this one I can't use because it clashes in G. [NOISE] And this one I can't use, it clashes, ah, D and G. So, ah, if we do, did, so so if I choose this guy, then I, then I have to cover the other four columns o- out, somehow ou- out of these except that I I didn't copy this very well. This is a one, right? [NOISE] It certainly gonna be hard to cop- co- cover B if there's no B, if there's no ones. Okay, so, bu- but but still, pretty soon you'll see that there's no way to, ah, to cover this because, you know, e- e- each each C interferes with the other guy. So, that isn't gonna work. So, we're gonna have to backtrack and say, "No. I'm not gonna choose this one. I'm going to choose this one instead." All right. Now, um, um, ah, le- let's let's pause for a minute to to look inside the computer because i- if, because, ah, if we're using dancing links, ah, we- well. Okay, le- let me show you, ah, ah, le- let me show you what I got. [LAUGHTER] Wha- what I got written so far. So so so this is a dra- this is a draft of the, o- of of what I, what I got online now. Actually, there's no link to it o- online but but there are links, the- there are links, ah, Fascicle five has three parts to it a- and there are links to the first part and the second part, a- and first one is called Fascicle 5A, the second one, Fascicle 5B. So, if you, if you change that link to Fascicle 5C, you're gonna, you gonna get a look at this, all right. [LAUGHTER] And and and in in in a month or so, I'll I'll, you know, I'll have a link to it ca- because I still haven't ma- made the index to this. And so I, so this is only for the people who are, you know, really courageous. Ah, ah, ah, I can't wait. Ah, but I, but now we get to the, oh, by the way yeah. There there's a a, I'm not gonna take time to zoom in on this but, ah, finding errors in this you get two fifty-six. [LAUGHTER] [NOISE] So so so it helps, pay your tuition. [LAUGHTER] Now, um, ah, so so, you can see the pictures of doubly-linked lists here and so on. Here's that very same, ah, matrix, er, ah, and and here's the way i- it looks in, um, let's see I gotta learn how to use - gotta learn this technology, ah. All right. Okay. Hello. I- I- I turned off the machine? [LAUGHTER] I- I- I hit the power button, I missed. Okay. So, um, yeah, that's that's it, that's a little bit of a danger, okay. So, ah, okay. So so so, in in memory, let's zoom in a little more. [NOISE] Yeah, my book is is interfering with the, with the, ah, o- okay. I'm had, I have to zoom, yeah. [NOISE] I have page numbers on here. I can get this back in order again at the end. [LAUGHTER] Okay. So, here we, okay. So hope you see, so this was the way it looks in memory. Um, and and everywhere there's a one in that matrix, I've got a node. Ah, and then a- and, ah, ah, there, and the the columns A, B, C, D, E, F, G, ah, are doubly-linked, ah, so so everything has a pointer instead to left and right, it has a pointer up and down. Um, and that, and in in the, ah, in the columns themselves, there are also pointers to the left and right. Ah, so these guys have four links. The- they have, they're doubly-linked horizontally and vertically both. Ah, a- and and that's the list of of columns that haven't been covered yet. Um, but the, but the vertical list are to all of the, ah, ah, the ways of covering that that particular guy. And, ah, in the old days, I al- also used to doubly link the, ah, ah, the guys indi- individual rows of the, of the matrix but that it turned out tho- those links were never changed and so there were no point in doing that. I just just keep it sequentially in memory. So so I have, ah, no- node 16,17,18. And then, and then, ah, each each, ah, ah, possibility has a spacer node before and after it tha- that tells you how to get to the end of the list or the beginning of the list i- if you encounter a spacer, if you encounter a spacer node. So this is, this is a faster data structure than I had 18 years ago. But but but the main idea is, ah, that that I've got the exact cover problem and it it's sitting here as a, ah, a- as a bunch of of of nodes in memory that are, that have links between them. Okay. Now, so i- if I decide to to cover column A, that means that I'm going to, I'm going to, ah, ah, ah, take out from this data structure everything every, ah, role that had, ah, that had something in A. So so I'm gonna take out this line. I'm gonna take out this line. And and so so I mark through, ah, like from 12 equal to 13 as take 13 out. So that's a delete delete operation. Delete 13 fro- from it- it's it's, ah, ah, doubly linked list. Delete 14 from this doubly linked list. And and similarly, this one I'm gonna delete 20, 20, I'm gonna delete 21 and 22 from from their list. Okay, so so, ah, no matter what I, what I do to cover, ah, to cover the A, I- I'm gonna be deleting all of these, all of these entries from the list. Now, whe- when I actually decide however to, ah, ah, that I'm going to, ah, try, ah, this one as a way to cover A, then I also have to, have to cover column D and cover column G. As I cover column D, that's gonna tell me I'm gonna have to delete, ah, this node 27. And I'm I'm sorry I'm gonna have to delete the row that contains 27. A- and and I walked down G and see what's still left in G and I see these two guys. Um, and so I'm gonna have to delete this line. Ah, this one has already been deleted. So so anyway, looking loo- looking inside, following one link after another, you see what you have to remove from these lists. Later on, when I'm gonna undo this operation, I can, ah, all of those links that I looked at are still there. I haven't cover and selected them away they- they're still sitting there. And so later on, when I wanna, when I wanna undo this operation, I can say, ah, I I chose 11. I looked at covering G, oh that means that I have to uncover G. And so, he tells me "Oh, yeah, put this guy back." And and and, ah, I did my deletions from left to right. So when I when I undo, I go from right to left. But all of those links are still sitting there. So, I I didn't have to store a single new thing in in memory in order to, in order to undo this complicated of removing from list to list. I'm walking through lists that didn't exist before. A- and and the, and the list jump back into place. Something like opening a zipper or something just before I need another link it- it- it's there and it's valid again. So so so this is, the this is a way that that you can walk through it in exact cover problem, ah, and, ah, and and, ah, delete, insert, delete, insert. And it never mess each other up. Ah, and, ah, it, and it, when you, when you look at it, ah, it just seems that that these these numbers in a computer are are following as elegantly choreographed dance. And so that's why I call a dancing links and I'm still waiting for, you know, for somebody to to write an app that that that takes his algorithm in an exact cover problem and and and, ah, and somehow animates it. So you you can see this thing. And as I'm debugging, I- I- I watch it happening and I marvel it but I wish I had a good visualization of of of the process. Okay. Any questions about this? The main point is that that even though the idea is extremely simple, ah, that one operation obviously undoes the other. Ah, the fact that I, that I didn't remove stuff from memory, means that all the scraps of information that I need to take me back are are there and they, and I keep changing them at nick. And once I needed, ah, ah, second-last, ah, ah, become available after I've done the last and after I've undone the last et cetera et cetera. Okay. So so that's the basic, ah, like a magical idea of of dancing link. Now, so so let's take a look at at at some applications. Ah, the easiest step of of. Uh, well, fi- first I wanna mention that I, I- I found out that there are so many applications that, uh, and I, I, I, I decided that, uh, [NOISE] as years went on, I didn't wanna think of this exact cover problem anymore as if it was a matrix of zeros and ones. I mean, [NOISE] I love zeros and ones. As a mathematician, I played with matrices of zeros and ones for years, but, but it- but it turned out that this- almost a really sparse matrix. And it's much better if I had some other, uh, uh, some other way. So, instead of talking about rows and columns, I talk about, um, options and items. And so, so the, the, the- these A, B, C, D, E, F, G, I call these items o- of, of my problem. And and then the various ways to cover the items I call options. So, so, we have options, um, a- and, and for example, the first option is CE, and the second option is ADG, and the third option is BC, the fourth option ADF, and two more options: BG, um, BG and DEG. Okay. So, so, instead of, instead of presenting my data as, as, as zeros and ones, I, I presented instead i, i- in a text file as as lines of options, um, and, uh, and thi- things in the option, uh, are I call them items. Okay. So, so, now I can actually talk about problems in which, i- in which items are rows instead of columns. For so- I mean, I, I- sometimes this- the, the terminology for, for all the a- applications of i- exact cover problem, uh, uh, uh, it, uh, wi- wi- will change from application to application, but, but, uh, uh, in every case, the word option has worked out well, and the word item has worked out well for the, for, uh, for the way to present it. So, so, let, let, so the the very simplest exact cover problems are the ones where there's only two items in every option. I- if there's only one i- item and option, that's even simpler, but that's so trivial. The, the, the, the main interesting ones, uh, uh, start when, when we have at least, uh, t- two items per option. Um, uh, and, uh, uh, the case where there's only one actually that, um, we, we have a shortcut to, uh, to handle it. So, so, um, uh, uh, the, a- and those are exactly the problems that uh, everybody knows under the name of, of perfect matching in graphs. I- i- if, if you have two items and an option, you can think of that as a graph with, ah, where that's an edge between those two items. And, a- and so, if we, if we wanna choose, uh, um, so, so that we- we've include- we've, uh, we've- now you have covered every vertex exactly once, that collection of edges where where every vertex that's called a perfect match in our graph. And a- and in general, um, a, a matrix of zeros and ones i- is, uh, it's called a hypergraph and the rows of a hypergraph are called hyperedges, and, and so this exact cover problem is the same as the problem of getting a perfect match in, in a hypergraph. Okay. So, so, um, uh, the the case of ordinary graph where there's, where there's two, um, one of the, one of the most beautiful examples of, of a perfect matching problem is the, um, i- it is called the, um, uh, it it it it, um, a problem made popular by Edouard Lucas in, in 19th century, and they call it the, the probleme des menages, this is the problem of couples. And, uh, and and so if you look in Wikipedia, you, uh, you get a very beautiful picture about the probleme des menages. The idea is you have, uh, you have n male/female couples and you wanna sit them at a circular table. So, in this picture, n is five. So we got 10 seats at the table and, and and the rule is, uh, that, uh, uh, has to alternate male, female, male female and nobody sits next to their s- spouse. So, so, so how many ways are there to to solve the the probleme des menages. In this, i- i- i- in this case, there's also a problem of, of how do you get a pink napkin for this place over here, but uh, but, uh, anyway, it's a nice picture. Um, and and this is a, uh, a- a- wha- a really kind of a nice practical problem. People face it all the time. Uh, uh, if they have a circular table and uh, and also, uh, uh, you know, there's beautiful mathematics because really what more could you add. Um, but, uh, let's take a look at it. Um, as I would set it up, uh, as an exact cover problem to, to my, uh, to my solvers. So, so, I, I have a bunch of solvers that I, that I call DLX. Um, some of you will know DLX as the, as the name of the ma- of the of the machine that Hennessy and Patterson used in their i- uh, i- i- in their book on architecture. Uh, uh, I, I had MIX and they wanted also to have a, a machine that was Roman numerals. Uh, uh, and so DLX is, is, is 560 and MIX is 1009. But anyway, um, now DLX is, uh, i- is actually, DL stands for dancing links here and X for exact cover. And and, uh, and so here's, here's, ah, a example data file, uh, and it's produced by a program called menage dlx with the parameter 5. Um, and, uh, and at first it states the item. So, so, the first line o- o- of the file input to DLX solver states all of the items. And, uh, in here I have items S0, M0 through S4- four there. There are, uh, there are five seats that have to be covered and there are five men that have to be covered, but I'm gonna assume that the women have already been seated somehow. No ma- no matter how we solve the problem we're gonna have, women are gonna occupy these ordinary seats. So, so, let's suppose that, that we, that, you know, there's lots of ways to, uh, there's, there's 2n factorial ways to do that, but but let's suppose that's already been done because no, no matter what happens, uh, we have to solve this residual problem after the women are seated. So, so, here we have then, h, uh, you know, I ha- I have, uh, W0, you know, the women are already sitting there. Uh, but but there are five seats, uh, uh, between them: S0, S1, S2, and so, and so on. A- and, uh, and then, and then, now, I've got to cover the five seats, ah, and I have to, you know, also cover them with five men; M0 through, through M1. And so, these are the people. And now, what are the options? So, so, we've got these 10 options to cover, uh, the the, uh, I'm sorry. The items, 10 items to cover, but the, but the op- the first option is S0, M1. So the, you know, man 1 can sit there as, man 0 can't sit there, man man 4 can't sit there because, because the- you're not allowed to sit next to your wife. Uh, so, so, so, S0, M1, S0, M2, S0, M3, uh, are the options for S0. Then there's options for S1, and so on, and so on. And I could have listed these options in any order, but, but these are the possib- these are the possibilities for, for the exact cover problem. And and, uh, and so, you know, make a doubly linked list inside the computer, uh, for this and, uh, uh, let, let me, uh, okay. Uh, let's- let me see where I am in my, in, yeah, okay, here I am. Okay. And so, um, fe- feed it to my solver and out come the answer. Um, and so, it turns out there's, there's 13 solutions to this problem. And let's just take a look at a typal one sol- solution number 8. Um, okay. So- solution number 8. So, this says, uh, S0, M0. This was two of three ways to cover S0. Uh, so we've already tried, uh, uh, the, you know, the first link, and uh, a- and here it is. It goes, it works S1, m- M4. Um, uh- Then, thi- this one says M3, S2 instead of S2, M3. It meant that, at this point, it says one of one it meant, after I've seeded S0, after I've seeded M2 here and M4 here, there's only one place for M3 to go. So- so it- it chose not to- to cover one of the S's, but you know, it looks at every item. There's no difference between the M items and the S items. One- one that has the fewest possibilities is the one that- that we tried to cover neck. And so, that's the way this particular solution came out. So actually they are 13 solutions. And how did, how did I get that well, for example here, I- I- I try, I tried for 3, 4, 5, 6, 7, 8, 9, 10 couples, each case I- I called my menages-dlx to generate the data and then I type it in. If I fit it into the DLX1 uh, solve it for that cover. And then I said oh, I actually echo statements like I can separate these out. So here's the. First of all, three men three women. There's three options of six items, nine total entries among the items um, because there are three options and nine entries but there should be, but that should be six. So what did I do? That's interesting. Why did that say nine entries? I have to check that out. Okay [LAUGHTER] Now, with four couples, we had eight options. With five couple, we had 15 options. And- and in the same, to think there are three entries instead of two for each option. So they- so that's a bit off by one somehow. That probably comes to something for the spacer, I don't know why. Okay, so, so we get 13 solutions with five. We got 80 solutions, we got 579 when there were ten couples 439,000 and some solutions. How long did it take to find these solutions? And- and all the algorithms in my book, I- I- I could tell you how many seconds it took, but that wouldn't mean anything next year because- because computers keep changing from year to year. So, instead I count how many references to memory were made, and- and- and that's not going to change. I mean, you can change the algorithm and find another you know, find a better way, but this particular method is gonna, is gonna, it's gonna read or write memory a certain number of times. And it turns out that for example, in his ten coupled case about a 180 memory references per solution. So it's piping out that I have to do much computation between solutions and these solutions are generated internally and they could have been pipe to file or something if I wanted to, but- but in this case I only count. Okay, any questions like, yeah? Do you have comparisons of [inaudible] that could have taken? Comparison with other algorithms, yeah. Yeah. I'll get to some of that quick. Because of course, this was- this was general purpose solver and- and when you get to a perfect matching problems, there is all kinds of different ways to solve a perfect matching problem as we know. [inaudible] What? Have you found a co-relation between memory reads and clock cycles? Yes. Yes, um, it- it- it- it's not, it's not as, it's not real tight, but and there are some problems that are more cache-friendly and others obviously. But this, I write about five new problems a week and- and it's been pretty steady for the last ten years the number of member. But you know, but if- but in my book, the Stanford GraphBase I have- I compared to six algorithms or something for minimum spanning tree and they use caches in different ways. And so the, the- the cost of a member per microsecond was, could definitely different, indifferent algorithm. Yeah. Okay good question. I will move on to dancing links. So um, this DLX software I'm talking about, it is is on the web. There's DLX1, DLX2 and so on. And you can download them from my homepage and it's not surprisingly written in C web, which is my favorite programming language. And, and you've got all the coding here. It starts out with in fact, an example to the very same example and uh, it explains the input data and various bells and whistles you have for running it. Big part of their, big part of the program is just inputting the thing into the doubly linked list in the first place, then- then we get the actual covering you know, so here's the cover sub-routine and it does the doubly-linked lists and does a deletion here. And then there's an uncovered which does the insertion operation and so on. So that's the program that you can take a look at. Now among the bells and whistles. I can say for example, here I tried it out on 16, on 16 couple. So, so now 16 and I- DLX1 and I, my first parameter is M one billion. And so it does show me every every billionth solution and then T1 billion says stop after you've found a billionth solutions. And then S says this is randomize when you're choosing between different options, I choose scramble the lists and- and do it randomly and see if that makes a difference. And this is the seed for random number generator. If I changed this seed, I would get another other random one. And then, okay, so now, standard by default, is that every ten, every 10 billion mems, it gives me a status report. When you're- when you're running a combinatorial problem, you don't like to just sit there and you want to know how it was doing. Uh, uh, you know, and so but every 20 seconds this was right now on my computer at home, the 20 seconds is about 10 billion mems, okay. [NOISE] And so it had found what, 52 million solutions turn on- during those first 2o second, and- and then, and then, it said well at the top level it's doing case one of 14, 1E, the E is hexadec- hexadecimal, so case 1 out of 14. After you, you know. So there are 14 ways to- to cover seed 0 probably, and then after I did that, there were 13 ways to cover some other seat and 12 ways and then. So I'm still working on the first. By the time I, by the time I, I'm- I'm down here, I'm- I'm still on the, on the first trace for through the first option in covering this one, but then I'm up to the ninth choice of this guy. And so you can watch this and you can see how far you are and also, there's a number at the end. It tells you percentage wise, how far have I gone. So, so at this point, I'm up to.003- Now, actually, the number of solutions to the menage problem is very close to N factorial divided by e squared. e squared is between seven and eight. And so this, you know, one out of every six, between one out of every seven, one out of every eight permutation actually works for this problem of seating people without being extra. Their spouses. And um, and so uh, uh, if you work out what 16 factorial, it's- it's I think, it's 21 trillion. And so you divide that by seven you get three trillion. So there's about three trillion solutions. And I said, you know, stop after the first billion. So anyway that's where we are. Okay. Now, and I knew, it would it would grind them out and that you know, I haven't in less than day. If- if I- if I really wanted, and- and- and the without randomization, this was going at at a 190 mems per uh, solution. I'm sorry, yeah, but a 190-192 billion mems in order to get 10 billion solution. So uh, or one billion solutions. And so that's, 192 personally, but- but it would have been a 175 if I hadn't if I hadn't use the randomization at every step. That's, you know, I had to generate random numbers, that takes more time. Okay. So there's an example of how I use this on one of the simplest problem, simple problem of a- of a perfect magic. Let me go next to a classic problem of computer science. The one we were watching on the movie, before it came in and the problem of N queens. Here, we're trying to put queens on a chessboard. The class of problem we have a ordinary transport and eight queens. And and so I want to get eight queens on the board. So that neither queen attacks another one, and and so now I set this up with another program called Queen's deal X8, to get the eight queens problem and it- and it sets up. It sets up the items are for C4. This is ranking column on a chessboard, and I put them in this order starting in the middle of the board and going to the edges because it- it's a little faster to decide on- on the on the queens in the middle but. But the interesting thing is that rows and columns are symmetrical. All of the textbook solutions to this problem go- go row by row. You first put a queen in row ze- zero then row one, you know, something rather and- and- and you try different cones but- but in this case, you know, sometimes it's better to- to choose a column because- because there's only a few ways left to- a few empty spaces left in that column. So, instead of going row by row, uh, the- this approach by options doesn't- doesn't distinguish between- between them [NOISE]. But then they have this vertical bar here [NOISE]. Uh, and so, there's secondary items coming up with a vertical bar. Secondary items. You don't have to cover them but you- but you're allowed only to cover them at most once instead of exactly one. And so- so a secondary item, these are for the diagonals. So- so, in the queens problem, I've got- I've got eight rows- I've got eight columns but I've also got 15- 15 diagonals going this way and 15 diagonals coming this way. And- and so there's an option for example r2 c5 a7 ba. This is- this is r2 c5, uh, b- b10 and a7. So, it says that I- I can't occupy a diagonal more than once, but I- but- but I don't have to occupy a diagonal exactly once [NOISE]. Okay. So, this is- in this case, uh, some of the options here have only three items but most of them have four items. Uh, and so that's the- so the N Queens problem [NOISE], uh, but another nice example of- of exact cover. Um, and so here I tried it for up to 16 queens, eight queens up to 16 queens. And, uh, so eight queens [NOISE], you now there's always 92 solutions and so on. You get up to, uh, when I get upto 16 queens it I- I hadn't solved them all. By default, it- it gives me this progress report, um, after every 10 billion mems. So, I got here. I- I was in case four of 16 cases, uh, after- after 10 billion. Finally, at the end, and it- it took a minute and 16 seconds to get all of the, you know, 15 million solutions to the 16 queens problem. And- and, uh, this compares favorably to special purpose algorithms that are written. Of course the- the world champions of solution to the n queens problem. Gosh, I forget exactly how far they got. But anyway they built an FPGA series and so on. They- they [NOISE] massively parallel [NOISE] squeeze everything up. Okay. Next problem, uh, you might recognize. This- this was in the Palo Alto weekly, uh, week a go on Friday, uh, [NOISE] I- I- I gotta talk about Sudoku because this is one of the great, uh, simple things I could do with this- with this exact cover algorithm. Um, So- so Sudoku. Some people say it's- it's- it's the most popular recreation in the world at the moment. Um, anyway this was the problem we had in last week's weekly sought. So- so here it is as a, uh, I have Sudoku DLX but and- and it puts out a whole bunch of items here. I did- didn't wanna list them all. Uh, but there's- there's an item for every empty cell. There's an item for every row [NOISE] every th- number that hasn't appeared in a row or a column or a box. Uh, so, uh, if we take a look at for example, these- these two options here. Uh, can you see that? Um, this is a P85 r81 c50. This- this option corresponds to putting a one in- in- in- in row eight and column five. I'm numbering from zero. So- so that would- that would- that would be the bottom row and- in this column so I would- that would be like putting a one right- right here. And the next option is- is for putting a seven in that- in that place. So- so that would say, you know, cover, uh, put something in p85. [NOISE] Put your seven in row eight, put your seven in column five, and put your seven in box number seven. So- so that would be one of the options. And- and after I've solved the- the problem I'm gonna have exactly one option for- for p85. I'm gonna have what- exactly one option for- for r87. I'm gonna have one option where I- where I chose a seven in this row, I'm gonna have one option where I chose a seven in this column, and one option where I chose a seven in this box. Okay. So- so- exact cover comes. Okay. So- so this, you know, this cruises is to victory in- in incredibly fast. So- so if you look at the solution to the problem, um, it- it- it's a well- there's only way- one way to, uh to fill p33. And after you fill that, then there's only one way to do 43 and so on. There was only one choice. I think- that- there would never- you never had- to stop and thinking, only how to do do is [NOISE] we go down. In- in fact, uh, that particular problem, uh, there was also only one way to- to put a three in column one- in row one or- or- or- or in row five, or only one way to put a foreign column on it and so on. They- they were all kind of force moves, you know, waiting for you [NOISE] to do. So. It turns out that if you look at- at over the years like on an airline I- I- I look at a magazine or I, you know, I may seen The London Times, or wherever I am I- everyone's awhile. I- I took a sample of the Sudoku problem that they were doing and arranged fro- from problems that were called, you know, diabolical and impo- impossible and so on. And- and- and I never found one that needed a search tree of more than 280 nodes. And [NOISE] it's almost always- it almost always really- really [inaudible] even with the- with the- with the limited heuristics that- that are in here. Well, I got a lot more to talk about those, so it's like I can't dwell on it, um, but I do wanna mention that- that since Sudoku is such a popular problem, I do- I do have some- some pages about it. And- and here's for example, uh, a Sudoku problem where the clues are 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9. So, you know, it has- it has the first 32 digits of pi. [NOISE] And a. And since my Sudoku covers so fast it wasn't hard to interactively uh, do this. I thought this was uh, an original idea. But I learned earlier this year that uh, Johann, the writer had already done this uh, work five or six years ago. And Johann, are you here tonight? Yeah. Oh, here you are. Okay. So um, and I thought he lived in Netherlands, but I got to meet him a couple of months ago. Uh, so uh, I think you know that over the years, whenever I have to choose an example in my book, I try to base it on pi if I can. And at the next one here is 314159, it doesn't, it's not perfect, but it has only 17 clues in it. And it's known that every Sudoku with a unique solution you have at least 17 clues. So this one has only 16 um, and so it got to have two solutions. Uh, but it turns out that uh, it doesn't use either a seven or eight anywhere. And so those two solutions are exactly the same except that you switch seven and eight. Um, okay, so anyway, lots of interesting fun things to do about Sudoku and I can't, I discussed how it corresponds with the dancing links algorithm and there are jigsaw Sudoku, which were instead of having three-by-three boxes uh, you can count the boxes be arbitrary size and here it turns out. Okay. Here's pi. Uh, giving a unique solution with the jigsaw Sudoku. All right now, um, But exact cover problems go to many other uh, cases, and uh, one of the uh, first that I knew about were problems like uh, polyominoes. How many people have heard of pentaminoes. We got about one out of four, okay. So this was all a rage in the 60's to taking these shapes and packing them into rectangles. How many people know about the Soma cube? Not as many. So the Soma cube is a three-dimensional toy. We're supposed to pack um, these seven pieces into a three by three by three uh, cube. And this was uh, such a popular. I mean, there were more than 2 million uh, Soma cubes in America alone, in 1970. This was before Rubik's Cube, this was the cube. And uh, I- I- I brought my set here tonight, but I don't have time to. You know. But anyway, I'm really proud of this because I got it in Denmark, beautiful Rosewood pieces um, and just as I was setting out on a desk here, I found out that this one came apart. But anyway [LAUGHTER] It's actually uh, how can I say it? It's um, a pleasure to play with these things. And so one of the greatest mathematician, John Conway, spent lot of time figuring all kinds of neat things out about Soma and also these have lessons in general, for exact cover problems because as I point out in the next uh, few pages uh, by reasoning about uh, there are a lot of tricks you can apply to exact cover problems to uh, simplify it and throw out a lot of options. And so uh, in particular for the Soma Cube, it turns out that uh, you can prove for example, that uh, that this piece has to go on an edge. Without loss of generality, you can start put this here and any solution can be rotated so that this is on the bottom. Okay. So that's uh, and it's a general principle about combinatorial uh, problems in general that I call factoring. Okay, now, er, but got to keep moving. Um, So let's go on um, to do Soma Cube. Uh, I have uh, items are the different pieces uh, and the different cells. And so the different options are to say a W uh, use piece WN fill cell 212, 213, 222. All these options and total weight who works. Okay now, [NOISE] let's go to another kind of problem. Er, this was a, let's see. I got. I got in here.Um, there was one of the great masters of combinatorial mathematics uh, was Major Percy MacMahon, of the Royal Artillery. And he was uh, what was the greatest combinatorial mathematician early 20th century and uh, in 1892 he has this patent on a game uh, plans, to use and play a new kind of game. And basically uh, he had 24 triangles and each triangle [NOISE] uh, was numbered zero, one, two, or three. You could think of this as four colors on the edges of the triangles. And you wanted to put these 24 trials together so that edges matched together. And uh, he became president of the London Math society and when 1921 came out with this book about mathematical pastimes and one of them was uh, his problem on not on triangles, but on squares. So again he has 24 squares. In this time, there are three colors instead of four. [NOISE] But there's exactly 24 different ways uh, to color the edges uh, with three colors uh, with three given colors and then he puts them together. So I got another set of tiles here. Uh, this is for MacMahon's uh, 24 things it arranged with here in the five by five grid instead of a four by six. But the four by six problem was the one that we've branded. And I mentioned it, because it has an interesting connection to Stanford AI Lab. Uh, one of the very first reports of the Stanford Artificial Intelligence Project is number, number 12 in 1964. And I believe it was the first large computation ever taken at Sta- in Stanford's AI department. Uh, the documentation with MacMahon's squares problem. And so he uh, sets it up computer program uh, er, could count how many solutions there were and uh, the program ran for 40 hours. And uh, he says right here um, total of 12,261 solutions exist. And so this number 12,261 was quoted in lots of publications throughout the 60's. And and so, it turned out that it was wrong. [LAUGHTER]. And uh, in 1977, uh, a man in Argentina. He's actually the director of a technical college in Buenos Aires. Uh, recomputed it and got about 4,000 more solutions. This program has had long gone, so I have no, we have no idea what the bug or bugs were in it for them, but I had to mention it as a piece of history. Well, it- it sets up there very nicely as a, b- but none is an exact cover problem of the normal kinds, because here's because here's here- here's a very important point. I- I'm extending the exact cover problem to something where it's the exact cover problem with colors or with color controls, [NOISE] and so, uh, uh, this, this is really wha- um wha- what I want to show you e- especially this new this new kind of combinatorial problem of where it's it's not exactly new but it bu- but it's, er, I'll try to explain why, I think it's- it's important [NOISE]. So I, so it just so it, it goes beyond, uh, uh, uh, wha- what I've said before. So so, the items, uh, fr- from the MacMahon's squares problem uh, there's an item for each cell, and there's an item for each kind of thing, but then I ask after the line I had these secondary items, and I have a secondary item for th- the each horizontal edge and each vertical edge in the diagram. Um, and, and now the and now with this new kind of problem which I call an XCC problem and that's ex- exact covering with color constraints, XCC. All right, uh, if you think of a better name, we might be- we might not be too, too late to change it, but anyway XCC has been working for me for the last three years. Um, so, XCC problem says, uh, for, for every secondary thing, I can give a color to it, and, and, and, and that means that you can use the secondary item more than once, with, with the queens problem, I was only using the the diagonal items what, uh, and most ones but, but I didn't give them colors. Uh, it is as if I every in every option of that problem, as if I had a new color for every option, but this time, uh, uh, you know, I- I can say, this secondary item the a vertical line number zero, zero is color A, and, and this secondary item is color A, and this secondary and and it's all for, for the different options I have. I- I- I can pick one of the one of the pieces like the BBBA piece, and, and I can rotate it different ways and I- I- I can put it in this particular place and that, and that gives colors to these things. S- so the rule is, o- on the, on the primary items, you have to cover your primary item exactly once. On the secondary item, uh, uh, you- you- you- you're allowed at most one cut. You- you can use the the secondary items more than once but if you do, they all have to have the same color and that's the ru- that's the that's the rule for XCC problem. Now, um, uh, I didn't realize un- until a, a year or so there was like like, uh, I think it was in that a year and a half ago, how, how widely I- I- I kept solving more and more problems [NOISE] er XCC problem but I didn't realize how, how, how generally it was, uh, until, until I want to co- convey some of that to you tonight. Um, uh, b- by by for as an example, uh, and so, uh, one example I have in my book, uh, is, uh, i- i- is based on another popular, uh, re- recreation that you find in, uh, that that you find in magazines and, and newspapers. How many people know word search problems have we seen, word search problems? We got a, a few, okay so so, on page 23 of my thing I got this problem here. Find the mathematicians. So, so put ovals around the names where they appear in this 15 by 15 or eight. Abel, Bertrand, B- Borel, Cantor, Hensel, Hermite and so on. Uh, you know, th- the and, and they can appear either left or right, like here's Catalan, uh, or they can appear right to left, um, uh, uh, uh, and they can appear diagonally up, up or down. So, there are eight ways they, um, uh, a, a name can appear, and, and I say here, uh, [NOISE] uh, take a break before reading any further. Spend a minute or two solving this puzzle, and, uh, because the- then you'll get the idea for wh- why this is a natural for exact co- cover with color. Okay, so on the next page, there's a solution. Look at that Catalan and Landau or book were were both there, here's Hadamard upside o- okay and so that's it. Now, the question is of course, not how to solve this problem, this pu- this puzzle, you know, it's just determining you just go scanning it you don't and it's just, uh, uh, no-brainer, uh, you just have to ha- ha- have to look at eight pa- eight passes for example and, and you find them. But the but the tell me, how do you design the puzzle? How do you pack all these, uh, all these names in here? So, so, for example, let's suppose I, suppose I have a six-by-six array, and I want to and, and I want to fill this array with, uh, [NOISE] uh, with, with 12, uh, with 12 words O-N-E, T-W-O, T-H-R-E-E, now one, two, three, four spelled out all the way up to 12 [NOISE], and so, for example here's 12 at the bottom, can can you read that there, T-W-E-L-V-E? Is that, is that too, too light? Uh, and six is there but if you know 11 is up here er. So, if I had to pack all of those words into a six-by-six array, how could I do it [NOISE] And and, and also with one space left over? And so, I set this up as a, er, you know I- I have a problem that, uh, A, A is driver that takes any word search, uh, uh, pu- put six-by-six here and a- and it fits in a, a dot for the empty space, and then one, two, three and, and he puts it in. Ho- how do you do it? Well, just to, er, it's just a color problem, uh, where, uh, I- I have to I have to cover o- one because I have to have so- I have to have a one somewhere on- that's one of the options is to put it here, here and here, all right. So, so, for each option that I have for, for pu- for putting in O-N-E, uh, th- there's a line here, it and similarly for, for T-W, er, O and, and pu- as long as the colors don't co- conflict I'll, I'll get a solution for this practical. [NOISE] Okay. So, uh, besides word, er, besides these words search problems, there's also word wo- word cross problems. So, so, that's exercise, 185, let's see here. So here so, so here, here's an example where I wh- where I, uh, I, I pack the to one, two, three or I, I even have zero in here, ze- zero up to, er, but here I have, uh, bu- but there are different rules, th- they all have to read like in a crossword puzzle, uh, left to right or, or, you know, crossword down. Uh, er, until I, and, and, er, not allowed to, uh, yeah have spaces between words and things like that. So, so, ano- another packing problem as it turns out, uh, uh, sure enough, um, um, that packing problem can be done with, uh, XCC problem here, and also I, you know, I have, er, I have different i- items that have to be covered, and then the and then di- different ways. So, the zeros and ones see do I have a to space here or not? Or, or, or a letter? Okay so, that was that's complicated, but it's, it's there i- in the book if you want to see. So, now le- let, let me go to, um, uh, to wha- what the, uh, many people consider the sort of the, the most impo- important class of combinatorial problems of of called CSP problems, uh, constraint satisfaction problem [NOISE], and, and, and constraint the model for constraint satisfaction problem, is that, that you're given a, a bunch of variables, uh, in different domains, uh, and you're given relations between the variables that have to be satisfied. Uh, [NOISE] and so, so there's, you know, many conferences or- organized around CSP. There are journals devoted to CSP, and the same model of, of CSP, al- also it's, it's equivalent to the model that joins in databases and it's equivalent to, uh, physicists models of, uh, of, uh, interaction between molecules and things like this. So, it's it, it, it's a very general problem, it turns out to be a, a special case of the XCC problem. So, so, let me, let me try to explain. Here's e- easy CSP, so Constraint Satisfaction Problem, let's say the variables are A, B, C, D, E, and F [NOISE], each variable is ternary has a domain zero, one, two. The first constraint is that a B and C have to be cy- in cyclic order, uh, also D, E, and F. The third constraint is, C has to be less than or equal to D and fourth constraint A less than E. So, so, now, let's set this up as a i- in XCC problem, uh, uh, [NOISE] uh, a line that begins here is, is a comment. So, so, uh, constraint one says that A is zero, B is one, C is two or, er, there are three ways to fu- to fulfill constraint one, and, and I those are three options here, uh, A, B, and C are cyclic. There's three are options for D, E, and F, they're cyclic. Uh, there's six options for C and D because C is less than or equal D. So, C that can be zero, zero, zero, one, zero two and so on, uh, and the and fourth constraint A less than E, okay. So, that's a, uh, i- in general when people have CSP the- they, they have ways of, of abbreviating co- constraints and sort of saying that these are all different or things like this, a- and there are also tricks, uh, to, to encode that, uh, the XCC, but but in general you, uh, you see that, uh, the, the sort of, uh, generic CSP is a special case of this coloring problem a- and the options are a very particular kind, each option has only one primary item and all of the secondary items a- are for that primary item are, are in the same exact same variables, exact same secondary item. So, they are in extremely small class of of XCC problems exactly covers all of the CSP problem, uh, it makes sense. Okay, so now, um, [NOISE], here's another, uh, uh, a- another example, uh, for, uh, for, uh, wh- what I- I'm going to have to, to move faster but one, one of the classical problems of, of computer science is, is called a combinatorics is to find a de Bruijn sequence, and, and this is a sequence of zeros and ones that contains an- and it's sub-sequences is it contains every possible, uh, n-tuple, and, and you can generalize that, uh, uh, uh, and say, uh, let's see what, what I have a page, I'd like to show it to you. Um, oh well, yeah. Page 20 [NOISE] so. [NOISE]. I am, uh, [NOISE] I- I talked about XCC. We wouldn't go beyond XCC as well. And- and- and instead of saying that I have to cover every primary item exactly once, I can also- I- I can also say, no, let's- let's cover it a range of times. Let's say that, uh, the first primary item should be covered either once or twice, the next one e- uh, exactly five times, the next one once through eight times and things like this. So- so- so I call this an MCC problem. This is a- this is a- a- [NOISE] a problem with color constraints and multiplicity. Um, and- and one example of this is that we can call the- the, uh, the- the partridge problem because, uh, uh, because a- Bob Wainwright [NOISE] was singing, uh, on- on the, uh, on the 12th day of Christmas my true love gave to me, and he had various partridge [NOISE] in a poetry. And, uh, and- and so he- he- he said well, [NOISE] er, it turns out that [NOISE] that the sum of the first N cubes is the square of the sum of the first N numbers, [NOISE] whi- which says that I- I should be able to take a one-by-one, and two two-by-twos and three three-by-threes and- and so on [NOISE], and- and N by Ns, and put them together in a square. Uh, and- and it turns out you can't do that until- until N is eight. But here's an example where you quer- you have eight, eight- eight by eight squares and seven seven by seven, and six by- and so on. We call this his partridge problem. [NOISE] And, er, you- you can solve this very nicely as MCC problem by saying that the- that, uh, you- you cover the eight guys eight times instead of once. All right. So- so, I- I also could be- could generate de Bruijn sequences so that I- so- so I have a sequence that, er, er, [NOISE]. Let's see. [NOISE] And it turned out that this problem has in fact 50,000 solutions but I- I chose the first solution. I- I want to get all- all four tuples, ah, in such a way that the- that, uh, i- if there's- if there's one one in the fourth tuple it curves once, if there's two two's it curves twice, and so on. So- so here's, he- he- here's a 32 cycle. Zero, zero, zero, one and so on. It repeats, er, 32 times. Starting at zero, I got zero, zero, zero, one. Starting at one, I got zero, zero, one. So, here I listed ah, different times, and- and so i- if something has two ones and it- it occurs twice in a cycle. If it has three ones it occurs three times in the cycle. Very easy to set this up as an MCC problem and literally get all the 50,000 answers. Well, um, I- I- I see the- I'm aware of the time so I gotta- I just gotta show you, um, uh, uh, maybe I'll gi- save this for next Christmas, I don't know. [LAUGHTER] But, uh, but- but I have so many, like, you know, I have so many things I wanted to do show and tell. So, um, I- I'm just gonna go through quickly now, and just- just show you, because all of these problems use XCC, er, mostly and sometimes MCC. And, uh, and so that's why I say I was like a kid playing with a new toy. And so, I'm going to just ru- run through quickly now. And- and yo- and you can go online and look at any of these that you're interested in. Uh, here, for example, ar- are some word problems where I got, uh, the common word stairs. And, this is a cyclic arrangement of words so that you can read them across or you can read them down, and- and makes words both- both ways. And- an- and here I could do so- so you can- you can make the stairs go this way or the stairs go this way. And here you use the same words and- and either ways you- you get different words, but it all works. Uh, that's very easy XCC problem. Uh, exercise 178, well, this was a application to music. If you wanna compose be- beautiful music twelve-tone system. Um, okay. They- I talked about the MacMan problems but there's- but there's um, um, but that was just the beginning. Um, oh, I'm sorry. Uh, so, um, [NOISE] for example, the- there's a set of- there's a set of 24 tiles that MacMahon didn't think of. That, uh, that turned out to- to make some really fascinating problems that- that you can- you can match e- edges, e- vertices instead of edges, and that gives you some really tough problem. He- here you can match both vertices and edges. Uh, you can also use hexagonal grids. Uh, there's three-dimensional matching of faces and cubes. Um, okay, now on page 83, I have more about the N queens. Um, so besides- be- besides finding all solutions, it turns out that we, uh, uh, I- I forgot to mention a DLX2 which does this- this cu- current problem. It's almost the same as DLX1. I- I can use all- all that code and just add a couple of more subroutines, uh, to put on this color constraint. [NOISE] But then, there's DLX5 which- which also says find the minimum cost solution. So, instead of finding all solutions, finds the solution that minimizes so- some cost. And for each option, you give it a cost and then choose it's options that have the smallest total cost. And so, here I took [NOISE] N Queens and I gave a cost, say, putting a queen somewhere it, ho- how- what's- what's the distance, uh, from the center? [NOISE] And so, you find the solution to the N Queens problem that have- that have the- the shortest distance to the center, [NOISE] or the longest distance to the center. Uh, or the- in this case, the, uh, the shortest i- if you take the Nth power of the distance the- the N go to infinity, then you get these patterns, which- which I believe are the most beautiful. [NOISE] I've got problems the- the- there's some delightful pieces called windmill dominoes, there's 10 of them. We- we take an ordinary domino and- and you put a half size domino at 45-degree angle above it. And then, there are lots of fascinating things that you can do to put them together, uh, so- so that, for example, you get a path of- for both colors. In this case, it gives you a good path on the top and not on the bottom. Here it gives you a good pa- good path on the bottom, but not a loop on the top. But, if you're clever you can get loops on both sides. Um, and so, um, then there's- there's- there's problems about Mondrian dividing rectangles into rectangles. A- and then I- I finish it with- with puzzles that- that appear in a- in lots of- of books and magazines. Uh, uh, first of all there's, uh, there's Futoshiki, which, uh, and then there's KenKen, and there's Slitherlink, and there's Masyu. All of these are- are- are just as fascinating as- as, uh, as Sudoku and probably more. A- and there's Hidach- this is Kakuro, and this is Hidato, and ah, Hitori. Anyway, these are all- I- I like to think that- that these pages contain the best write-ups ever made of- of those seven puzzles. [LAUGHTER] Ah, but anyway, uh, yap, uh, uh, it- it was great fun to, uh, to write about them, and they all involve pie somehow. Okay. Well, um, here I am, 8 o'clock, so, time to go. I- I wish you all a merry Christmas. But, uh, but I hope I- I've explained to you why I- it's taken me so long, uh, to finish this- this particular part of Art of Computer Programming. But I really think, uh, that- that, you know, the DLX hours, I- I- I can't see why this isn't going to become kind of a- a- a- a new thing. The old, you know, there's already a $1 billion industry for CSP but this goes a lot further. And it seems to have lots of potential, so I'm- I'm kind of feeling that I'm- I'm- I'm trying to in- trying to in- introduce it and, uh, and- and I- I- it looks like it- it- it might tell a really bright future for people having better and better DLXRs as time goes on. Thanks for your patience. [APPLAUSE] [NOISE] Thank you. Okay. Okay, so don't feel bad about walking out but- but- but I- I could take it. It's just one question anyway, and then I can handle other questions afterwards. So who's- who's got a question that they wouldn't mind having online? [LAUGHTER]. Yeah. [inaudible] that students created? Yes. Did you ever write down segments, you know, what kind of exact solving problems are exciting to play? No. [LAUGHTER] No. But, uh, there- there are some that- that are obviously more, uh, more addictive than others. But- but- but the- the ones that I, you know, I gave them these seven out yet, Nicoli has encyclopedia, 200 puzzle. Okay. And took- I- I took the ones that are- that are most popular but also [NOISE] most different. Because each of those seven used a different technique. So- so, I- I learned something with each- with each of those. I- there was another thing that I could do with XCC that I didn't know I could do. [NOISE] Okay. Thanks a lot.
What a pleasant individual. I wonder if he mellowed with age or if he was always this way. Maybe I’ll search for a video of a younger him later. He’s definitely no Dijkstra.
Knuth has an incredibly nice (and, in parts, colourful!) paper for this:
https://arxiv.org/pdf/cs/0011047.pdf
I'm not much into reading formal computer science research papers, but this one was actually pretty accessible, and I had a lot of run implementing the algorithm in C. It was so clearly spelled out that my program pretty much ran first time, despite all the pointers flying around in it.
Came to see Knuth dancing. Dissapointed now
One of my kids got a kanoodle game for their birthday.
A few weeks later I had gone down a rabbit hole that finally ended with dancing links. Fantastic recursive problem and solution.
After watching this, I spent my last couple of twitch streams implementing a version of Dancing Links in C++ for use from Haskell:
[ Part 1 | Part 2 ]
My next step is to implement Dancing with Decision Diagrams.
[Edit: Done ]
About 10 years ago I used Dancing Links to solve Sudoku. It's a so beautiful algorithm!
A few years ago I used dancing links to implement not exact cover but maximal independent sets. That was fun! :)
My final year BSc project was based on implementing his dancing links with algorithm X!
Thanks for this :)