Originally Posted by
Samson Thank you! I greatly appreciate it and I look forward to seeing what you come up with!
All right, so I wrote most of the program whose algorithm I described above, but I didn't actually need to complete the program because the partial output allowed me to find one on paper.
Here is the square I found:
Code:
00 11 22 33
12 03 30 21
23 32 01 10
31 20 13 02
00 05 10 15
06 03 12 09
11 14 01 04
13 08 07 02
And here is the Java code I used:
Code:
import java.util.ArrayList;
public class RegularSquares {
public static void main(String[] args) {
int[][] square = new int[4][4];
for (int i = 1; i < 4; i++)
square[0][i] = 4*i;
ArrayList<Integer> rowRemaining = fullRowRemaining1();
recurse1(square, 1, 0, rowRemaining);
}
public static void recurse1(int[][] square, int ind1, int ind2, ArrayList<Integer> rowRemaining) {
if (ind1 == 4) {
recurse2(square, 0, fullRowRemaining2());
return;
}
int nextInd1 = (ind2 == 3) ? ind1 + 1 : ind1;
int nextInd2 = (ind2 == 3) ? 0 : ind2 + 1;
for (int i = 0; i < rowRemaining.size(); i++) {
int num = rowRemaining.get(i);
boolean possible = true;
for (int j = 0; j < ind1; j++)
if (num == square[j][ind2]) {
possible = false;
break;
}
if (possible)
for (int j = 0; j < ind2; j++)
if (num == square[ind1][j]) {
possible = false;
break;
}
if (possible) {
int[][] nextSquare = deepCopy(square);
nextSquare[ind1][ind2] = num;
ArrayList<Integer> nextRowRemaining;
if (ind2 < 3) {
nextRowRemaining = new ArrayList<Integer>(rowRemaining);
nextRowRemaining.remove(i);
}
else nextRowRemaining = fullRowRemaining1();
recurse1(nextSquare, nextInd1, nextInd2, nextRowRemaining);
}
}
}
public static void recurse2(int[][] square, int ind, ArrayList<Integer> rowRemaining) {
if (ind == 4) {
fillInBlanks(square);
return;
}
for (int i = 0; i < rowRemaining.size(); i++) {
int num = rowRemaining.get(i);
int[][] nextSquare = deepCopy(square);
nextSquare[0][ind] += num;
ArrayList<Integer> nextRowRemaining = new ArrayList<Integer>(rowRemaining);
nextRowRemaining.remove(i);
recurse2(nextSquare, ind + 1, nextRowRemaining);
}
}
static int test = 0;
public static void fillInBlanks(int[][] square) {
ArrayList<ArrayList<Integer>> options = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 4; i++)
options.add(new ArrayList<Integer>());
int[] taken = new int[4];
for (int i = 0; i < 4; i++)
taken[square[0][i] / 4] = square[0][i] % 4;
for (int i = 1; i < 4; i++)
for (int j = 0; j < 4; j++) {
ArrayList<Integer> currOptions = new ArrayList<Integer>();
int mostSigDig = square[i][j] / 4;
int takenByFirstRow = square[0][j] % 4;
for (int k = 0; k < 4; k++)
if (k != takenByFirstRow && k != taken[mostSigDig])
currOptions.add(k);
options.add(currOptions);
}
if (test < 2) {
printSquare(square, 4);
System.out.println();
System.out.println(options);
System.out.println();
}
test++;
}
public static int getX(int n) {
return n / 4;
}
public static int getY(int n) {
return n % 4;
}
public static int encode(int x, int y) {
return 4*x + y;
}
public static boolean hasAllNums(int[][] square) {
ArrayList<Integer> allNums = getAllNums();
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) {
if (!allNums.contains(square[i][j])) return false;
allNums.remove(allNums.indexOf(square[i][j]));
}
return true;
}
public static ArrayList<Integer> getAllNums() {
ArrayList<Integer> allNums = new ArrayList<Integer>();
for (int i = 0; i < 16; i++)
allNums.add(i);
return allNums;
}
public static ArrayList<Integer> fullRowRemaining1() {
ArrayList<Integer> rowRemaining = new ArrayList<Integer>();
for (int i = 0; i < 4; i++)
rowRemaining.add(4*i);
return rowRemaining;
}
public static ArrayList<Integer> fullRowRemaining2() {
ArrayList<Integer> rowRemaining = new ArrayList<Integer>();
for (int i = 0; i < 4; i++)
rowRemaining.add(i);
return rowRemaining;
}
public static int[][] deepCopy(int[][] square) {
int[][] copy = new int[4][4];
for (int i = 0; i < 4; i++)
copy[i] = square[i].clone();
return copy;
}
public static void printSquare(int[][] square, int base) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
System.out.print(addLeadingZeroes(Integer.toString(square[i][j], base), 2));
if (j != 3) System.out.print(" ");
}
System.out.println();
}
}
public static String addLeadingZeroes(String s, int x) {
if (s.length() >= x) return s;
return addLeadingZeroes("0" + s, x);
}
}
Here is the partially finished program's output:
Code:
00 11 22 33
10 00 30 20
20 30 00 10
30 20 10 00
[[], [], [], [], [2, 3], [2, 3], [0, 1], [0, 1], [1, 3], [0, 2], [1, 3], [0, 2], [1, 2], [0, 3], [0, 3], [1, 2]]
00 11 23 32
10 00 30 20
20 30 00 10
30 20 10 00
[[], [], [], [], [2, 3], [2, 3], [0, 1], [0, 1], [1, 2], [0, 3], [1, 2], [0, 3], [1, 3], [0, 2], [0, 2], [1, 3]]
I'll make an image to describe the algorithm a bit more.