For those that have seen my previous post and are eventually interested to see a simple example of the described algorithm, here you can find a bare-bone implementation in Java.
You can configure the size of the square by setting the values of sizeX and sizeY.
Be warned that solutions for squares up to 7x7 come out pretty quickly on an i5 PC, from 8x8 on the magnitude of the problem requires LONG times of execution before the first solution is found.
This is an example of the solution found for a 5x5 problem :
As it is designed now, the algorithm does not implement any kind of optimization and it stops when it finds the first solution (but it can be easily modified to find ALL the solutions) or when it runs out of options.
The reason why I am proposing this java implementation is because it is easily readable and implements a basic execution logic which allows me to easily experiment trying to add some parallelism.
The final solution is not intended to be in Java
public class LatinPuzzle {
private int stepCounter;
private int step[];
private int cell[][];
static final int moves[][] =
{{1,-2},{2,-1},{2,1},{1,2},
{-1,2},{-2,1},{-2,-1},{-1,-2}};
static final int sizeX = 6;
static final int sizeY = 6;
private int pSize= sizeX * sizeY;
// debugging/control info
private long needUpdate =0;
private int low = 100;
private int high=0;
void init()
{
step = new int[pSize];
cell = new int[pSize][2];
stepCounter = 0;
cell[0][0]=1;
cell[0][1]=1;
step[0]=0;
}
private boolean isValid(int x,int y)
{
if ((x<1)||(y<1)||(x>sizeX)||(y>sizeY))
return false;
int scan =0;
while (scan<stepCounter)
{
if ((cell[scan][0]==x)&&(cell[scan][1]==y))
return false;
scan++;
}
return true;
}
private void move(int n)
{
step[stepCounter]=n;
if (n>=8) return;
int x = cell[stepCounter][0]+moves[n][0];
int y = cell[stepCounter][1]+moves[n][1];
if (isValid(x,y))
{
stepCounter++;
cell[stepCounter][0] = x;
cell[stepCounter][1] = y;
}
}
private boolean backOne()
{
step[stepCounter--]=0;
if (stepCounter<1) return false; else return true;
}
public void tryPuzzle()
{
boolean running = true;
while ((stepCounter<(pSize-1))&&(running))
{
if (step[stepCounter]>=8) running = backOne();
else
move(step[stepCounter]+1);
// debugging/control start
if (stepCounter>high) high = stepCounter;
if (stepCounter<low) low = stepCounter;
if (needUpdate++ % 10000000 == 0)
{
System.out.println(""+needUpdate+","+stepCounter+" "+low+"-"+high);
low = pSize;
high = 0;
}
// debugging/control end
}
// final output
if (stepCounter>=(pSize-1))
{
System.out.println(""+needUpdate+", Success !! "+stepCounter+".");
for (int i=0;i<stepCounter;i++)
System.out.print(""+step[i]+".");
System.out.println();
for (int i=0;i<=stepCounter;i++)
System.out.print(""+cell[i][0]+","+cell[i][1]+" ");
} else
System.out.println(""+needUpdate+",failed "+stepCounter+".");
}
public static void main(String[] args)
{
LatinPuzzle lp = new LatinPuzzle();
lp.init();
lp.tryPuzzle();
}
}
