//reaches 301962 with one line system.out.println
// TOTAL:  362880
/*
Online Java - IDE, Code Editor, Compiler
Online Java is a quick and easy tool that helps you to build, compile, test your programs
online.
*/
// This has been created to ensure I can utilize any random functions more efficiently.
// It is a creation of the nPr permutation calculator.
// It has used techniques I learnt including recursion and also memoization to speed up execution.
// I will incorporate this into Java applications I created
//TEST CASES
//r=2 n=5 PASS
//r=5 n=5 PASS
//r=1 n=4 PASS
//r=0 n=3 PASS
//r=0 n=0 PASS
// now going to flip the above
//r=5 n=2 PASS
//r=5 n=5 PASS
//r=4 n=1 PASS
//r=3 n=0 PASS
//test to make numerator less than r
// n = 4 r=3 PASS

import java.math.*;
import java.util.*;
import java.util.stream.*;

interface Fillable
{
    public void fill3x3();
    public void fill9x9(Map<Integer, int[][]> mp);
    public boolean checkUniqueRows();
    public boolean checkUniqueColumns();
    public void place3X3Into9x9();
    public boolean SudokuComplete();
    public void get9x9Grid();
    public void get3x3Grid();
    
}


class Sudoku implements Fillable
{
    Map<Integer, int[][]> mp = new HashMap();
    int possibleNumbers[] = new int[]{1,2,3,4,5,6,7,8,9};
    //List<int> lst = new ArrayList<>(Arrays.asList(possibleNumbers));
    
    List<Integer> lst = new ArrayList<Integer>();
    
    
    long permutations;
    
    int threeBythree[][] = new int[3][3];    //0,0 0,1, 0,2  
                                             //1,0, 1,1, 1,2
                                             //2,0, 2,1, 2,2
    //Set <Integer[][]> s = new HashSet<>();
    
    Set<String> s = new HashSet();
    
    
    
    int storeMiniGrids[][][];
    int item=0;
    
    int currentSize;
    int newSize;
    int[][] miniGrid;
    
    List<Integer> copy = new ArrayList<>(lst);
    boolean processedDivisibleTwo=false;
    Random rand = new Random();
    
    
    public Sudoku(long permutations)
    {
        this.permutations =permutations;
       
       /* 
        // can also add viable numbers into list this way.
        //But I want to introduce new coding techniques so used stream....
       
        for (int i=0; i<possibleNumbers.length; i++)
    {
        System.out.println("fucking here");
        lst.add(possibleNumbers[i]);
    }
    
    */
   
    fill3x3();
        
    }
    
