/*
 Sudoku 4.4
 Mats Anderbok
 2008-09-07
*/

// View options:
// best viewed with a monospace font,
// TAB = 4 and width > 80 columns

import java.applet.*;

import java.awt.*;
import java.awt.event.*;
import java.io.*;
import java.net.URL;

public class Sudoku extends Applet implements Constants,
		KeyListener, MouseListener, MouseMotionListener {
	String[] version = {"Version 4.4  7 Sept. 2008",
						"Version 4.4  2008-09-07"};

// flag set when thread for complete elimination is active
	static volatile boolean running = false;
	Thread tryThread;
	static volatile boolean solving = false;
	Thread solveThread;

	Image offImg;
	Font font_text, font_lang, font_narrow, font_bold, font_small, font_tiny,
		font_area, font_load, font_btn, font_btn11;

// background colour: pale yellow
	Color backgr = new Color(224, 224, 128);

// sizes on screen for cell and candidate squares
	int sq_size = 24, cand_size = 5;

// number of cells filled in by user and by computer
	int numUser = 0, numSolved = 0, numCand = 0;

// cursor position
	int cursorX = 0, cursorY = 0;
	boolean cursor_visible = true;

	boolean highlight = false;
	int highlight_digit = 0;

// upper left corner on screen
	static final int screenX = 6 + 18, screenY = 28 + 18;

// upper left corner of printout
	static final int[] printX = {42, 319}, printY = {40, 306, 572};
//	static final int[] printX = {40, 310}, printY = {80, 327, 574};

	static int printPos = 0;	// printing position
	static SudokuConfig[] printConfig =
		new SudokuConfig[printX.length * printY.length];

// drawing of printing positions on screen
	static final int printpos_x = 423 + 20, printpos_y = 182, printpos_w = 50,
		printpos_h = 71, printpos_size = 20;

	static TextArea tArea, loadArea;
	Panel langPanel, elimPanel, candiPanel, advPanel, labelPanel, labelPanel3, versionPanel;
	Label langLabel, elimLabel, candiLabel, versionLabel;

// chosen language
	static Checkbox english, swedish;

	Checkbox auto;
	static Checkbox simple, advanced, complete;
	static Checkbox inters, sets, xy_wings, xy_set, n_wing, nishio, chain;
	Checkbox squares, figures;
	Button solve, clear, undo, redo, permute;
	Button save, load, archive, print, print_later;
	static final String PRINT_CMD = "print";
//						 inters sets  xy-wi  xy-set n-wing nishio chain
	boolean[] prevAdv  = {true, true, true,  false, true,  false, false},
			  prevComp = {true, true, false, false, false, false, false};
	static final int INTERS = 0, SETS = 1, XY_WINGS = 2, XY_SET = 3,
					 N_WING = 4, NISHIO = 5, CHAIN = 6;

// key ASCII numbers
	static final int LEFT = 37, RIGHT = 39, UP = 38, DOWN = 40, SPACE = 32,
					 DELETE = 127, BACK = 8, NUMPAD_0 = 96,
					 CURSOR_VISIBLE = 67, HIGHLIGHT = 72,
					 UNDO_KEY = 85, REDO_KEY = 82, SOLVE_KEY = 83,
					 LF = 10, CR = 13;

// the main board drawn on screen
	static Board main;

// previous boards for undo
	SudokuConfig[] prev = new SudokuConfig[200];
	State state; // status for checkboxes
	int UNDO_INDX = 0;
	boolean firstUndo = true;

// table of which cells are in which row, column and box
	static int[][] rcb_sq = new int[27][9]; // rcb = row, column, box
	static int[][] rcb_rev = new int[81][3]; // reverse table

	static boolean[] user; // figures typed by user
	static int[] latest; // latest solved digits, marked blue on screen

	boolean inited = false;

	void resetUser() {
		user = new boolean[81];
	}

	void resetLatest() {
		latest = new int[81];
	}

	public void init() {
		System.out.println("init");


		main = new Board(true);

		resetUser();
		resetLatest();

		offImg = createImage(9 * sq_size + 14 + 36, 9 * sq_size + 36 + 36);

		setBackground(backgr);

		addKeyListener(this);
		addMouseListener(this);
		addMouseMotionListener(this);
		requestFocus();
		running = false;

// calculate index for every cell in boxes, rows and columns
		for (int m = 0; m < 9; m++) {
			for (int n = 0; n < 9; n++) {
				rcb_sq[m][n] = 27 * (m / 3) + 3 * (m % 3) + 9 * (n / 3)
								 + n % 3;
				rcb_sq[m + 9][n] = 9 * m + n;
				rcb_sq[m + 18][n] = m + 9 * n;
// the reverse: boxes, rows and columns for every cell
				rcb_rev[27 * (m / 3) + 3 * (m % 3) + 9 * (n / 3)
					  + n % 3][0] = m;
				rcb_rev[9 * m + n][1] = m + 9;
				rcb_rev[m + 9 * n][2] = m + 18;
			}
		}

		this.setLayout(null);

		font_text = new Font("Serif", Font.PLAIN, 12);
		font_lang = new Font("Serif", Font.PLAIN, 10);
		font_narrow = new Font("SansSerif", Font.PLAIN, 16);
		font_bold = new Font("SansSerif", Font.BOLD, 19);
		font_small = new Font("Monospaced", Font.PLAIN, 11);
		font_tiny = new Font("Monospaced", Font.PLAIN, 10);
		font_area = new Font("Monospaced", Font.PLAIN, 12);
		font_load = new Font("Monospaced", Font.PLAIN, 11);
		font_btn = new Font("SansSerif", Font.PLAIN, 12);
		font_btn11 = new Font("SansSerif", Font.PLAIN, 11);

// set language
		int lang = 0; // English
		try {
			String s = getParameter("language"); // read language from HTML tag
			if(s != null && s.toLowerCase().equals("swedish")) {
				lang = 1;
			}
		} catch(Exception e) {}
		Printing.lang = lang;

		langPanel = new Panel(new FlowLayout(FlowLayout.LEFT));
		langLabel = new Label(LANGUAGE[lang]);
		langPanel.add(langLabel);
		langPanel.setFont(font_lang);
		CheckboxGroup langGroup = new CheckboxGroup();

		english = new Checkbox(ENGLISH[lang], langGroup, (lang == 0));
		langPanel.add(english);
		english.addItemListener(new LangListener());

		swedish = new Checkbox(SWEDISH[lang], langGroup, (lang == 1));
		langPanel.add(swedish);
		swedish.addItemListener(new LangListener());

		this.add(langPanel);

		tArea = new TextArea("", 8, 71, TextArea.SCROLLBARS_VERTICAL_ONLY);
		tArea.setFont(font_area); // only one font within a textarea
		this.add(tArea);

		loadArea = new TextArea(LOAD_WINDOW[lang], 1, 54, TextArea.SCROLLBARS_VERTICAL_ONLY);
		loadArea.setFont(font_load);
		this.add(loadArea);

// automatic solving
		auto = new Checkbox(AUTO[lang], true);
		this.add(auto);
		auto.addItemListener(new AutoListener());

// elimination
		labelPanel = new Panel(new GridLayout(2, 1, 0, -8));
		elimLabel = new Label(ELIMINATION[lang]);
		labelPanel.add(elimLabel);
		elimPanel = new Panel(new FlowLayout(FlowLayout.LEFT));
		labelPanel.add(elimPanel);
		CheckboxGroup elim = new CheckboxGroup();

		simple = new Checkbox(BASIC[lang], elim, true);
		elimPanel.add(simple);
		simple.addItemListener(new ElimListener());

		advanced = new Checkbox(ADVANCED[lang], elim, false);
		advanced.setEnabled(true);
		elimPanel.add(advanced);
		advanced.addItemListener(new ElimListener());

		complete = new Checkbox(COMPLETE[lang], elim, false);
		complete.addItemListener(new ElimListener());
		elimPanel.add(complete);

		this.add(labelPanel);

// advanced choices
		advPanel = new Panel(new FlowLayout(FlowLayout.LEFT));

		inters = new Checkbox(INTERS_str[lang], false);
		advPanel.add(inters);
		inters.addItemListener(new AdvListener());
		inters.setEnabled(false);

		sets = new Checkbox(SETS_str[lang], false);
		advPanel.add(sets);
		sets.addItemListener(new AdvListener());
		sets.setEnabled(false);

		n_wing = new Checkbox(N_WING_str[lang], false);
		advPanel.add(n_wing);
		n_wing.addItemListener(new AdvListener());
		n_wing.setEnabled(false);

		xy_wings = new Checkbox(XY_WINGS_str[lang], false);
		advPanel.add(xy_wings);
		xy_wings.addItemListener(new AdvListener());
		xy_wings.setEnabled(false);

		xy_set = new Checkbox(XY_SET_str[lang], false);
/* wait until version 4.5
		advPanel.add(xy_set);
		xy_set.addItemListener(new AdvListener());
		xy_set.setEnabled(false);
*/

		nishio = new Checkbox(NISHIO_str[lang], false);
		advPanel.add(nishio);
		nishio.addItemListener(new AdvListener());
		nishio.setEnabled(false);

		chain = new Checkbox(CHAIN_str[lang], false);
		advPanel.add(chain);
		chain.addItemListener(new AdvListener());
		chain.setEnabled(false);

		this.add(advPanel);

// candidates
		labelPanel3 = new Panel(new GridLayout(2, 1, 0, -8));
		candiLabel = new Label(CANDIDATES[lang]);
		labelPanel3.add(candiLabel);
		candiPanel = new Panel(new FlowLayout(FlowLayout.LEFT));
		CheckboxGroup candi = new CheckboxGroup();

		squares = new Checkbox(SQUARES[lang], candi, true);
		candiPanel.add(squares);
		squares.addItemListener(new CandiListener());

		figures = new Checkbox(FIGURES[lang], candi, false);
		candiPanel.add(figures);
		figures.addItemListener(new CandiListener());

// version
		versionPanel = new Panel(new BorderLayout());
		versionLabel = new Label(version[lang]);
		versionPanel.add(versionLabel, "East");
		versionPanel.add(candiPanel, "West");
		labelPanel3.add(versionPanel);

		this.add(labelPanel3);

// buttons
		solve = new Button(SOLVE[lang]);
		solve.setEnabled(false);
		add(solve);
		solve.addActionListener(new SolveListener());
		solve.setFont(font_btn);

		clear = new Button(CLEAR[lang]);
		add(clear);
		clear.addActionListener(new ClearListener());
		clear.setFont(font_btn);

		undo = new Button(UNDO[lang]);
		add(undo);
		undo.setEnabled(false);
		undo.addActionListener(new UndoListener());
		undo.setFont(font_btn);

		redo = new Button(REDO[lang]);
		add(redo);
		redo.setEnabled(false);
		redo.addActionListener(new RedoListener());
		redo.setFont(font_btn);

		permute = new Button(PERMUTE[lang]);
		add(permute);
		permute.setEnabled(true);
		permute.addActionListener(new PermuteListener());
		permute.setFont(font_btn);

		print = new Button(PRINT[lang]);
		add(print);
		print.setEnabled(true);
		print.addActionListener(new PrintListener());
		print.setActionCommand(PRINT_CMD);
		print.setFont(font_btn);

		print_later = new Button(PRINT_LATER[lang]);
		add(print_later);
		print_later.setEnabled(true);
		print_later.addActionListener(new PrintListener());
		print_later.setFont(font_btn11);

		save = new Button(SAVE[lang]);
		add(save);
		save.setEnabled(true);
		save.addActionListener(new SaveListener());
		save.setFont(font_btn);

		load = new Button(LOAD[lang]);
		add(load);
		load.setEnabled(true);
		load.addActionListener(new LoadListener());
		load.setFont(font_btn);

		archive = new Button(ARCHIVE[lang]);
//		add(archive);
//		archive.setEnabled(true);
//		archive.addActionListener(new ArchiveListener());
//		archive.setFont(font_btn);

		state = new State();
		state.save(); // save the states of the check boxes

		inited = true;
		compLayout();
		repaint();
	} // init

	void initLang(int lang) {
		System.out.println("init language");

// checkboxes
		auto.setLabel(AUTO[lang]);
		auto.doLayout();

		elimLabel.setText(ELIMINATION[lang]);
		simple.setLabel(BASIC[lang]);
		advanced.setLabel(ADVANCED[lang]);
		complete.setLabel(COMPLETE[lang]);
		elimPanel.doLayout();

		inters.setLabel(INTERS_str[lang]);
		sets.setLabel(SETS_str[lang]);
		n_wing.setLabel(N_WING_str[lang]);
		xy_wings.setLabel(XY_WINGS_str[lang]);
		xy_set.setLabel(XY_SET_str[lang]);
		nishio.setLabel(NISHIO_str[lang]);
		chain.setLabel(CHAIN_str[lang]);
		advPanel.doLayout();

		langLabel.setText(LANGUAGE[lang]);
		english.setLabel(ENGLISH[lang]);
		swedish.setLabel(SWEDISH[lang]);
		langPanel.doLayout();

		candiLabel.setText(CANDIDATES[lang]);
		squares.setLabel(SQUARES[lang]);
		figures.setLabel(FIGURES[lang]);
		candiPanel.doLayout();
		versionLabel.setText(version[lang]);
		versionPanel.doLayout();

// buttons
		solve.setLabel(SOLVE[lang]);
		clear.setLabel(CLEAR[lang]);
		undo.setLabel(UNDO[lang]);
		redo.setLabel(REDO[lang]);
		permute.setLabel(PERMUTE[lang]);
		print.setLabel(PRINT[lang]);
		print_later.setLabel(PRINT_LATER[lang]);
		save.setLabel(SAVE[lang]);
		load.setLabel(LOAD[lang]);
		archive.setLabel(ARCHIVE[lang]);
	} // initLang

	void startTry() {
		if (complete.getState() && main.auto) {
			tryThread = new TryAll();
			tryThread.start();
		} else {
			Printing.printlnBoth("");
		}
	}

	void finishTry() {
		running = false;
		if (tryThread != null) {
// give the thread time to finish
			while (tryThread.isAlive()) {
				try {Thread.sleep(10);
				} catch (InterruptedException e) {}
			}
		}
		solving = false;
		if (solveThread != null) {
			while (solveThread.isAlive()) {
				try {Thread.sleep(10);
				} catch (InterruptedException e) {}
			}
		}
	}

	class AutoListener implements ItemListener {
		public void itemStateChanged(ItemEvent ev) {
			requestFocus();
			saveConfig();
			finishTry();

			if (auto.getState()) { // automatic solving
				resetLatest();
				solve.setEnabled(false);
				main.auto = true;
//				Printing.printlnBoth("-1-");
				Printing.printlnBoth(AUTO[Printing.lang]);
				reCalculate(false);
			} else { // manual solving
				solve.setEnabled(true);
				main.auto = false;
			}
//			undo.setEnabled(false);
			repaint();
		}
	}

	class ElimListener implements ItemListener {
		public void itemStateChanged(ItemEvent ev) {
			requestFocus();
			finishTry();

			if (advanced.getState() || complete.getState()) {
				inters.setEnabled(true);
				sets.setEnabled(true);
				xy_wings.setEnabled(true);
//				xy_set.setEnabled(true);
				n_wing.setEnabled(true);
				nishio.setEnabled(true);
				chain.setEnabled(true);
			} else { // basic elimination
				inters.setEnabled(false);
				inters.setState(false);
				sets.setEnabled(false);
				sets.setState(false);
				xy_wings.setEnabled(false);
				xy_wings.setState(false);
				xy_set.setEnabled(false);
				xy_set.setState(false);
				n_wing.setEnabled(false);
				n_wing.setState(false);
				nishio.setEnabled(false);
				nishio.setState(false);
				chain.setEnabled(false);
				chain.setState(false);
			}
			if (advanced.getState()) {
				inters.setState(prevAdv[0]);
				sets.setState(prevAdv[1]);
				xy_wings.setState(prevAdv[2]);
				xy_set.setState(prevAdv[3]);
				n_wing.setState(prevAdv[4]);
				nishio.setState(prevAdv[5]);
				chain.setState(prevAdv[6]);
			}
			if (complete.getState()) {
				inters.setState(prevComp[0]);
				sets.setState(prevComp[1]);
				xy_wings.setState(prevComp[2]);
				xy_set.setState(prevComp[3]);
				n_wing.setState(prevComp[4]);
				nishio.setState(prevComp[5]);
				chain.setState(prevComp[6]);
			}
			saveConfig(); // save the new configuration

// only recalculate if automatic solving
			if (main.auto) {
//				Printing.printlnBoth("");
				Printing.printlnBoth(AUTO[Printing.lang]);
				reCalculate(false);
			}
			repaint();
		}
	}

// choose language: English or Swedish
	public class LangListener implements ItemListener {
		public void itemStateChanged(ItemEvent ev) {
			if (english.getState()) {
				Printing.lang = 0;
			} else {
				Printing.lang = 1;
			}
// change button and checkbox labels
			initLang(Printing.lang);
			requestFocus();
			repaint();
		}
	}

	public class CandiListener implements ItemListener {
		public void itemStateChanged(ItemEvent ev) {
			requestFocus();
			saveConfig();
			repaint();
		}
	}

	public class AdvListener implements ItemListener {
		public void itemStateChanged(ItemEvent ev) {
			saveConfig();
			finishTry();

// we can't have nishio without n-wing and intersection, because these
// are special cases of nishio
			if (nishio.getState() && !(n_wing.getState() && inters.getState())) {
				if ((advanced.getState() && !prevAdv[NISHIO])
					|| (complete.getState() && !prevComp[NISHIO]))
				{ // nishio has been set
					inters.setState(true);
					n_wing.setState(true);
				} else { // n-wing or intersection has been unset
					nishio.setState(false);
				}
			}

// if no box was checked, it wouldn't be advanced elimination
			if (advanced.getState() && !inters.getState() && !sets.getState() &&
				!xy_wings.getState() && !xy_set.getState() && !n_wing.getState() &&
				!nishio.getState() && !chain.getState())
			{
				if (prevAdv[INTERS])	// if intersection was checked last
					sets.setState(true);
				else
					inters.setState(true);
			}

// store current state so we can go back later
			if (advanced.getState()) {
				prevAdv[0] = inters.getState();
				prevAdv[1] = sets.getState();
				prevAdv[2] = xy_wings.getState();
				prevAdv[3] = xy_set.getState();
				prevAdv[4] = n_wing.getState();
				prevAdv[5] = nishio.getState();
				prevAdv[6] = chain.getState();
			}
			if (complete.getState()) {
				prevComp[0] = inters.getState();
				prevComp[1] = sets.getState();
				prevComp[2] = xy_wings.getState();
				prevComp[3] = xy_set.getState();
				prevComp[4] = n_wing.getState();
				prevComp[5] = nishio.getState();
				prevComp[6] = chain.getState();
			}

// only recalculate if automatic solving
			if (main.auto) {
//				Printing.printlnBoth("");
				Printing.printlnBoth(AUTO[Printing.lang]);
				reCalculate(false);
			}

			requestFocus();
			repaint();
		}
	}

	void reCalculate(boolean solved) {
		finishTry();
		boolean changed = false;
// create a new board without auto
		Board tmp = new Board(false);

		if (main.auto) {
			for (int x = 0; x < 81; x++) {
				if (user[x]) {
					tmp.set(x, main.figure[x]);
				}
			}
			main.copy(tmp);
// set auto and solve
			main.auto = true;
			if (simple.getState()) {
				tmp.copy(main);
				main.checkAndSolve();
				if (diff(main.figure, tmp.figure)) {
					Printing.printlnBoth("");
					Printing.printlnBoth("");
				}
			} else {
				do {
// version 4.4
// Temporary solution: check if there is any change that gives
// printout, so we have to insert a new line. Change to a more
// elegant solution for the next version.
					tmp.copy(main);
					main.checkAndSolve();
					if (diff(main.figure, tmp.figure)) {
						Printing.printlnBoth("");
					}
					changed = main.eliminateAdv();
				} while (changed);
			}
			startTry();
		} else { // manual solving
			if (solved) {
// include solved cells
				for (int x = 0; x < 81; x++) {
					if (main.figure[x] > 0) {
						tmp.set(x, main.figure[x]);
					}
				}
			} else {
				for (int x = 0; x < 81; x++) {
// include only given cells
					if (user[x]) {
						tmp.set(x, main.figure[x]);
					}
				}
			}
			main = tmp;
// eliminate once
			if (advanced.getState() || complete.getState()) {
				main.eliminateAdv();
			}

//			if (complete.getState()) {
//				running = true;
//				main.tryAllOnce(false, true);
//				running = false;;
//			}

		}
//		Printing.printlnBoth("-5-");
	}

// compare two arrays and return true if they are different
	boolean diff(int[] a1, int[] a2) {
		if (a1 == null && a2 == null) {
			return false;
		}
		if (a1 == null || a2 == null || a1.length != a2.length) {
			return true;
		}
		for (int n = 0; n < a1.length; n++) {
			if (a1[n] != a2[n] ) {
				return true;
			}
		}
		return false;
	}

	boolean diff(boolean[] a1, boolean[] a2) {
		if (a1 == null && a2 == null) {
			return false;
		}
		if (a1 == null || a2 == null || a1.length != a2.length) {
			return true;
		}
		for (int n = 0; n < a1.length; n++) {
			if (a1[n] != a2[n] ) {
				return true;
			}
		}
		return false;
	}

	boolean diff(Board b1, Board b2) {
		if (b1 == null && b2 == null) {
			return false;
		}
		if (diff(b1.figure, b2.figure)) {
			return true;
		}
		for (int n = 0; n < 81; n++) {
			if (b1.figure[n] == 0 && diff(b1.imposs[n], b2.imposs[n])) {
				return true;
			}
		}
		return false;
	}

	class SolveListener implements ActionListener {
// the user presses the Solve button; note that
// it is always manual solving, that is main.auto = false
		public void actionPerformed(ActionEvent ev) {
			requestFocus();
			finishTry();

			saveConfig();
			resetLatest();

// solve once
			if (do_solve()) {
// print an extra line if anything has changed
				Printing.printlnBoth("");
			}

			repaint();
		}
	}

	boolean do_solve() {
		if (main.solved()) {
			return false; // puzzle already solved
		}
// create a copy to search on
			Board tmp = new Board(false);
			tmp.copy(main);

			boolean changed = false;

			changed = main.setLast(false);

				for (int m = 0; m < 27; m++) {
			for (int k = 1; k <= 9; k++) { // digits 1-9
					int sq = tmp.check_rcb(m, k);
					if (sq >= 0) {
						changed = true;
						latest[sq] = k; // save for paint
						main.set(sq, k);
					}
				}
			}

			for (int i = 0; i < 81; i++) {
				int single = tmp.check(i);
				if (single > 0) {
					changed = true;
					latest[i] = single;
					main.set(i, single);
				}
			}

			if (changed) {
				Printing.printlnBoth("");
			}

			if (main.solved()) {
				return true; // puzzle solved
			}

// do advanced elimination once (on 'tmp')
			if (advanced.getState() || complete.getState()) {
				changed = changed | main.eliminateAdv(tmp);
			}

// if nothing else helps, start a thread for complete elimination
			if (complete.getState() && !changed) {
				tryThread = new TryAll();
				tryThread.start();
// wait for the thread to finish
				while (tryThread.isAlive()) {
					try { Thread.sleep(20); }
					catch (InterruptedException e) {}
				}
// test if anything has changed
				if (diff(main, tmp)) {
					return true;
				}
			} // if complete

		return changed;
	}

	class ClearListener implements ActionListener {
		public void actionPerformed(ActionEvent ev) {
			requestFocus();
			finishTry();

			saveConfig();
			Printing.clearArea();

			if (numSolved == 0 || auto.getState()) {
				main = new Board(auto.getState());
				resetUser();
				cursorX = 0;
				cursorY = 0;
			} else { // only remove the solution
//				Printing.printlnBoth("-7-");
				reCalculate(false);
			}

			repaint();
		}
	}

	void set_undo(int i) {
		main = new Board(false);
		main.copy(prev[i].board);
		user = new boolean[Sudoku.user.length];
		System.arraycopy(prev[i].user, 0, user, 0, user.length);
		latest = new int[Sudoku.latest.length];
		System.arraycopy(prev[i].latest, 0, latest, 0, latest.length);

// switch between simple and advanced/complete
		if (prev[i].simple != simple.getState()) {
			inters.setEnabled(!inters.isEnabled());
			sets.setEnabled(!sets.isEnabled());
			xy_wings.setEnabled(!xy_wings.isEnabled());
			xy_set.setEnabled(!xy_set.isEnabled());
			n_wing.setEnabled(!n_wing.isEnabled());
			nishio.setEnabled(!nishio.isEnabled());
			chain.setEnabled(!chain.isEnabled());
		}

		auto.setState(prev[i].board.auto);
		simple.setState(prev[i].simple);
		advanced.setState(prev[i].advanced);
		complete.setState(prev[i].complete);

		inters.setState(prev[i].inters);
		sets.setState(prev[i].sets);
		xy_wings.setState(prev[i].xy_wings);
		xy_set.setState(prev[i].xy_set);
		n_wing.setState(prev[i].n_wing);
		nishio.setState(prev[i].nishio);
		chain.setState(prev[i].chain);

		squares.setState(prev[i].squares);
		figures.setState(prev[i].figures);

		cursorX = prev[i].cursX;
		cursorY = prev[i].cursY;

		solve.setEnabled(!auto.getState());
	}

	class UndoListener implements ActionListener {
		public void actionPerformed(ActionEvent ev) {
			requestFocus();
			do_undo(1);
			repaint();
		}
	}

	void do_undo(int n) {
		finishTry();
// if there are no more moves to undo
		if ((UNDO_INDX >= prev.length) || (prev[UNDO_INDX] == null)) {
			return;
		}

		if (firstUndo) {
			saveConfig();
		}
		UNDO_INDX += n;
// if this is the last undo, disable the button
		if ((UNDO_INDX + 1 >= prev.length) || (prev[UNDO_INDX + 1] == null)) {
			undo.setEnabled(false);
		}
		redo.setEnabled(true);

		if (UNDO_INDX >= prev.length) {
			UNDO_INDX = prev.length - 1;
		}
		while (UNDO_INDX >= 0 && prev[UNDO_INDX] == null) {
			UNDO_INDX--;
		}

		set_undo(UNDO_INDX);

		firstUndo = false;
	}

	class RedoListener implements ActionListener {
		public void actionPerformed(ActionEvent ev) {
			requestFocus();
			do_redo(1);
			repaint();
		}
	}

	void do_redo(int n) {
		finishTry();
// if there are no more moves to redo
		if (UNDO_INDX <= 0) {
			return;
		}

		UNDO_INDX -= n;
// if this is the last redo, disable the button
		if (UNDO_INDX <= 0) {
			redo.setEnabled(false);
			UNDO_INDX = 0;
		}
		undo.setEnabled(true);
		set_undo(UNDO_INDX);
	}

	class SudokuConfig {
		Board board = new Board(false);
		boolean[] user = new boolean[Sudoku.user.length];
		int[] latest = new int[Sudoku.latest.length];
		boolean simple; boolean advanced; boolean complete; boolean inters; boolean sets;
		boolean xy_wings; boolean xy_set; boolean n_wing; boolean nishio; boolean chain;
		boolean squares; boolean figures;
		int cursX, cursY;
		SudokuConfig(State s) {
			board.copy(main); board.auto = s.autoS;
			System.arraycopy(Sudoku.user, 0, user, 0, user.length);
			System.arraycopy(Sudoku.latest, 0, latest, 0, latest.length);
			simple = s.simpleS; advanced = s.advancedS; complete = s.completeS;
			inters = s.intersS; sets = s.setsS; xy_wings = s.xy_wingsS; xy_set = s.xy_setS;
			n_wing = s.n_wingS; nishio = s.nishioS; chain = s.chainS;
			squares = s.squaresS; figures = s.figuresS;
			cursX = cursorX; cursY = cursorY;
		}
	}

	void saveConfig() {
// put the board and state variables on the top of the undo stack
		for (int i = prev.length - 1; i > 0; i--) {
			prev[i] = prev[i - 1];
		}
		prev[0] = new SudokuConfig(state);
		UNDO_INDX = 0;

		undo.setEnabled(true);
// Save the state variables for next 'saveConfig'. This is
// necessary because they are changed by the user before to read
// their state.
		state.save();

		firstUndo = true;
		redo.setEnabled(false);
	}

	class State {
		boolean autoS, simpleS, advancedS, completeS, intersS, setsS, xy_wingsS,
			xy_setS, n_wingS, nishioS, chainS, squaresS, figuresS;
		void save() {
			autoS = auto.getState();
			simpleS = simple.getState();
			advancedS = advanced.getState();
			completeS = complete.getState();
			intersS = inters.getState();
			setsS = sets.getState();
			xy_wingsS = xy_wings.getState();
			xy_setS = xy_set.getState();
			n_wingS = n_wing.getState();
			nishioS = nishio.getState();
			chainS = chain.getState();
			squaresS = squares.getState();
			figuresS = figures.getState();
		}
	}

// produce an equivalent sudoku by doing permutations of rows, columns and digits
	class PermuteListener implements ActionListener {
		public void actionPerformed(ActionEvent ev) {
			requestFocus();
			finishTry();

			saveConfig();
			resetLatest();

			int[] box_hor = randVect(3);
			int[] box_ver = randVect(3);
			int[][] row = new int[3][];
			int[][] col = new int[3][];
			for (int box = 0; box < 3; box++) {
				row[box] = randVect(3);
				col[box] = randVect(3);
			}
			boolean trans = (Math.random() < 0.5);

			Board tmp = new Board(main.auto);
			for (int y = 0; y < 9; y++) {
				for (int x = 0; x < 9; x++) {
// new column
					int x0 = 3 * box_ver[x / 3] + col[x / 3][x % 3];
// new row
					int y0 = 3 * box_hor[y / 3] + row[y / 3][y % 3];
					if (trans) {
// transpone (exchange rows and columns)
						int swap = x0;
						x0 = y0;
						y0 = swap;
					}
// transfer digits to the temporary variable
					tmp.figure[x0 + 9 * y0] = main.figure[x + 9 * y];
					tmp.imposs[x0 + 9 * y0] = (boolean[]) main.imposs[x + 9 * y].clone();
// copy the saved user variable
					user[x0 + 9 * y0] = prev[0].user[x + 9 * y];
				}
			}
// move cursor to new position
			cursorX = 3 * box_ver[cursorX / 3] + col[cursorX / 3][cursorX % 3];
			cursorY = 3 * box_hor[cursorY / 3] + row[cursorY / 3][cursorY % 3];
			if (trans) {
				int swap = cursorX;
				cursorX = cursorY;
				cursorY = swap;
			}

			main = new Board(auto.getState());

// fill a vector with 0, 1, ..., 8
			int[] numbers = randVect(9);
			for (int i = 0; i < 9; i++) {
// increase to 1, 2, ..., 9
				numbers[i]++;
			}
			for (int i = 0; i < 81; i++) {
				if (tmp.figure[i] > 0) {
// use the old digit as index
					int newFigure = numbers[tmp.figure[i] - 1];
					main.figure[i] = newFigure;
					main.isSet[rcb_rev[i][0]][newFigure] = true;
					main.isSet[rcb_rev[i][1]][newFigure] = true;
					main.isSet[rcb_rev[i][2]][newFigure] = true;
				} else {
					for (int k = 1; k <= 9; k++) {
						main.imposs[i][numbers[k - 1]] = tmp.imposs[i][k];
					}
				}
			}

			repaint();
		}
	}

// place 0, 1, ..., length-1 in random order in a vector
	int[] randVect(int length) {
		int[] vector = new int[length];
		for (int n = length - 1; n > 0; n--) {
// generate a random integer from 0 to n
// Note that the digit 'n' is placed among n+1 positions. The zero
// will be in the last place left.
			int rand = (int) ((n + 1) * Math.random());
			int i = 0;
			do {
				while (vector[i] > 0) { // find next free position
					i++;
				}
				i++;
				rand--;
			} while (rand >= 0); i--;
			vector[i] = n; // place the digit in a free position
		}
		return vector;
	}

// print on A4 paper
	class PrintListener implements ActionListener {
		public void actionPerformed(ActionEvent ev) {
// write to text area and console
			if (squares.getState()) {
				main.print();
			} else {
// print candidates as well
				main.printCand();
			}
// increase the printing position first in case printing is cancelled
			printPos = (printPos % 6) + 1;
			Printing.printlnBoth(P_POSI[Printing.lang] + ": " + printPos);
// save board and state variables for later printing
			SudokuConfig sudo = new SudokuConfig(state);
			sudo.squares = squares.getState();
			sudo.figures = figures.getState();
			printConfig[printPos - 1] = sudo;

// if the print button was pressed, draw and send to the printer
			if (ev.getActionCommand().equals(PRINT_CMD)) {
				Frame fr = new Frame();
				PrintJob print_job = fr.getToolkit().getPrintJob(fr, "Sudoku", null);
				if (print_job == null) {
					Printing.printlnBoth(P_INTERRUPT[Printing.lang]);
// delete board from memory
					printConfig[printPos - 1] = null;
				} else {
// create new Graphics object to draw on
					Graphics print_g = print_job.getGraphics();

					if (print_g != null) {
						for (int n = 0; n < printConfig.length; n++) {
							if (printConfig[n] != null )
							{
								sq_size++; // make cells a little larger on paper
								paintBoard(printConfig[n], printX[n % 2],
									printY[n / 2 % 3], false, print_g);
								sq_size--;
// delete board from memory
								printConfig[n] = null;
							}
						}
						print_g.dispose();
					}
// send to printer
					print_job.end();
				} // else
			} // if "print"

			Printing.printlnBoth("");
			repaint();
			requestFocus();
		}
	}

   static String inFilename = "sudoku.txt";
   static String outFilename = "sudoku.txt";
   static String saveTitle = "";

   class SaveListener implements ActionListener {
		public void actionPerformed(ActionEvent ev) {
			Printing.printlnBoth(SAVE_FILE[Printing.lang]);
			PrintWriter pw = null;
			boolean app = true;

			FileDialog fd = new FileDialog(new Frame(), "", FileDialog.SAVE);
			fd.setFile(outFilename);
			fd.show();

			String name = fd.getFile();
			String dir = fd.getDirectory();
			if (name != null && name.length() > 0 && dir != null) {
				outFilename = dir + name;
			}
// open file in append mode
			try {
				 pw = new PrintWriter(new FileWriter(outFilename, app));
			} catch (IOException e) {}

			pw.print("// " + numUser + " " + gIVEN[Printing.lang]);
			if (numSolved > 0) {
				pw.print(", " + numSolved + " " + sOLVED[Printing.lang]);
			}
			pw.println();

			pw.println(main.printStr());
			pw.close();
		}
	}

	class LoadListener implements ActionListener {
		public void actionPerformed(ActionEvent ev) {
//			Printing.printlnBoth("Read from file");
			BufferedReader br = null;

// only read from text area until file reading works better
if (true) {
readFromFile(br);
return;
}

			FileDialog fd = new FileDialog(new Frame(), "", FileDialog.LOAD);
			fd.setFile(inFilename);
			fd.show();
			String name = fd.getFile();
			String dir = fd.getDirectory();
			if (name != null && name.length() > 0 && dir != null) {
				inFilename = dir + name;
			}


// open file
			try {
				br = new BufferedReader(new FileReader(inFilename));
			} catch (Exception e) {
				System.err.println(e);
			}
			readFromFile(br);
		}
	}

	void readFromFile(BufferedReader br) {
		int num_sq = 0;
		Board tmp = new Board(false);
		String line = "";

		if (br == null ) {  // read from TextArea
			 line = loadArea.getText();
			 num_sq = setNumbers(line, tmp, num_sq);
// if the load area is empty, read from primary text area instead
			 if (num_sq == 0) {
				line = tArea.getText();
				num_sq = setNumbers(line, tmp, num_sq);
			 }
		}
		else {  // read from file
		try {
			 while (br.ready() && num_sq < 81) {
// read one line at a time
				 line = br.readLine();
				 num_sq = setNumbers(line, tmp, num_sq);
			 }
		} catch (Exception e) {System.err.println(e);}
		try {br.close();}
		catch (IOException e) {System.err.println(e);}
		}
// set the board
		if (num_sq > 0) {
// correction 2008-08-22 (have to change state before saving)
			if (main.auto) {
				auto.setState(false); // manual solving
				solve.setEnabled(true);
			}
			saveConfig();
			for (int i = 0; i < 81; i++) {
				user[i] = (tmp.figure[i] > 0);
			}

			main = tmp;
			repaint();
		}
	}


	int setNumbers(String str, Board tmp, int indx) {
// (temporary solution to recognize empty load window)
		boolean digits = false;

// skip null lines
		if (str ==  null)
			return indx;
//// skip comment lines
//		if (str.length() > 2 && str.charAt(0) == '/' && str.charAt(1) ==  '/')
//			return indx;

		char ch;

		for (int i = 0; i < str.length(); i++) {
			switch (ch = str.charAt(i)) {
			case '1':case '2':case '3':case '4':case '5':
			case '6':case '7':case '8':case '9':
				if (indx < tmp.figure.length) {
					tmp.set(indx, (int) ch - (int) '0');
					indx++;
					digits = true;
				}
				break;
// space characters
			case '0':case '.':case '_':
				indx++;
				break;
			default:
// all other characters are ignored
			}
		}
// (change for version 4.5 with file load)
		if (digits)
			return indx;
		else
			return 0;
   }

// component layout (buttons, checkboxes and textfields)
	void compLayout() {
		int xOff = 266 + 26, yOff = 27, width = 64, heigth = 29, space = 13;
		solve.setBounds  (xOff, yOff + 0 * (heigth + space), width, heigth);
		clear.setBounds  (xOff, yOff + 1 * (heigth + space), width, heigth);
		undo.setBounds   (xOff, yOff + 2 * (heigth + space), width, heigth);
		redo.setBounds   (xOff, yOff + 3 * (heigth + space), width, heigth);
		permute.setBounds(xOff, yOff + (int) (4.7 * (heigth + space)), width, heigth);

		save.setBounds   (xOff + width + space, yOff + 0 * (heigth + space), width, heigth);
		load.setBounds   (xOff + width + space, yOff + 1 * (heigth + space), width, heigth);
		archive.setBounds(xOff + width + space, yOff + 2 * (heigth + space), width, heigth);
		print_later.setBounds(xOff + width + space, yOff + (int) (3.7  * (heigth + space)), width, heigth);
		print.setBounds  (xOff + width + space, yOff + (int) (4.7  * (heigth + space)), width, heigth);

		int w = this.getSize().width;
		int h = this.getSize().height;
		tArea.setBounds(2, h*2/3 -20, w-4, h/3-2 -37 +18);
		loadArea.setBounds(2, h -37, w-4, 35);

		yOff = 200 + 36;
		langPanel.setBounds  (312, yOff + 62, 200, 24);
		auto.setBounds	 (128, yOff + 54, 130, 30);
		labelPanel.setBounds (5, yOff + 65, w-8, 50);
		advPanel.setBounds   (5, yOff + 104, w-8, 30);
		labelPanel3.setBounds(5, yOff + 132, w-8, 50);
   }


	public void update(Graphics g) {
		highlight = false;
		paint(g);
	}

	public void paint(Graphics g) {
		if (!inited)
			return;
//		compLayout();

		Graphics offscreen = offImg.getGraphics();
		offscreen.setColor(backgr);
		offscreen.fillRect(0, 0, 400, 400);
		offscreen.setColor(Color.lightGray);
		offscreen.fillRect(3, 25, 400, 400);

		numUser = 0;
		numSolved = 0;
		numCand = 0;

// paint cursor
		if (cursor_visible) {
			if (delete) {
				offscreen.setColor(Color.red);
			} else {
				offscreen.setColor(Color.white);
			}
			offscreen.fillRect(sq_size * cursorX + cursorX / 3 + screenX + 2,
				sq_size * cursorY + cursorY / 3 + screenY + 2, sq_size - 1,
				sq_size - 1);
		}

// paint the board with figures and lines
		paintBoard(null, screenX, screenY, true, offscreen);

		offscreen.setColor(Color.black);
		offscreen.setFont(font_text);
		offscreen.drawString(Printing.solvedCand(numUser, numSolved, numCand),
			screenX - 18, screenY - 9 - 18); ;

		if (printPos > 0) {
			Image printpos_img = createImage(printpos_w, printpos_h);
			Graphics offprintpos = printpos_img.getGraphics();
			paintPrintPos(offprintpos, printpos_w, printpos_h, printpos_size);
			g.drawImage(printpos_img, printpos_x, printpos_y, null);
		}

		g.drawImage(offImg, 0, 0, null);
		offscreen.dispose();
		requestFocus();
	}

	void paintBoard(SudokuConfig sudo, int xOff, int yOff, boolean screen, Graphics g) {
		if (sudo == null) {
			sudo = new SudokuConfig(state);
			sudo.squares = squares.getState();
			sudo.figures = figures.getState();
		}
// draw lines
		g.setColor(Color.darkGray);
		for (int i = 1; i < 9; i++) {
			g.drawLine(sq_size * i + i / 3 + xOff + 1, yOff + 2,
				sq_size * i + i / 3 + xOff + 1, yOff + sq_size * 9 + 3);
			g.drawLine(xOff + 2, sq_size * i + i / 3 + yOff + 1,
				xOff + sq_size * 9 + 3, sq_size * i + i / 3 + yOff + 1);
		}
		g.setColor(Color.black);
		for (int i = 0; i < 4; i++) {
			g.fillRect(sq_size * i * 3 + i + xOff, yOff, 2, sq_size * 9 + 5);
			g.fillRect(xOff, sq_size * i * 3 + i + yOff, sq_size * 9 + 5, 2);
		}

// draw row and column numbers
		if (screen) {
			g.setColor(new Color(220, 220, 255));
			for (int x = 0; x < 9; x++) {
				g.fillOval(sq_size * x + x / 3 + xOff + 4, yOff - 18, 16, 16);
				g.fillOval(sq_size * x + x / 3 + xOff + 4, sq_size * 9 + yOff + 7, 16, 16);
			}
			for (int y = 0; y < 9; y++) {
				g.fillOval(xOff - 18, sq_size * y + y / 3 + yOff + 5, 16, 16);
				g.fillOval(sq_size * 9 + xOff + 7, sq_size * y + y / 3 + yOff + 5, 16, 16);
			}
			g.setColor(Color.black);
			g.setFont(font_small);
			for (int x = 0; x < 9; x++) {
				g.drawString(COL_STR[x], sq_size * x + x / 3 + xOff + 5, yOff - 18 + 12);
				g.drawString(COL_STR[x], sq_size * x + x / 3 + xOff + 5, sq_size * 9 + yOff + 7 + 12);
			}
			g.setFont(font_small);
			for (int y = 0; y < 9; y++) {
				g.drawString(ROW_STR[y], xOff - 18 + 1, sq_size * y + y / 3 + yOff + 5 + 12);
				g.drawString(ROW_STR[y], sq_size * 9 + xOff + 7 + 1, sq_size * y + y / 3 + yOff + 5 + 12);
			}
		} // if

// draw digits and small squares
		g.setColor(Color.black);
		for (int x = 0; x < 9; x++) {
			for (int y = 0; y < 9; y++) {
				if (sudo.board.figure[x + 9 * y] > 0) { // if there is a digit
					g.setColor(Color.black);
					if (sudo.user[x + 9 * y]) {
						numUser++;
						g.setFont(font_bold);
// given digits
						g.drawString(sudo.board.figure[x + 9 * y] + "",
							sq_size * x + x / 3 + xOff + 8,
							sq_size * y + y / 3 + yOff + 18 + 3);
					} else {
						if (screen) {
							numSolved++;
							if (latest[x + 9 * y] > 0) {
								g.setColor(Color.blue);
							}
						}
						g.setFont(font_narrow);
// solved digits
						g.drawString(sudo.board.figure[x + 9 * y] + "",
							sq_size * x + x / 3 + xOff + 9,
							sq_size * y + y / 3 + yOff + 20);
					}
				} else { // no digit set
					if (screen) {
						for (int k = 1; k <= 9; k++) {
							if (!sudo.board.imposs[x + 9 * y][k]) {
								numCand++;
							}
						}
					}
					if (sudo.squares) {
						if (screen) { // squares only on screen, not printer
							g.setColor(Color.gray);
							paintSquares(xOff + sq_size * x + x / 3 + 4,
								yOff + sq_size * y + y / 3 + 4,
								sudo.board.imposs[x + 9 * y], g);
						}
					}
					if (sudo.figures) {
						g.setColor(Color.darkGray);
						paintFigures(xOff + sq_size * x + x / 3 + 4,
							yOff + sq_size * y + y / 3 + 4,
							sudo.board.imposs[x + 9 * y], g);
					}
				}
			} // for x, y
		}
	}

// draw small squares
	void paintSquares(int x, int y, boolean[] imposs, Graphics g) {
		Color old_colour = g.getColor();
		for (int k = 1; k <= 9; k++) {
			if (!imposs[k]) {
				if (highlight_digit == k) {
					g.setColor(Color.yellow);
				}
				g.fillRect(x + (k - 1) % 3 * (cand_size + 2),
					y + (k - 1) / 3 * (cand_size + 2), cand_size, cand_size);
				if (highlight_digit == k) {
					g.setColor(old_colour);
				}
			}
		}
	}

// draw small digits
	void paintFigures(int x, int y, boolean[] imposs, Graphics g) {
		int allowed = 0;
		for (int k = 1; k <= 9; k++) {
			if (!imposs[k]) {
				allowed++;
			}
		}
		if (allowed > 6) {
			g.setFont(font_tiny);
		} else {
			g.setFont(font_small);

		}
		int k = 0, n = 0;
		Color old_colour = g.getColor();
		switch (allowed) {
		case 9:
		case 8:
		case 7:
			while (++k <= 9) {
				if (!imposs[k]) {
					if (highlight_digit == k) {
						g.setColor(Color.yellow);
						g.fillRect(x + n % 3 * (cand_size + 2) - 2,
							y + n / 3 * (cand_size + 3) - 2, 
							cand_size + 3, cand_size + 2);
						g.setColor(old_colour);
					}
					g.drawString(k + "", x + n % 3 * (cand_size + 2) - 1,
						y + n / 3 * (cand_size + 3) + 5);
					n++;
				}
			}
			break;
		case 6:
		case 5:
			while (++k <= 9) {
				if (!imposs[k]) {
					if (highlight_digit == k) {
						g.setColor(Color.yellow);
						g.fillRect(x + n % 3 * (cand_size + 2) - 1,
							y + n / 3 * (cand_size + 6) - 1, cand_size + 3, cand_size + 5);
						g.setColor(old_colour);
					}
					g.drawString(k + "", x + n % 3 * (cand_size + 2) - 1,
						y + n / 3 * (cand_size + 6) + 8);
					n++;
				}
			}
			break;
		case 4:
		case 3:
			while (++k <= 9) {
				if (!imposs[k]) {
					if (highlight_digit == k) {
						g.setColor(Color.yellow);
						g.fillRect(x + n % 2 * (cand_size + 4) + 1,
							y + n / 2 * (cand_size + 6) - 1, cand_size + 3, cand_size + 5);
						g.setColor(old_colour);
					}
					g.drawString(k + "", x + n % 2 * (cand_size + 4) + 1,
						y + n / 2 * (cand_size + 6) + 8);
					n++;
				}
			}
			break;
		case 2:
			while (++k <= 9) {
				if (!imposs[k]) {
					if (highlight_digit == k) {
						g.setColor(Color.yellow);
						g.fillRect(x + n % 2 * (cand_size + 4) + 1,
							y + 2 * cand_size - 6, cand_size + 3, cand_size + 5);
						g.setColor(old_colour);
					}
					g.drawString(k + "", x + n % 2 * (cand_size + 4) + 1,
						y + 2 * cand_size + 3);
					n++;
				}
			}
			break;
		case 1:
			while (++k <= 9) {
				if (!imposs[k]) {
					if (highlight_digit == k) {
						g.setColor(Color.yellow);
						g.fillRect(x + cand_size + 1,
							y + 2 * cand_size - 6, cand_size + 3, cand_size + 5);
						g.setColor(old_colour);
					}
					g.drawString(k + "", x + cand_size + 1,
						y + 2 * cand_size + 3);
					n++;
				}
			}
		default:
		}
	}

	void paintPrintPos(Graphics g, int width, int height, int size) {
		g.setColor(Color.white);
		g.fillRect(0, 0, width, height);
		g.setColor(Color.darkGray);
		g.drawRect(0, 0, width-1, height-1);

		int space_x = (width - size * printX.length) / (printX.length + 1);
		int space_y = (height - size * printY.length) / (printY.length + 1);

		g.setFont(font_bold);
		for (int n = 0; n < printConfig.length; n++) {
			if (n + 1 == (printPos % printConfig.length) + 1) { // next printing position
				g.setColor(Color.blue);
			} else {
				g.setColor(Color.gray);
			}
			g.drawString("" + (n+1),
						 space_x + (n % printX.length) * (size + space_x) + 5,
						 space_y + (n / printX.length) * (size + space_y) + size - 2);

			if (n + 1 == (printPos % printConfig.length) + 1) { // next printing position
				g.setColor(Color.green);
				g.drawRect(space_x + (n % printX.length) * (size + space_x),
						   space_y + (n / printX.length) * (size + space_y),
						   size, size);
				g.drawRect(space_x + (n % printX.length) * (size + space_x) + 1,
						   space_y + (n / printX.length) * (size + space_y) + 1,
						   size - 2, size - 2);
			} else if (printConfig[n] == null ) {
//				g.setColor(Color.lightGray);
//				g.fillRect(space_x + (n % printX.length) * (size + space_x),
//						   space_y + (n / printX.length) * (size + space_y),
//						   size + 1, size + 1);

			} else {
				g.setColor(Color.black);
				g.drawRect(space_x + (n % printX.length) * (size + space_x),
						   space_y + (n / printX.length) * (size + space_y),
						   size, size);
// draw diagonal lines
				g.drawLine(space_x + (n % printX.length) * (size + space_x),
						   space_y + (n / printX.length) * (size + space_y),
						   space_x + (n % printX.length) * (size + space_x) + size,
						   space_y + (n / printX.length) * (size + space_y) + size);
				g.drawLine(space_x + (n % printX.length) * (size + space_x),
						   space_y + (n / printX.length) * (size + space_y) + size,
						   space_x + (n % printX.length) * (size + space_x) + size,
						   space_y + (n / printX.length) * (size + space_y));
			}
		} // for n
	}

// stop the applet
	public void stop() {
		System.out.println("stop");
		running = false;
		solving = false;
	}

// destroy the applet
	public void destroy() {
		stop();
		System.exit(1);
	}

	public void keyReleased(KeyEvent e) {}

	public void keyTyped(KeyEvent e) {}

	public void keyPressed(KeyEvent e) {
//System.out.println("-- " + e.getKeyCode() + " -- " + e.getModifiers());
		cursor_fixed = false;
		switch (e.getKeyCode()) {
		case LEFT:
			cursorX--;
			if (cursorX < 0) {
				cursorX = 8;
			}

// restore from delete mode
			delete = false;
			repaint();
			return;
		case RIGHT:
			cursorX++;
			if (cursorX > 8) {
				cursorX = 0;
			}
			delete = false;
			repaint();
			return;
		case UP:
			cursorY--;
			if (cursorY < 0) {
				cursorY = 8;
			}
			delete = false;
			repaint();
			return;
		case DOWN:
			cursorY++;
			if (cursorY > 8) {
				cursorY = 0;
			}
			delete = false;
			repaint();
			return;
		case SPACE:
			cursorX++;
			if (cursorX > 8) {
				cursorX = 0;
				cursorY++;
				if (cursorY > 8) {
					cursorY = 0;
				}
			}
			delete = false;
			repaint();
			return;
		case BACK:
			cursorX--;
			if (cursorX < 0) {
				cursorX = 8;
				cursorY--;
				if (cursorY < 0) {
					cursorY = 8;
				}
			}
// continue with DELETE to remove digit
		case DELETE:
// if a digit is set
			if (main.figure[cursorX + 9 * cursorY] > 0) {
				finishTry(); // interrupt solving
				saveConfig();
				if (main.auto) {
// remove digit and start over
					user[cursorX + 9 * cursorY] = false;
					reCalculate(false);
				} else {
// remove digit and resolve with already solved digits included
					user[cursorX + 9 * cursorY] = false;
					main.figure[cursorX + 9 * cursorY] = 0;
					reCalculate(true);
				}
				delete = false;
			} else {
// prepare to delete next time or restore
				if (e.getKeyCode() == BACK) {
					delete = true;
				} else {
					delete = !delete;
				}
			}
			repaint();
			return;
		case CURSOR_VISIBLE:
			if (e.getModifiers() == InputEvent.SHIFT_MASK) {
				cursor_visible = !cursor_visible;
				repaint();
				return;
			}
		case HIGHLIGHT:
			if (e.getModifiers() == InputEvent.SHIFT_MASK) {
				if (highlight_digit > 0) {
					highlight_digit = 0;
					repaint();
				} else {
					highlight = true;
				}
				return;
			}
		case UNDO_KEY:
			if (e.getModifiers() == InputEvent.SHIFT_MASK) {
				do_undo(5);
			} else {
				do_undo(1);
			}
			repaint();
			return;
		case REDO_KEY:
			if (e.getModifiers() == InputEvent.SHIFT_MASK) {
				do_redo(5);
			} else {
				do_redo(1);
			}
			repaint();
			return;
		case SOLVE_KEY:
			if (main.auto)
				return;

			finishTry();
			saveConfig();
			resetLatest();

			if (e.getModifiers() == InputEvent.SHIFT_MASK) {
// solve as far as possible
				solveThread = new SolveRepeat();
				solveThread.start();
			} else {
// solve once
				if (do_solve()) {
					Printing.printlnBoth("");
					repaint();
				}
			}
			return;
		case LF:
		case CR:
			int x = cursorX + 9 * cursorY;
			if (main.figure[x] > 0) {
// if the cell is solved, make it a given
				user[x] = true;
			} else if (!main.auto) {
				finishTry();
				saveConfig();
				resetLatest();
// try to solve the cell by singles
				int single = main.check(x);
				if (single > 0) {
					latest[x] = single;
					main.set(x, single);
				}
				for (int q = 0; q < 3; q++) {
					int m = rcb_rev[x][q];
					for (int k = 1; k <= 9; k++) {
						int cell = main.check_rcb(m, k);
						if (cell == x) {
							latest[x] = k;
							main.set(x, k);
						}
					}
				}
			}
			cursorX++;
			if (cursorX > 8) {
				cursorX = 0;
				cursorY++;
				if (cursorY > 8) {
					cursorY = 0;
				}
			}
			delete = false;
			repaint();
			return;
		} // switch

		int s;
// special numerical keys
		if (e.getKeyCode() > NUMPAD_0) {
			s = e.getKeyCode() - NUMPAD_0;
		} else {
			s = e.getKeyCode() - (int) '0';
		}

		if (1 <= s && s <= 9) {
// the user has typed a digit
			if (highlight) {
				highlight_digit = s;
				repaint();
				return;
			}
			int x = cursorX + 9 * cursorY;
// if the digit is already solved by the programme
			if (main.figure[x] == s && !user[x]) {
// change to user set
				user[x] = true;
			}
			if (main.figure[x] == 0 && !main.imposs[x][s]) {
				finishTry(); // interrupt solving
				saveConfig();
				if (delete) {
// remove a candidate
					main.imposs[x][s] = true;
					if (main.auto) {
						boolean changed;
						if (simple.getState()) {
							Board tmp = new Board(false);
							tmp.copy(main);
							main.checkAndSolve();
							if (diff(main.figure, tmp.figure)) {
								Printing.printlnBoth("");
							}
						} else {
							do {
								Board tmp = new Board(false);
								tmp.copy(main);
								main.checkAndSolve();
								if (diff(main.figure, tmp.figure)) {
									Printing.printlnBoth("");
								}
								changed = main.eliminateAdv();
							} while (changed);
						}
					}
				} else {
// mark the digit as user set
					user[x] = true;
					main.set(x, s);
					if (!main.auto && (advanced.getState() || complete.getState())) {
						reCalculate(true);
					}
				}
				startTry();
			}
// move to next cell
			if (!delete) {
				cursorX++;
				if (cursorX > 8) {
					cursorX = 0;
					cursorY++;
					if (cursorY > 8) {
						cursorY = 0;
					}
				}
			}
// restore from delete mode
			delete = false;
			repaint();
		}
	}

	class SolveRepeat extends Thread {
		public void run() {
			solving = true;

			Printing.printlnBoth("");
			boolean changed = false;
			int i = 0;
			while (do_solve()) {
				if (!solving) {
					Printing.interrupt();
					return;
				}
				changed = true;
				Printing.printlnBoth(" - " + (++i) + " - ");
				repaint();
				try { Thread.sleep(100); }
				catch (InterruptedException ex) {}
			}
			if (changed) {
				Printing.printlnBoth("");
				repaint();
			}

			solving = false;
		}
	}

	class TryAll extends Thread {
		public void run() {
			if (main.solved()) {
				return;
			}

			running = true; // set flag to allow interruption

			boolean changed, solved;
			if (main.auto) {
				do {
					changed = try_auto();
					if (changed && running) {
						repaint();
						boolean new_elim;
						do {
// do the basic and advanced techniques as far as possible
							if (main.checkSolve()) {
								main.checkAndSolve();
								Printing.printlnBoth("");
							}
							new_elim = main.eliminateAdv();
						} while (new_elim && running);
					}
					solved = main.solved();
				} while (changed && running && !solved);
			} else { // Solve button
				boolean[][] two_c = main.two_cand();
// start with cells and digits with two alternatives (bi-value/bi-location)
				Printing.cand_test(false, false, true);
				changed = main.tryAllOnce(false, true, two_c, null);
//				Printing.printlnBoth("");
				if (!changed && running) {
					Printing.cand_test(false, false, false);
					changed = main.tryAllOnce(false, false, two_c, null);
//					Printing.printlnBoth("");
					if (!changed && running) {
						Printing.cand_test(false, true, true);
// valid candidates for solutions
						boolean[][] valid = new boolean[81][10];

						changed = main.tryAllOnce(true, true, two_c, valid);
//						Printing.printlnBoth("");
						if (!changed && running) {
							Printing.cand_test(false, true, false);
							main.tryAllOnce(true, false, two_c, valid);
//						  Printing.printlnBoth("");
						}
					}
				}
//				Printing.printlnBoth("-9-");
			}

			repaint();
			running = false;
		} // run

		boolean try_auto() {
			boolean[][] two_c = main.two_cand();
			boolean changed = false;
			Printing.cand_test(true, false, true);
			two_c = main.two_cand();
// test candidates with two alternatives (no recursion)
			changed = main.tryAllOnce(false, true, two_c, null);
			if (changed || !running) {
//				Printing.printlnBoth("-10-");
				return changed;
			}
			Printing.cand_test(true, false, false);
// test the rest of the candidates (no recursion)
			changed = main.tryAllOnce(false, false, two_c, null);
			if (changed || !running) {
//				Printing.printlnBoth("-11-");
				return changed;
			}
			Printing.cand_test(true, true, true);
long startTime = System.currentTimeMillis();

// valid candidates for solutions
			boolean[][] valid = new boolean[81][10];

// test candidates with two alternatives as far as possible
			changed = main.tryAllOnce(true, true, two_c, valid);
			if (changed || !running) {
//				Printing.printlnBoth("-12-");
				return changed;
			}
			Printing.cand_test(true, true, false);
// test the rest of the candidates as far as possible
			main.tryAllOnce(true, false, two_c, valid);
			if (changed) {
//				Printing.printlnBoth("-13-");
			}
System.out.println(TIME[Printing.lang] + ": " + (System.currentTimeMillis() - startTime) + " ms");
			return changed;
		}
	} // class TryAll

	boolean cursor_fixed = false;
	boolean delete = false;
	public void mouseMoved(MouseEvent e) {
		if (!cursor_fixed) {
			setCursor(e.getX(), e.getY());
		}
		requestFocus();
	}

	public void mouseDragged(MouseEvent e) {}

	public void mouseClicked(MouseEvent e) {
		cursor_fixed = true;
		setCursor(e.getX(), e.getY());
		requestFocus();
	}

	public void mousePressed(MouseEvent e) {}

	public void mouseReleased(MouseEvent e) {}

	public void mouseEntered(MouseEvent e) {
		cursor_fixed = false;
	}

	public void mouseExited(MouseEvent e) {
		cursor_fixed = false;
	}

	void setCursor(int x, int y) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				int cornerX = sq_size * i + i / 3 + 1 + screenX;
				int cornerY = sq_size * j + j / 3 + 1 + screenY;
				if (x > cornerX + 1 && x < cornerX + sq_size - 1
					&& y > cornerY + 1 && y < cornerY + sq_size - 1)
				{
					cursorX = i;
					cursorY = j;
				}
			}
		}
		repaint();
	}

