Created
October 21, 2015 21:48
-
-
Save pjt33/759d03033a38d1abde84 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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