    public void fill3x3()
    {
        //PSEUDO CODE
       
       //might be worth using stream in future
      
      int row=0;
      int col=0;
      int numbersProcessed;
      
      
     
     
      StringJoiner sj = new StringJoiner(",");
      
      System.out.println("There are : " + permutations + " permutations of arranging  3 x 3 grid" );
      
      /*
      //ok so it has completed the full population of a single 3 x 3 grid
      since it has processed   0,0  0,1  0,2
                               1,0  1,1  1,2
                               2,0, 2,1, 2,2
      */
      
      
      do
      {
          //lst=copy;  //restore the original list;
          
          IntStream stream = Arrays.stream(possibleNumbers); 
  
        // Displaying elements in Stream 
        stream.forEach(str -> lst.add(str));
          
          //fucking mistake here
          //why reset this at start of new set entry...
          
          //for a new attempt to add into the set, row continues from next row
          //col=0;  //column will start again from 0 index, however it has already also done this below in modulus check
          //so best to take it out!
          
          
          numbersProcessed=0;
          
          //System.out.println("*****This is the list size------: " + lst.size());
          //System.out.println("******These are permutations completed:" + s.size());
         
         // this is fucking wrong loop..
         //since the loop gets smaller in size... i will process what is left!!!
         //fucking!
         
         //for (int i=0; i<lst.size();i++)  // this will ensure process of random selection from lst
         
         do
         {
             processedDivisibleTwo=false;
             
             //System.out.println("numbers processed:" + numbersProcessed);
             
           int randomNumber = rand.nextInt(lst.size());   //this will get 0-8, so needs addition of 1
      
      //System.out.println("HERE!!!!");
      //System.out.println(row);
      //System.out.println(col);
      
      threeBythree[row][col]= lst.get(randomNumber);
      
      // since set has failed to work with List<String>, Int[][], Integer[][], String[][]
      //it has proven to work with String....
      //so all the numbers will be concatenated to a String
      //it might be sensible potentially to complete stringjoiner with ,
      //StringTokenizer can be used to perform retrieval....
      
      sj.add(Integer.toString(lst.get(randomNumber)));
      //sudokuMiniGrid = sudokuMiniGrid + Integer.toString(lst.get(randomNumber));
      
      //System.out.println("Following number added into the 3 x 3 grid: " + lst.get(randomNumber));
      lst.remove(randomNumber);
      
      //System.out.println("This is new list size: " + lst.size());
      
      if (col%2==0 && col!=0)    // at this point it has populated row of 3 x 3 grid...
      {
          //System.out.println("divisible");
          row++;  //it has to start a new row
          col=0;  //the column is reset back to 0
          processedDivisibleTwo = true;
      }
      
      if (!processedDivisibleTwo)   // it will only do this condition if it hasn't already been reset to 0 as part of new column above...
      {
      col++;  //otherwise it will increase the column in the given row by 1 until above condition is met...
      //System.out.println("new column: " + col);
      }
      
      numbersProcessed++;
         }while(!lst.isEmpty());
      
      currentSize=s.size();
      //System.out.println("This is the current set size: " + currentSize);
      
      //s.add(Arrays.asList(threeBythree[0][0].toString()));
      s.add(sj.toString());
      
      
      //System.out.println("************This is the first row into String: " + sj.toString());
     
      
      newSize=s.size();
      System.out.println("This is the new set size: " + newSize + "   " + sj.toString());
      
       sj=new StringJoiner(",");
      
      //this will put the matrix version of 3 x 3 if permutation is unique....
      if (newSize>currentSize)
      {
          mp.put(newSize,threeBythree);
      }
      
      get3x3Grid();
      
      row=0;     // the process starts again..
      col=0;  // the process starts again..
      
      //}while (s.size()<permutations);
      }while (s.size()<20);
      
      
      fill9x9(mp);
       
/*
numbers can be generated via random. and stored in int[row][col] array   (0-2 for rows and col)
get current set size
add int[row][col]  into the set
get new set size
continue until below condition....
}while (set.size()<P(9,9);  // can not do this... since these are permutations if sudoku not met...
// but at same time, it has to explore every single one.....


3 x 3 grids (9 total) filled into   9 x 9 grid    int[this will go from 0-8][value from  0-8]  (need to think about this!!)
                                                                                [between 0-2,  3-5,  6-8] [between 0-2,  3-5,  6-8]

//This will be the natural partitions of the set entries....
0-2
3-5
6-8

Checking at each time that the rows and columns do not contain duplicate numbers.....

Print out the grid to end user......

// this showing that it has placed all small 9 grids inside....
} while (!gridFull)
}  end for

*/
    }
    
    
    public void fill9x9(Map<Integer, int[][]> mp)
    {
      
        
        
        /*
        pseudo
        do
{

                                                                         col=0  col=1 col=2
start any one of the 3x3 grids in position [0,0]       of the      row=0[3x3] [3x3] [3x3]
                                                                   row=1[3x3] [3x3] [3x3]
                                                                   row=2[3x3] [3x3] [3x3]

*remove it from lst (it is removed since it is believed the 3x3 grid can not be replicated)..  and randomnly *pick another 3x3 grid... 
*Check if it can go at [0,1]
*if it can, then remove it from lst (since not possible for the grid to go elsewhere).....
*randomnly pick next one from lst.. check if it can go in position [0,2]
*keep going until gridisFull (9x9)
* store the grid...


*next time around.. item that was [0,1] can not go back in same place....
start process again until grid is full

}while(permutations<UNKNOWN>    // this means that once it has exceeded set number of permutations, it will                                    end.
*/      
        
        Collection<int[][]> col = mp.values();  // this will store all the values.....
        int temp[][];
        
        
        //Since I am so familiar with working with lists and all the entries in HashMap are unique and it 
        //consists of int[][] which is the most workable for exercise, I will put all the map values and add it into
        //a list
        List <int[][]> lt = new ArrayList<>(mp.values());
        Set <int[][]> st = new HashSet<>(mp.values());
        int [][] nineByNine = new int[][]{{0,0,0,0,0,0,0,0,0},
                                            {0,0,0,0,0,0,0,0,0},
                                            {0,0,0,0,0,0,0,0,0},
                                            {0,0,0,0,0,0,0,0,0},
                                            {0,0,0,0,0,0,0,0,0},
                                            {0,0,0,0,0,0,0,0,0},
                                            {0,0,0,0,0,0,0,0,0},
                                            {0,0,0,0,0,0,0,0,0},
                                            {0,0,0,0,0,0,0,0,0}};
        
        // This i10 just a quick lambda validation that there is a key and expected entry for number keys
        mp.forEach((key, value) -> System.out.println(key + " : " + value));
        
        
        // we know it has added all map.values() in set and also list...
        
        int rowCount=0;   //used for small 3x3 grid
        int colCount=0;   //used for small 3x3 grid
        boolean ReachEndColMiniGrid=false;
        
        int rowIndex=0;   
        int colIndex=0;
        int offset=0;
        int numbersProcessed3x3=0;
        
        System.out.println("***CHECKING PROPER LIST:");
        for (int i=0; i<lt.size(); i++)  //using 10 mini grids  for now testing
        {
            // this is int[][] array containing the first mini grid...
            temp = lt.get(i);
         
         System.out.println("\n******This is picking list item:" + i);
         System.out.println("*****************************************" + i);
         
            
            ReachEndColMiniGrid=false;
            
            
// *********************
//At moment, once it finishes the first correctly at (2,2)

/*
1 1 1 X 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 X 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
*/

// The next list item should be stored in  (0,3)  - it should be stored here
// current logic is taking it here... (2,3)  as expected......
//There is no logic in the coding currently telling it to return back here....

//in first last 3 x 3 grid it finished at  (2,2)
//so clearly the rowIndex (of 9x9) has not reset to 0....

//once it has processed 9 numbers, the row index always goes back to  0,3, 6
//it will go to 0 if it is processing first 3 list items (0,1,2 zero index based).
//it will go to 3 if it is processing next 3 list items (3,4,5 zero index based).
//it will go to 6 if it is processing next 3 list items (6,7,8 zero index based).

/*
It now resolves the issue and writes content from (0,3) to (0,5) for the 2nd list item....

1 1 1 X 0 ! 0 0 0
! 0 0 ! 0 0 0 0 0
0 0 X 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

after(0,5) it needs to go to (1,3)     - since colIndex 3 is the new starting point...
it is currently going into  (1,0)  - this is similar to it starting the 2nd row  for the 1st list item...
//logic is somewhere in the code once it has realised that rowCount has reached 2
*/


if (numbersProcessed3x3==9)
{
    System.out.println("DECISION");
if (i==0 || i==1 || i==2)
{
    System.out.println("DECISION1");
    
    rowIndex=0;
    
}

if (i==3 || i==4 || i==5)
{
    rowIndex=3;
    
}

if (i==6 || i==7 || i==8)
{
    rowIndex=6;
    
}

}


numbersProcessed3x3=0;

            //all values in mini grid to be inserted into top left corner...
           
            
            for (int n=0; n<temp.length;n++ )  // this will go through each row of the 3 x 3  (0-2)(0-2)
            {
                
               
                System.out.println("value of n: " + n);
                System.out.println("Value colcount993: "  + colCount);
                
                if (colCount>=2 && rowCount!=2)  // if it reaches last number of row mini grid in first row
                {
                    System.out.println("Current colcount 3x3: " + colCount);
                    System.out.println("Current rowcount 3x3: " + rowCount);
                    
                    rowCount++;   // it starts new row of mini grid...
                    colCount=0;   // it starts again at column 0 mini grid
                    ReachEndColMiniGrid=true;  //sets flag
                    
                    //ut would also have to start new row on big grid..
                    // for second row of 3x3
                    rowIndex++;
                    colIndex=0;
                  
                    //IT HAS REACHED THE LAST COLUMN BIG GRID..  COLINDEX8..
                    //IN THIS CASE, IT HAS TO reset back to start new row
                    //IT SHOULD HIT THIS POINT WHEN numbersprocessed has hit 9...
                    
                    
                        //it has to also start again on big grid
                        //but this time it moves down 3 places from [0,0] no to overwrite any data....
                        
                      
                    if (colIndex==8 && numbersProcessed3x3==9)
                    {
                        colIndex=0;
                        rowIndex=rowIndex+3;
                        
                    }
                    
                    //if it hasn't reached the last column on 9x9
                    //and it has processed entire 3 x 3 mini grid...
                    //The next grid is adjacent....
                    // There is no bearing on 
                    
                    
                    if (colIndex!=8 && numbersProcessed3x3==9)
                    {
                        System.out.println("**********************BACK HERE!");
                        colIndex=colIndex+1;
                        rowIndex=0;
                        
                    }
                    
                    
                }
                
                for (int k=0; k<temp[0].length;k++)  // this will then go through each column in row....
                {
                    
                    numbersProcessed3x3++;
                    
                    //this has to keep track of the offset in the colIndex (9 by 9 grid)
                    //otherwise when it starts the next row, it will take the colIn
                    if (k==0)
                    {
                        offset=colIndex;
                        
                    }
                    
                    System.out.println("\n$$$$$$$$$$$$$$Current offset in 9x9 grid: " + offset);
                    System.out.println("*****Starting in this col in 9 x 9: " + colIndex);
                    System.out.println("numbersProcessed: " + numbersProcessed3x3);
                    System.out.println("The current coordinate:" + rowCount);
                    System.out.println("The current coordinate:" + colCount);
                    
                    //colindex is wrong for the second list item....
                    //in first row, its fine since it is set to +1 pos from last grid.
                    //when the row has increased, the column has gone to 0, need to change this logic...
                    
                    System.out.println("Following number: " + temp[rowCount][colCount]);
                    
                    System.out.println("being stored at index: " + rowIndex + " " + colIndex);
                    System.out.println("currently processing this from 3 x 3:" + "(" + rowCount + "," +colCount+")");
                    nineByNine[rowIndex][colIndex]=temp[rowCount][colCount];
                    System.out.println("Final ready column: " + colIndex);
                    
                    
                    colCount++;  //moves forwad position on 3 x 3
                    
                    colIndex++;  //moves forward position on the main 9 x 9
                    
                    if (numbersProcessed3x3==9)   //if it has done all avlues in 3x3
                    {
                        colCount=0;   //starts again in 3x3
                        rowCount=0; //starts again in 3x3
                        
                        
                    }
                    
                }
                
                //UNSURE
                /*
                if (!ReachEndColMiniGrid)
                {
                    colCount++;
                }
                */
                
                //numbersProcessed3x3++;
                
            }
            
            
        }
    
        
        
        

        
        /*
        **************************************************************
        //going through all the keys
        for (int key: mp.keySet())
        {
        System.out.println(key);
        }
        
        //this is technique to get int array out of col (which is map.values() of m)
        
        for (int i=0; i<lt.size(); i++)
        {
            temp = lt.get(i);
            
            for (int k[]:temp)
            {
                System.out.println(Arrays.asList(k));
            }
        }
        
        *********************************************************
        */
        
    
        
        //content is stored in three locations.....
        //**** SO FAR  *****
            //The data is stored in following places:
            // threeBythree int[][],   this is stored in the
            // in set as String of all 9 numbers
            
            //miniGrid this is no different to info in set.... 
            // it is used since it has containsKey.......
            
        //The pseudo code is here
        

//my algorithm  (only issue is not sure how many times to repeat this process).....
//Will just set a large figure in UNKNOWN


//int test[][][] = new int [][][];   //3d array

//int [][] gridOne = m.get[0];
//int [][] gridTwo = m.get[1];

/*




*/

//now want to store 2D array inside...
//although the whole process can be completed without storing anything into huge grid...


        
        
        
        
    }
    
