import java.util.ArrayList;
import java.util.Random;

public class sudoku {

	int randomNumber1;
	int randomNumber2;
	int randomNumber3;
	boolean[] linjacheck = {false, false, false, false, false, false, false, false, false};
	boolean[] finalcheck = {false,false,false};
	Random r = new Random();
	ArrayList<Integer> values = new ArrayList<Integer>();
	int[][] rivix = new int[9][9];

			public void startti(){
			for (int i = 0; i < 9; i++) {
				rivix[i] = new int[]{1,2,3,4,5,6,7,8,9};
			}
			}

               /**Randomize the board. **/
		public int[][] sekoitus (int[][] rivi){

			for (int i = 0; i < 300; i++) {

				randomNumber1 = r.nextInt(9);

				randomNumber2 = r.nextInt(9);
				randomNumber3 = r.nextInt(9);

				int swap1 = rivi[randomNumber1][randomNumber2];
				int swap2 = rivi[randomNumber1][randomNumber3];
				if(!linjacheck[randomNumber2] && !linjacheck[randomNumber3]){
				rivi[randomNumber1][randomNumber2] = swap2;
				rivi[randomNumber1][randomNumber3] = swap1;
				}

			}
			return rivi;

		}
                   /**print out the board**/
		public void poyta (int[][] rivi){

			System.out.println ("----------------------------");
				for (int i = 0; i < 9; i++) {
						for (int a = 0; a < 9; a++) {
						System.out.print(rivi[i][a]);
						if((a+1)%3==0 && a!=0)
							System.out.print(" ");
						}
						System.out.println("");

				}

			System.out.println("\n");

		}
                   /**check vertical lines one by one**/
		 public boolean checktable (int[][] rivi){
			int[][] riviy = new int[9][9];

			for (int i = 0; i < 9; i++) {
				for (int a = 0; a < 9; a++) {
					riviy[i][a] = rivi[a][i];
				}
			}

				for (int i=0; i < 9; i++){
					int check = 0;

						for (int a = 1; a < 10; a++) {
							if (AC(riviy[i], a))
								check++;
						}
					if (check==9){
						linjacheck[i]=true;
					}else
						linjacheck[i]=false;


				}
				if (linjacheck[0] && linjacheck[1] && linjacheck[2] && linjacheck[3] && linjacheck[4] && linjacheck[5] && linjacheck[6] && linjacheck[7] && linjacheck[8] && checkOtherSquares(rivi)){
					return true;
				}else
					return false;

		}
           /**check 3x3 squares.**/
	private boolean checkOtherSquares(int[][] rivi) {
		boolean[] fullcheck = {false,false,false,false,false,false,false,false,false};
		for (int a = 0; a < 9; a++) {
			 values.clear();
			 switch(a){
				 case 0:
						for (int i=0;i<3;i++){
							values.add(rivi[i][0]);
							values.add(rivi[i][1]);
							values.add(rivi[i][2]);
						}
				break;
				 case 1:
						for (int i=3;i<6;i++){
							values.add(rivi[i][0]);
							values.add(rivi[i][1]);
							values.add(rivi[i][2]);
						}
				break;
				 case 2:
						for (int i=6;i<9;i++){
							values.add(rivi[i][0]);
							values.add(rivi[i][1]);
							values.add(rivi[i][2]);
						}
				break;
				 case 3:
						for (int i=0;i<3;i++){
							values.add(rivi[i][3]);
							values.add(rivi[i][4]);
							values.add(rivi[i][5]);
						}
				break;
				 case 4:
						for (int i=3;i<6;i++){
							values.add(rivi[i][3]);
							values.add(rivi[i][4]);
							values.add(rivi[i][5]);
						}
				break;
				 case 5:
						for (int i=6;i<9;i++){
							values.add(rivi[i][3]);
							values.add(rivi[i][4]);
							values.add(rivi[i][5]);
						}
				break;
				 case 6:
						for (int i=0;i<3;i++){
							values.add(rivi[i][6]);
							values.add(rivi[i][7]);
							values.add(rivi[i][8]);
						}
				break;
				 case 7:
						for (int i=3;i<6;i++){
							values.add(rivi[i][6]);
							values.add(rivi[i][7]);
							values.add(rivi[i][8]);
						}
				break;
				 case 8:
						for (int i=6;i<9;i++){
							values.add(rivi[i][6]);
							values.add(rivi[i][7]);
							values.add(rivi[i][8]);
						}
				break;
			 }



			if (values.contains(1) && values.contains(2) && values.contains(3) && values.contains(4) && values.contains(5)&&values.contains(6)&& values.contains(7)&& values.contains(8)&& values.contains(9)){
				fullcheck[a] = true;
			}

		}

			if(fullcheck[8] && fullcheck[7] && fullcheck[6]){
				finalcheck[2] = true;
			}
			else{
				linjacheck[6] = false;
				linjacheck[7] = false;
				linjacheck[8] = false;
				}
			if(fullcheck[5] && fullcheck[4] && fullcheck[3])
				finalcheck[1] = true;
			else{
				linjacheck[5] = false;
				linjacheck[4] = false;
				linjacheck[3] = false;
			}
			if(fullcheck[2] && fullcheck[1] && fullcheck[0])
				finalcheck[0] = true;
			else{
				linjacheck[2] = false;
				linjacheck[1] = false;
				linjacheck[0] = false;
			}

			if(finalcheck[0] && finalcheck[1] && finalcheck[2])
				return true;
			else
				return false;

		}

	public boolean AC(int[] arrays, int searchValue){
		boolean check = false;
		for (int i = 0; i < arrays.length; i++) {
			if(arrays[i] == searchValue)
				check = true;
		}
		return check;

	}

	public int incrementLinja(){
		int linja=0;
		for (int i = 0; i < 9; i++) {
			if(linjacheck[i])
				linja++;
		}
		return linja;
	}

	public void runStuff(){
		startti();
		rivix = sekoitus(rivix);
		while (!checktable(rivix)){
			rivix = sekoitus(rivix);
			checktable(rivix);
		}
		poyta(rivix);

	}

	public static void main(String[] args) {
		sudoku s = new sudoku();
		double time = System.currentTimeMillis();
		s.runStuff();
		double timeAfter = System.currentTimeMillis();
		System.out.println("Puzzle generated in: " + ((timeAfter-time)/1000) + " seconds.");

	}

}