// Application starter from
// http://java.sun.com/developer/technicalArticles/Programming/TurningAnApplet/index.html

  static public void main (String argv[]) {
	final int width  = 534 + 8, // bigger window to compensate for titlebar and frame
			  height = 664 + 34;
	final Applet applet = new Sudoku();
	System.runFinalizersOnExit(true);
	Frame frame = new Frame ("Sudoku Solver by Mats Anderbok");
	frame.addWindowListener (
				  new WindowAdapter()
	{
	  public void windowClosing (WindowEvent event)
	  {
		applet.stop();
		applet.destroy();
		System.exit(0);
	  }
	});
	frame.add ("Center", applet);
	frame.setSize(width, height);
//	applet.setStub (new MyAppletStub (argv, applet));
	frame.show();
	applet.init();
	applet.start();
	frame.pack();
  }

} // Sudoku

class Board implements Constants {
	int[] figure; // board of digits
	boolean[][] isSet; // digit set in a unit
	boolean[][] imposs; // eliminated digits for every cell
	boolean auto;

// boards for different levels of recursive tests
	static Board[] tmp = new Board[81];
//	static Board[] tmp = Sudoku.tmp;

// table of which cells are in which box, row and column
	int[][] rcb_sq = Sudoku.rcb_sq; // rcb = row, column, box
	int[][] rcb_rev = Sudoku.rcb_rev; // reverse table

