Resistor grid problem

• posted
I believe this came from an interview question asked of prospective
too much of my time. I am hoping someone here can give me an answer ao
that I can go on to other things.u
Suppose you have an infinite square array of nodes. between every node
and its four closest neighbors a one-ohm resistor is connected. What is
the resistance between two nodes separated by a chess night move? That
is to get from the first node to the second node you first go to an
adjacent node and then go to a node with a single diagonal step across
an array square that increases the distace from the first node.
• posted
That problem has been around for a while...
I believe the easiest solution is to model it by computing the voltage drops if you inject a fixed current (say, 1A) at a node with a current flowing through the grid to infinity, then do the same for the second node, but with a current of -1A, and then superimposing (adding) the two solutions, which you can do because it's linear.
• posted
It has been a long time since I heard this one but I seem to remember the resistance is the same no matter where you measure it.
• posted
I figured that out years ago. That works well for adjacent nodes. I have not figured out how to extend that to nodes on a knight's move. I have not been able to do that for the case of two nodes on a diagonal of a small square.
• posted
I remembered a little more. The key to this is symmetry. Current injected into a node will split equally among the four resistors since each path is equal in its path to infinity.
Second, due to symmetry, once you go to the second node, the path to the left must be the same as the path to the right. (but not necessarily the same as the path straight ahead). Combining these two symmetries, the path, for example, east to north must be the same as north to east. We can, therefore, without changing anything, split the connection at coordinate (1,1) into two, resulting in two resistors in series connected to the resistor going east, and another two resistors in series connected to the resistor going north. This can be repeated until you have four separate parallel paths to infinity, which can be solved for.
Certainly this must be on the web so I will stop here.
• posted
I have given up hoping to solve this problem rigorously in closed form. It reminds me of a mixed boundary value condition.
My approach now will be based on a numrical approach. I have two ways of tackling it.
1. Use what I think is a relaxation method. The current distribution in a sheet of uniform isotropic surface conductivity can be determined from Laplace's differential equation for potential. To solve the problem, A rectangular grid is used to approximate the surface. The finite difference equations correspond the the grid of resistors. To solve Laplace's equation you make a new grid with potentials equal to the average of the potentials at the nearest neighbors That is, the four nearest nodes to the point where the potential is desired. That process is iterated to get a new set of potentials at the nodes. That leads to a good approximation to the solution.
2. Another way is to set up the network equations on a square grid and then solving them. If the grid is large enough, what happens in the center is close to what it would be for the infinite grid. There may be confusion in setting up the equations. For example, if you use an 11x11 grid, there will be 12a points. The network will consists of 121 nodes. The network matrix will be 121x121. It will be a sparse matrix with most of the matrix elements zero. Finding the inverse of such a matrix, however, is easy these days on even a small computer.
This probably sounds complicated, but probably easy to do. The difficulty is keeping track of the details. I think an Excel spread sheet with a simple macro is all that is needed, but as I age, that is becoming more difficult.
I would also expect that a program like SPICE could handle it easily, but I have little experience using it.
In any event, just typing this out helped me get my thoughts together, even if it bores everyone else.
• posted
It appears that this is a problem with no simple solution, like the three body problem. If you're into heavy math, see this page: