It is really amazing to know that the ground work for routing algorithms have been laid with ARPANET itself. The distance vector routing protocol and the new improved link state routing protocol etc. have been invented and applied when operating ARPANET. In one of those famous papers, The ARPANET routing algorithm, the BBN folks (who were given the task of setting up, operating and maintaining ARPANET) lay three functional properties of any routing protocol:
A mechanism to measure the delay to appropriately allocate a cost to the link
A mechanism to reliably distribute the information among the nodes in the network
A mechanism to calculate the shortest paths given the costs and the connectvitiy information.
Measuring delay may be very necessary then, but does not sound so anymore given all the high speed links. The cost in case becomes mostly the administrative cost. The algorithm to calculate the shortest path has already been invented by Dijkstra. After this paper was published, and when everybody was thinking everything is fine with the new routing protocol, suddenly something happened in the ARPANET and it collapsed. It turned out that it was a hardware problem, but still the routing protocol could have done something about it to prevent the damage that occured. Radia Perlman (yes, the same brilliant lady who later on invented spanning tree protocol and rbridges) wrote a paper that details how information can be distributed reliably among the nodes in the network. Those foundational principles can be seen even today in the OSPF protocol.
The N-Queens Problem goes as follows: In a NxN square chess board, place all the queens so that they cannot kill each other – technically, it means no two queens can be in the same row/column/diagonal. As they say, part of the problem is solved by properly (mathematically or otherwise) phrasing the problem.
What does it mean to say the two queens are in the same row/column/diagonal? If we take $latex (r1, r2 .. r8)$ to be the row numbers of the queen for the columns 1 to 8, then for any i,j such that i is not equal to j, then if ri not equal to rj, it means that the two queens in question are not in the same column and same row. But how to make sure they are not in the same diagonal? Note that (ri, i) represents the co-ordinate for a queen on the chessboard. Two queens are in the same diagonal if one of the following is true: ri + i = rj + j or ri – i = rj – j. I took a 3×3 square and worked out to understand this.
Once these conditions are met, then it is more or less straight forward to do the actual check – loop over all values of column and row – if there is any failure, backtrack and start fresh with new values. Backtracking is one of the most elegant (may not be efficient) solutions to this problem.
A slightly related problem is detecting cycles in a di-graph (or a simple graph for that matter): This again takes a node, puts it in the list and tries to find its neighbors and adds them to the list, when it sees any neighbor (to be added) as the initial node, there is a cycle and it is noted. I will shortly come up with code for both of these problems.
An engineer is a man [woman] who can do for a dime what any fool can do for a dollar -Anon
Is the high paying software industry a set of engineers or fools? 🙂