//Instant Insanity Puzzle Applet by Mark Mammel

import java.awt.*;
import java.awt.event.*;
import java.applet.Applet;

public class Insanity extends Applet implements ActionListener, MouseListener {

int NCUBES = 4;  //(NCOLORS = NCUBES)
int SQRSIZE = 20;
int RMARG = 20;
int TMARG = 60;
int[][] board = new int [NCUBES][6];
int[][] block = {{0,2,1,3,0,0},{3,0,2,1,0,1},{2,1,0,2,1,3},{1,3,3,0,2,2}};
//ACBDAA DACBAB CBACBD BDDACC initial config from Conway's book
//ACBDAB BDCECD CEDAEA DAEBBC EBACDE simple five cube config
//{{0,2,1,3,0,1},{1,3,2,4,2,3},{2,4,3,0,4,0},{3,0,4,1,1,2},{4,1,0,2,3,4}}; //five cube
int[] boxx = {1,1,1,1,0,2}; //relative coordinates of faces
int[] boxy = {0,2,1,3,1,1};
/*  |0|       faces are numbered this way
  |4|2|5|
    |1|
    |3|    */
int[][] rot = {{2,5,3,4},{2,4,3,5},{0,4,1,5},{0,5,1,4},{0,3,1,2},{0,2,1,3}};
//rotation of 4 faces clockwise around each face
boolean donefl;

Button buttonA = new Button("Scramble");
Button buttonB = new Button("Reset");
Button buttonC = new Button("Answer");

public void init() {
  
donefl=false;
buttonA.addActionListener(this);
buttonB.addActionListener(this);
buttonC.addActionListener(this);  
add(buttonA);
add(buttonB);
add(buttonC);
addMouseListener(this);
reset();
scramble();

} //init()

public void start() {
}

public void stop() {
}

public void actionPerformed(ActionEvent e) {

if (e.getSource() == buttonA) {   
	scramble();
} 
if (e.getSource() == buttonB) {   
	reset();
} 
if (e.getSource() == buttonC) {   
      solve();
} 
repaint();

} //action

public void mouseClicked(MouseEvent e) {

int x,y,x1,y1,i,j,k;

//x=RMARG + i*SQRSIZE*4 + boxx[j]*SQRSIZE;
//y=TMARG + boxy[j]*SQRSIZE;

x=e.getX()-RMARG;
y=e.getY()-TMARG;
i=x/(4*SQRSIZE);
x1=(x-i*SQRSIZE*4)/SQRSIZE;
y1=y/SQRSIZE;
j=-1;
for (k=0; k<6; k++)
	if (boxx[k]==x1 && boxy[k]==y1) j=k;
if (i<NCUBES && j>-1) {
	rotate(i,j);
	donefl=isDone();
	repaint();
}


} //mouseclicked

public void mousePressed(MouseEvent e) {
} //required but not used
public void mouseReleased(MouseEvent e) {
} //required but not used
public void mouseEntered(MouseEvent e) {
} //required but not used
public void mouseExited(MouseEvent e) {
} //required but not used

public void paint(Graphics g) {

int i,j,x,y;

for (i=0; i<NCUBES; i++)
for (j=0; j<6; j++) {
	switch(board[i][j]) {
		case 0:  g.setColor(Color.red); break;
		case 1:  g.setColor(Color.green); break;
		case 2:  g.setColor(Color.yellow); break;
		case 3:  g.setColor(Color.blue); break;
		case 4:  g.setColor(Color.magenta); break;
		default: g.setColor(Color.gray);
	}
	x=RMARG + i*SQRSIZE*4 + boxx[j]*SQRSIZE;
	y=TMARG + boxy[j]*SQRSIZE;
	g.fillRect(x,y,SQRSIZE,SQRSIZE);
	g.setColor(Color.gray);
	g.drawRect(x,y,SQRSIZE,SQRSIZE);
} //j

if (donefl) {
	g.setColor(Color.darkGray);
	g.drawString("Done!", 8, 16);
}

} //paint

private void reset() {

int i,j;

for (i=0; i<NCUBES; i++)
for (j=0; j<6; j++)
	board[i][j]=block[i][j];
donefl=false;

} //reset

private void rotate(int cube, int face) {

int f1,f2,t;

f1=rot[face][0];
t=board[cube][f1];
f2=rot[face][1];
board[cube][f1]=board[cube][f2];
f1=f2;
f2=rot[face][2];
board[cube][f1]=board[cube][f2];
f1=f2;
f2=rot[face][3];
board[cube][f1]=board[cube][f2];
board[cube][f2]=t;

} //rotate

private void scramble() {

int i,j,k,x;

for (i=0; i<NCUBES; i++)
	for (j=0; j<6; j+=2) {
		x = (int) (Math.random() * 4.0);
		for (k=0; k<x; k++)
			rotate(i,j);
	}
for (i=0; i<NCUBES; i++) //set as start
for (j=0; j<6; j++)
	block[i][j]=board[i][j];
donefl=false;

} //scramble

private boolean isDone() {

int i,j,k;
boolean fl=true;

for (i=0; i<4; i++)
	for (j=0; j<NCUBES-1; j++)
		for (k=j+1; k<NCUBES; k++)
			if (board[j][i]==board[k][i]) fl=false;

return fl;
} //isDone

private void solve() {

boolean newfl, overfl, okfl; 
boolean[] used = new boolean[NCUBES];
int[] vert = new int[NCUBES];
int[] edge = new int[NCUBES*2];
int[][] solution = new int [NCUBES][6];
int i,j,k,lvl,cube,a,b,a0,b1;

for (i=0; i<NCUBES; i++)
	vert[i]=0;

lvl=-1;
newfl=true;
do
{
	lvl++;
	cube=lvl%NCUBES; //2 rounds for each cube
	if (newfl) //reset start of vertex pairs
		edge[lvl]=-1;
	overfl=false;
	okfl=false;
	do 
	{  //increment vertex pair for block
		edge[lvl]++;
		if (edge[lvl]>2) 
			overfl=true;
		else //edge already used ?
			okfl=(lvl<NCUBES || edge[lvl]!=edge[cube]);
	} while (okfl==false && overfl==false);

	if (overfl==false) 
	{ 
		okfl=true;
		if (++vert[board[cube][edge[lvl]*2]] > 2+lvl/NCUBES*2) okfl=false;
		if (++vert[board[cube][edge[lvl]*2+1]] > 2+lvl/NCUBES*2) okfl=false;
		if (lvl%NCUBES==NCUBES-1 && okfl==true) //check that each vertex is order 2
			for (i=0; i<NCUBES; i++)
				if (vert[i] != 2+lvl/NCUBES*2) okfl=false;

		if (okfl==true) //continue with circuit
		{ 
			if (lvl==NCUBES*2-1)
			{	
				/* to continue...   --vert[board[cube][edge[lvl]*2]];
				--vert[board[cube][edge[lvl]*2+1]];
				lvl--;
				newfl=false;*/
				lvl=-2; //exit with first solution found
			}
			else 
			{
				newfl=true;
			}
		} //okfl
		else
		{ //try another
			--vert[board[cube][edge[lvl]*2]];
			--vert[board[cube][edge[lvl]*2+1]];
			lvl--;
			newfl=false;
		}

	} //overfl
	else 
	{ //backtrack
		lvl--;
		if (lvl>-1)
		{
			cube=lvl%NCUBES;
			--vert[board[cube][edge[lvl]*2]];
			--vert[board[cube][edge[lvl]*2+1]];
		}
		lvl--;
		newfl=false;
	}

} while (lvl>-2);

if (edge[0]==3) ; //printf("No solutions.\n");
else //print solution
{
	for (i=0; i<2; i++) //two subgraphs
	{
		for (j=0; j<NCUBES; j++) used[j]=false;
		do
		{ //follow cycles
			j=0; //find next unused edge
			b1=a0=-1;
			while (j<NCUBES && used[j]==true) j++;
			if (j<NCUBES)
			do { //go thru cycle
				okfl=true;
				a=board[j][edge[i*NCUBES+j]*2];
				b=board[j][edge[i*NCUBES+j]*2+1];
				if (b==b1)
				{ //swap
					k=a;
					a=b;
					b=k;
				}
				solution[j][i*2]=a;
				solution[j][i*2+1]=b;
				used[j]=true;
				if (a0<0) a0=a; //start vertex of cycle
				b1=b; //previous b
				for (k=0; k<NCUBES; k++) //find next cube (contains b)
					if (used[k]==false && (board[k][edge[i*NCUBES+k]*2]==b ||
						board[k][edge[i*NCUBES+k]*2+1]==b)) j=k;
					
			} while (b!=a0);
		} while (j<NCUBES); 
	}

	for (j=0; j<NCUBES; j++)
	{ //fill in hidden sides
		k=3-edge[j]-edge[j+NCUBES]; //missing edge
		a=board[j][k*2];
		b=board[j][k*2+1];
		solution[j][4]=a;
		solution[j][5]=b;
	}

	for (i=0; i<NCUBES; i++) //copy
		for (j=0; j<6; j++)
			board[i][j]=solution[i][j];
	donefl=true;
	repaint();
} //print

} //solve


} //end Class