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

public class sudokuSpoiler extends Applet implements MouseListener, MouseMotionListener,
	KeyListener
{
	Image background;
	Image clueDigits[]=new Image[9],solutionDigits[]=new Image[9],buttons[]=new Image[4];
	Graphics bg;
	Font f;
	int bgInt=0xc0c0c0;
	Color bgcol;
	FontMetrics fm;
	
	int myBoard[][]=new int[9][9];
	int xPos[]=new int[9],yPos[]=new int[9];
	boolean clues[][]=new boolean[9][9];
	
	// For the user interface
	int curX,curY,downButton=-1;
	
	// Arrays and variables used for the solution algorithm
	int solution[]=new int[81]; // Store the solution here when done
	boolean working,solved;
	int baseIx[][]=new int[27][9]; // All the groups (rows, columns, 3x3 grids) to check
	int scanIx[][]=new int[81][20]; // All the neighbor squares that might contain conflicts
	int tempBoard[]=new int[81];
	boolean filled[]=new boolean[10];	
	
	public void init()
	{
		background=createImage(281,331);
		bg=background.getGraphics();
		f=new Font("SansSerif",Font.PLAIN,12);
		fm=getFontMetrics(f);
		bg.setFont(f);
		
		String s=getParameter("bgcolor"); // Specific background color?
		if (s!=null)
		{
			int i=0;
			int j=s.length();
			while (i<j && Character.digit(s.charAt(i),16)==-1)
				i++;
			try{
				bgInt=Integer.parseInt(s.substring(i),16);
			}
			catch(Exception e){e.printStackTrace();
			}
		}
		bgcol=new Color((bgInt>>16)&255,(bgInt>>8)&255,bgInt&255);
		
		prepareBoard();
		prepareBackground();
		
		prepareIndices();
		
		addMouseListener(this);
		addMouseMotionListener(this);
		addKeyListener(this);
	}

	void prepareBoard()
	{
		int i,j,k,l;
		
		k=0;
		// Check if there is an initial problem configuration
		String s=getParameter("problem");
		if (s!=null)
		{
			l=s.length();
			i=0;
			while (i<l && k<81)
			{
				j=s.charAt(i);
				if (j>='0' && j<='9')
				{
					myBoard[k/9][k%9]=j-'0';
					clues[k/9][k%9]=(myBoard[k/9][k%9]>0);
					k++;
				}
				i++;
			}
		}
		while (k<81)
		{
			myBoard[k/9][k%9]=0;
			clues[k/9][k%9]=false;
		}

		for (i=0;i<9;i++)
		{
			xPos[i]=5+i*30+(i/3);
			yPos[i]=5+i*30+(i/3);
		}
	}

	void prepareBackground()
	{
		MediaTracker mt;
		ImageProducer ip1,ip2;
		Image temp1,temp2;
		int i,j,k;
		bg.setColor(bgcol);
		bg.fillRect(0,0,281,331);
		bg.setColor(Color.black);
		bg.drawRect(2,2,276,276);
		bg.drawRect(3,3,274,274);
		bg.drawRect(168,282,110,46);
		bg.setColor(Color.lightGray);
		bg.draw3DRect(169,283,108,44,false);
		bg.fill3DRect(170,284,107,43,false);
		for (i=0;i<3;i++)
			for (j=0;j<3;j++)
			{
				bg.setColor(Color.black);
				bg.drawRect(xPos[j*3]-1,yPos[i*3]-1,90,90);
				bg.setColor(Color.gray);
				bg.drawLine(xPos[j*3],yPos[i*3+1]-1,xPos[j*3]+88,yPos[i*3+1]-1);
				bg.drawLine(xPos[j*3],yPos[i*3+2]-1,xPos[j*3]+88,yPos[i*3+2]-1);
				bg.drawLine(xPos[j*3+1]-1,yPos[i*3],xPos[j*3+1]-1,yPos[i*3]+88);
				bg.drawLine(xPos[j*3+2]-1,yPos[i*3],xPos[j*3+2]-1,yPos[i*3]+88);
			}
		mt=new MediaTracker(this);
		temp1=getImage(getCodeBase(),"digits.gif");
		temp2=getImage(getCodeBase(),"buttons.gif");
		mt.addImage(temp1,0);
		mt.addImage(temp2,0);
		try
		{
			mt.waitForID(0);
		}
		catch(InterruptedException e) {}
		ip1=temp1.getSource();
		ip2=temp2.getSource();
		for (i=0;i<9;i++)
		{
			clueDigits[i]=createImage(new FilteredImageSource(ip1,
				new CropImageFilter(0,29*i,29,29)));
			mt.addImage(clueDigits[i],1);
			solutionDigits[i]=createImage(new FilteredImageSource(ip1,
				new CropImageFilter(29,29*i,29,29)));
			mt.addImage(solutionDigits[i],1);
		}
		for (i=0;i<4;i++)
		{
			buttons[i]=createImage(new FilteredImageSource(ip2,
				new CropImageFilter(78*(i/2),32*(i&1),78,32)));
			mt.addImage(buttons[i],1);
		}
		try
		{
			mt.waitForID(1);
		}
		catch(InterruptedException e) {}

		bg.drawImage(buttons[0],2,289,this);
		bg.drawImage(buttons[2],82,289,this);
		fillInSquares();
	}

	void fillInSquares()
	{
		int i,j;
		bg.setColor(Color.white);
		for (i=0;i<9;i++)
			for (j=0;j<9;j++)
			{
				if (myBoard[i][j]>0)
					if (clues[i][j])
						bg.drawImage(clueDigits[myBoard[i][j]-1],xPos[j],yPos[i],this);
					else
						bg.drawImage(solutionDigits[myBoard[i][j]-1],xPos[j],yPos[i],this);
				else
					bg.fillRect(xPos[j],yPos[i],29,29);
			}
		bg.setColor(Color.red);
		bg.drawRect(xPos[curX],yPos[curY],28,28);
	}

	void drawSquare(int x, int y, boolean highlight)
	{
		bg.setColor(Color.white);
		if (myBoard[y][x]>0)
			if (clues[y][x])
				bg.drawImage(clueDigits[myBoard[y][x]-1],xPos[x],yPos[y],this);
			else
				bg.drawImage(solutionDigits[myBoard[y][x]-1],xPos[x],yPos[y],this);
		else
			bg.fillRect(xPos[x],yPos[y],29,29);
		if (highlight)
		{
			bg.setColor(Color.red);
			bg.drawRect(xPos[x],yPos[y],28,28);
		}
	}

	void clearBoard()
	{
		int i,j;
		boolean hasSolutionNumbers=false;
		for (i=0;i<9;i++)
			for (j=0;j<9;j++)
			{
				if (myBoard[i][j]>0 && !clues[i][j])
				{
					hasSolutionNumbers=true;
					myBoard[i][j]=0;
				}
			}
		if (!hasSolutionNumbers) // Clear entire board, otherwise keep clues
		{
			for (i=0;i<9;i++)
				for (j=0;j<9;j++)
				{
					myBoard[i][j]=0;
					clues[i][j]=false;
				}
		}
		setMessage(null,null);
		fillInSquares();
	}

	void setMessage(String s1, String s2)
	{
		bg.setColor(Color.lightGray);
		bg.setColor(Color.lightGray);
		bg.fill3DRect(170,284,107,43,false);
		if (s1!=null)
		{
			bg.setColor(Color.black);
			bg.drawString(s1,172,305-fm.getDescent()/2);
			if (s2!=null)
				bg.drawString(s2,172,305+fm.getHeight()-fm.getDescent()/2);
		}
	}

	void prepareIndices()
	{
		int i,j,k,l,m,n,o,p;
		// Prepare base indices
		k=0;
		for (i=0;i<9;i++) // Rows
		{
			for (j=0;j<9;j++)
				baseIx[k][j]=i*9+j;
			k++;
		}
		for (j=0;j<9;j++) // Columns
		{
			for (i=0;i<9;i++)
				baseIx[k][i]=i*9+j;
			k++;
		}
		for (l=0;l<3;l++) // Boxes
			for (m=0;m<3;m++)
			{
				n=0;
				for (i=3*l;i<3*l+3;i++)
					for (j=3*m;j<3*m+3;j++)
						baseIx[k][n++]=i*9+j;
				k++;
			}
			
		// Prepare scan indices,
		// 20 for each position on the board.
		p=0;
		for (i=0;i<9;i++)
			for (j=0;j<9;j++)
			{
				k=3*(i/3);
				l=3*(j/3);
				o=0;
				for (m=k;m<k+3;m++)
					for (n=l;n<l+3;n++)
						if (m!=i || n!=j)
							scanIx[p][o++]=m*9+n;
				for (m=0;m<9;m++)
					if (m<k || m>=k+3)
						scanIx[p][o++]=m*9+j;
				for (n=0;n<9;n++)
					if (n<l || n>=l+3)
						scanIx[p][o++]=i*9+n;
				p++;
			}
	}

	void solve(int board[],int lev)
	{
		int i,j,k,l,m;
		int leastOptions=10;
		int optPos[]=new int[9],optDigit=0;
		int tempOpt,tempPos[]=new int[9];
		boolean found;
		if (!solved)
		{
			if (lev==81)
			{
				solved=true;
				for (i=0;i<81;i++)
					solution[i]=board[i];
			}
			else
			{
				// Check all groups
				for (i=0;i<27;i++)
				{
					// First check which numbers have not been filled in yet.
					for (j=1;j<10;j++)
						filled[j]=false;
					for (j=0;j<9;j++)
						filled[board[baseIx[i][j]]]=true;
					// Investigate unfilled numbers
					for (j=1;j<10;j++)
						if (!filled[j])
						{
							tempOpt=0;
							k=0;
							// Test all empty squares,
							// but don't bother with alternatives that are more ambiguous
							// than what we already have.
							while (k<9 && tempOpt<leastOptions) // Try all empty squares
							{
								if (board[baseIx[i][k]]==0)
								{
									l=baseIx[i][k];
									found=false;
									for (m=0;m<20;m++)
										found=found || board[scanIx[l][m]]==j;
									if (!found)
									{
										tempPos[tempOpt++]=l;
									}
								}
								k++;
							}
							// Check if there are any valid positions and the options
							// for this digit are fewer than our previous best move.
							if (tempOpt>0 && tempOpt<leastOptions)
							{
								for (m=0;m<tempOpt;m++)
									optPos[m]=tempPos[m];
								leastOptions=tempOpt;
								optDigit=j;
							}
							else if (tempOpt==0) // Infeasible. Quit both loops right here.
							{
								i=27;
								j=10;
							}
						}
				}
				if (leastOptions<10) // Possible to continue?
				{
					// Try all positions for the best digit.
					for (i=0;i<leastOptions;i++)
					{
						board[optPos[i]]=optDigit;
						solve(board,lev+1);
						board[optPos[i]]=0; // Clear square afterwards, for backtracking.
					}
				}
			}
		}
	}

	public void mouseDragged(MouseEvent me)
	{
	}
	public void mouseMoved(MouseEvent me){}
	public void mouseEntered(MouseEvent me){}
	public void mouseExited(MouseEvent me)
	{
		if (downButton>=0)
			releaseButton(me);
	}
	public void mouseReleased(MouseEvent me)
	{
		if (downButton>=0)
			releaseButton(me);
	}
	public void mouseClicked(MouseEvent me){}
	
	public void mousePressed(MouseEvent me)
	{
		int x,y,i,j;
		x=me.getX();
		y=me.getY();
		requestFocus();
		if (x>=xPos[0] && y>=yPos[0] && x<xPos[8]+29 && y<yPos[8]+29)
		{
			drawSquare(curX,curY,false);
			curX=0;
			while (xPos[curX]+29<=x)
				curX++;
			curY=0;
			while (yPos[curY]+29<=y)
				curY++;
			drawSquare(curX,curY,true);
			repaint();
		}
		else if (!working)
		{
			if (x>=4 && x<78 && y>=291 && y<317) // Solve
			{
				downButton=0;
				bg.drawImage(buttons[1],2,289,this);
				repaint();
			}
			else if (x>=84 && x<158 && y>=291 && y<317) // Clear
			{
				downButton=1;
				bg.drawImage(buttons[3],82,289,this);
				repaint();
			}
		}
	}

	public void releaseButton(MouseEvent me)
	{
		int x,y;
		x=me.getX();
		y=me.getY();
		if (downButton==0) // Solve button
		{
			bg.drawImage(buttons[0],2,289,this);
			if (x>=4 && x<78 && y>=291 && y<317)
			{
				solveBoard();
			}
		}
		else // Clear button
		{
			bg.drawImage(buttons[2],82,289,this);
			if (x>=84 && x<158 && y>=291 && y<317)
			{
				clearBoard();
			}
		}
		downButton=-1;
		repaint();
	}

	public void solveBoard()
	{
		int i,j,k,numClues=0;
		long startTime,endTime;
		working=true;
		solved=false;
		k=0;
		for (i=0;i<9;i++)
			for (j=0;j<9;j++)
			{
				if (myBoard[i][j]>0 && clues[i][j])
				{
					tempBoard[k++]=myBoard[i][j];
					numClues++;
				}
				else
					tempBoard[k++]=0;
			}
		setMessage("Thinking ...",null);
		repaint();
		
		startTime=System.currentTimeMillis();
		solve(tempBoard,numClues);
		endTime=System.currentTimeMillis();
		
		if (solved)
		{
			// Copy solution to board
			k=0;
			for (i=0;i<9;i++)
				for (j=0;j<9;j++)
					myBoard[i][j]=solution[k++];
			fillInSquares();
			
			j=(int)(endTime-startTime);
			if (j<3000)
				setMessage("Solved in",j+" milliseconds.");
			else
				setMessage("Solved in",((j+500)/1000)+" seconds.");
		}
		else
		{
			setMessage("There is no","solution.");
		}
		working=false;
		repaint();
	}

	public void keyTyped(KeyEvent ke){}
	public void keyPressed(KeyEvent ke)
	{
		int kc=ke.getKeyCode();
		if (!working)
		{
			drawSquare(curX,curY,false);
			if (kc==KeyEvent.VK_UP && curY>0)
				curY--;
			else if (kc==KeyEvent.VK_DOWN && curY<8)
				curY++;
			else if (kc==KeyEvent.VK_LEFT && curX>0)
				curX--;
			else if (kc==KeyEvent.VK_RIGHT && curX<8)
				curX++;
			else if (kc==KeyEvent.VK_0 || kc==KeyEvent.VK_SPACE)
			{
				myBoard[curY][curX]=0;
				clues[curY][curX]=false;
			}
			else if (kc>=KeyEvent.VK_1 && kc<=KeyEvent.VK_9)
			{
				myBoard[curY][curX]=kc-KeyEvent.VK_0;
				clues[curY][curX]=true;
			}
			drawSquare(curX,curY,true);
			repaint();
		}
	}
	public void keyReleased(KeyEvent ke){}

	public void update(Graphics g)
	{
		g.drawImage(background,0,0,this);
	}
	
	public void paint(Graphics g)
	{
		g.drawImage(background,0,0,this);
	}
}