Find the cheapest cycle through two points on a rectangular grid I have a task, but I have no idea how to solve it.

We have to find a cycle going through $(1,1)$ and $(n,n)$ (X axis on the picture is indexed right to left) such that the sum of values in cells is minimized. A cycle can't contain a cell more than once.

Example:
Ok, here's a reduction from Hamiltonian cycles in grid graphs to your problem. It requires the grid graph to have vertices in the two opposite corners but that shouldn't be an obstacle to getting the details to work.