
package edu.unl.consystlab.sudoku;

// AWT to start with
import java.applet.Applet;
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Container;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.GridLayout;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;

import javax.swing.JButton;
import javax.swing.JCheckBox;
import javax.swing.JComboBox;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;


public class Solve extends Applet implements MouseListener, Runnable, KeyListener
{
	public static final String VERSION = "v1.61";	
	// static
	private static String INFO = 
      "Select one of the puzzles, then Solve.\n" +  
      "\n" +
      "Alternatively, use Clear and then your mouse to fill\n" +
      "in your own puzzle, then press Solve.\n" +
      "\n" +
      "Mail me at sudoku@klaas.nl (this is " + VERSION + ")\n";
	                              
	// graphics
	private JButton[][] jbuttons = new JButton[9][9];
	private JTextArea info = new JTextArea(INFO,6,20);
	private JScrollPane infoScroll = new JScrollPane(info);
	private JFrame frame;
	private boolean isFirstRun = true;
	private JCheckBox optimize;

	// some GUI definitions
 	private static Font cellFont = new Font(null, Font.BOLD, 18);
	private static Color colorFixed = Color.black;
	private static Color colorTrying = Color.blue;
	private static Color colorError = Color.red;
	private static Color colorFound = Color.gray;
	
	// field info
	private int[][] values= new int[9][9];
	private boolean fixeds[][] = new boolean[9][9];
	private int rowUsed[][] = new int[9][10];
	private int colUsed[][] = new int[9][10];
	private int sqUsed[][] = new int[9][10];
	private Thread thread = null;
	private boolean pleaseStop = true;
	private boolean pleaseOptimize = false;
	
	// rest
	private static int UNKNOWN=0;
	private static int OK=1;
	private static int ERR=2;
	private JButton jbuttonStart = new JButton("Solve");
	private JButton jbuttonStop = new JButton("Stop");
	private JButton jbuttonGame1 = new JButton("Puzzle 1");
	private JButton jbuttonGame2 = new JButton("Puzzle 2");
	private JButton jbuttonGame3 = new JButton("Puzzle 3");
	private JButton jbuttonGame4 = new JButton("Puzzle 4");
	private JButton jbuttonClear = new JButton("Clear");
	private JButton jbuttonQuit = new JButton("Quit");
	
	// from sigpublic 
	void game1()
	{
		clearGame();
		info.setText("From http://www.simetric.co.uk/sudoku/step1.htm\n");
		fix(1,2,3); fix(1,4,5); fix(1,7,8); fix(1,8,1);
		fix(2,4,7); fix(2,5,6); fix(2,8,9);
		fix(3,1,4); 
		fix(4,2,4); fix(4,3,3); fix(4,4,9); fix(4,6,5);fix(4,9,6);
		fix(5,2,1); fix(5,8,7);
		fix(6,1,6); fix(6,4,8); fix(6,6,1); fix(6,7,9);fix(6,8,3);
		fix(7,9,9);
		fix(8,2,9); fix(8,5,8); fix(8,6,6);
		fix(9,2,6); fix(9,3,1); fix(9,6,2); fix(9,8,8);		
	} // game1
	
	// may 22. 2005: http://www.griffiths-jones.co.uk/sudoku/
	public void game2()
	{
		clearGame();
		info.setText("From  may 22. 2005: \n"  +
			"http://www.griffiths-jones.co.uk/sudoku/\n");
		fix(1,3,6); fix(1,6,2);
		fix(2,5,5); fix(2,7,4); fix(2,9,2);
		fix(3,2,7); fix(3,4,4); fix(3,5,9); fix(3,8,1);
		fix(4,1,7); fix(4,3,4); fix(4,6,9); fix(4,7,2);
		fix(5,1,1); fix(5,9,8);
		fix(6,3,9); fix(6,4,1); fix(6,7,5); fix(6,9,3);
		fix(7,2,1); fix(7,5,4); fix(7,6,6); fix(7,8,5);
		fix(8,1,6); fix(8,3,5); fix(8,5,7); 
		fix(9,4,5); fix(9,7,3);		
	} // game2

	// times online, 14 may
	public void game3()
	{
		clearGame();
		info.setText("From Times Online, may 14, 2005\n"+
			"http://www.timesonline.co.uk/article/0,,18209-1609537,00.html\n");
		fix(1, " 6       ");
		fix(2, "1     264");
		fix(3, "    4   5");
		fix(4, "7  62 9  ");
		fix(5, " 9 4 8 7 ");
		fix(6, "  5 91  2");
		fix(7, "5   7    ");
		fix(8, "937     6");
		fix(9, "       8 ");
	} // game3
	
