/* The Computer Language Shootout | |
http://shootout.alioth.debian.org/ | |
benchmark implementation (not optimized) | |
JRE 1.5 only | |
contributed by Josh Goldfoot */ | |
import java.io.*; | |
import java.lang.*; | |
import java.util.*; | |
public class magicsquares { | |
static int n; | |
static int mn; | |
public static class FfmResult { | |
public int x; | |
public int y; | |
public int[] moves; | |
public FfmResult(int ix, int iy, int[] imoves) { | |
x = ix; | |
y = iy; | |
moves = (int[]) imoves.clone(); | |
} | |
} | |
public static class PQNode implements Comparable { | |
public int [] grid; | |
boolean priorityCalculated; | |
private int priority; | |
private FfmResult ffm; | |
public PQNode() { | |
grid = new int [n * n]; | |
int i; | |
for (i = 0; i < n * n; i++) | |
grid[i] = 0; | |
priorityCalculated = false; | |
ffm = null; | |
} | |
public PQNode(PQNode other) { | |
grid = (int[]) other.grid.clone(); | |
priorityCalculated = false; | |
} | |
public int[] gridRow(int y) { | |
int[] r = new int[n]; | |
int x; | |
for (x = 0; x < n; x++) | |
r[x] = grid[x + y * n]; | |
return r; | |
} | |
public int[] gridCol(int x) { | |
int[] r = new int[n]; | |
int y; | |
for (y = 0; y < n; y++) | |
r[y] = grid[x + y * n]; | |
return r; | |
} | |
public int[] diagonal(int q) { | |
int[] r = new int[n]; | |
int i; | |
for (i = 0; i < n; i++) { | |
if (q == 1) | |
r[i] = grid[i + i * n]; | |
else if (q == 2) { | |
r[i] = grid[i + (n - 1 - i) * n]; | |
} | |
} | |
return r; | |
} | |
public int[] possibleMoves(int x, int y) { | |
int zerocount, sum, highest, j, i; | |
if (grid[x + y * n] != 0) | |
return ( new int [] { }); | |
ArrayList<int[]> cellGroups = new ArrayList<int[]>(); | |
cellGroups.add(gridCol(x)); | |
cellGroups.add(gridRow(y)); | |
if (x == y) | |
cellGroups.add(diagonal(1)); | |
if (x + y == n - 1) | |
cellGroups.add(diagonal(2)); | |
HashSet<Integer> usedNumbers = new HashSet<Integer>(); | |
for (i = 0; i < grid.length; i++) | |
usedNumbers.add(new Integer(grid[i])); | |
HashSet<Integer> onePossible = new HashSet<Integer>(); | |
highest = n * n; | |
for (int[] group: cellGroups) { | |
zerocount = 0; | |
sum = 0; | |
for (int num: group) { | |
if (num == 0) | |
zerocount++; | |
sum += num; | |
} | |
if (zerocount == 1) | |
onePossible.add(new Integer(mn - sum)); | |
if (mn - sum < highest) | |
highest = mn - sum; | |
} | |
if (onePossible.size() == 1) { | |
Integer onlyPossibleMove = (Integer) onePossible.iterator().next(); | |
int opmint = onlyPossibleMove.intValue(); | |
if (opmint >= 1 && | |
opmint <= n * n && | |
! usedNumbers.contains(onlyPossibleMove)) | |
return (new int[] { opmint }); | |
else | |
return ( new int [] { }); | |
} else if (onePossible.size() > 1) | |
return ( new int [] { }); | |
ArrayList<Integer> moves = new ArrayList<Integer>(); | |
for (i = 1; i <= highest; i++) { | |
Integer ii = new Integer(i); | |
if (! usedNumbers.contains(ii)) | |
moves.add(ii); | |
} | |
int[] r = new int[moves.size()]; | |
i = 0; | |
for (Integer move: moves) { | |
r[i++] = move.intValue(); | |
} | |
return r; | |
} | |
public FfmResult findFewestMoves() { | |
if (ffm != null) | |
return ffm; | |
int x, y, mx, my, ind; | |
int[] minmoves = (new int[] { }); | |
int[] moves; | |
mx = my = -1; | |
for (y = 0; y < n; y++) | |
for (x = 0; x < n; x++) { | |
ind = x + y * n; | |
if (grid[ind] == 0) { | |
moves = possibleMoves(x,y); | |
if (mx == -1 || moves.length < minmoves.length) { | |
mx = x; | |
my = y; | |
minmoves = (int[]) moves.clone(); | |
} | |
} | |
} | |
ffm = new FfmResult(mx, my, minmoves); | |
return ffm; | |
} | |
public void calculatePriority() | |
{ | |
int i, zerocount; | |
zerocount = 0; | |
for (int cell: grid) | |
if (cell == 0) | |
zerocount++; | |
priority = zerocount + findFewestMoves().moves.length; | |
priorityCalculated = true; | |
} | |
public int getPriority() | |
{ | |
if (priorityCalculated) | |
return priority; | |
else { | |
calculatePriority(); | |
return priority; | |
} | |
} | |
public int compareTo(Object anotherMSquare) throws ClassCastException { | |
if (!(anotherMSquare instanceof PQNode)) | |
throw new ClassCastException(); | |
PQNode other = (PQNode) anotherMSquare; | |
int c = getPriority() - other.getPriority(); | |
if (c == 0) { | |
int i = 0; | |
while (c == 0 && i < n * n) { | |
c = grid[i] - other.grid[i]; | |
i++; | |
} | |
} | |
return c; | |
} | |
public String toString() { | |
StringBuilder sb = new StringBuilder(); | |
int y, x; | |
for (y = 0; y < n; y++) { | |
for (x = 0; x < n; x++) { | |
sb.append(grid[x + y * n]); | |
if (x < n-1) | |
sb.append(' '); | |
} | |
if (y < n-1) | |
sb.append('\n'); | |
} | |
return sb.toString(); | |
} | |
} | |
public magicsquares() { } | |
public static void main(String[] args) { | |
n = 3; | |
if (args.length > 0) | |
n = Integer.parseInt(args[0]); | |
mn = n * (1 + n * n) / 2; | |
PriorityQueue<magicsquares.PQNode> pq = new PriorityQueue<magicsquares.PQNode>(); | |
pq.offer(new magicsquares.PQNode() ); | |
while (! pq.isEmpty()) { | |
PQNode topSquare = pq.poll(); | |
if (topSquare.getPriority() == 0) { | |
System.out.println(topSquare); | |
break; | |
} | |
magicsquares.FfmResult result = topSquare.findFewestMoves(); | |
int ind = result.x + result.y * n; | |
for (int move: result.moves) { | |
magicsquares.PQNode newSquare = new magicsquares.PQNode(topSquare); | |
newSquare.grid[ind] = move; | |
pq.offer(newSquare); | |
} | |
} | |
} | |
} |