Resistor grid problem

I believe this came from an interview question asked of prospective
employees by Google. I have not made much headway on it. It is taking up
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.
Reply to
Salmon Egg
Loading thread data ...
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.
Reply to
Michael Moroney
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.
Reply to
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.
Reply to
Salmon Egg
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.
Reply to
Michael Moroney
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.
Reply to
Salmon Egg
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:
formatting link
From a chart on the page, it appears the "chess move" has a resistance of 4/(pi) - 1/2.
No, it's nice to have some electrical theory in here for once, even if it is ultimately really a math problem.
Reply to
Michael Moroney
I greatly appreciate your response and the link you gave. It is a rather long paper, and I have not read it completely yet. I was hoping that the link would definitively give me the answers I want so that I go on to other things. I find, however, that I just get sucked in deeper into the puzzle.
W. R. Smythe in the foreword to his ostensibly highly mathematized book, Static and Dynamic Electricity, almost bragged that Physics and Engineering students taking his course did better than mathematics students. In his view, it was physical insight rather than mathematical prowess that enabled students to solve problems. I can attest that his exam questions were easily answered--if you understood the physics involved. If you did not understand and tried to calculate your answer, you could write down equations covering pages and still not get it right. Very often, symmetry was the key to simplifying the problem.
What I am trying to point out here is that it is not cheating to use symmetry to solve problems. Apparently, symmetries were more difficult for mathematicians to dig out than for engineers and physicists.
I had already figured out that what happens remotely from the nodes where current is injected is unimportant. Current injected in one node and extracted at another node result in no current at distant branches of the grid far away.
Reply to
Salmon Egg

PolyTech Forum website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.