	Board(boolean auto) {
		this.auto = auto;
		figure = new int[81];
		isSet = new boolean[27][10]; // use index 1-9
		imposs = new boolean[81][10];
	}

//	Board() {}

	void copy(Board src) {
		this.auto = src.auto;
		for (int i = 0; i < 81; i++) {
			this.figure[i] = src.figure[i];
		}
		for (int m = 0; m < 27; m++) {
			for (int n = 1; n <= 9; n++) {
				this.isSet[m][n] = src.isSet[m][n];
			}
		}
		for (int i = 0; i < 81; i++) {
			if (src.figure[i] == 0) {
				for (int n = 1; n <= 9; n++) {
					this.imposs[i][n] = src.imposs[i][n];
				}
			}
		}
	}

	boolean setAndReduce(int index, int number) {
		if (figure[index] > 0) {
			return false;
		}

		figure[index] = number;

// remove the digit in box, row and column
		for (int q = 0; q < 3; q++) {
			int m = rcb_rev[index][q]; // find the right unit
// step through the nine cells of the unit
			for (int p = 0; p < 9; p++) {
				int i = rcb_sq[m][p];
				imposs[i][number] = true;
			}
			isSet[m][number] = true;
		}

		return true;
	}

	boolean set(int index, int number) {
// if the cell is already occupied
		if (figure[index] > 0) {
			return false;
		}
		return set(index, number, false);
	}