    public boolean checkUniqueRows()
    {
        return false;
        
    }
    public boolean checkUniqueColumns()
    {
        return false;
        
    }
    public void place3X3Into9x9()
    {
        
    }
    public boolean SudokuComplete()
    {
        return false;
        
    }
    
    public void get9x9Grid()
    {
        
    }
    
    //for some fucking reason, the set is not getting bigger..
    
    public void get3x3Grid()
    {
        
        
        //System.out.println("***********");
        
        //this will get out all the 3x3 grids from the permutations.....
        
        if (mp.containsKey(newSize))
        {
            miniGrid = mp.get(newSize);    //minigrid is of type int[][]
            
            
            //mp.getKey()
            
            //at this point in might be worth calling fall 9x9 grid
            //now it has reached this...  P (362880,9)
            //n will the unique key...
            
        }
        
        //System.out.println("This should be same in map:");
        //this will print out all the rows.....
        for (int[] g :miniGrid)
        {
            //System.out.println("!!!!!This is the key: " + mp.getKey(newSize));
            System.out.println(Arrays.toString(g));
        }
        
        
        // since set has got an  int[][] it will need a nested solution to get value back
        // for each row, go through all the columns.....
        
        // this is just to test that it can reach the grid correctly,
        // this is easiest route to allow it traverse the set....
        
        
        // can imagine this being huge problem in future.
        //since there is no get by index.....
        // this will potential mean the amount of screen output will be very limited..
        // since it will have show entirety!!!
        //very similar to StringTokenizer!!!! and no point taking content and storing elsewhere...
        //Perhaps it can be added into Map at future point only once its fully populated with all permutations...
        // This will then allow it to use the containskey method...
        
        /*
        for (int i=0; i<s.size(); i++)
        {
            System.out.println(s.get(i));
        }
        */
        
        /*
        for (List<String> t: s)   //for each integer array in the set
        {
            String grid =  t.get();             // this is the grid
            System.out.println(grid);
            
            //this will be extremely code expensive as the set grows...
            //But for now, it is being done just to understand what is actually being stored in set.
          
          /*
             for (Integer g[]: grid)
             {
                 System.out.println(Arrays.toString(g));
             }
          */
          
          /*
            for (int j=0; j<grid.length; j++)
              //this will tell you number columns in the row 
            {   
                 //this will tell you number columns ... always gets confusing which way round
                for (int i=0; i<grid[0].length; i++)
                {
                    //need all values on the same line here....
                    System.out.println("Number here: " + grid[j][i]);
                    
                }
            }
            */
            
    }
}
    
            
            //System.out.println(t[0][0]);
            //System.out.println(t[0][1]);