	// times online, puzzle 4, very hard
	public void game4()
	{
		clearGame();
		info.setText("From Times Online, 'very hard'\n"+
			"http://www.timesonline.co.uk/article/0,,18209-1354183,00.html\n");
		fix(1, " 43 8 25 ");
		fix(2, "6        ");
		fix(3, "     1 94");
		fix(4, "9    4 7 ");
		fix(5, "   6 8   ");
		fix(6, " 1 2    3");
		fix(7, "82 5     ");
		fix(8, "        5");
		fix(9, " 34 9 71 ");
	}
	public void clearGame()
	{
		for(int row=0; row<9; row++)
		{
			for(int col=0;col<9;col++)
			{
				JButton b = jbuttons[row][col];
				b.setText("");
				b.setEnabled(true);
				values[row][col]=UNKNOWN;
				fixeds[row][col]=false;
				b.setForeground(Color.blue);
				b.setFont(cellFont);
			}
		}	
	} // newGame()	
	
	public void fix(int row, String s)
	{
		for(int col=0; col<9; col++)
		{
			char c = s.charAt(col);
			if(c>='0'&& c<='9')
			{
				int i = c - '0';
				fix(row, col+1, i);
			}
		}
	} // fix(row, String)
	
	public void fix(int r,int c,int v)
	{
		r--; c--;
		values[r][c] = v;
		fixeds[r][c] = true;
		JButton b = jbuttons[r][c];
		b.setText(""+v);
		//b.setEnabled(false);
		b.setForeground(Color.black);
	}
	
	public void clearInfo()
	{
		info.setText(INFO);
	}

	// fix bug - see http://forums.java.sun.com/thread.jspa?threadID=576390&messageID=2909099
	public void paint(Graphics g)
	{
           super.paint(g);
           if (isFirstRun && frame != null){
               frame.setVisible(true);
               frame.toFront();
               isFirstRun = false;
           }
	} // paint()
	
	public void init()
	{		
 		frame = new JFrame();
 		frame.setJMenuBar(new SuMenuBar(null));
 		Container content = frame.getContentPane();
		/*
		frame.addWindowListener(new WindowAdapter() {
			public void windowClosing(WindowEvent e) {
				System.exit(0);
			}
			// close anon inner class
		});
		*/
		
		content.setLayout(new BorderLayout());
		
		// North: info 
		info.setAutoscrolls(true);
		info.setEditable(false);
		info.setToolTipText("All kinds of informational messages can be found here");
		content.add("North", infoScroll);
		
		// South: JButton area
		JPanel jbuttonPanel = new JPanel();	
		jbuttonPanel.setLayout(new GridLayout(-1,4));			
		
		jbuttonPanel.add(jbuttonGame1);
		jbuttonGame1.addMouseListener(this);
		
		jbuttonPanel.add(jbuttonGame2);
		jbuttonGame2.addMouseListener(this);
		
		jbuttonPanel.add(jbuttonGame3);
		jbuttonGame3.addMouseListener(this);		
		
		jbuttonPanel.add(jbuttonGame4);
		jbuttonGame4.addMouseListener(this);
		
		jbuttonStart.setToolTipText("Start the solving process");
		jbuttonPanel.add(jbuttonStart);
		jbuttonStart.addMouseListener(this);
		
		jbuttonStop.setToolTipText("Stop the solving process (if active)");
		jbuttonPanel.add(jbuttonStop);
		jbuttonStop.addMouseListener(this);
		jbuttonStop.setEnabled(false);		
		
		jbuttonClear.setToolTipText("Clear the grid; use your mouse to fill in a puzzle, then press the Solve button");
		jbuttonPanel.add(jbuttonClear);
		jbuttonClear.addMouseListener(this);
		
		jbuttonQuit.setToolTipText("Stop this applet");
		jbuttonPanel.add(jbuttonQuit);
		jbuttonQuit.addMouseListener(this);
		
		optimize = new JCheckBox("Optimize");
		optimize.setToolTipText("When enabled, solving is done far smarter (more like a human would)");
		jbuttonPanel.add(optimize);
		
		// drop down list of puzzles, to do
		String data[] = { "red", "green", "blue" };
		JComboBox puzzles = new JComboBox(data);
		jbuttonPanel.add(puzzles);
				
		content.add("South", jbuttonPanel);
		
		// Center holds displayable field
		JPanel field = new JPanel();
		field.setLayout(new GridLayout(3,3,7,7));
		field.setBackground(Color.lightGray);
		int row, col, n;
		for(int i=0; i<9; i++)
		{
			JPanel p = new JPanel();
			p.setLayout(new GridLayout(3,3,1,1));
			p.setBackground(Color.lightGray);
				
			for(int j=0; j<9; j++)
			{
				row = 3*(i/3);
				col = 3*(i%3);
				row += j/3;
				col += j%3;
				String s = (j+1)+"";
				JButton b = jbuttons[row][col] = new JButton(s);
			    //s = row+"/"+col;
			    p.add(b);
			    b.addMouseListener(this);
				b.addKeyListener(this);
				b.setToolTipText("Just click here to add or change the entry");
			}
			   
			field.add(p);
		}
		content.add("Center", field);
		clearGame();
		clearInfo();
		//frame.pack();
		frame.setSize(600,600);
		//frame.setFocusable(true);
		frame.setVisible(true);
		frame.requestFocus();
		frame.show();
		frame.toFront();
	} // init()