	boolean set(int index, int number, boolean recurse) {

if ((figure[index] > 0) || imposs[index][number]) {
	System.out.println("Can't set " + Printing.cell_str(index)
		+ " = " + number + "!");
	return false;
}
	if (this == Sudoku.main && !Sudoku.user[index]) {
		Printing.set_digit(index, number);
	}

		figure[index] = number;

// remove the digit in box, row and column
		for (int q = 0; q < 3; q++) {
			int m = rcb_rev[index][q]; // find the right unit
// step through the nine cells of the unit
			for (int p = 0; p < 9; p++) {
				int i = rcb_sq[m][p];
				imposs[i][number] = true;
			}
			isSet[m][number] = true;
		}

		if (!auto) { // manual solving, no check
			return true;
		}

		boolean check = checkAndSolve(); // check the whole board and set recursively

// Terminate if the check found contradictions, or if this is a
// recursive call, in which case we will wait with advanced methods.
		if (!check || recurse) {
			return check;
		}
		if (this == Sudoku.main && !Sudoku.user[index]) {
//			Printing.printlnBoth("");
		}

		if (solved()) {
			return true; // puzzle solved
		}

// do advanced elimination
		boolean changed = false;
		if (Sudoku.advanced.getState() || Sudoku.complete.getState()) {
			do {
				changed = eliminateAdv();
				if (changed) {
					check = checkAndSolve();
					if (this == Sudoku.main && !Sudoku.user[index]) {
						Printing.printlnBoth("");
					}
					if (!check) {
						return check;
					}
				}
			} while (changed && !solved());
		}

		return true; // setting the digit went fine without contradiction
	}

