Skip to content

Instantly share code, notes, and snippets.

@pjt33

pjt33/A263542.cs

Created Oct 21, 2015
Embed
What would you like to do?
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);
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.