/*
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
//Difficult to produce..

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

interface Fillable
{
    public void fill3x3Manual();
    public void fill3x3();
    public void fill9x9(Map<Integer, int[][]> mp);
    public boolean checkUniqueRows(int [][] temp, int rowIndex);
    public boolean checkUniqueColumns(int[][] nineByNine, int colIndex);
    public boolean sudokuComplete(boolean a, boolean b);
    public void get9x9Grid();
    public void get3x3Grid();
    public void wipe9x9Board(int[][] formattedBoard, int[][] nineByNine);
    public void print9x9Board(String history, int numComplete9x9Boards);
    public int convertStringTo3x3(String permutations3x3, int getNumString);
    public void realTime9x9Fill(String history);
    public void display9x9();
}

class nineByNine
{
    int test;
   
    public nineByNine()
    {
        
    }
}

class Sudoku implements Fillable
{
    Map<Integer, int[][]> mp = new HashMap();
    
    int possibleNumbers[] = new int[]{1,2,3,4,5,6,7,8,9};
    
    List<Integer> lst = new ArrayList<Integer>();
   
    int MiniTest[][] = new int[3][3];
    int formattedBoard[][] = new int [9][9];
    
    Map<Integer, int[][]> completedBoards = new HashMap<>();
    int numComplete9x9Boards=1;
   
    StringJoiner sj1 = new StringJoiner(",");
   
    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} };
   
  
    int totalNumbersProcessed=1;
   
    long permutations;
    String Permutations3x3into9x9;
   
    int threeBythree[][] = new int[3][3];
    Set<String> s = new HashSet();
    
    Set<String> copyPermuations = new HashSet(s);
   
    StringJoiner sj;
    int storeMiniGrids[][][];
    
    int currentSize;
    int newSize;
    int[][] miniGrid;
    int[][][] miniGridContainer;
   
    List<Integer> copy = new ArrayList<>(lst); 
    
    boolean endFirstRow3x3=false;
    Random rand = new Random();
    
    String[] completedBoardsLogs = new String[10000];
    
    int count=0;
    int rowIndex=0;
    int colIndex=0;
   
    int randomNumber1to9List;
    boolean failedColumns;
    boolean failedRows;
    boolean sudokuSuccess;
   
    public void wipe9x9Board(int [][]formattedBoard, int nineByNine[][])
    {
        for (int q=0; q<nineByNine.length; q++)
        {
            for (int r=0; r<nineByNine[0].length; r++)
            {
                formattedBoard[q][r]=0;
                nineByNine[q][r]=0;
            }
        }
    }
    
    public Sudoku(long permutations, String  Permutations3x3into9x9)
    {
        this.permutations =permutations;
        this.Permutations3x3into9x9=Permutations3x3into9x9;
   
        fill3x3();
    }
   
    public int convertStringTo3x3(String permutations3x3, int getNum)
    {
        int temp;
        char num;
        String numString;
       
        num=permutations3x3.charAt(getNum);
        numString= String.valueOf(num);
               
        temp= Integer.parseInt(numString);
        return temp;
    }
    
    public void fill3x3Manual()
    {
        s.add("1,2,3,4,5,6,7,8,9");
        s.add("4,5,6,7,8,9,1,2,3");
        s.add("7,8,9,1,2,3,4,5,6");
        s.add("2,3,1,5,6,4,8,9,7");
        s.add("6,4,5,9,7,8,3,1,2");
        s.add("9,7,8,3,1,2,6,4,5");
        s.add("3,1,2,6,4,5,9,7,8");
        s.add("5,6,4,8,9,7,2,3,1");
        s.add("8,9,7,2,3,1,5,6,4");
        
        //get3x3Grid();  can not do this....
        //fill9x9(mp);  // having issue running this.... even tried taking off references to mp...
    }
   
    public void fill3x3()
    {
        int row=0;              
        int col=0;
        int numbersProcessed;
        sj = new StringJoiner(",");
     
        System.out.println("There are : " + permutations + " permutations of arranging  3 x 3 grid" );
        System.out.println("There are : " + Permutations3x3into9x9 + " permutations of arranging  3 x 3 grid into 9 x 9:" + "P(362880,9)" );
        System.out.println("There are : 6,670,903,752,021,072,936,960" + " permutations of completing sudoku");
      
        System.out.println("This code will attempt to explore but its impossible to expect much");
        System.out.println("It is used for foundation of experimentation but also it has made serious attempt to complete random process to make a grid");
        System.out.println("I am removing excess code so it is ready future development.");
      
      do    
      {
          IntStream stream = Arrays.stream(possibleNumbers); //Stream to take numbers from array
          stream.forEach(str -> lst.add(str));
          
          numbersProcessed=0;
         
          System.out.println("******These are permutations completed:" + s.size());
         
         do
         {
             endFirstRow3x3=false;
             int randomNumber = rand.nextInt(lst.size());
             randomNumber1to9List=lst.get(randomNumber);
             threeBythree[row][col]= randomNumber1to9List;
             
             sj.add(Integer.toString(randomNumber1to9List));
             lst.remove(randomNumber);
     
            if (col%2==0 && col!=0)
            {
                row++;
                col=0;
                endFirstRow3x3 = true;
            }
            
            if (!endFirstRow3x3)
            {
                col++;
            }
     
            numbersProcessed++;
            
         }while(!lst.isEmpty());
     
        currentSize=s.size();
     
        s.add(sj.toString());
        newSize=s.size();
        sj=new StringJoiner(" ");
        
        if (newSize>currentSize)
        {
          mp.put(newSize,threeBythree);
        }
     
        get3x3Grid();
     
        row=0;
        col=0;
      
      //}while (!sudokuComplete(failedRows,failedColumns))    
       
      }while (s.size()<permutations);
     
      fill9x9(mp);
      get9x9Grid();
       
    }
   
    public void fill9x9(Map<Integer, int[][]> mp)
    {
        Collection<int[][]> col = mp.values();
        
        int temp[][]=new int[3][3];
        int successfulInputted3x3=0;
        List <int[][]> lt = new ArrayList<>(mp.values());
        Set <int[][]> st = new HashSet<>(mp.values());
       
        int rowCount=0;
        int colCount=0;
        boolean ReachEndColMiniGrid=false;
       
        int offset=0;
        int i=1;
        int numberOf3x3Processed=0;
        int m;
        int entry3x3=0;
        
        boolean condition1=false;  
        boolean condition2=false;
        boolean condition3=false;
       
        do
        {
            String[] perm3x3 = s.toArray(new String[s.size()]);
            String second3x3StringPlacedInGrid;
            second3x3StringPlacedInGrid=perm3x3[1]; 
        
            temp[0][0]=convertStringTo3x3(perm3x3[entry3x3],0);
            temp[0][1]=convertStringTo3x3(perm3x3[entry3x3],2);
            temp[0][2]=convertStringTo3x3(perm3x3[entry3x3],4);
            temp[1][0]=convertStringTo3x3(perm3x3[entry3x3],6);
            temp[1][1]=convertStringTo3x3(perm3x3[entry3x3],8);
            temp[1][2]=convertStringTo3x3(perm3x3[entry3x3],10);
            temp[2][0]=convertStringTo3x3(perm3x3[entry3x3],12);
            temp[2][1]=convertStringTo3x3(perm3x3[entry3x3],14);
            temp[2][2]=convertStringTo3x3(perm3x3[entry3x3],16);
            

            int first3x3GridSelected[][] = new int[3][3];
            int rollBackRowIndex;
       
            if (entry3x3==0)
            {
                first3x3GridSelected=temp.clone();
            }
            
            entry3x3++;
           
            if (totalNumbersProcessed<=81)
            {
                if (totalNumbersProcessed<=27 && !condition2 && !condition3)
                {
                    rollBackRowIndex=rowIndex;
                    rowIndex=0;     
                    colIndex=0;
                    condition1=true;
                    condition2=true;
                    condition3=true;
               }
               
                if (totalNumbersProcessed<=54 && totalNumbersProcessed>27 && condition1 && condition3)
                {
                    rollBackRowIndex=rowIndex;
                    rowIndex=3;
                    colIndex=0;
                    condition2=true;
                    condition1=false;
                    condition3=false;
                }
                
                if (totalNumbersProcessed<=81 && totalNumbersProcessed>54 && condition2 && !condition1)
                {
                    rowIndex=6;
                    colIndex=0;
                    condition3=false;
                    condition1=true;
                    condition2=false;               
                }
                
                ReachEndColMiniGrid=false;         

                if (numberOf3x3Processed==9)
                {
                    switch(i)
                    {
                        case 1:
                            rowIndex=0;
                            break;
                            
                        case 2:
                            rowIndex=0;
                            break;
                        case 3:
                            rowIndex=0;
                            break;
                        case 4:
                            rowIndex=3;
                            break;
                        case 5:
                            rowIndex=3;
                            break;
                        case 6:
                            rowIndex=3;
                            break;
                        case 7:
                            rowIndex=6;
                            break;
                        case 8:
                            rowIndex=6;
                            break;
                        case 9:
                            rowIndex=6;
                            break;
                    }
                }
                
                numberOf3x3Processed=0;

                for (int n=0; n<temp.length;n++ )
                {
                    if (colCount>=2 && rowCount!=2)
                    {
                        rowCount++;
                        colCount=0;
                        rowIndex++;

                        if (offset==0)
                        {
                            colIndex=0;
                        }
                        else
                        {
                        colIndex=offset;
                        }
                        
                        if (colIndex==8 && numberOf3x3Processed==9)
                        {
                            colIndex=0;
                            rowIndex=rowIndex+3;
                            ReachEndColMiniGrid=true;
                        }
                        
                        if (colIndex!=8 && numberOf3x3Processed==9)
                        {
                            colIndex=colIndex+1;
                            rowIndex=0;
                        }
                    }
                   
                    for (int k=0; k<temp[0].length;k++)
                    {
                        numberOf3x3Processed++;
                        
                        if (k==0)
                        {
                            offset=colIndex;
                        }
                        
                        sj.add(temp[rowCount][colCount] + "("+rowIndex+","+colIndex+")");
                        nineByNine[rowIndex][colIndex]=temp[rowCount][colCount];
                        
                        realTime9x9Fill(sj.toString());
                        colCount++;
                        colIndex++;
                   
                        if (numberOf3x3Processed==9)
                        {
                            colCount=0;
                            rowCount=0;
                        }
                        
                        if (totalNumbersProcessed!=0 && totalNumbersProcessed%9==0)
                        {
                            System.out.println("row: " + failedRows);
                            System.out.println("col: " + failedColumns);
                            System.out.println("Numbers processed in 3x3 grid:" + numberOf3x3Processed);
                            
                            if (numberOf3x3Processed==9)
                            {
                                if (!failedRows&& !failedColumns)
                                {
                                    System.out.println("ever here");
                                    successfulInputted3x3++;
                                }
                                else
                                {
                                    successfulInputted3x3=0;
                                }
                            }
                            
                            System.out.println("Streak of successful 3x3 blocks: " + successfulInputted3x3);

                            i++;
                        }
                        
                        if (totalNumbersProcessed%81==0)
                        {
                            completedBoards.put(numComplete9x9Boards,nineByNine); 
                       	    print9x9Board(sj.toString(), numComplete9x9Boards);
                           
                            System.out.println("\nCurrent sudoku board: " + numComplete9x9Boards + "  out of " + (int) (s.size()/9) );
                            numComplete9x9Boards++;
                            totalNumbersProcessed=0;
                            
                            i=1;
                           
                            sj = new StringJoiner(" ");
                            
                            if (sudokuComplete(failedRows, failedColumns))
                            {
                                s = new HashSet(copyPermuations);
                                sudokuSuccess=true;
                            }
                            else
                            {
                                
                            }
                        }
                        
                        totalNumbersProcessed++;
                    }//end for loop  to go through  columns in each row
                }//end for loop for each row
            }
           
        }while((numComplete9x9Boards*9)<=s.size()); 
    }
    
    public void print9x9Board(String currentStringJoinerFullGrid, int numComplete9x9Boards)
    {
        completedBoardsLogs[count]=currentStringJoinerFullGrid;
        count=count+1;
    }  
    
    public void realTime9x9Fill(String history)
    {
        int row=0;  
        int col=0;  
        int boardValue=0;  
        int startLastNumber;
       
        int rowtoInt=0;
        int coltoInt=0;
        int boardValuetoInt=0;
       
        if (history.lastIndexOf(" ")==-1)
        {
            row = Character.getNumericValue(history.charAt(2));
            col = Character.getNumericValue(history.charAt(4));
            boardValue= Character.getNumericValue(history.charAt(0));
            formattedBoard [row][col]=boardValue;  
        }
        else
        {
            startLastNumber=history.lastIndexOf(" ");
            row = history.charAt((startLastNumber+3));
            col = history.charAt((startLastNumber+5));
            boardValue = history.charAt((startLastNumber+1));
            rowtoInt = Character.getNumericValue(row);
            coltoInt = Character.getNumericValue(col);
            boardValuetoInt= Character.getNumericValue(boardValue);
            
            formattedBoard [rowtoInt][coltoInt]=boardValuetoInt;  
        }
        
        display9x9();
        checkUniqueRows(formattedBoard, rowIndex); 
        checkUniqueColumns(formattedBoard, colIndex);
    }
    
    public void display9x9()
    {
        for (int i=0; i<formattedBoard.length; i++)
        {
            sj1= new StringJoiner(" ");
            
            for (int j=0; j<formattedBoard[0].length; j++)
            {
                sj1.add(Integer.toString(formattedBoard[i][j]));
            }
        }
    }
    
    public boolean checkUniqueRows(int[][] nineByNine, int rowIndex)
    {
        int occurenceNumberRow=0;
      
        for (int j=0; j<possibleNumbers.length; j++)    
        {
            occurenceNumberRow=0;
           
            for (int i=0; i<nineByNine[0].length; i++)
            {
                if (possibleNumbers[j]==nineByNine[rowIndex][i])
                {
                    occurenceNumberRow++;
                    
                    if (occurenceNumberRow>1 && !failedRows)  
                    {
                        failedRows = true;
                    }
                }
            }
            
        }//end of main for loop going through all numbers.....
        
        return failedRows;   //returns flag value...
    }
   
    public boolean checkUniqueColumns(int[][] nineByNine, int colIndex)
    {
        int occurenceNumberCol=0;
       
        for (int j=0; j<possibleNumbers.length; j++)    
        {
            occurenceNumberCol=0;
           
            for (int i=0; i<nineByNine.length; i++)
            {
                if (possibleNumbers[j]==nineByNine[i][colIndex])
                {
                    occurenceNumberCol++;
                    
                    if (occurenceNumberCol>1 && !failedColumns)
                    {
                    failedColumns = true;
                    }
                }
            }
        }
        
        return failedColumns;
     }
     
     public boolean sudokuComplete(boolean duplicateNumbersRow, boolean duplicateNumbersCol)
     {
        if (duplicateNumbersRow || duplicateNumbersCol)   //if both are true, it means that sudoku has failed...
        {
            System.out.println("Better luck next time, failed on board: " + count);
                        
            wipe9x9Board(formattedBoard,nineByNine);
            failedRows=false;
            failedRows=false;
                        
            return false;
        }           
        else
        {
            System.out.println("\nCongratulations, sudoku complete on board: " + count);
            wipe9x9Board(formattedBoard,nineByNine); 
                
            return true;
        }
    }
   
    public void get9x9Grid()
    {
        
    } 
    
    public void get3x3Grid()
    {
        int k=0;
        
        if (mp.containsKey(newSize))
        {
            miniGrid = mp.get(newSize);
            k++;
        }
        
        for (int[] g :miniGrid)
        {
        }
    }

}

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+")!");

        String Permutations3x3into9x9="108,883,584,818,776,183,656,945,007,213,012,309,135,068,193,536,000";
        String sudokuSolutions = "6,670,903,752,021,072,936,960";

        Sudoku sud = new Sudoku (Permutations (n,r,originalNumber, m),Permutations3x3into9x9);
    }
    
    public static long Permutations (int n, int r, int originalNumber, Map factorialResults)
    {
        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)
        {
            result = (n* (Permutations (n-1, r,originalNumber, factorialResults)));
            factorialResults.put(n,result);
            
            if (n==originalNumber)
            {
                denominator = originalNumber-r;
                
                if (factorialResults.containsKey(denominator))
                {
                    return result / (long)factorialResults.get(denominator);
                }
            }
            return result;
        }
    return 1;
    }
}