    public void start()
    {
        frame.toFront();
    }

    public void stopThread()
    {
    	pleaseStop = true;
    	thread = null;
    	info.append("Stopped.\n");
		jbuttonStop.setEnabled(false);
		jbuttonStart.setEnabled(true);
		jbuttonGame1.setEnabled(true);
		jbuttonGame2.setEnabled(true);
		jbuttonGame3.setEnabled(true);
		jbuttonGame4.setEnabled(true);
		jbuttonClear.setEnabled(true);
    }
    
	public void startThread()
	{	
		jbuttonStop.setEnabled(true);
		jbuttonStart.setEnabled(false);
		jbuttonGame1.setEnabled(false);
		jbuttonGame2.setEnabled(false);
		jbuttonGame3.setEnabled(false);
		jbuttonGame4.setEnabled(false);
		jbuttonClear.setEnabled(false);
		thread = new Thread(this);	
		pleaseStop = false;
		thread.start();
	} // startThread()
   
	public void SolveIt()
	{ 
		int errors = initStats();
 		if(errors>0)
		{
			showErrors();
			info.append("Sorry, cannot solve, errors in grid.\n");
			info.setCaretPosition(9999);
			return;
		}
		startThread();
	}

	public boolean isActionJButton(JButton b)
	{
		if(b == jbuttonQuit)
		{
			stopThread();
			frame.setSize(100,100);
			frame.setVisible(false);
			frame.setEnabled(false);
			frame.dispose();
			frame=null;
			// System.exit(0);
			return true;
		}
		if(b == jbuttonStop)
		{
			stopThread();
			return true;
		}
		if(thread!=null)
		{
			return true; // but ignore all else
		}
		if(b == jbuttonStart)
		{
			SolveIt();
			return true;
		}
		if(b == jbuttonGame1)
		{
						game1();
			return true;
		}
		if(b == jbuttonGame2)
		{
			game2();
			return true;
		}
		if(b == jbuttonGame3)
		{
			game3();
			return true;
		}
		if(b == jbuttonGame4)
		{
			game4();
			return true;
		}
		if(b == jbuttonClear)
		{
			clearGame();
			info.setText("Field cleared.\nUse your mouse to fill in the puzzle.\n");
			return true;
		}
		return false;
	} // isActionJButton - one of start, stop etc.
	
	/* (non-Javadoc)
	 * @see java.awt.event.MouseListener#mouseClicked(java.awt.event.MouseEvent)
	 */
	public void mouseClicked(MouseEvent e)
	{
		// TODO Auto-generated method stub
		Object o = e.getSource();
		if(! (o instanceof JButton))
		   return;
		JButton b = (JButton)o;
		if(isActionJButton(b))
		   return;
		pressJButton(b, -1);
	}
	
	public void pressJButton(JButton b, int val)
	{
		for(int row=0;row<9;row++)
		{
			for(int col=0;col<9;col++)
			{
				if(jbuttons[row][col] == b)
				{
					press(row,col,val);
				}
			}
		}		
	} // pressJButton()
	
