//
//  sudoku.java
//  sudoku solver
//
//  Created by Perette Barella on 2006-06-06.
//  Copyright (c) 2006 Perette Barella. All rights reserved.
//	$Id: Sudoku.java,v 1.7 2006/08/04 23:47:20 perette Exp $
//



import java.awt.*;
import java.applet.*;
import javax.swing.*;
import java.util.*;
import java.awt.*;
import java.awt.event.*;



/**
 * Create square buttons instead of the default rectangular JButton.
 */
class SquareButton extends JButton {
	SquareButton (String s) {
		super (s);
	}
	public Dimension getPreferredSize () {
		Dimension d = super.getPreferredSize ();
		d.width = d.height * 3 / 2;
		return (d);
	}
}


/**
 * Interactive sudoku game.
 * The game features an automated sudoku resolver which operates in real-time based
 * on user input; this requires the resolver operate sufficiently fast for the
 * user's experience.  Features:
 * <UL>
 * <LI>Switchable displaying of resolved values.
 * <LI>Multi-level undo.
 * <LI>Switchable resolving algorithms, and statistics for performance of each
 * algorithm.
 * <LI>Option to display possible remaining values in not-fully-resolved cells.
 * <LI>Option to display redundant user-input cells (i.e., cells which could be
 * calculated from other values if not supplied by user input.)
 * </UL>
 * @author Perette Barella
 * @version $Id: Sudoku.java,v 1.7 2006/08/04 23:47:20 perette Exp $
 */
public class Sudoku extends JApplet {
	JPanel gridPanel = new JPanel (new GridLayout (9, 9));
	JPanel buttonPanel = new JPanel (new GridLayout (10, 1));
	JPanel algorithmPanel = new JPanel (new GridLayout (SudokuResolver.NUMBER_OF_ALGORITHMS * 2, 1));
	JPanel statusPanel = new JPanel ();
	
	JCheckBox validButton = new JCheckBox ("Valid", true);
	JCheckBox resolveButton = new JCheckBox ("Resolve", true);
	JCheckBox showOptionsButton = new JCheckBox ("Show options", false);
	JCheckBox redundantButton = new JCheckBox ("Show redundant clues", false);

	JButton undoButton = new JButton ("Undo");
	JButton resetButton = new JButton ("Reset");
	JLabel algorithmStatus [] = new JLabel [SudokuResolver.NUMBER_OF_ALGORITHMS];
	JCheckBox algorithmButton [] = new JCheckBox [SudokuResolver.NUMBER_OF_ALGORITHMS];
	JButton[] button = new JButton [10];
	JButton[][] grid = new JButton [9][9];
	int [][] sudokuGrid = new int [9][9];
	int currentNumber = 0;
	
	Stack<int [][]> gameHistory = new Stack<int [][]> ();
	
    public void init() {
		Container contain = getContentPane();
		for (int y = 0; y < 10; y++) {
			button [y] = new JButton (y + "");
			buttonPanel.add (button [y]);
			button[y].addActionListener (new SelectButtonListener (y));
			button [y].setBackground (Color.LIGHT_GRAY);
		}
		button [0].setText ("Clear");
		button [0].setBackground (Color.GRAY);
		
		for (int y = 0; y < 9; y++) {
			for (int x = 0; x < 9; x++) {
				grid [y][x] = new SquareButton (" ");
				gridPanel.add (grid [y][x]);
				grid[y][x].addActionListener (new GridButtonListener (y, x));
				grid[y][x].addKeyListener (new GridKeyListener (y, x));
			}
		}
		for (int y = 0; y < 3; y++) {
			for (int x = 0; x < 3; x++) {
				grid [0 + y][0 + x].setBackground (Color.GRAY);
				grid [0 + y][6 + x].setBackground (Color.GRAY);
				grid [6 + y][0 + x].setBackground (Color.GRAY);
				grid [6 + y][6 + x].setBackground (Color.GRAY);
				grid [3 + y][3 + x].setBackground (Color.GRAY);
			}
		}
		for (int x = 0; x < algorithmButton.length; x++) {
			algorithmButton [x] = new JCheckBox ("Algorithm " + (char) ('A' + x), true);
			algorithmButton [x].addActionListener (updateAction);
			algorithmStatus [x] = new JLabel ("0/0");
			algorithmPanel.add (algorithmButton [x]);
			algorithmPanel.add (algorithmStatus [x]);
		}
		algorithmButton [0].setEnabled (false);
		
		statusPanel.add (validButton);
		validButton.setEnabled (false);
		statusPanel.add (undoButton);
		undoButton.addActionListener (new ActionListener () {
			public void actionPerformed (ActionEvent event) {
				if (!gameHistory.empty()) {
					sudokuGrid = gameHistory.pop();
					display ();
				}
			}
		});
		statusPanel.add (resetButton);
		resetButton.addActionListener (new ActionListener () {
			public void actionPerformed (ActionEvent event) {
				Container contain = getContentPane ();
				int action = JOptionPane.showConfirmDialog (contain, "Clear the history too?", "Reset grid",
					JOptionPane.YES_NO_CANCEL_OPTION);
				if (action == JOptionPane.YES_OPTION || action == JOptionPane.NO_OPTION) {
					if (action == JOptionPane.YES_OPTION) {
						gameHistory = new Stack ();
					} else {
						gameHistory.push (duplicateGrid (sudokuGrid));
					}
					for (int x = 0; x < 9; x++) {
						sudokuGrid [x] = new int [9];
					}
					display ();
				}
			}
		});
		statusPanel.add (resolveButton);
		resolveButton.addActionListener (updateAction);
		statusPanel.add (showOptionsButton);
		showOptionsButton.addActionListener (updateAction);
		statusPanel.add (redundantButton);
		redundantButton.addActionListener (updateAction);
		
		contain.setLayout (new BorderLayout());
		contain.add (gridPanel, BorderLayout.CENTER);
		contain.add (buttonPanel, BorderLayout.WEST);
		contain.add (algorithmPanel, BorderLayout.EAST);
		contain.add (statusPanel, BorderLayout.SOUTH);

		setSize (getPreferredSize ());
		grid [0][0].requestFocus ();
	}
	
