Just another WordPress site   To do it solving this one optimally using breadth-first search would probably– would definitely– take more than the lifetime of the universe So don’t try seven by seven by seven Leave that to the cubing experts, I guess I think no one will ever solve a seven by seven by seven Rubik’s Cube optimally There are ways to find a solution just not the best one So let me tell you just for fun, as an example This Pocket Cube, which is a two by two by two Rubik’s Cube What we have in mind is called the configuration graph or sometimes configuration space But it’s a graph, so we’ll call it a graph This graph has a vertex for each possible state of the cube So this is a state This is a state This is a state This is a state Now I’m hopelessly lost Anyone want to work on this? Bored? No one? Alright, I’ll leave it unsolved then So all those are vertices There’s actually a lot of vertices There are 264 million vertices or so If you want To the side here Number of vertices is something like 8 factorial times 3 to the 8 And one way to see that is to draw a two by two by two Rubik’s Cube So these are what you might call cubelets, or cubies I think is the standard term in Rubik’s Cube land There’s eight of them in a two by two by two Two cubed You can essentially permute those cubies within the cube however you like That’s 8 factorial And then each of them has three possible twists It could be like this It could be like this Or it could be like this So you’ve got three for each And this is actually an accurate count You’re not over-counting the number of configurations All of those are, at least in principle, conceivable If you take apart the cube, you can reassemble it in each of those states And that number is about 264 million Which is not so bad for computers You could search that Life is a little bit easier You get to divide by 24 because there’s 24 symmetries of the cube Eight times three You can divide by three, also, because only a third of the configuration space is actually reachable If you’re not allowed to take the parts apart, if you have to get there by a motion, you can only get to 1/3 of the two by two by two So it’s a little bit smaller than that, if you’re actually doing a breadth-first search, which is what you’re going to be doing on your problem set But in any case, it’s feasible That was vertices We should talk about edges For every move– every move takes you from one configuration to another You could traverse it in one direction and make that move You could also undo that move Because every move is undoable in a Rubik’s Cube, this graph is undirected Or you can think of it as every edge works in both directions So this is a move It’s called a quarter twist This is a controversy if you will Some people allow a whole half twist as a single move Whether you define that as a single move or a double move is not that big a deal It just changes some of the answers But you’re still exploring essentially the same graph So that’s the graph and you’d like to know some properties about it So let me draw a picture of the graph I’m not going to draw all 264 million vertices But in particular, there’s the solved state– we kind of care about that one, where all the colors are aligned– then there’s all of the configurations you could reach by one move So these are the possible moves from the solved state And then from those configurations, there’s more places you can go Maybe there’s multiple ways to get to the same node    And then if you add up– Each of these is an edge You have to be a little careful In undirected graphs, each of these is a half edge So there’s actually two times e nodes over here But it’s theta E So theta V plus E is the amount of space we need And ideally, all our algorithms will run in this much time Because that’s what you need just to look at the graph So let’s do an actual algorithm, which is breadth-first search So to the simplest algorithm you can think of in graphs I’ve already outlined it several times You start at some node You look at all the nodes you can get to from there You look at all the nodes you can get to from there Keep going until you’re done So this is going to explore all of the vertices that are reachable from a node The challenge– The one annoying thing about breadth-first search and why this is not trivial is that there can be some edges that go sort of backwards, like that, to some previous layer Actually, that’s not true, is it? This can’t happen You see why? Because if that edge existed, then from this node you’d be able to get here So in an undirected graph, that can’t happen In a directed graph, you could conceivably have a back edge like that You’d have to realize, oh, that’s a vertex I’ve already seen, I don’t want to put it here, even though it’s something I can reach from this node, because I’ve already been there We’ve got to worry about things like that That’s, I guess, the main thing to worry about So our goal is to visit all the nodes– the vertices– reachable from given node, s We want to achieve V plus E time And the idea is to look at the nodes that are reachable first in zero moves Zero moves That’s s Then in one move Well that’s everything you can reach from s in one step That’s adjacency of s And then two moves, and three moves, and so on until we run out of graph But we need to be careful to avoid duplicates We want to avoid revisiting vertices for a couple of reasons One is if we didn’t, we would spend infinite time Because we’d just go there and come back, and go there and come back As long as there’s at least one cycle, you’re going to keep going around the cycle forever and ever if you don’t try to avoid duplicates So let me write down some code for this algorithm It’s pretty straightforward So straightforward, we can be completely explicit and write pseudocode There’s a few different ways to implement this algorithm I’ll show you my favorite The textbook has a different favorite I’m going to write in pure Python, I believe Almost done I think I got that right So this is at the end of the while-loop And at that point we should be done We can do an actual example, maybe I’m going to do it on an undirected graph, but this algorithm works just as well on directed and undirected graphs There’s an undirected graph We’re given some start vertex, s, and we’re given the graph by being given the adjacency lists So you could iterate over the vertices of that thing Given a vertex, you can list all the edges you can reach in one step And then the top of the algorithm’s just some initialization The basic structure– We have this thing called the frontier, which is what we just reached on the previous level I think that’s going to be level i minus one Just don’t want to make an index error These are going to be all the things you can reach using exactly i minus one moves And then next is going to be all the things you can reach in i moves So to get started, what we know is s s is what you can reach in zero moves So we set the level of s to be zero That’s the first line of the code There’s this other thing called the parent We’ll worry about that later It’s optional It gives us some other fun structure We set i to be one because we just finished level zero Frontier of what you can reach in level zero is just s itself So we’re going to put that on the list That is level zero. i equals one So one minus one is zero All good And then we’re going to iterate And this is going to be looking at– The end of the iteration is to increment i So you could also call this a for-loop except we don’t know when it’s going to end So it’s easier to think of i incrementing each step not knowing when we’re going to stop We’re going to stop whenever we run out of nodes So whenever frontier is a non-empty list the bulk of the work here is computing what the next level is That’s called next It’s going to be level i We do some computation Eventually we have what’s on the next level Then we set frontier next Because that’s our new level We increment i, and then invariant of frontier being level i minus 1 is preserved Right after here And then we just keep going till we run out of nodes How do we compute next? Well, we look at every node in the frontier, and we look at all the nodes you can reach from those nodes So every node, u, in the frontier and then we look at– So this means there is an edge from u to v through the picture We look at all the edges from all the frontier nodes where you can go And then the key thing is we check for duplicates   