	public void press(int row, int col, int val)
	{
		//if(fixeds[row][col]==true) return;
		if(val>=0 && val<=9)
			values[row][col]=val;
		else
		{
			values[row][col]++;
			if(values[row][col] > 9)
		   		values[row][col] = UNKNOWN;
		}
	    int v = values[row][col];
	    JButton b = jbuttons[row][col];
	    if(v==UNKNOWN)
	    {
			fixeds[row][col]=false;
	    	b.setText("");
	    	b.setForeground(Color.blue);
	    }
	    else
	    {
			fixeds[row][col]=true;
	    	b.setText(""+v);
		  	b.setForeground(Color.black);	
	    } 
		if(initStats() > 0) // errors!!
		{
			showErrors();
		}
	} // press();
	
	public void checkRowCol(boolean doRow, int where)
	{
		int state = UNKNOWN;
		int sum=0;
		boolean[] have = new boolean[10];
		for(int i=0;i<10;i++) have[i]=false;
		for(int n=0; n<9; n++)
		{
			int r = (doRow==true ? where : n);
			int c = (doRow==false ? where : n);
			if(values[r][c]==UNKNOWN)
			{
			   continue;
			}	
			int v = values[r][c];
			if(have[v])
			{
				state = ERR;
				break;
			}
			sum += values[r][c];
			have[v]=true;
		}
		// if(state==UNKNOWN && sum==SUM_OK) state=OK;
		for(int k=0;k<9;k++)
		{
			int r = (doRow==true ? where : k);
			int c = (doRow==false ? where : k);
			setState(r,c,state);
		}			   
	} // checkRowCol
	
	private void setState(int row, int col, int state)
	{
		JButton b = jbuttons[row][col];
		if(fixeds[row][col]==true) return; // dont touch		
		if(state==OK) b.setForeground(new Color(0.0f,0.7f,0.0f));
		if(state==UNKNOWN) b.setForeground(Color.blue);
		if(state==ERR) b.setForeground(Color.red);
	}

	/* (non-Javadoc)
	 * @see java.awt.event.MouseListener#mouseEntered(java.awt.event.MouseEvent)
	 */
	public void mouseEntered(MouseEvent e)
	{
		// TODO Auto-generated method stub
		
	}

	/* (non-Javadoc)
	 * @see java.awt.event.MouseListener#mouseExited(java.awt.event.MouseEvent)
	 */
	public void mouseExited(MouseEvent e)
	{
		// TODO Auto-generated method stub
		
	}

	/* (non-Javadoc)
	 * @see java.awt.event.MouseListener#mousePressed(java.awt.event.MouseEvent)
	 */
	public void mousePressed(MouseEvent e)
	{
		// TODO Auto-generated method stub
		
	}

	/* (non-Javadoc)
	 * @see java.awt.event.MouseListener#mouseReleased(java.awt.event.MouseEvent)
	 */
	public void mouseReleased(MouseEvent e)
	{
		// TODO Auto-generated method stub
		
	}

	public int getSq(int row, int col)
	{
		return 3 * (row/3) + col/3;
	}

	public int getSq(int pos)
	{
		return getSq(pos/9, pos%9);
	}

	public int initStats() // result is number of errors
	{
		int val;	
		int errors = 0;
		// first clear all
		for(int x=0; x<9; x++)
		{
			for(val=1; val<10; val++) // NOTE: from 1 to 9 !!!
			{
				rowUsed[x][val]=0;
				colUsed[x][val]=0;
				sqUsed[x][val]=0;
			}
		}
		// now really init used fields
		for(int row=0; row<9; row++)
		{	
			for(int col=0; col<9; col++)
			{
				if(fixeds[row][col]==false)
				{
					values[row][col]=UNKNOWN;
					jbuttons[row][col].setText("");
					jbuttons[row][col].setForeground(Color.blue);
					continue;
				}
				jbuttons[row][col].setForeground(Color.black);
				int v = values[row][col];
				int sq = 3 * (row/3) + col/3;
				if(rowUsed[row][v]>0 ||
                                   colUsed[col][v]>0 ||
                                   sqUsed[sq][v]>0)
				{
					errors++;
				}
				rowUsed[row][v]++;
				colUsed[col][v]++;
				sqUsed[sq][v]++;
			} // columns
		} // all rows
		return errors;
	} // initStats() - result is number of errors
	
	public int getEntropy(int pos)
	{
		int row=pos/9;
		int col=pos%9;
		if(fixeds[row][col]==true) return 0;
		int sq = 3 * (row/3) + col/3;
		int entropy = 0;
		for(int v=0; v<9; v++)
		{
			if(rowUsed[row][v]>0) continue;
			if(colUsed[col][v]>0) continue;
			if(sqUsed[sq][v]>0) continue;
			entropy++;
		}
		return entropy;
	}  // lower getEntropy() is better
	