	boolean checkSolve() {
		for (int m = 0; m < 27; m++) {
			for (int k = 1; k <= 9; k++) {
				int i = check_rcb(m, k);
				if (i >= 0) {
					return true;
				}
			}
		}
		for (int i = 0; i < 81; i++) {
			int single = check(i);
			if (single > 0) {
				return true;
			}
		}
		return false;
	} // checkSolve

	boolean checkAndSolve() {
		boolean check = true;

//		if (setLast(true)) {
//			return true;
//		}
		setLast(true);

// step through boxes, rows and columns to see if there is
// more than one position for digit 'k'
			for (int m = 0; m < 27; m++) {
		for (int k = 1; k <= 9; k++) { // digits 1-9
				int i = check_rcb(m, k);
// if there is only one possible cell
				if (i >= 0) {
					return set(i, k, true); // set recursively
				}
// if the digit can't be placed despite that it is not set in this unit
				if (i < -1) {
					check = false;
				}
			}
		}
// check for naked singles
		for (int i = 0; i < 81; i++) {
			int single = check(i);
			if (single > 0) {
				return set(i, single, true);
			} else if (single < 0) {
// no candidtate is this cell
				check = false;
			}
		}
// return true if there are no contradictions
		return check;
	} // checkAndSolve

// check a cell and return the only candidate
	int check(int x) {
		int last_allowed = 0;
// if the cell is not set
		if (figure[x] == 0) {
			int allowed = 0;
			for (int k = 1; k <= 9; k++) {
				if (!imposs[x][k]) {
					allowed++;
					last_allowed = k;
				}
			}
// if there is only one candidate
			if (allowed == 1) {
				return last_allowed;
			}
			if (allowed == 0) {
				return -1;
			}
		}
		return 0;
	}

// check a unit and return index for the cell where 'k' is a candidate
	int check_rcb(int m, int k) {
		if (!isSet[m][k]) { // if the 'k' isn't yet set
			int last_i = 0;
			int allowed = 0;
// step through the nine cells
			for (int p = 0; p < 9; p++) {
				int i = rcb_sq[m][p];
				if (figure[i] == 0 && !imposs[i][k]) {
					allowed++;
					last_i = i;
				}
			}
// if there is only one possible cell
			if (allowed == 1) {
				return last_i;
			}
// if the digit can't be placed despite that it is not set
			if (allowed == 0) {
//				// make all free cells empty
//				for (int p = 0; p < 9; p++) {
//					int i = rcb_sq[m][p];
//					if (figure[i] == 0) {
//						for (int n = 1; n <= 9; n++) {
//							imposs[i][n] = true;
//						}
//					}
//				}
				return -2;
			}
		}
// 'k' is already set or is a candidate in more than one cell
		return -1;
	}

	boolean checkBoard() {
// check for cells with no candidates
		for (int i = 0; i < 81; i++) {
			if (check(i) < 0) {
				return false;
			}
		}
// check if digits can be placed in all units
			for (int m = 0; m < 27; m++) {
		for (int k = 1; k <= 9; k++) {
				if (check_rcb(m, k) < -1) {
					return false;
				}
			}
		}
		return true; // no contradictions
	}

// if there is only one cell left in a unit, set it
	boolean setLast(boolean recurs) {
		boolean isSet = false;
		Board tmp;
		if (recurs) {
			tmp = this;
		} else {
			tmp = new Board(false);
			tmp.copy(this);
		}
		for (int m = 0; m < 27; m++) {
			int last_i = 0;
			int allowed = 0;
// step through the nine cells of the unit
			for (int p = 0; p < 9; p++) {
				int i = rcb_sq[m][p];
				if (tmp.figure[i] == 0) {
					allowed++;
					last_i = i;
				}
			}
// if only one cell is not set
			if (allowed == 1) {
				int digit = tmp.check(last_i);
				if (digit > 0) {
//					printText(SETLAST, m, last_i);
					set(last_i, digit, true);
					if (recurs) {
						setLast(true);
						return true;
					}
					isSet = true;
				}
			} // if allowed
		} // for m
		return isSet;
	}

	boolean eliminateAdv() {
		Board tmp;
		if (auto) {
			tmp = this;
		} else {
			tmp = new Board(false);
			tmp.copy(this);
		}
		return eliminateAdv(tmp);
	}

