/*
Online Java - IDE, Code Editor, Compiler
Online Java is a quick and easy tool that helps you to build, compile, test your programs
online.
*/

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

interface Fillable   //KEEP
{  
    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 wipe9x9Board(int[][] formattedBoard, int[][] nineByNine);
    public void print9x9Board(String history, BigInteger numComplete9x9Boards);
    public int convertStringTo3x3(String permutations3x3, int getNumString);
    public void realTime9x9Fill(String history);
    public void display9x9();

}

class Sudoku implements Fillable
{
    int minimum=362880;
    int maximum=0;

    StringJoiner permutationsSelected;
    int randomNumber;
    StringJoiner summary;
    StringJoiner summary1;

    //Moved this across to BigInteger. It did not work previously since I was unable
    //to increment this by one
    //int numAttempts;
    BigInteger numAttempts=new BigInteger("0");

    //I introduced this to keep track of number completed suduko boards which pass validation
    BigInteger numSuccessfulCompletedBoards = new BigInteger("0");
    
    int numRetrieved3x3GridsIn9x9Grid;

    BigInteger numberPossibleBoards = new BigInteger("108883584818776183656945007213012309135068193536000");

    Set<String> permutationAllBoards = new HashSet();

    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<BigInteger, int[][]> completedBoards = new HashMap<>();

    //Need to change this into BigInteger
    BigInteger numComplete9x9Boards = new BigInteger("1");
    //int numComplete9x9Boards=1;   //number completed 9x9 boards....

    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();

    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();


    //We are now using Set PermutationAllBoards to hold the completed board (currentStringJoinerFullGrid)
    //This can be phased out
    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 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 (taken from internet)");

        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.forEach(str -> lst.add(str));

            numbersProcessed=0;

            //System.out.println("*****This is the list size------: " + lst.size());   //list size

            //System.out.println("\n******These are permutations completed:" + s.size());  //set size

            do   
            {
                endFirstRow3x3=false; 

                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();   
            //System.out.println("This is the new set size: " + newSize + "     Added:   " + sj.toString());

            sj=new StringJoiner(" ");

            if (newSize>currentSize)
            {
                mp.put(newSize,threeBythree);
            }

            row=0;     
            col=0;

        }while (s.size()<362880);    // this is getting  <(NUMBER)  x   (3x3 boards)
        //}while (s.size()<2000);    // this is getting  <(NUMBER)  x   (3x3 boards)