	/**
	 * Action listener to respond to a mouse click on a grid cell.
	 */
	class GridButtonListener implements ActionListener {
		int row, column;
		GridButtonListener (int row, int column) {
			this.row = row;
			this.column = column;
		}
		
		public void actionPerformed (ActionEvent event) {
			int assign = currentNumber;
			// If reassigning the same number, clear the space instead.
			if (assign == sudokuGrid [row][column]) {
				assign = 0;
			}
			setLocation (column, row, assign);
		}
	}

	
	/** Action listener to refresh the sudoku display. */
	ActionListener updateAction = new ActionListener () {
		public void actionPerformed (ActionEvent event) {
			display ();
		}
	};

	
	/**
	 * Action listener to respond to a mouse click in the select-placement-number
	 * panel.
	 */
	class SelectButtonListener implements ActionListener {
		int number;
		SelectButtonListener (int number) {
			this.number = number;
		}
		
		public void actionPerformed (ActionEvent event) {
			button [currentNumber].setBackground (Color.LIGHT_GRAY);
			currentNumber = number;
			button [currentNumber].setBackground (Color.GRAY);
		}
	}


	/**
	 * KeyListener to respond to a keypress in a grid cell.
	 * <UL>
	 * <LI>Zero (0) erases any entry in the current cell.
	 * <LI>Backspace erases any entry in the current cell, or the prior cell if
	 * the current cell was empty.  This behaviour makes sense when considering
	 * the behaviour when placing values.
	 * <LI>Arrows move on cell in their respective direction, looping around
	 * the edge of the grid.
	 * <LI>1-9 assign numbers and move one cell to the right, wrapping around to
	 * the left and down one row at the end of a line.
	 * </UL>
	 */
	class GridKeyListener implements KeyListener {
		int row, column;
		GridKeyListener (int row, int column) {
			this.row = row;
			this.column = column;
		}
		
		public void keyTyped (KeyEvent event) {
			char key = event.getKeyChar ();
			if (key >= '0' && key <= '9') {
				setLocation (column, row, key - '0');
				grid [row][column].transferFocus ();
			}
		}
		public void keyPressed (KeyEvent event) {
			switch (event.getKeyCode ()) {
				case KeyEvent.VK_UP:
					grid [(row + 8) % 9][column].requestFocus ();
					break;
				case KeyEvent.VK_DOWN:
					grid [(row + 1) % 9][column].requestFocus ();
					break;
				case KeyEvent.VK_LEFT:
					grid [row][(column + 8) % 9].requestFocus ();
					break;
				case KeyEvent.VK_RIGHT:
					grid [row][(column + 1) % 9].requestFocus ();
					break;
				case KeyEvent.VK_BACK_SPACE:
					int r = row;
					int c = column;
					if (sudokuGrid [r][c] == 0) {
						// Back up to the prior box
						if (column == 0) {
							r = (row + 8) % 9;
						}
						c = (column + 8) % 9;
						grid [r][c].requestFocus ();
					}
					setLocation (c, r, 0);
					break;
			}
		}
		public void keyReleased (KeyEvent event) {
		}
	}

	
	/**
	 * Make a change to the grid.
	 * If a value is being placed in a cell already containing that value,
	 * no action is taken.
	 * Otherwise, the grid is pushed onto the undo stack, the value
	 * changed in the grid, and the sudoku window updated.
	 * @param column		The column in which the value is to be placed.
	 * @param row			The row in which the value is to be placed.
	 * @param assign		The value to place in the sudoku grid.
	 *						Zero indicates a value should be cleared.
	 */
	void setLocation (int column, int row, int assign) {
		if (sudokuGrid [row][column] != assign) {
			gameHistory.push (duplicateGrid (sudokuGrid));
			grid [row][column].setText (assign == 0 ? " " : assign + "");
			sudokuGrid [row][column] = assign;
			display ();
		}
	}
	
