A263542.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox {
	// NB This is not really "production-quality" code
	class Program {
		static void Main(string[] args) {
			for (int m = 2; m < 7; m++) {
				for (int n = 2; n <= m; n++) {
					SearchGrids(m, n);
				}
			}
		}

		private static long Count;
		private static int SumMin, SumMax;

		private static void SearchGrids(int m, int n) {
			Count = 0;

			if (m % 2 == 0 && n % 2 == 0) SetBounds(4 * T(m*n), 4 * T(m*n), m*n);
			else if (m % 2 == 0 && n % 2 == 1) SetBounds(2 * T(m*n) + 2 * T(m*(n-2)), 4 * T(m*n) - 2*T(2*m), m*(n-1));
			else if (m % 2 == 1 && n % 2 == 0) SetBounds(2 * T(m*n) + 2 * T((m-2)*n), 4 * T(m*n) - 2*T(2*n), (m-1)*n);
			else SetBounds(T(m*n) + T(m*n - (2*m+2*n-4)) + 2*T(4), 4*T(m*n) - 2*T(2*m+2*n-4) - T(4), (m-1)*(n-1));

			int[,] grid = new int[m, n];
			Search(m, n, Range(m * n), Range(0), grid, 0, 0);
			// Symmetries: 4 for a rect, 8 for a square
			Console.WriteLine("{1}x{2}: {0} solution(s)", Count * (m == n ? 8 : 4), m, n);
		}

		private static void SetBounds(int p, int q, int d) {
			SumMin = (p + d - 1) / d;
			SumMax = q / d;
		}

		private static int T(int x) {
			return x * (x-1) / 2;
		}

		private static ISet<int> Range(int n) {
			ISet<int> rv = new HashSet<int>();
			for (int i = 0; i < n; i++) rv.Add(i);
			return rv;
		}

		private static void Search(int m, int n, ISet<int> avail, ISet<int> used, int[,] grid, int row, int col) {
			// Search or calc?
			if (row == m) {
				// Constrain top-left corner to be smallest.
				if (grid[0, 0] > grid[m - 1, n - 1]) return;

				Count++;
			}
			else if (row * col > 1) {
				// Calc
				int sum = grid[0,0] + grid[1,1] + grid[0,1] + grid[1,0];
				int val = sum - grid[row - 1, col - 1] - grid[row - 1, col] - grid[row, col - 1];
				if (avail.Contains(val)) {
					avail.Remove(val);
					used.Add(val);
					grid[row, col] = val;
					Search(m, n, avail, used, grid, col == n - 1 ? row + 1 : row, col == n - 1 ? 0 : (col + 1));
					used.Remove(val);
					avail.Add(val);
				}
			}
			else {
				int min = int.MinValue, max = int.MaxValue;

				// Special cases...
				// We require that:
				//   grid[0,0] < grid[0,n-1]
				//   grid[0,0] < grid[m-1,0]
				if (row == 0 && col == n - 1) min = grid[0,0];
				if (row == m - 1 && col == 0) min = grid[0,0];

				// For squares we fix the diagonal symmetry by requiring:
				//   grid[0,1] < grid[1,0]
				if (m == n && row == 1 && col == 0) min = grid[0,1];

				// grid[1,1] defines the sum
				if (row == 1 && col == 1) {
					min = SumMin - grid[0,0] - grid[0,1] - grid[1,0];
					max = SumMax - grid[0,0] - grid[0,1] - grid[1,0];
				}

				ISet<int> _avail = new HashSet<int>(avail);
				foreach (var val in avail) {
					if (val < min || val > max) continue;
					_avail.Remove(val);
					used.Add(val);
					grid[row,col] = val;
					Search(m, n, _avail, used, grid, col == n - 1 ? row + 1 : row, col == n - 1 ? 0 : (col + 1));
					used.Remove(val);
					_avail.Add(val);
				}
			}
		}
	}
}