	boolean eliminateAdv(Board tmp) {
		boolean changed = false;

// do each method once if manual solving,
// otherwise go back at every change

		if (Sudoku.inters.getState()) {
			changed = rcbVersus(tmp);
			if (auto && changed) {
				return changed;
			}
		}

		if (Sudoku.sets.getState()) {
			changed = changed | reduce_sets(tmp);
			if (auto && changed) {
				return changed;
			}
		}

		if (Sudoku.n_wing.getState()) {
			changed = changed | nWing(tmp);
			if (auto && changed) {
				return changed;
			}
		}

		if (Sudoku.xy_wings.getState()) {
			for (int n = 2; n < 8; n++) {
				changed = changed | xyzWing(tmp, n);
				if (auto && changed) {
					return changed;
				}
			}
		}

		/*
		if (Sudoku.xy_set.getState()) {
			changed = changed | xySet(tmp);
			if (auto && changed) {
				return changed;
			}
		}
		*/

		if (Sudoku.nishio.getState()) {
			changed = changed | nishio(tmp);
			if (auto && changed) {
				return changed;
			}
		}

// search for chains in cells with two candidates
// When two chains have been followed from one cell, checks are made to see if one
// of them gives a contradiction, and if both chains give the same result somewhere.
// A chain may bifurcate in each step.
		if (Sudoku.chain.getState()) {
			changed = changed | fChain(tmp, true);
			if (auto && changed) {
				return changed;
			}
		}

// search for more chains
// Here we use a wider definition and also use candidates with two locations
// within a unit (conjugate pair).

//		changed = changed | fChain(tmp, false);

		return changed;
	}

// combined method for xy- and xyz-wings (and higher)
// cand = 2 gives ordinary xy- and xyz-wings
	boolean xyzWing(Board tmp, int cand) {
		boolean changed = false;
		for (int z = 1; z <= 9; z++) {
			next_pivot:
			for (int index = 0; index < 81; index++) {
// find a pivot cell with 'cand' candidates except z
				if ((tmp.count_allowed(index) == cand && tmp.imposs[index][z])
					|| (tmp.count_allowed(index) == (cand + 1)
					&& !tmp.imposs[index][z])) {
// produce a list of candidates
					int[] cand_list = new int[cand];
					int k = 1;
					for (int c = 0; c < cand; c++) {
						while (tmp.imposs[index][k] || k == z) {
							k++;
						}
						cand_list[c] = k; // digit no. c+1 (except z)
						k++;
					}

// produce lists of cells with 'z' and one other candidate
					int[] count_i = new int[cand];
					int[][] i_list = new int[cand][21];
					for (int c = 0; c < cand; c++) {
						for (int i = 0; i < 81; i++) {
							if (same_rcb(i,
								index) && tmp.count_allowed(i) == 2
								&& !tmp.imposs[i][cand_list[c]]
								&& !tmp.imposs[i][z])
							{
								i_list[c][count_i[c]] = i;
								count_i[c]++;
							}
						}
// if there are no pairs with 'z'
						if (count_i[c] == 0) {
// go to next pivot cell (with new 'index')
							continue next_pivot;
						}
					}

					int[] counter = new int[cand];
					do {
// exclude cases where all cells are in the same unit
						if (!same_rcb(i_list, counter)) {
// eliminate candidates from target cells
							changed = changed | this.set_impossXYZ(tmp, index,
									  i_list, counter, z);
							if (auto && changed) {
								return changed;
							}
						}
// imitate a for loop with 'cand' levels
// for (counter[c]=0;counter[c]<count_i[c];counter[c]++)
						int c = cand - 1;
						counter[c]++;
						while (counter[c] >= count_i[c] && c > 0) {
							counter[c] = 0;
							c--;
							counter[c]++;
						}
					} while (counter[0] < count_i[0]);
				}
			} // for index
		} // for z
		return changed;
	} // xyzWing

// are i and j two different cells in the same unit?
	boolean same_rcb(int i, int j) {
		if (i == j) {
			return false;
		}
		for (int q = 0; q < 3; q++) {
// test if same row, column or box
			if (rcb_rev[i][q] == rcb_rev[j][q]) {
				return true;
			}
		}
		return false;
	}

// is 'i' in same unit as all cells in the list?
// If 'i' belongs to the list, false is returned.
	boolean same_rcb(int i, int[][] i_list, int[] counter) {
		for (int c = 0; c < i_list.length; c++) {
			if (!same_rcb(i, i_list[c][counter[c]])) {
				return false;
			}
		}
		return true;
	}

// are all cells in the list in the same unit?
	boolean same_rcb(int[][] i_list, int[] counter) {
		for (int c1 = 0; c1 < i_list.length; c1++) {
			for (int c2 = 0; c2 < c1; c2++) {
				if (!same_rcb(i_list[c1][counter[c1]], i_list[c2][counter[c2]])) {
					return false;
				}
			}
		}
		return true;
	}

// When we have found a possible xy/xyz wing (3 cells), wxy/wxyz wing
// (4 cells) etc, this method will search the entire board for candidates
// 'z' (target candidate) to eliminate
	boolean set_impossXYZ(Board tmp, int pivot, int[][] i_list, int[] counter,
		int z)
	{
		boolean changed = false;
int num_elim = 0;
int[] elimIndex = null;
int[] pincers = null;
		for (int i = 0; i < 81; i++) {
			if (figure[i] == 0 && !imposs[i][z] && i != pivot) {
// check that 'i' is in the same unit as all cells in the list
				boolean same;
				if (tmp.imposs[pivot][z]) { // note: tmp
					same = true;
				} else {
// xyz-wing, pivot cell must be included
					same = same_rcb(i, pivot);
				}
				same = same & same_rcb(i, i_list, counter);
				if (same) {
					if (this == Sudoku.main) {
if (num_elim == 0) {
	elimIndex = new int[5];
	pincers = new int[i_list.length];
	for (int c = 0; c < i_list.length; c++) {
		pincers[c] = i_list[c][counter[c]];
	}
}
elimIndex[num_elim] = i;
num_elim++;
					}
					this.imposs[i][z] = true;
					changed = true;
				}
			}
		}
		if (this == Sudoku.main) {
if (num_elim > 0) {
	Printing.xy_wing(tmp, z, pivot, pincers, elimIndex, num_elim);
}
		}
		return changed;
	}

// is 'i' in same unit as all cells with 'z'?
	boolean same_rcb_z(Board tmp, int i, int[] i_list, int z) {
		for (int c = 0; c < i_list.length; c++) {
			if (!tmp.imposs[i][z] && !same_rcb(i, i_list[c])) {
				return false;
			}
		}
		return true;
	}

	boolean nWing(Board tmp) {
		boolean changed = false;
// find 2-wing (X-wing), 3-wing (swordfish) and 4-wing for every digit 'k'
		for (int n = 2; n <= 4; n++) {
		  for (int k = 1; k <= 9; k++) {
// count the number of set k (in boxes)
			int numSet = 0;
			for (int m = 0; m < 9; m++) {
				if (tmp.isSet[m][k]) {
					numSet++;
				}
			}
			if (2 * n <= (9 - numSet)) {
				changed = changed | nWing(k, n, 9, tmp); // n-wing for 'k' on rows
				if (auto && changed) {
					return changed;
				}
			}
			if (2 * n < (9 - numSet)) {
				changed = changed | nWing(k, n, 18, tmp); // n-wing for 'k' on columns
				if (auto && changed) {
					return changed;
				}
			}
		  }
		}
		return changed;
	}

	boolean nWing(int k, int numRC, int start_m, Board tmp) {
		boolean changed = false;
		int[] counter = new int[numRC];
		counter[0] = start_m;
		int cnt_m = 0;
		boolean[][] bits = new boolean[numRC][9];

// imitate a for loop with numRC levels
// for (counter[cnt_m] = counter[cnt_m - 1] + 1;
//	counter[cnt_m] < 9 - (); counter[cnt_m]++)

		do {
// count positions for 'k' in this row/column
			int allowed = tmp.count_pos(counter[cnt_m], k, bits[cnt_m]);
			if (allowed >= 2 && allowed <= numRC) {
				if (cnt_m == 0) { // first row/column
// match at least one more row/column
					cnt_m++;
					counter[cnt_m] = counter[cnt_m - 1] + 1;
				} else {
// merge positions from multiple units
					int pos = 0;
					for (int p = 0; p < 9; p++) {
// set the bit if it is set in any of the studied rows/columns
						bits[cnt_m][p] |= bits[cnt_m - 1][p];
						if (bits[cnt_m][p]) {
							pos++;
						}
					}
					if (pos > numRC) {
// too many positions, test next row/column
						counter[cnt_m]++;
// bug fixed 2008-02-01
//						while (counter[cnt_m] > (9 - numRC + cnt_m)
						while (counter[cnt_m] > (9 + start_m - numRC + cnt_m)
							   && cnt_m > 0)
						{
							cnt_m--;
							counter[cnt_m]++;
						}
					} else if (cnt_m + 1 < numRC) {
// we must match more cells
						cnt_m++;
						counter[cnt_m] = counter[cnt_m - 1] + 1;
					} else {
// a wing with equal number of rows/columns and positions
						int cnt_rc = 0;
int num_elim = 0;
int[] elimIndex = null;
						for (int m = start_m; m < start_m + 9; m++) {
//	remove the digit in all other rows/columns
							if ((cnt_rc >= numRC) || (m != counter[cnt_rc])) {
								for (int p = 0; p < 9; p++) {
									if (bits[cnt_m][p]) {
										int i = rcb_sq[m][p];
										if (figure[i] == 0 && !imposs[i][k]) {
											this.imposs[i][k] = true;
											changed = true;
											if (this == Sudoku.main) {
if (num_elim == 0) {
	elimIndex = new int[20];
}
elimIndex[num_elim] = i;
num_elim++;
											}
										}
									}
								} // for p
							} else { // a row/column that is part of the wing
								cnt_rc++;
							}
						}
						if (this == Sudoku.main) {
if (num_elim > 0) {
	Printing.n_wing(k, counter, elimIndex, num_elim);
}
						}
// go back to search for a new wing
						cnt_m = 0;
						counter[0]++;
					} // if pos > numRC
				}
			} else { // if allowed
// too few or too many positions; go on to next row/column
				counter[cnt_m]++;
				while (counter[cnt_m] > (9 + start_m - numRC + cnt_m)
					   && cnt_m > 0)
				{
					cnt_m--;
					counter[cnt_m]++;
				}
			}
		} while (counter[0] <= 9 + start_m - numRC);
		return changed;
	}

	boolean rcbVersus(Board tmp) {
		boolean changed = false;
		for (int k = 1; k <= 9; k++) {
			changed = changed | rcbVersus_k(tmp, k);
		}
		return changed;
	}

// intersection for digit 'k'
	boolean rcbVersus_k(Board tmp, int k) {
		boolean changed = false;
		for (int m = 0; m < 27; m++) {
			if (!tmp.isSet[m][k]) { // if digit is not set in this unit
				boolean same1 = true, same2 = true;
				boolean first = true;
				int subset1 = 0, subset2 = 0;
				int last_i = 0;
// step through the nine cells
				for (int p = 0; p < 9; p++) {
					int i = rcb_sq[m][p];
// if 'k' is a candidate in cell 'i'
					if (tmp.figure[i] == 0 && !tmp.imposs[i][k]) {
						if (first) {
							first = false;
						} else {
// try if the candidate is in the same part of the unit as other candidates
							if (subset1 != p / 3) {
								same1 = false;
							}
							if (subset2 != p % 3) {
								same2 = false;
							}
						}
						subset1 = p / 3;
						subset2 = p % 3; // needed only for box versus column
						last_i = i;
					}
				}
				if (m < 9) {
// box versus row
					if (same1 & !first) {
// if all candidates are in the same third of the unit
						int m0 = rcb_rev[last_i][1]; // row number
int num_elim = 0;
int[] elimIndex = null;
						for (int p = 0; p < 9; p++) {
// block one box, and remove 'k' from the other two
							if (m % 3 != p / 3) {
								int i = rcb_sq[m0][p];
								if (figure[i] == 0 && !imposs[i][k]) {
									this.imposs[i][k] = true;
									changed = true;
									if (this == Sudoku.main) {
if (num_elim == 0) {
	elimIndex = new int[6];
}
elimIndex[num_elim] = i;
num_elim++;
									}
								}
							}
						} // for p
						if (this == Sudoku.main) {
if (num_elim > 0) {
	Printing.intersection(k, m, m0, elimIndex, num_elim);
}
						}
					}
// box versus column
					if (same2 & !first) {
						int m0 = rcb_rev[last_i][2]; // column number
int num_elim = 0;
int[] elimIndex = null;
						for (int p = 0; p < 9; p++) {
// block one box, and remove 'k' from the other two
							if (m / 3 != p / 3) {
								int i = rcb_sq[m0][p];
								if (figure[i] == 0 && !imposs[i][k]) {
									this.imposs[i][k] = true;
									changed = true;
									if (this == Sudoku.main) {
if (num_elim == 0) {
	elimIndex = new int[6];
}
elimIndex[num_elim] = i;
num_elim++;
									}
								}
							}
						} // for p
						if (this == Sudoku.main) {
if (num_elim > 0) {
	Printing.intersection(k, m, m0, elimIndex, num_elim);
}
						}
					}
				} else if (m < 18) {
// row versus box
					if (same1 & !first) {

						int m0 = rcb_rev[last_i][0]; // box number
int num_elim = 0;
int[] elimIndex = null;
						for (int p = 0; p < 9; p++) {
// block one row, and remove 'k' from the other two
							if (m % 3 != p / 3) {
								int i = rcb_sq[m0][p];
								if (figure[i] == 0 && !imposs[i][k]) {
									this.imposs[i][k] = true;
									changed = true;
									if (this == Sudoku.main) {
if (num_elim == 0) {
	elimIndex = new int[6];
}
elimIndex[num_elim] = i;
num_elim++;
									}
								}
							}
						} // for p
						if (this == Sudoku.main) {
if (num_elim > 0) {
	Printing.intersection(k, m, m0, elimIndex, num_elim);
}
						}
					}
				} else {
// column versus box
					if (same1 & !first) {

						int m0 = rcb_rev[last_i][0]; // box number
int num_elim = 0;
int[] elimIndex = null;
						for (int p = 0; p < 9; p++) {
// block one box, and remove 'k' from the other two
							if (m % 3 != p % 3) {
								int i = rcb_sq[m0][p];
								if (figure[i] == 0 && !imposs[i][k]) {
									this.imposs[i][k] = true;
									changed = true;
									if (this == Sudoku.main) {
if (num_elim == 0) {
	elimIndex = new int[6];
}
elimIndex[num_elim] = i;
num_elim++;
									}
								}
							}
						} // for p
						if (this == Sudoku.main) {
if (num_elim > 0) {
	Printing.intersection(k, m, m0, elimIndex, num_elim);
}
						}
					}
				} // if m
			}
		} // for m
		return changed;
	}

// count free cells in one unit
	int count_free(int m) {
		int free = 0;
		for (int p = 0; p < 9; p++) {
			int i = rcb_sq[m][p];
			if (figure[i] == 0) {
				free++;
			}
		}
		return free;
	}

// count candidates in one cell
	int count_allowed(int i) {
		if (figure[i] > 0) {
			return 0;
		}
		int allowed = 0;
		for (int k = 1; k <= 9; k++) {
			if (!imposs[i][k]) {
				allowed++;
			}
		}
		return allowed;
	}

	int count_pos(int m, int k, boolean[] pos) {
		if (isSet[m][k]) {
			return 0;
		}
// count positions in unit
		int allowed = 0;
		for (int p = 0; p < 9; p++) {
			int i = rcb_sq[m][p];
// if 'k' is a candidate in cell 'i'
			if (figure[i] == 0 && !imposs[i][k]) {
				pos[p] = true;
				allowed++;
			} else {
				pos[p] = false;
			}
		}
		return allowed;
	}

	int count_pos(int m, int k) {
		if (isSet[m][k]) {
			return 0;
		}
		int allowed = 0;
		for (int p = 0; p < 9; p++) {
			int i = rcb_sq[m][p];
			if (figure[i] == 0 && !imposs[i][k]) {
				allowed++;
			}
		}
		return allowed;
	}