	/**
	 * Update the applet window.  Resolve the sudoku to see if it is valid.
	 * Update the valid checkbox and update the displayed grid:
	 * <UL>
	 * <LI>Resolve: Disabled; Show options: Disabled.
	 * <BR>Clears all cells for which the user hasn't supplied a value.
	 * <LI>Resolve: Enabled; Show options: Disabled.
	 * <BR>Displays any computed values in blue in their corresponding cells.
	 * <LI>Resolve: Disabled; Show options: Enabled.
	 * <BR>Displays possible values for each cell.  Row, cell, and quadrant
	 * eliminations for known values are performed before displaying values, but
	 * no further processing occurs.
	 * <BR>Resolve: Enabled; Show options: Enabled.
	 * <BR>After reducing the sudoku as much as possible, displays values
	 * for each cell.
	 * </UL>
	 * If the show redundant values option is checked, then for each user-supplied
	 * value a sudoku is created with the value removed, then the resolver run.
	 * If the resolver restores the value, then it is redundant and is highlighted
	 * in red in the displayed grid.
	 */
	void display () {
		boolean handleRedundant = false;
		boolean displayOptions = showOptionsButton.isSelected ();
		
		// Collect the algorithm-enable options from the UI.
		boolean active [] = new boolean [SudokuResolver.NUMBER_OF_ALGORITHMS];
		for (int i = 0; i < algorithmButton.length; i++) {
			active [i] = algorithmButton [i].isSelected ();
		}
		
		// Resolve the sudoku, then update the algorithm performance.
		SudokuResolver resolved = new SudokuResolver (sudokuGrid, active);
		for (int x = 0; x < SudokuResolver.NUMBER_OF_ALGORITHMS; x++) {
			algorithmStatus [x].setText (resolved.status [x].reductionsMade + "/" +
										 resolved.status [x].groupsAnalyzed);
		}

		// Updated the displayed grid validity status.
		validButton.setSelected (resolved.isValid ());

		// If the grid is invalid, don't try to display redundant value information.
		// If it is valid, display it if the user wants it displayed.
		if (resolved.isValid ()) {
			redundantButton.setEnabled (true);
			handleRedundant = redundantButton.isSelected ();
		} else {
			redundantButton.setEnabled (false);
		}

		// If resolving is enabled, use the resolved grid for display.
		// If it is disabled, use the user-supplied grid.
		SudokuGrid sudoku = resolved;
		if (!resolveButton.isSelected ()) {
			sudoku = new SudokuGrid (sudokuGrid);
		}
		
		// Update the UI grid cells.
		sudoku.setAccessMode (AccessMethod.BY_ROW);
		for (int y = 0; y < 9; y++) {
			sudoku.setGroupNumber (y);
			for (int x = 0; x < 9; x++) {
				int z = sudoku.getValue (x);
				if (displayOptions) {
					long possibs = sudoku.getPossibilities (x);
					StringBuffer possibStr = new StringBuffer ("");
					for (int i = 0; i < 9; i++) {
						if ((possibs & (1 << i)) != 0) {
							possibStr.append ((char) ('1' + i));
						}
					}
					grid [y][x].setText (possibStr.toString ());
				} else {
					grid [y][x].setText (z == 0 ? " " : z + "");
				}
				grid [y][x].setForeground (sudokuGrid [y][x] == 0 ? Color.BLUE : Color.BLACK);
				if (handleRedundant && sudokuGrid [y][x] != 0) {
					int [][] workgrid = duplicateGrid (sudokuGrid);
					workgrid [y][x] = 0;
					resolved = new SudokuResolver (workgrid);
					resolved.setAccessMode (AccessMethod.BY_ROW);
					resolved.setGroupNumber (y);
					if (resolved.getValue (x) == z) {
						grid [y][x].setForeground (Color.RED);
					}
				}
			}
		}
	}

	/**
	 * Make a copy of an int [][].
	 * @param grid		The array to copy.
	 * @return			A fully-duplicated array.
	 */
	public int [][] duplicateGrid (int [][] grid) {
		int [][] newgrid = new int [grid.length][];
		for (int x = 0; x < grid.length; x++) {
			newgrid [x] = grid [x].clone ();
		}
		return (newgrid);
	}
}