        fill9x9(mp); 
    }

    public void fill9x9(Map<Integer, int[][]> mp)
    {
        int temp[][]=new int[3][3];
        int successfulInputted3x3=0;
        
        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[] perm3x3Selection = new String[perm3x3.length];

            String second3x3StringPlacedInGrid; 
            {
                int uniqueEntries=0;
                int[] storeRetrieved3x3Grid=new int[9];

                do
                {
                    randomNumber = rand.nextInt(perm3x3.length);
                    
                    if (randomNumber<minimum)
                    {
                        minimum=randomNumber;
                    }

                    if (randomNumber>maximum)
                    {
                        maximum=randomNumber;
                    }

                    if ((perm3x3Selection[randomNumber])=="ALREADY SELECTED")
                    {
                        //System.out.println("*********************************GRID ALREADY SELECTED" + "("+randomNumber+") " +"GENERATING ANOTHER");
                        
                        randomNumber = rand.nextInt(perm3x3.length);
                        if (randomNumber<minimum)
                        {
                            minimum=randomNumber;
                        }

                        if (randomNumber>maximum)
                        {
                            maximum=randomNumber;
                        }
                    }
                    else
                    {
                        //System.out.println("*********************************NEW ENTRY: " + randomNumber);
                        storeRetrieved3x3Grid[uniqueEntries]=randomNumber;
                        uniqueEntries++;
                        perm3x3Selection[randomNumber]="ALREADY SELECTED";
                    }

                }while (uniqueEntries<9);
                
                permutationsSelected = new StringJoiner(",");
                
                for (int z: storeRetrieved3x3Grid)
                {
                    entry3x3=z;
                    permutationsSelected.add(String.valueOf(entry3x3));

                    //System.out.println("VALUE OF ENTRY in 3x3:" + entry3x3);
                    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);
                }

                storeRetrieved3x3Grid = new int[9];
                uniqueEntries=0;

                perm3x3 = s.toArray(new String[s.size()]);
                
                if (totalNumbersProcessed<=81)
                {
                    if (totalNumbersProcessed<=27 && !condition2 && !condition3)
                    {
                        rowIndex=0;
                        colIndex=0;
                        condition1=true;
                        condition2=true;
                        condition3=true;
                    }

                    if (totalNumbersProcessed<=54 && totalNumbersProcessed>27 && condition1 && condition3)
                    {
                        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;
                            }

                            /*
                            System.out.println("Selecting grid (3x3) " + i +" from : "+ s.size());
                            System.out.println("Total numbers processed so far: " + totalNumbersProcessed + " out of 81");
                            System.out.println("Current offset in 9x9 grid: " + offset);
                            System.out.println("Starting in this col in 9 x 9: " + colIndex);
                            System.out.println("The current coordinate(3x3):  " + "(" +rowCount +","+ colCount +")");
                            System.out.println("Following number chosen: " + temp[rowCount][colCount]);
                            System.out.println("being stored at coordinate(9x9): " + "(" + rowIndex + "," + colIndex +")");
                            System.out.println("currently processing this from 3 x 3:" + "(" + rowCount + "," +colCount+")");
                            */

                            sj.add(temp[rowCount][colCount] + "("+rowIndex+","+colIndex+")");

                            nineByNine[rowIndex][colIndex]=temp[rowCount][colCount];

                            realTime9x9Fill(sj.toString());
                            
                            //System.out.println("FILLING BOARD REAL TIME");
                            //display9x9();
                            
                            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)
                                    {
                                        successfulInputted3x3++;
                                    }
                                    else
                                    {
                                        successfulInputted3x3=0;
                                    }
                                }

                                //System.out.println("Streak of successful 3x3 blocks: " + successfulInputted3x3);

                                i++;
                            }

                            if (totalNumbersProcessed%81==0)
                            {
                                completedBoards.put(numComplete9x9Boards,nineByNine);
                                
                                //I have now completed this modification to support BigInteger
                                //numAttempts++;
                                numAttempts=numAttempts.add(new BigInteger("1"));
                                
                                //I adjusted the current suduko board with this value:  numSuccessfulCompletedBoard
                                System.out.println("\n*********************Current successful sudoku board(s): " + numSuccessfulCompletedBoards + "  out of " + Permutations3x3into9x9 + "  Attempts: " + numAttempts);

                                totalNumbersProcessed=0;

                                i=1;
                                sj = new StringJoiner(" ");
                                
                                if (sudokuComplete(failedRows, failedColumns))
                                {
                                    
                                }
                            }

                            totalNumbersProcessed++;
                        } 
                    } 
                    //System.out.println("*************************************");
                }
            }
        } while (numComplete9x9Boards.compareTo(numberPossibleBoards)==-1);
    }

    public void print9x9Board(String currentStringJoinerFullGrid, BigInteger numComplete9x9Boards)
    {
        
        //System.out.println("STORING: " + currentStringJoinerFullGrid);
        permutationAllBoards.add(currentStringJoinerFullGrid);

        numComplete9x9Boards = new BigInteger(String. valueOf(permutationAllBoards.size()));

        System.out.println("********************************************************************************");
        System.out.println("\nThis is your board number " + (numComplete9x9Boards) + " summary: " + currentStringJoinerFullGrid);

        System.out.println("********************************************************************************");
        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;
        }

        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]));

            }
                System.out.println(sj1);
        }
    }

    public boolean checkUniqueRows(int[][] nineByNine, int rowIndex)
    {
        summary1 = new StringJoiner("| ");
        //System.out.println("**************************************************************************************");

        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;  
                    }
                }
            }
            
            //System.out.println("Number: " + possibleNumbers[j] + " has occured: " + occurenceNumberRow +  " times in  row " + rowIndex);
            summary1.add("N:" + String.valueOf(possibleNumbers[j]) + "  O:" + String.valueOf(occurenceNumberRow) + "  Row:" + String.valueOf(rowIndex));
        }
        
        return failedRows;   //returns flag value...
    }

    public boolean checkUniqueColumns(int[][] nineByNine, int colIndex)
    {
        summary = new StringJoiner("| ");
        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;
                    }
                }
            }
            //System.out.println("Number: " + possibleNumbers[j] + " has occured: " + occurenceNumberCol +  " times in column " + colIndex);
            summary.add("N:" + String.valueOf(possibleNumbers[j]) + "  O:" + String.valueOf(occurenceNumberCol) + "  Col:" + String.valueOf(colIndex));
        }

        return failedColumns;
    }
    
    public boolean sudokuComplete(boolean duplicateNumbersRow, boolean duplicateNumbersCol)
    {
        if (duplicateNumbersRow || duplicateNumbersCol)
        {
            //System.out.println("**************************");
            System.out.println("Better luck next time, failed on board attempt:" + count + "\tPermutations selected: (" + permutationsSelected+")" + "minimum: "+ minimum + " maximum:" + maximum);
            //System.out.println("N=Number, O=Occurrences Col = Column   "  + summary);
            //System.out.println("N=Number, O=Occurrences Row = Row   "  + summary1);
            
            
            //I have disabled this since it will give full board summary... It is not imporatnt for a fail and more importantly burden on the screen outputs
            //I have also moved it from where it had totalNumbersProcessed==81...  it is summary
            //print9x9Board(sj.toString(), numComplete9x9Boards);
            
            //We can optionally turn this on to view the completed board in the expected format
            //display9x9();

            wipe9x9Board(formattedBoard,nineByNine);

            //System.out.println("**************************");

            System.out.println("Moving onto Board Number: " + numComplete9x9Boards);
            permutationsSelected=new StringJoiner(",");

            failedRows=false;
            //This was the critical failure before when I had the same variable above
            //reset twice. it practically
            failedColumns=false;

            return false;
        }
        else
        {
            System.out.println("**************************");
            System.out.println("\nCongratulations, sudoku complete on board: " + count + " Permutations selected: (" + permutationsSelected+")");
            System.out.println("Complete solution:" + sj.toString());

            //System.out.println("N=Number, O=Occurrences Col = Column   "  + summary);
            //System.out.println("N=Number, O=Occurrences Row = Row   "  + summary1);
            System.out.println("**************************");
            permutationsSelected=new StringJoiner(",");

            //Instead of exiting, I have continued for more completions
            
            //System.exit(0);
            wipe9x9Board(formattedBoard,nineByNine);

            System.out.println("Moving onto Board Number: " + numComplete9x9Boards);

            failedRows=false;
            
            //This was the critical failure before when I had the same variable above
            //reset twice
            failedColumns=false;
            
            //Display the completed board
            display9x9();
                                    
            //Need to increment a successful board
            numSuccessfulCompletedBoards=numAttempts.add(new BigInteger("1"));
            
            return true;
        }
    }
}

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); // this is number permutations
                }
            }
            return result;
        }
        return 1;
    }
}