	public int getNext(int prev)
	{
		if(pleaseOptimize==false)
		   return prev+1; // no optimization yet
		// calc best candidate
		int lowPos = -1;
		int lowEntropy = 0;
		for(int pos=0; pos<(9*9); pos++)
		{
			if(values[pos/9][pos%9] != UNKNOWN) continue; // not a candidate
			int entropy = getEntropy(pos);
			if(lowPos == -1)
			{
				lowPos = pos;
				lowEntropy = entropy;
				continue;
			}
			if(entropy < lowEntropy)
			{
				lowPos = pos;
				lowEntropy = entropy;
			}
		} // every position
		//System.out.println("getNext(): lowPos="+lowPos+" with entropy "+lowEntropy);
		return lowPos;
	} // getNext - with/without optimization
	
	public boolean solveBrute(int prev)
	{
		int start = getNext(prev);
		if(start<0)
		{
			// nothing to do - we are done!!!
			return true;
		}
		
		// convert single-valued start to row/col
		int row = start/9;
		int col = start%9;
		
		if(pleaseStop)
			return false;

		if(row>=9 || col>=9)
		{
			// System.out.println("Done???");
			repaint();
			return true; // DONE
		}
		int sq = 3 * (row/3) + col/3;
		//System.out.println("startSeeking at "+row+"x"+col+" which is sq "+sq);
		
		// if fixed, go to next field
		if(fixeds[row][col]==true)
		{
			return solveBrute(start);
		}
		
		// now try every possible combi
		for(int v=1; v<=9; v++)
		{
			if(rowUsed[row][v]>0) continue;
			if(colUsed[col][v]>0) continue;
			if(sqUsed[sq][v]>0) continue;
			// use it
			values[row][col]=v;
			jbuttons[row][col].setText(""+v);
			rowUsed[row][v]++;
			colUsed[col][v]++;
			sqUsed[sq][v]++;
			boolean res = solveBrute(start);
			if(res==true) // found!!!
				return true;
			rowUsed[row][v]--;
			colUsed[col][v]--;
			sqUsed[sq][v]--;
		}
		values[row][col]=UNKNOWN;
		jbuttons[row][col].setText("");
		return false; // :(
	} // solveBrute(recursive)
	
	public void showSolved()
	{
		for(int row=0;row<9;row++)
		{
			for(int col=0;col<9;col++)
			{
				if(fixeds[row][col])
				{
					jbuttons[row][col].setForeground(colorFixed);
				}
				else
				{
					jbuttons[row][col].setForeground(colorFound);
				}
			}
		}
	} // showSolved()

	public void showErrors()
	{
		for(int row=0;row<9;row++)
		{
			for(int col=0;col<9;col++)
			{
				int v = values[row][col];
				if(v==UNKNOWN) continue;
				int sq = getSq(row,col);
				if(rowUsed[row][v]<=1 &&
				   colUsed[col][v]<=1 &&
				   sqUsed[sq][v]<=1) continue;
				jbuttons[row][col].setForeground(colorError);
			}
		}
	} // showErrors
	
	public void run()
	{
		info.append("Solving ");
		pleaseOptimize = optimize.isEnabled();
		info.append(" optimization, please wait...\n");	
		boolean res = solveBrute(-1);
		stopThread();
		if(res==true)
		{
			showSolved();
			info.append("Solved!\n");
		}
		else		
		{
			info.append("NOT SOLVED!\n");
		}
	}

	/* (non-Javadoc)
	 * @see java.awt.event.KeyListener#keyPressed(java.awt.event.KeyEvent)
	 */
	public void keyPressed(KeyEvent e)
	{
		// TODO Auto-generated method stub
		Object o = e.getSource();
		if(o==null || !(o instanceof JButton))
			return;
		if(thread!=null)
			return;
		char c = e.getKeyChar();
		if(c==' ') c='0';
		if(c>='0' && c<='9')
		{
			pressJButton((JButton)o, (c-'0'));
		}		
	} // keyPressed()

	/* (non-Javadoc)
	 * @see java.awt.event.KeyListener#keyReleased(java.awt.event.KeyEvent)
	 */
	public void keyReleased(KeyEvent e)
	{
		// TODO Auto-generated method stub
		
	}

	/* (non-Javadoc)
	 * @see java.awt.event.KeyListener#keyTyped(java.awt.event.KeyEvent)
	 */
	public void keyTyped(KeyEvent e)
	{
		// TODO Auto-generated method stub
		
	} // run()



}
