/*
    Solve The Dion Cube.

    By: Jon Donker.

    Please pay me millions of dollars to use this source code as
    this program has taken many years off my life for stress.

 */



 import java.util.*;
 
public class SolveDino2 {
    
    //int[][] base;
    private int globalRow;
    private int globalColumn;
    private int globalDepth;
    
    /** Creates a new instance of SolveSudoku */
    public SolveDino2()
    {
    }
    

    public static void main(String[] args) {
        // TODO code application logic here
        SolveDino2 theApp = new SolveDino2();
        
        theApp.run();
    }

    public void run()
    {
        boolean finished = false;
        //int[][][] base = new int[9][9][9];

        int[][][] base =
        {
            // Slice 1
            {
                {0, 0, 0, 0, 3, 0, 0, 0, 0},
                {0, 9, 0, 0, 4, 0, 0, 8, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {7, 3, 0, 0, 1, 0, 0, 5, 4},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 2, 0, 0, 7, 0, 0, 6, 0},
                {0, 0, 0, 0, 5, 0, 0, 0, 0}
            },

            // Slice 2
            {
                {3, 0, 0, 0, 9, 0, 0, 0, 2},
                {0, 0, 0, 0, 7, 0, 0, 0, 0},
                {0, 0, 9, 2, 0, 4, 7, 0, 0},
                {0, 0, 4, 7, 0, 8, 6, 0, 0},
                {1, 9, 0, 0, 0, 0, 0, 8, 7},
                {0, 0, 3, 9, 0, 1, 4, 0, 0},
                {0, 0, 1, 4, 0, 5, 8, 0, 0},
                {0, 0, 0, 0, 1, 0, 0, 0, 0},
                {5, 0, 0, 0, 8, 0, 0, 0, 6}
            },

            // Slice 3
            {
                {0, 0, 0, 4, 0, 5, 0, 0, 0},
                {0, 3, 0, 6, 0, 9, 0, 5, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {3, 8, 0, 0, 0, 0, 0, 4, 2},
                {0, 0, 0, 0, 7, 0, 0, 0, 0},
                {6, 1, 0, 0, 0, 0, 0, 3, 8},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 9, 0, 5, 0, 2, 0, 8, 0},
                {0, 0, 0, 9, 0, 1, 0, 0, 0}
            },

            // Slice 4
            {
                {0, 0, 6, 0, 0, 0, 3, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {2, 0, 4, 0, 0, 0, 6, 0, 9},
                {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},
                {4, 0, 5, 0, 0, 0, 9, 0, 1},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 7, 0, 0, 0, 5, 0, 0}
            },

            // Slice 5
            {
                {4, 2, 0, 0, 7, 0, 0, 6, 1},
                {6, 1, 0, 0, 0, 0, 0, 3, 8},
                {0, 0, 0, 0, 9, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {8, 0, 3, 0, 6, 0, 4, 0, 5},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 1, 0, 0, 0, 0},
                {5, 4, 0, 0, 0, 0, 0, 9, 6},
                {9, 6, 0, 0, 2, 0, 0, 7, 3}
            },

            // Slice 6
            {
                {0, 0, 8, 0, 0, 0, 2, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {9, 0, 1, 0, 0, 0, 8, 0, 3},
                {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},
                {1, 0, 6, 0, 0, 0, 3, 0, 7},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 4, 0, 0, 0, 6, 0, 0}
            },

            // Slice 7
            {
                {0, 0, 0, 9, 0, 1, 0, 0, 0},
                {0, 5, 0, 7, 0, 8, 0, 1, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {5, 4, 0, 0, 0, 0, 0, 9, 6},
                {0, 0, 0, 0, 2, 0, 0, 0, 0},
                {7, 3, 0, 0, 0, 0, 0, 5, 4},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 8, 0, 1, 0, 6, 0, 4, 0},
                {0, 0, 0, 8, 0, 3, 0, 0, 0}
            },

            // Slice 8
            {
                {6, 0, 0, 0, 5, 0, 0, 0, 8},
                {0, 0, 0, 0, 9, 0, 0, 0, 0},
                {0, 0, 5, 8, 0, 3, 9, 0, 0},
                {0, 0, 3, 9, 0, 1, 4, 0, 0},
                {2, 5, 0, 0, 0, 0, 0, 1, 9},
                {0, 0, 6, 5, 0, 2, 3, 0, 0},
                {0, 0, 2, 3, 0, 7, 1, 0, 0},
                {0, 0, 0, 0, 2, 0, 0, 0, 0},
                {7, 0, 0, 0, 1, 0, 0, 0, 4}
            },

            // Slice 9
            {
                {0, 0, 0, 0, 8, 0, 0, 0, 0},
                {0, 6, 0, 0, 2, 0, 0, 7, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {3, 8, 0, 0, 9, 0, 0, 4, 2},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 5, 0, 0, 3, 0, 0, 1, 0},
                {0, 0, 0, 0, 4, 0, 0, 0, 0}
            },
        };

        
        System.out.println("Running");
        
        if(isValidSudoku(base, true))
        {
            System.out.println("Is valid");
            double startTime = System.currentTimeMillis();
        
            try
            {
                finished = findSolution(base);
                double endTime = System.currentTimeMillis();
                System.out.println("Time taken: " + (endTime - startTime) + " milliseconds");
            }
            catch(CannotCompleteSuduko e)
            {
                System.out.println ("Cannot Find a solution");
            }

            // Print results.
            for(int depthLoop = 0; depthLoop < 9; depthLoop ++)
            {
                for(int rowLoop = 0; rowLoop < 9; rowLoop ++)
                {
                    for(int columnLoop = 0; columnLoop < 9; columnLoop ++)
                    {
                        System.out.print(base[depthLoop][rowLoop][columnLoop] + "\t");
                    }
                    System.out.println("\n");
                }

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

        }
        else
        {
            System.out.println("Error.  Not a valid Sudoku");
        }
    }
    
    public boolean isValidSudoku(int base[][][], boolean checkNumbers)
    {
        boolean returnValue = true;

        /*
        for(int rowLoop = 0; (rowLoop < 9 && returnValue); rowLoop ++)
        {
            for(int columnLoop = 0; (columnLoop < 9 && returnValue); columnLoop ++)
            {
                for(int depthLoop = 0; (depthLoop < 9 && returnValue); depthLoop ++)
                {
                    returnValue = checkNumber(base, rowLoop, columnLoop, depthLoop);

                    if(!returnValue)
                    {
                        System.out.println("Row: " + rowLoop + "\tColumn: "+ columnLoop + "\tDepth: " + depthLoop);
                        System.out.println(base[rowLoop][columnLoop][depthLoop]);
                    }
                }
            }
        }
        */
        
        // Check all rows, columns and depths
        for(int count = 0; (count < base.length && returnValue); count ++)
        {
            returnValue = checkNumber(base, count, 0, 0);
            returnValue = checkNumber(base, 0, count, 0);
            returnValue = checkNumber(base, 0, 0, count);

            if(!returnValue)
            {
                System.out.println("Count: " + count);
            }
        }
        
        // Check squares
        
        for(int rowLoop = 1; (rowLoop <= 7 && returnValue); rowLoop += 3)
        {
            for(int columnLoop = 1; (columnLoop <= 7 && returnValue); columnLoop += 3)
            {
                for(int depthLoop = 1; (depthLoop <= 7 && returnValue); depthLoop += 3)
                {
                    returnValue = checkNumber(base, rowLoop, columnLoop, depthLoop);
                }
            }
        }

        if(checkNumbers)
        {
            for(int rowLoop = 0; (rowLoop < 9 && returnValue); rowLoop ++)
            {
                for(int columnLoop = 0; (columnLoop < 9 && returnValue); columnLoop ++)
                {
                    for(int depthLoop = 0; (depthLoop < 9 && returnValue); depthLoop ++)
                    {
                        if((base[rowLoop][columnLoop][depthLoop] < 0) || (base[rowLoop][columnLoop][depthLoop] > 9))
                        {
                            returnValue = false;
                        }
                    }
                }
            }
        }
        
        return returnValue;
    }
    
    public boolean checkNumber(int base[][][], int row, int column, int depth)
    {
        boolean cont = true;
        
        // Check row & Column
        int[] testRow = new int[10];
        int[] testColumn = new int[10];
        int[] testDepth = new int[10];
        
        for(int count = 0; ((count < 9) && (cont)); count ++)
        {
            //System.out.println("Row: " + row);
            //System.out.println("loopColumns: " + loopColumns);

            int indexOfNumber = base[row][count][depth];
            testRow[indexOfNumber] ++;
            
            if((testRow[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
            {
                cont = false;
            }
            
            indexOfNumber = base[count][column][depth];
            testColumn[indexOfNumber] ++;
            
            if((testColumn[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
            {
                cont = false;
            }

            indexOfNumber = base[row][column][count];
            testDepth[indexOfNumber] ++;
            
            if((testDepth[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
            {
                cont = false;
            }
        }
        
        // Check row/column square
        
        int[] test = new int[10];
        
        for(int loopSquareRow = ((row / 3) * 3); ((loopSquareRow < ((row / 3) * 3) + 3) && (cont)); loopSquareRow ++)
        {
            for(int loopSquareColumn = ((column / 3) * 3); ((loopSquareColumn < ((column / 3) * 3) + 3) && (cont)); loopSquareColumn ++)
            {
                int indexOfNumber = base[loopSquareRow][loopSquareColumn][depth];
                test[indexOfNumber] ++;

                if((test[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
                {
                    cont = false;
                }
            }
        }

        // Check row/depth square
        
        test = new int[10];
        
        for(int loopSquareRow = ((row / 3) * 3); ((loopSquareRow < ((row / 3) * 3) + 3) && (cont)); loopSquareRow ++)
        {
            for(int loopSquareDepth = ((depth / 3) * 3); ((loopSquareDepth < ((depth / 3) * 3) + 3) && (cont)); loopSquareDepth ++)
            {
                int indexOfNumber = base[loopSquareRow][column][loopSquareDepth];
                test[indexOfNumber] ++;

                if((test[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
                {
                    cont = false;
                }
            }
        }

        test = new int[10];
        
        for(int loopSquareColumn = ((column / 3) * 3); ((loopSquareColumn < ((column / 3) * 3) + 3) && (cont)); loopSquareColumn ++)
        {
            for(int loopSquareDepth = ((depth / 3) * 3); ((loopSquareDepth < ((depth / 3) * 3) + 3) && (cont)); loopSquareDepth ++)
            {
                int indexOfNumber = base[row][loopSquareColumn][loopSquareDepth];
                test[indexOfNumber] ++;

                if((test[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
                {
                    cont = false;
                }
            }
        }
        return cont;
    }
    
    public boolean findSolution(int base[][][])
    {
        boolean foundResult = true;
        
        HashSet[][][] numbersLeft = new HashSet[9][9][9];
        HashSet temp = new HashSet();
        
        System.out.println("Initialised hash array");
        
        for(int count = 1; count < 10; count ++)
        {
            temp.add(new Integer(count));
        }

        for(int rowLoop = 0; rowLoop < 9; rowLoop ++)
        {
            for(int columnLoop = 0; columnLoop < 9; columnLoop ++)
            {
                for(int depthLoop = 0; depthLoop < 9; depthLoop ++)
                {
                    numbersLeft[rowLoop][columnLoop][depthLoop] = (HashSet)temp.clone();
                    //System.out.println(numbersLeft[rowLoop][columnLoop]);
                }
            }
        }
        
        System.out.println("----------------");
        
        System.out.println("Created and populated hash array");
        
        trimmingHashSets(base, numbersLeft);
        
        System.out.println("Trimmed numbers");
        
        for(int rowLoop = 0; rowLoop < 9; rowLoop ++)
        {
            for(int columnLoop = 0; columnLoop < 9; columnLoop ++)
            {
                for(int depthLoop = 0; depthLoop < 9; depthLoop ++)
                {
                   System.out.println(numbersLeft[rowLoop][columnLoop][depthLoop]);
                }
            }
        }

        try
        {
            boolean result = tryNumbers(base, numbersLeft);
        }
        catch(CannotCompleteSuduko e)
        {
            foundResult = false;
        }
        
        return foundResult;
    }
    
    public boolean tryNumbers(int base[][][], HashSet numbersLeft[][][])
    {
        
        //System.out.println("Created Iterator");

        if(globalDepth == 9)
        {
            return true;
        }
        else
        {
			System.out.println("Golbal Row: " + globalRow + "\tGlobal Column: " + globalColumn + "\tGlobal Depth: " + globalDepth);
			Iterator loopHashSet = numbersLeft[globalRow][globalColumn][globalDepth].iterator();
		
            if(numbersLeft[globalRow][globalColumn][globalDepth].size() == 1)
            {
                if(base[globalRow][globalColumn][globalDepth] == 0)
                {
                    base[globalRow][globalColumn][globalDepth] = ((Integer)loopHashSet.next()).intValue();
                }
                advanceGlobalRef();
                
                if(tryNumbers(base, numbersLeft))
                {
                    return true;
                }
                subGlobalRef();
                return false;
            }
            else
            {
                //System.out.println(numbersLeft[globalRow][globalColumn][globalDepth]);
                //boolean foundAMatch = true;

                while(loopHashSet.hasNext())
                {
                    int testNumber = ((Integer)loopHashSet.next()).intValue();

                    base[globalRow][globalColumn][globalDepth] = testNumber;

                    if(checkNumber(base, globalRow, globalColumn, globalDepth))
                    {
                        advanceGlobalRef();
                        if(tryNumbers(base, numbersLeft))
                        {
                            return true;
                        }
                    }
                }
            
                base[globalRow][globalColumn][globalDepth] = 0;
                subGlobalRef();
                return false;
            }
        }
        
        //return false;
    }
    
    public void advanceGlobalRef()
    {
        globalRow ++;
        if(globalRow > 8)
        {
            globalColumn ++;
            globalRow = 0;

            if(globalColumn >= 9)
            {
                globalDepth ++;
                globalColumn = 0;

                //if(globalDepth >= 9)
                //{
                //    throw new CannotCompleteSuduko();
                //}
            }
        }
    }
    
    public void subGlobalRef()
    {
        globalRow --;
        if(globalRow < 0)
        {
            globalColumn --;
            
            globalRow = 8;

            if(globalColumn < 0)
            {
                globalDepth --;
                globalColumn = 8;

                if(globalDepth < 0)
                {
                    throw new CannotCompleteSuduko();
                }
            }
        }
    }
    
    public void trimmingHashSets(int base[][][], HashSet numbersLeft[][][])
    {
        boolean finished;

        do
        {
            // Initial Pass
            finished = true;

            for(int rowLoop = 0; rowLoop < 9; rowLoop ++)
            {
                for(int columnLoop = 0; columnLoop < 9; columnLoop ++)
                {
                    for(int depthLoop = 0; depthLoop < 9; depthLoop ++)
                    {
                        if(base[rowLoop][columnLoop][depthLoop] != 0)
                        {
                            for(int count = 0; count < 9; count ++)
                            {
                                numbersLeft[rowLoop][count][depthLoop].remove(new Integer(base[rowLoop][columnLoop][depthLoop]));
                                numbersLeft[count][columnLoop][depthLoop].remove(new Integer(base[rowLoop][columnLoop][depthLoop]));
                                numbersLeft[rowLoop][columnLoop][count].remove(new Integer(base[rowLoop][columnLoop][depthLoop]));
                            }
    
                            for(int loopSquareRow = ((rowLoop / 3) * 3); (loopSquareRow < ((rowLoop / 3) * 3) + 3); loopSquareRow ++)
                            {
                                for(int loopSquareColumn = ((columnLoop / 3) * 3); (loopSquareColumn < ((columnLoop / 3) * 3) + 3); loopSquareColumn ++)
                                {
                                    numbersLeft[loopSquareRow][loopSquareColumn][depthLoop].remove(new Integer(base[rowLoop][columnLoop][depthLoop]));
                                }
                            }

                            for(int loopSquareRow = ((rowLoop / 3) * 3); (loopSquareRow < ((rowLoop / 3) * 3) + 3); loopSquareRow ++)
                            {
                                for(int loopSquareDepth = ((depthLoop / 3) * 3); (loopSquareDepth < ((depthLoop / 3) * 3) + 3); loopSquareDepth ++)
                                {
                                    numbersLeft[loopSquareRow][columnLoop][loopSquareDepth].remove(new Integer(base[rowLoop][columnLoop][depthLoop]));
                                }
                            }

                            for(int loopSquareColumn = ((columnLoop / 3) * 3); (loopSquareColumn < ((columnLoop / 3) * 3) + 3); loopSquareColumn ++)
                            {
                                for(int loopSquareDepth = ((depthLoop / 3) * 3); (loopSquareDepth < ((depthLoop / 3) * 3) + 3); loopSquareDepth ++)
                                {
                                    numbersLeft[rowLoop][loopSquareColumn][loopSquareDepth].remove(new Integer(base[rowLoop][columnLoop][depthLoop]));
                                }
                            }
    
                            numbersLeft[rowLoop][columnLoop][depthLoop].clear();
                            numbersLeft[rowLoop][columnLoop][depthLoop].add(new Integer(base[rowLoop][columnLoop][depthLoop]));
                        }
                            //System.out.println(numbersLeft[rowLoop][columnLoop]);
                    }
                }
            }

            for(int rowLoop = 0; rowLoop < 9; rowLoop ++)
            {
                for(int columnLoop = 0; columnLoop < 9; columnLoop ++)
                {
                    for(int depthLoop = 0; depthLoop < 9; depthLoop ++)
                    {
                        if((numbersLeft[rowLoop][columnLoop][depthLoop].size() == 1) && (base[rowLoop][columnLoop][depthLoop] == 0))
                        {
                            Iterator loopHashSet = numbersLeft[rowLoop][columnLoop][depthLoop].iterator();
    
                            base[rowLoop][columnLoop][depthLoop] = ((Integer)loopHashSet.next()).intValue();
    
                            finished = false;
                        }
    
                        //System.out.println(numbersLeft[rowLoop][columnLoop]);
                    }
                }
            }
        }
        while(!finished);
    }
}