	boolean reduce_sets(Board tmp) {
		boolean changed = false;
		for (int m = 0; m < 27; m++) {
// Find locked sets with n digits: n = 2, 3, ..., free-2.
// This means naked pair, naked triple, ..., hidden pair.
			int free = tmp.count_free(m);
			for (int n = 2; n <= free - 2; n++) {
				changed = changed | reduce_sets(m, n, tmp);
				if (auto && changed) {
					return changed;
				}
			}
		}
		return changed;
	}

// reduce unit 'm' for locked sets with 'numFig' digits
	boolean reduce_sets(int m, int numFig, Board tmp) {
		boolean changed = false;
		int[] counter = new int[numFig];
		int cnt_index = 0;
		boolean[][] bits = new boolean[numFig][10];

// imitate a for loop with numFig levels
// for (counter[cnt_index] = counter[cnt_index - 1] + 1;
//	  counter[cnt_index] < 9 - (); counter[cnt_index]++)
		do {
			int i = rcb_sq[m][counter[cnt_index]];
			int allowed = tmp.count_allowed(i);
			if (allowed >= 2 && allowed <= numFig) {
				if (cnt_index == 0) { // first cell
// set bits for candidates
					for (int k = 1; k <= 9; k++) {
						bits[0][k] = !tmp.imposs[i][k];
					}
// match at least one more cell
					cnt_index++;
					counter[cnt_index] = counter[cnt_index - 1] + 1;
				} else {
// merge lists from multiple cells
					int candi = 0;
					for (int k = 1; k <= 9; k++) {
// set the bit if the corresponding candidate is allowed in any of the studied cells
						bits[cnt_index][k] = !tmp.imposs[i][k];
						bits[cnt_index][k] |= bits[cnt_index - 1][k];
						if (bits[cnt_index][k]) {
							candi++; // count candidates
						}
					}
					if (candi > numFig) {
// too many candidates, go to next cell
						counter[cnt_index]++;
						while (counter[cnt_index] > (9 - numFig + cnt_index)
							   && cnt_index > 0)
						{
							cnt_index--;
							counter[cnt_index]++;
						}
					} else if (cnt_index + 1 < numFig) {
// we must match more cells
						cnt_index++;
						counter[cnt_index] = counter[cnt_index - 1] + 1;
					} else {
// a matching set with equal number of cells and digits
						int cnt_i = 0;
						int num_elim = 0;
						String digits = "";
						int[] elimIndex = null;
						int[] elimDigit = null;
						for (int pos = 0; pos < 9; pos++) {
// remove the matching digits in all other cells
							if ((cnt_i >= numFig) || (pos != counter[cnt_i])) {
								for (int k = 1; k <= 9; k++) {
									if (bits[cnt_index][k]) {
	int indx = rcb_sq[m][pos];
	if (figure[indx] == 0 && !imposs[indx][k]) {
		this.imposs[indx][k] = true;
		changed = true;
		if (this == Sudoku.main) {
			if (num_elim == 0) {
				elimIndex = new int[20];
				elimDigit = new int[20];
				for (int k0 = 1; k0 <= 9; k0++) {
					if (bits[cnt_index][k0]) {
						digits += k0;
					}
				}
			}
			elimIndex[num_elim] = indx;
			elimDigit[num_elim] = k;
			num_elim++;
		}
	}
									}
								}
							} else {
								cnt_i++;
							}
						}
if (num_elim > 0) {
	Printing.sets(digits, m, elimIndex, elimDigit, num_elim);
}

// go back and look for next set
						cnt_index = 0;
						counter[0]++;
					}
				}
			} else { // if allowed
// too few or too many candidates, go to next cell
				counter[cnt_index]++;
				while (counter[cnt_index] > (9 - numFig + cnt_index)
					   && cnt_index > 0)
				{
					cnt_index--;
					counter[cnt_index]++;
				}
			}
		} while (counter[0] <= 9 - numFig);
		return changed;
	} // reduce_sets

	boolean nishio(Board tmp) {
		boolean changed = false;
		Board test = new Board(false);  // create a new variable because 'tmp'
										// must be intact
		for (int k = 1; k <= 9; k++) {
int num_elim = 0;
int[] elimIndex = null;
			for (int i = 0; i < 81; i++) {
				// if 'k' is a candidate in cell 'i'
				if (this.figure[i] == 0 && !this.imposs[i][k]) {
					test.copy(tmp);
					test.auto = false;  // we do the solving ourselves and only
										// study one digit at a time
					if (!test.set_nishio(i, k)) { // try digit 'k'
						this.imposs[i][k] = true;
						if (this == Sudoku.main) {
if (num_elim == 0) {
	elimIndex = new int[72];
}
elimIndex[num_elim] = i;
num_elim++;
						}
						changed = true;
						if (auto && changed) {
							if (this == Sudoku.main) {
if (num_elim > 0) {
	Printing.nishio(k, elimIndex, num_elim);
}
							}
							return changed;
						}
					}
				}
			}
			if (this == Sudoku.main) {
if (num_elim > 0) {
	Printing.nishio(k, elimIndex, num_elim);
}
			}
		}
		return changed;
	} // nishio

	boolean set_nishio(int i, int k) {
		set(i, k); // reduce in box, row and column
		for (int m = 0; m < 27; m++) {
			int single = check_rcb(m, k);
// if there is only one possible cell
			if (single >= 0) {
				return set_nishio(single, k); // set digit recursively
			}
// if the digit can't be placed despite that it is not set in this unit
			if (single < -1) {
				return false;
			}
		}
// try to reduce further
		if (rcbVersus_k(this, k)) {
			set_nishio(i, k); // recursive check
		}

		return true; // no contradiction
	}

	static Board chainX = new Board(false), chainY = new Board(false);
	static boolean[] pairs = new boolean[81];

	boolean fChain(Board tmp, boolean pair) {
		boolean changed = false;
// find all bi-value cells
		for (int index = 0; index < 81; index++) {
			pairs[index] = (tmp.count_allowed(index) == 2);
		}
		next_index:
		for (int index = 0; index < 81; index++) {
			if (this.figure[index] == 0 && pairs[index]
				&& (this.count_allowed(index) == 2))
			{
				int k = 1;
				while (tmp.imposs[index][k]) {
					k++;
				}
				int x = k; // first candidate
				k++;
				while (tmp.imposs[index][k]) {
					k++;
				}
				int y = k; // second candidate

// set the first link of the chain and do the rest recursively
				chainX.copy(tmp);
				chainX.auto = false; // only basic elimination
				if (pair) {
					chainX.setChainPair(pairs, index, x);
				}

				chainY.copy(tmp);
				chainY.auto = false;
				if (pair) {
					chainY.setChainPair(pairs, index, y);
				}

				boolean cont = false;
				if (!chainX.checkBoard()) {
// x gives a contradiction
					if (!this.imposs[index][x]) {
						this.imposs[index][x] = true;
						changed = true;
						if (this == Sudoku.main) {
							Printing.chain1(index, x);
						}
					}
// When automatic solving this = tmp, so that 'tmp' may change. This means
// we can't use pairs[index] again, and interrupt instead.
					if (this.auto) {
						return changed;
					} else {
						cont = true;
					}
				}
				if (!chainY.checkBoard()) {
// y gives a contradiction
					if (!this.imposs[index][y]) {
						this.imposs[index][y] = true;
						changed = true;
						if (this == Sudoku.main) {
							Printing.chain1(index, y);
						}
					}
					if (this.auto) {
						return changed;
					} else {
						cont = true;
					}
				}
				if (cont) continue next_index;

// check which changes both x and y lead to
				for (int i = 0; i < 81; i++) {
// if the cell isn't already occupied
					if (tmp.figure[i] == 0) {
// if the cell has been set by a naked single in both cases,
// we count this as eliminations (chain2 below)
						boolean allImposs = (chainX.count_allowed(i) <= 1)
							& (chainY.count_allowed(i) <= 1);
						if ((chainX.figure[i] > 0)
							&& (chainX.figure[i] == chainY.figure[i])
							&& !allImposs)
						{
// both x and y lead to setting the same cell
							if (this.figure[i] == 0) {
								if (this == Sudoku.main) {
									Printing.chain3(this, index, i, chainX.figure[i]);
								}
								this.setAndReduce(i, chainX.figure[i]);
								changed = true;
								if (this.auto) {
									return changed;
								}
							}
						} else {
							for (k = 1; k <= 9; k++) {
								if (!tmp.imposs[i][k]) {
// 'k' may become impossible either by elimination or through
// the setting of another digit
									boolean impossX = (chainX.figure[i] == 0
	  && chainX.imposs[i][k]) || (chainX.figure[i] > 0 && chainX.figure[i] != k);
									boolean impossY = (chainY.figure[i] == 0
	  && chainY.imposs[i][k]) || (chainY.figure[i] > 0 && chainY.figure[i] != k);
									if (impossX && impossY) {
// the same digit is eliminated
	if (!this.imposs[i][k]) {
		this.imposs[i][k] = true;
		changed = true;
		if (this == Sudoku.main) {
			Printing.chain2(this, index, i, k);
		}
		if (this.auto) {
			return changed;
		}
	}
									}
								}
							} // for k
						}
					}
				} // for i
			}
		} // for index
		return changed;
	}

	void setChainPair(boolean[] pairs, int index, int x) {
		set(index, x);
// search for bi-value cells in the same unit as 'index'
		for (int i = 0; i < 81; i++) {
// if the cell originally contained a pair and is not already set
			if (pairs[i] && figure[i] == 0 && same_rcb(i, index)) {
				int single = check(i);
				if (single > 0) {
// set digit recursively
					setChainPair(pairs, i, single);
				}
			}

		}
	}


// use the two candidate feature to include or exclude
		boolean[][] two_cand() {
// only include cells with two candidates (bi-value) and digits
// which are candidates in exactly two cells in one unit (bi-location)
			Board cand = new Board(false);
			cand.copy(this);

// set all cells to zero except those with two candidates
			for (int i = 0; i < 81; i++) {
				if (figure[i] == 0 && count_allowed(i) != 2) {
					cand.figure[i] = -1;
					for (int k = 1; k <= 9; k++) {
						cand.imposs[i][k] = true;
					}
				}
			} // for i

// make digits with two candidate cells possible
			for (int k = 1; k <= 9; k++) {
				for (int m = 0; m < 27; m++) {
					if (count_pos(m, k) == 2) {
						for (int p = 0; p < 9; p++) {
							int i = rcb_sq[m][p];
							if (figure[i] == 0 && !imposs[i][k]) {
								cand.figure[i] = 0;
								cand.imposs[i][k] = false;
							}
						}
					}
				}
			} // for k
System.out.println(" -- two --");
// print cells with two alternatives
	for (int i = 0; i < 81; i++) {
		for (int n = 1; n <= 9; n++) {
			if (cand.figure[i] == 0 && !cand.imposs[i][n]) {
System.out.print(sq_str(i) + ": " + n + "  ");
	}}}
System.out.println("");
			return cand.imposs;
		} // two_cand

	boolean tryAllOnce(boolean deep, boolean two, boolean[][] two_imposs,
		boolean[][] valid)
	{
		boolean changed = false;
		int tried = 0;
		int eliminated = 0;
		int solved = 0;

		if (tmp[0] == null) {
			tmp[0] = new Board(true);
		}
		tmp[0].copy(this);
		tmp[0].auto = true; // make sure solving is done

		autoChange:

		for (int i = 0; i < 81; i++) {
			for (int n = 1; n <= 9; n++) {
				if (!Sudoku.running) {
					Printing.interrupt();
					return false; // break on user's request
				}

				boolean try_cand = (this.figure[i] == 0);
				if (two) {
					try_cand &= !two_imposs[i][n];
				} else {
					try_cand &= (two_imposs[i][n] && !this.imposs[i][n]);
				}
				if (try_cand) {
					tried++; // count number of tried candidates
					if (tmp[1] == null) {
						tmp[1] = new Board(true);
					}
					tmp[1].copy(tmp[0]);
					boolean res = true;
					if (deep) {
// if we already know that the candidate is part of a valid solution,
// we don't need to try it again
						if (!valid[i][n]) {
							res = tmp[1].setDeep(i, n, 1, valid);
						}
					} else {
						res = tmp[1].set(i, n);
					}
					if (!res) { // contradiction
						eliminated++; // count eliminations
Printing.printBoth("elim " + sq_str(i) + ": " + n + "  ");
						changed = true;
// remove digit from 'main'
						this.imposs[i][n] = true;
						if (auto) {
							if (two) {
								break autoChange;
							}
// 2008-07-22
// new in version 4.4
// if the elimination leeds to progress either by basic or advanced
// techniques, break and start over
							boolean ch = checkSolve();
							if (!ch) {
// use a copy to avoid printing
								Board tmp_adv = new Board(true);
								tmp_adv.copy(this);
								ch = tmp_adv.eliminateAdv();
							}
							if (ch) {
								break autoChange;
							}
						}
					} else if (!deep) { // if !res
						if (tmp[1].solved()) {
							solved++; // count how many leed to solution
if (Printing.lang == 0)
Printing.printBoth("sol " + sq_str(i) + ": " + n + "  ");
else
Printing.printBoth("lösn " + sq_str(i) + ": " + n + "  ");
						}
					}
				}
			} // for n
		} // for i
// break autoChange jumps here

		if (changed || solved > 0) {
			Printing.printlnBoth("");
		}
		Printing.tried(deep, tried, eliminated, solved);

		return changed;
	}

// recursive method for trying if a candidate can be part of a valid solution
	boolean setDeep(int index, int number, int depth, boolean[][] valid) {
		if (!tmp[depth].set(index, number)) {
			return false;
		}

		for (int i = 0; i < 81; i++) {
			if (tmp[depth].figure[i] == 0) {
				for (int n = 1; n <= 9; n++) {
					if (!tmp[depth].imposs[i][n]) {
						if (tmp[depth + 1] == null) {
							tmp[depth + 1] = new Board(true);
						}
						tmp[depth + 1].copy(tmp[depth]);
						if (setDeep(i, n, depth + 1, valid)) {
							for (int i0 = 0; i0 < 81; i0++) {
// set the digit as part of a valid solution
								valid[i0][tmp[depth + 1].figure[i]] = true;
							}
// at least one candidate leeds to solution
							return true;
						}
					}
				} // for n
// no valid candidate in this cell
				return false;
			}
		}
		return true;
	}

	boolean solved() {
		for (int i = 0; i < 81; i++) {
			if (figure[i] == 0) {
				return false;
			}
		}
		return true;
	}

// print the sudoku board to both text area and system window
	void print() {
		String outStr = "\n" + printOneLine() + printStr();
		Sudoku.tArea.append(outStr);
		System.out.print(outStr);
	}

// print the board on one line
	String printOneLine() {
		String blank = ".";
//		String blank = "0";
//		String blank = "_";
		String newLine = "";
//		String newLine = "+";

		String str = "";
		for (int y = 0; y < 9; y++) {
			for (int x = 0; x < 9; x++) {
				if (figure[9 * y + x] > 0) {
					str += figure[9 * y + x];
				} else {
					str += blank;
				}
			}
			if (y < 8)
				str += newLine;
		}
		str += "\n";
		return str;
	}

// print the board in the standard rectangular form
// (only solved and given cells)
	String printStr() {
		String str = "";
//if(true) return str;

		for (int y = 0; y < 9; y++) {
			if (y % 3 == 0) {
				str += "+-------+-------+-------+\n"; // between box rows
			}
			str += "| "; // start new row
			for (int x = 0; x < 9; x++) {
				if (figure[9 * y + x] > 0) {
					str += figure[9 * y + x] + " ";
				} else {
					str += ". ";
				}
				if (x % 3 == 2) {
					str += "| "; // between boxes
				}
			}
			str += "\n";
		}
		str += "+-------+-------+-------+\n";
		return str;
	}

// print the sudoku board including candidates
	void printCand() {
		String outStr = "\n" + printOneLine() + boardCandStr();
		Sudoku.tArea.append(outStr);
		System.out.print(outStr);
	}

// return the whole board including candidates
	String boardCandStr() {
//		String beforeGiven = "<";
		String beforeGiven = " ";
//		String afterGiven = ">";
		String afterGiven = "";

		int minWidth = 4;

		String str = "";

// calculate column widths
		int[] colWidth = new int[9];
		for (int x = 0; x < 9; x++) {
			int max = minWidth;
			for (int y = 0; y < 9; y++) {
				int width = cand_str(9 * y + x).length();
				if (width > max) {
					max = width;
				}
			}
			colWidth[x] = max;
		}

// horizontal line between boxes
		String delim = "";
		for (int x = 0; x < 9; x++) {
			if (x % 3 == 0) {
				delim += "+-";
			}
			for (int w = 0; w < colWidth[x] + 1; w++) {
				delim += "-";
			}
		}
		delim += "+\n";

		for (int y = 0; y < 9; y++) {
			if (y % 3 == 0) {
				str += delim;
			}
			for (int x = 0; x < 9; x++) {
				if (x % 3 == 0) {
					str += "| "; // between boxes
				}
				String cStr;
				if (figure[9 * y + x] > 0) {
					cStr = beforeGiven + figure[9 * y + x] + afterGiven;
				} else {
					cStr = cand_str(9 * y + x);
				}
				str += cStr;
// fill with blanks
				for (int w = cStr.length(); w < colWidth[x] + 1; w++) {
					str += " ";
				}
			}
// end the row
			str += "|\n";
		}
		str += delim;

		return str;
	}