public class Permutation
{
public static void main(String[] args) {
System.out.println("Welcome to Online IDE!! Happy Coding :)");
int originalNumber=9;
int n=originalNumber;
int r =9;
Map <Integer, Long> m = new HashMap<>();
System.out.println("***PERMUTATIONS***");
System.out.println("P(n,r) = n! / (n−r)!");
System.out.println("P(" + n+","+r+") = " + n+"!" + " / " + "("+n+"-"+r+")!");

Sudoku sud = new Sudoku (Permutations (n,r,originalNumber, m));


//System.out.println(Permutations (n,r,originalNumber, m));
}
public static long Permutations (int n, int r, int originalNumber, Map factorialResults)
{
// n are objects
// r is sample
/*
***CALCULATION***
P(n,r) = n! / (n−r)!
*/
long result=0;
int temp;
int denominator;
if (originalNumber<r || r<0)
{
System.out.println("please enter n ≥ r ≥ 0");
System.exit(0);
return 0;
}
if (n>=1)
{
// EXAMPLE
// P (5,6) = 5* 4 * 3 * 2 * 1 / (6-5)! = 24 / 2! = 24 / 2 * 1 = 24/2 = 12
result = (n* (Permutations (n-1, r,originalNumber, factorialResults))); // this completes factorial for numerator
factorialResults.put(n,result); //result stored in the Map
//System.out.println("getting result back out numerator " + n+": " + factorialResults.get(n));
if (n==originalNumber) // this will occur once
{
denominator = originalNumber-r; // originalNumber required since n has reduced as part of the recursive calls
//System.out.println("This is denominator: " + denominator);
// this is using the Java Memoization technique to ensure the factorial outcome is not calculated again, to save program execution cycles.
// since the returns are done in reverse order.... n = 1 is processed first and n=6 last...
//Hence in practice there will be entry in Map for all factorials, ready for the denominator..
if (factorialResults.containsKey(denominator))
{
//System.out.println("here");
//System.out.println("This is exact value of factorial denominator " + (denominator) + " : " + factorialResults.get(denominator));
return result / (long)factorialResults.get(denominator); // this is number permutations
}
}
return result; // this will be returning already calculating numerator part
}
return 1; // // it should reach here if this is false: (n>=1) }
}
}