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.

--

Sam

Conservatives are against Darwinism but for natural selection.

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.

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.

--

Sam

Conservatives are against Darwinism but for natural selection.

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.

--

Sam

Conservatives are against Darwinism but for natural selection.

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:
http://www.mathpages.com/home/kmath668/kmath668.htm
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.

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.

--

Sam

Conservatives are against Darwinism but for natural selection.

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.

Polytechforum.com is a website by engineers for engineers. It is not affiliated with any of manufacturers or vendors discussed here.
All logos and trade names are the property of their respective owners.