	void printText(int text, int rcb, int square) {
		String rcbText = (rcb<9) ? "box " : ((rcb<18) ? "row " : "column ");
		rcbText += (rcb % 9);
		switch (text) {
		  case SETLAST:
			System.out.print("\nLast cell in " + rcbText + ": ");
		}
	}

	String sq_str(int index) {
		return ROW_STR[index / 9] + COL_STR[index % 9];
	}

	String cand_str(int index) {
		String str = "";
		for (int k = 1; k <= 9; k++) {
// if 'k' is a candidate in the cell
			if (this.figure[index] == 0 && !this.imposs[index][k]) {
				str += k;
			}
		}
		return str;
	}

} // Board

interface Constants {
	static final int SETLAST = 0;

// languages
	static final String[] LANGUAGE	= {"Language", "Språk "};
	static final String[] ENGLISH	= {"English", "engelska"};
	static final String[] SWEDISH	= {"Swedish", "svenska"};

	static final String[] ROW_STR	=
		{"r1", "r2", "r3", "r4", "r5", "r6", "r7", "r8", "r9"};
	static final String[] COL_STR	=
		{"c1", "c2", "c3", "c4", "c5", "c6", "c7", "c8", "c9"};

	static final String[] DIGITS	= {"digits", "siffror"};
	static final String[] MATCH		=
		{"matching " + DIGITS[0] + " in", "matchande " + DIGITS[1] + " i"};
	static final String[] ROW		= {"row", "rad"};
	static final String[] ROWs		= {"rows", "rader"};
	static final String[] COLUMN	= {"column", "kolumn"};
	static final String[] COLUMNs	= {"columns", "kolumner"};
	static final String[] BOX		= {"box", "box"};
	static final String[] BOXes		= {"boxes", "boxar"};
	static final String[] ELIM		= {"eliminate", "eliminerar"};
	static final String[] ELIMs		= {"eliminates", "eliminerar"};
	static final String[] IN		= {"in", "i"};
	static final String[] INTERS	= {"intersection for", "snitt för"};
	static final String[] VERSUS	= {"versus", "mot"};
	static final String[] N_WING	= {"wing for", "vinge för"};
	static final String[] NISHIO	= {"nishio", "nishio"};
	static final String[] XY_WING	= {"xy-wing on", "xy-vinge på"};
	static final String[] XYZ_WING	= {"xyz-wing on", "xyz-vinge på"};
	static final String[] CHAIN_F	= {"chain from", "kedja från"};
	static final String[] CHAIN		= {"chain", "kedja"};
	static final String[] SET		= {"set", "sätt"};
	static final String[] SETs		= {"sets", "sätter"};

	static final String[] CONTRA	= {"contradiction testing", "motsägelsetest"};
	static final String[] TWO		= {"two", "två"};
	static final String[] ARIADNE	= {"Ariadne's thread", "djuptest"};

	static final String[] TRIED		= {"Tried", "Prövade"};
	static final String[] ELIMIN	= {"Eliminated", "Eliminerade"};
	static final String[] SOLUTION	= {"Leed to solution", "Leder till lösning"};
	static final String[] TIME		= {"Time", "Tid"};

	static final String[] INTERRUPT = {"interruption during candidate testing",
										"avbrott under kandidatprövning"};
	static final String[] P_POSI	= {"Printing position", "Utskriftsposition"};
	static final String[] P_INTERRUPT = {"Printing interrupted", "Utskrift avbruten"};
	static final String[] SAVE_FILE = {"Save to file", "Spara i fil"};

// checkbox labels
	static final String[] AUTO		= {"Automatic solving", "Lös automatiskt"};
	static final String[] ELIMINATION = {"Elimination", "Eliminering"};
	static final String[] BASIC		= {"Basic", "Enkel"};
	static final String[] ADVANCED	= {"Advanced", "Avancerad"};
	static final String[] COMPLETE	= {"Complete", "Fullständig"};

// advanced choises
	static final String[] INTERS_str	= {"intersec.", "snitt"};
	static final String[] SETS_str		= {"locked set", "m. mängd"};
	static final String[] N_WING_str	= {"n-wing", "n-vinge"};
	static final String[] XY_WINGS_str	= {"xy wings", "xy-vingar"};
	static final String[] XY_SET_str	= {"xy set", "xy-mängd"};
	static final String[] NISHIO_str	= {"nishio", "nishio"};
	static final String[] CHAIN_str		= {"chains", "kedjor"};

// candidates
	static final String[] CANDIDATES	= {"Candidates", "Kandidater"};
	static final String[] SQUARES		= {"Squares", "Kvadrater"};
	static final String[] FIGURES		= {"Small " + DIGITS[0], "Små " + DIGITS[1]};

// button labels
	static final String[] SOLVE		= {"Solve", "Lös"};
	static final String[] CLEAR		= {"Clear", "Rensa"};
	static final String[] UNDO		= {"Undo", "Ångra"};
	static final String[] REDO		= {"Redo", "Gör om"};
	static final String[] PERMUTE	= {"Permute", "Permutera"};
	static final String[] PRINT		= {"Print", "Skriv ut"};
	static final String[] PRINT_LATER = {"Print later", "Skriv senare"};
	static final String[] SAVE		= {"Save", "Spara"};
	static final String[] LOAD		= {"Load", "Läs in"};
	static final String[] ARCHIVE	= {"Archive", "Arkiv"};

	static final String[] GIVEN		= {"Given", "Givna"};
	static final String[] SOLVED	= {"Solved", "Lösta"};
	static final String[] CANDI		= {"Candidates", "Kandidater"};
	static final String[] gIVEN		= {"given", "givna"};
	static final String[] sOLVED	= {"solved", "lösta"};

	static final String[] LOAD_WINDOW = {"Load window \n ", "Läs in-fönster \n "};
}

// This class handles most of the printing:
// writing to console, writing to text window.
// Reading from and writing to files is done in Sudoku.LoadListener
// and Sudoku.SaveListener,
// drawing on screen in Sudoku.paint() and
// printing on paper in Sudoku.PrintListener.
class Printing implements Constants {
	static int lang = 0; // English
	static int previousRows = 0;

	static void printBoth(String str) {
		System.out.print(str);
		int charsInRow = Sudoku.tArea.getCaretPosition() - previousRows;
		if ((charsInRow + str.length()) > Sudoku.tArea.getColumns()) {
			Sudoku.tArea.append("\n  ");
			previousRows = Sudoku.tArea.getCaretPosition();
		}
		Sudoku.tArea.append(str);
	}

	static void printlnBoth(String str) {
		printBoth(str + "\n");
		previousRows = Sudoku.tArea.getCaretPosition();
	}

	static void clearArea() {
		Sudoku.tArea.setText("");
	}

// return the label of one cell
	static String cell_str(int index) {
		return ROW_STR[index / 9] + COL_STR[index % 9];
	}

// return the candidates of one cell
	static String cand_str(Board b, int index) {
		String str = "";
		if (b.figure[index] == 0)
			for (int k = 1; k <= 9; k++) {
// if 'k' is a candidate in the cell
				if (!b.imposs[index][k]) {
					str += k;
				}
			}
		return str;
	}

// state variables printed at the top
	static String solvedCand(int numUser, int numSolved, int numCand) {
		return GIVEN[lang] + ": " + numUser + "   " + SOLVED[lang] + ": " + numSolved + "   " + CANDI[lang] + ": " + numCand;
	}

// set the cell to a specified digit
	static void set_digit(int cell, int digit) {
		printBoth(SET[lang] + " " + cell_str(cell) + "=" + digit + "  ");
	}

// print "box", "row" or "column" together with its number
	static void rcb(int m) {
		if (m < 9) {
			printBoth(BOX[lang] + " " + (m + 1));
		} else if (m < 18) {
			printBoth(ROW[lang] + " " + (m + 1 - 9));
		} else {
			printBoth(COLUMN[lang] + " " + (m + 1 - 18));
		}
	}

	static void sets(String digits, int m, int[] elimCell, int[] elimDigit, int numElim) {
		printBoth(digits.length() + " " + MATCH[lang] + " ");
		rcb(m);
		printBoth(" (" + digits + ") " + ELIM[lang] + " ");
		for (int n = 0; n < numElim; n++) {
			if (n < numElim - 1)
				printBoth(elimDigit[n] + " " + IN[lang] + " " + cell_str(elimCell[n]) + ", ");
			else // last elimination
				printBoth(elimDigit[n] + " " + IN[lang] + " " + cell_str(elimCell[n]));
		}
		printlnBoth("");
	}

	static void intersection(int digit, int m0, int m1, int[] elimCell, int numElim) {
		printBoth(INTERS[lang] + " " +  + digit + ": ");
		rcb(m0);
		printBoth(" " + VERSUS[lang] + " " );
		rcb(m1);
		printBoth(" ");
		printBoth(ELIMs[lang] + " " + digit + " " + IN[lang] + " ");
		for (int n = 0; n < numElim; n++) {
			if (n < numElim - 1)
				printBoth(cell_str(elimCell[n]) + ", ");
			else // last elimination
				printBoth(cell_str(elimCell[n]));
		}
		printlnBoth("");
	}

	static void n_wing(int digit, int[] m, int[] elimCell, int numElim) {
		int n = m.length;
		printBoth(n + "-" + N_WING[lang] + " " + digit + " ");
		printBoth("(");
		for (int i = 0; i < n-1; i++) {
			rcb(m[i]);
			printBoth(" ");
		}
		rcb(m[n-1]);
		printBoth(") ");

		printBoth(ELIMs[lang] + " " + digit + " " + IN[lang] + " ");
		for (int i = 0; i < numElim; i++) {
			if (i < numElim - 1)
				printBoth(cell_str(elimCell[i]) + ", ");
			else // last elimination
				printBoth(cell_str(elimCell[i]));
		}
		printlnBoth("");
	}

	static void nishio(int digit, int[] elimCell, int numElim) {
		printBoth(NISHIO[lang] + " " + ELIMs[lang] + " " + digit + " " + IN[lang] + " ");
		for (int i = 0; i < numElim; i++) {
			if (i < numElim - 1)
				printBoth(cell_str(elimCell[i]) + ", ");
			else // last elimination
				printBoth(cell_str(elimCell[i]));
		}
		printlnBoth("");
	}

	static void xy_wing(Board b, int z, int pivot, int[] pincers,
		int[] elimCell, int numElim)
	{
		if (pincers.length > 2) { // wxy/wxyz or larger
			printBoth("*");
		}

		if (b.imposs[pivot][z]) {
			printBoth(XY_WING[lang] + " ");
		} else {
			printBoth(XYZ_WING[lang] + " ");
		}
		printBoth(cell_str(pivot) + "=" + cand_str(b, pivot) + ", ");
		for (int p = 0; p < pincers.length; p++) {
			if (p < pincers.length - 1)
				printBoth(cell_str(pincers[p]) + "=" +
					cand_str(b, pincers[p]) + ", ");
			else // last pincer cell
				printBoth(cell_str(pincers[p]) + "=" +
					cand_str(b, pincers[p]) + " ");
		}

		printBoth(ELIMs[lang] + " " + z + " " + IN[lang] + " ");
		for (int i = 0; i < numElim; i++) {
			if (i < numElim - 1)
				printBoth(cell_str(elimCell[i]) + ", ");
			else // last elimination
				printBoth(cell_str(elimCell[i]));
		}
		printlnBoth("");
	}

// eliminate 'digit' from the starting cell
	static void chain1(int start, int digit) {
		printBoth(CHAIN[lang] + " ");
		printBoth(ELIMs[lang] + " " + digit + " " + IN[lang] + " ");
		printBoth(cell_str(start));
		printlnBoth("");
	}

// eliminate 'digit' from the target cell
	static void chain2(Board b, int start, int target, int digit) {
		printBoth(CHAIN_F[lang] + " ");
		printBoth(cell_str(start) + "=" + cand_str(b, start) + " ");
		printBoth(ELIMs[lang] + " " + digit + " " + IN[lang] + " ");
		printBoth(cell_str(target));
		printlnBoth("");
	}

// set 'digit' in the target cell
	static void chain3(Board b, int start, int target, int digit) {
		printBoth(CHAIN_F[lang] + " ");
		printBoth(cell_str(start) + "=" + cand_str(b, start) + " ");
		printBoth(SETs[lang] + " ");
		printBoth(cell_str(target) + "=" + digit);
		printlnBoth("");
	}

// general candidate testing
	static void cand_test(boolean auto, boolean deep, boolean two) {
		if (deep) {
			if (two) {
				printBoth(ARIADNE[lang] + " (" + TWO[lang] + ")");
			} else {
				printBoth(ARIADNE[lang]);
			}
		} else {
			if (two) {
				printBoth(CONTRA[lang] + " (" + TWO[lang] + ")");
			} else {
				printBoth(CONTRA[lang]);
			}
		}
		printlnBoth("");
	}

// total number of tried candidates
	static void tried(boolean deep, int tried, int elim, int sol) {
		printBoth(TRIED[lang] + ": " + tried + "  " + ELIMIN[lang] + ": " + elim);
		if (!deep) {
			printBoth("  " + SOLUTION[lang] + ": " + sol);
		}
		printlnBoth("");
	}

	static void interrupt() {
		printlnBoth(" -- " + INTERRUPT[lang]);
	}

} // class Printing