/*
  * Solving Sudoku Problems.
  *
  * By: Jon Donker
  */

import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.event.*;

public class GUISolveSudoku extends JFrame implements  ActionListener
{
   
   public final static long serialVersionUID = 46;
   
   private int globalRow;
   private int globalColumn;
   private JButton[][] buttonArray;
   private JPanel displayPanel;
   private Container cp;
   
   private JButton solveButton;
   private JButton resetButton;
   private JButton exitButton;
   
   public GUISolveSudoku()
   {
      super("Sudoku Program");
      setupGUI();
      addActionListeners();
   }
   
   public static void main(String[] args)
   {
      new GUISolveSudoku();
   }
   
    /*
     *  Sets up the GUI part of the program
     */
   private void setupGUI()
   {
      // Adds the Control Buttons to the panel
      JPanel bottomPanel = new JPanel();
      
      bottomPanel.setLayout(new GridLayout(1, 3));
      solveButton = new JButton("Solve");
      resetButton = new JButton("Reset");
      exitButton = new JButton("Exit");
      
      bottomPanel.add(solveButton);
      bottomPanel.add(resetButton);
      bottomPanel.add(exitButton);
      
      cp = getContentPane();
      
      displayPanel = new JPanel();
      displayPanel.setLayout(new GridLayout(3, 3, 20, 20));
      
      cp.setLayout(new BorderLayout());
      
      buttonArray = new JButton[9][9];
      
      
      // Adds the buttons and arrange them in 3x3 squares
      for(int loopDisplayRow = 0; loopDisplayRow < 3; loopDisplayRow ++)
      {
         for(int loopDisplayColumn = 0; loopDisplayColumn < 3; loopDisplayColumn ++)
         {
            JPanel tempPanel = new JPanel();
            tempPanel.setLayout(new GridLayout(3, 3));
            
            for(int loopRow = loopDisplayRow * 3; loopRow < (loopDisplayRow + 1) * 3 ; loopRow ++)
            {
               for(int loopColumn = loopDisplayColumn * 3; loopColumn < (loopDisplayColumn + 1) * 3; loopColumn ++)
               {
                  buttonArray[loopRow][loopColumn] = new JButton("0");
                  buttonArray[loopRow][loopColumn].setForeground(Color.white);
                  tempPanel.add(buttonArray[loopRow][loopColumn]);
               }
            }
            
            displayPanel.add(tempPanel);
         }
      }
      
      setUpContentPane(false);
      
      
      cp.add(bottomPanel, BorderLayout.SOUTH);
      cp.add(displayPanel, BorderLayout.CENTER);
      
      setBounds(100, 100, 500, 400);
      setVisible(true);
   }
   
    /*
     *  Adds action listeners to the buttons
     */
   public void addActionListeners()
   {
      for(int loopRow = 0; loopRow < 9; loopRow ++)
      {
         for(int loopColumn = 0; loopColumn < 9; loopColumn ++)
         {
            buttonArray[loopRow][loopColumn].addActionListener(this);
         }
      }
      
      solveButton.addActionListener(this);
      resetButton.addActionListener(this);
      exitButton.addActionListener(this);
   }
   
   public void actionPerformed(ActionEvent event)
   {
      if(event.getSource() == solveButton)
      {
         solve();
      }
      else
      {
         if(event.getSource() == resetButton)
         {
            for(int loopRow = 0; loopRow < 9; loopRow ++)
            {
               for(int loopColumn = 0; loopColumn < 9; loopColumn ++)
               {
                  buttonArray[loopRow][loopColumn].setText("0");
                  buttonArray[loopRow][loopColumn].setForeground(Color.white);
               }
            }
            setUpContentPane(true);
         }
         else
         {
            if(event.getSource() == exitButton)
            {
               System.exit(0);
            }
            else
            {
               JButton temp = (JButton)event.getSource();
               int buttonNumber = Integer.parseInt(temp.getText());
               
               buttonNumber ++;
               
               if(buttonNumber > 9)
               {
                  buttonNumber = 0;
                  temp.setForeground(Color.white);
               }
               else
               {
                  temp.setForeground(Color.black);
               }
               
               temp.setText("" + buttonNumber);
            }
         }
      }
   }
   
   public void setUpContentPane(boolean reset)
   {
      displayPanel.removeAll();
      displayPanel.setLayout(new GridLayout(3, 3, 20, 20));
      
      for(int loopDisplayRow = 0; loopDisplayRow < 3; loopDisplayRow ++)
      {
         for(int loopDisplayColumn = 0; loopDisplayColumn < 3; loopDisplayColumn ++)
         {
            JPanel tempPanel = new JPanel();
            tempPanel.setLayout(new GridLayout(3, 3));
            
            
            for(int loopRow = loopDisplayRow * 3; loopRow < (loopDisplayRow + 1) * 3 ; loopRow ++)
            {
               for(int loopColumn = loopDisplayColumn * 3; loopColumn < (loopDisplayColumn + 1) * 3 ; loopColumn ++)
               {
                  buttonArray[loopRow][loopColumn].setBackground(Color.white);
                  
                  tempPanel.add(buttonArray[loopRow][loopColumn]);
               }
            }
            
            displayPanel.add(tempPanel);
         }
      }
   }
   
   public boolean checkNumberGUI(int row, int column)
   {
      boolean cont = true;
      // Check row
      int[] test = new int[10];
      
      for(int loopColumns = 0; ((loopColumns < 9) && (cont)); loopColumns ++)
      {
         int indexOfNumber = Integer.parseInt(buttonArray[row][loopColumns].getText());
         
         test[indexOfNumber] ++;
         
         if((test[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
         {
            cont = false;
         }
      }
      
      // Check column
      
      test = new int[10];
      
      for(int loopRow = 0; ((loopRow < 9) && (cont)); loopRow ++)
      {
         int indexOfNumber = Integer.parseInt(buttonArray[loopRow][column].getText());
         
         test[indexOfNumber] ++;
         
         if((test[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
         {
            cont = false;
         }
      }
      
      // Check square
      
      test = new int[10];
      
      for(int loopSquareRow = ((row / 3) * 3); ((loopSquareRow < ((row / 3) * 3) + 3) && (cont));
      loopSquareRow ++)
      {
         for(int loopSquareCoulumn = ((column / 3) * 3); ((loopSquareCoulumn < ((column / 3) * 3) + 3) && (cont));
         loopSquareCoulumn ++)
         {
            int indexOfNumber = Integer.parseInt(buttonArray[loopSquareRow][loopSquareCoulumn].getText());
            
            test[indexOfNumber] ++;
            
            if((test[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
            {
               cont = false;
            }
         }
      }
      
      return cont;
   }
   
   public void solve()
   {
      int[][] base = new int[9][9];
      boolean[][] initialNumbers = new boolean[9][9];
      globalRow = 0;
      globalColumn = 0;
      
      boolean isSolved = true;
      
      for(int loopRow = 0; loopRow < 9; loopRow ++)
      {
         for(int loopColumn = 0; loopColumn < 9; loopColumn ++)
         {
            base[loopRow][loopColumn] = Integer.parseInt(buttonArray[loopRow][loopColumn].getText());
            if(base[loopRow][loopColumn] != 0)
            {
               initialNumbers[loopRow][loopColumn] = true;
            }
            else
            {
               initialNumbers[loopRow][loopColumn] = false;
            }
         }
      }
      
      if(isValidSudoku(base))
      {
         isSolved = findSolution(base);
         
         for(int loopRow = 0; loopRow < 9; loopRow ++)
         {
            for(int loopColumn = 0; loopColumn < 9; loopColumn ++)
            {
               buttonArray[loopRow][loopColumn].setText(base[loopRow][loopColumn] + "");
               buttonArray[loopRow][loopColumn].setForeground(Color.black);
               
               if(initialNumbers[loopRow][loopColumn])
               {
                  buttonArray[loopRow][loopColumn].setBackground(Color.YELLOW);
               }
            }
         }
      }
   }
   
   public boolean isValidSudoku(int base[][])
   {
      return isValidSudoku(base, false);
   }
   
   public boolean isValidSudoku(int base[][], boolean checkNumbers)
   {
      boolean returnValue = true;
      
      // Check all rows & columns
      for(int count = 0; (count < base.length && returnValue); count ++)
      {
         returnValue = checkNumber(base, count, 0);
         returnValue = checkNumber(base, 0, count);
      }
      
      // Check squares
      
      for(int rowLoop = 1; (rowLoop <= 7 && returnValue); rowLoop += 3)
      {
         for(int columnLoop = 1; (columnLoop <= 7 && returnValue); columnLoop += 3)
         {
            returnValue = checkNumber(base, rowLoop, columnLoop);
         }
      }
      
      if(checkNumbers)
      {
         for(int rowLoop = 0; (rowLoop < 9 && returnValue); rowLoop ++)
         {
            for(int columnLoop = 0; (columnLoop < 9 && returnValue); columnLoop ++)
            {
               if((base[rowLoop][columnLoop] < 0) || (base[rowLoop][columnLoop] > 9))
               {
                  returnValue = false;
               }
            }
         }
      }
      
      return returnValue;
   }
   
   public boolean checkNumber(int base[][], int row, int column)
   {
      boolean cont = true;
      // Check row & Column
      int[] testRow = new int[10];
      int[] testColumn = new int[10];
      
      for(int count = 0; ((count < 9) && (cont)); count ++)
      {
         int indexOfNumber = base[row][count];
         testRow[indexOfNumber] ++;
         
         if((testRow[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
         {
            cont = false;
         }
         
         indexOfNumber = base[count][column];
         testColumn[indexOfNumber] ++;
         
         if((testColumn[indexOfNumber] > 1) && (!(indexOfNumber == 0)))
         {
            cont = false;
         }
      }
      
      // Check 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];
            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];
      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 ++)
         {
            numbersLeft[rowLoop][columnLoop] = (HashSet)temp.clone();
         }
      }
      
      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 ++)
//         {
//            System.out.println(numbersLeft[rowLoop][columnLoop]);
//         }
//      }
      
      
      try
      {
         boolean result = tryNumbers(base, numbersLeft);
      }
      catch(CannotCompleteSuduko e)
      {
         foundResult = false;
      }
      
      return foundResult;
   }
   
   public boolean tryNumbers(int base[][], HashSet numbersLeft[][])
   {
      if(globalColumn == 9 )
      {
         return true;
      }
      else
      {
         Iterator loopHashSet = numbersLeft[globalRow][globalColumn].iterator();
         if(numbersLeft[globalRow][globalColumn].size() == 1)
         {
            if(base[globalRow][globalColumn] == 0)
            {
               base[globalRow][globalColumn] = ((Integer)loopHashSet.next()).intValue();
            }
            advanceGlobalRef();
            
            if(tryNumbers(base, numbersLeft))
            {
               return true;
            }
            subGlobalRef();
            return false;
         }
         else
         {
            while(loopHashSet.hasNext())
            {
               int testNumber = ((Integer)loopHashSet.next()).intValue();
               
               base[globalRow][globalColumn] = testNumber;
               
               if(checkNumber(base, globalRow, globalColumn))
               {
                  advanceGlobalRef();
                  if(tryNumbers(base, numbersLeft))
                  {
                     return true;
                  }
               }
            }
            
            base[globalRow][globalColumn] = 0;
            subGlobalRef();
            return false;
         }
      }
   }
   
   public void advanceGlobalRef()
   {
      globalRow ++;
      if(globalRow > 8)
      {
         globalColumn ++;
         globalRow = 0;
      }
      
//        if(globalColumn >= 9)
//        {
//            throw new CannotCompleteSuduko();
//        }
   }
   
   public void subGlobalRef()
   {
      globalRow --;
      if(globalRow < 0)
      {
         globalColumn --;
         globalRow = 8;
      }
      
      if(globalColumn < 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 ++)
            {
               if(base[rowLoop][columnLoop] != 0)
               {
                  for(int count = 0; count < 9; count ++)
                  {
                     numbersLeft[rowLoop][count].remove(new Integer(base[rowLoop][columnLoop]));
                     numbersLeft[count][columnLoop].remove(new Integer(base[rowLoop][columnLoop]));
                  }
                  
                  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].remove(new Integer(base[rowLoop][columnLoop]));
                     }
                  }
                  
                  numbersLeft[rowLoop][columnLoop].clear();
                  numbersLeft[rowLoop][columnLoop].add(new Integer(base[rowLoop][columnLoop]));
               }
            }
         }
         
         for(int rowLoop = 0; rowLoop < 9; rowLoop ++)
         {
            for(int columnLoop = 0; columnLoop < 9; columnLoop ++)
            {
               if((numbersLeft[rowLoop][columnLoop].size() == 1) && (base[rowLoop][columnLoop] == 0))
               {
                  Iterator loopHashSet = numbersLeft[rowLoop][columnLoop].iterator();
                  
                  base[rowLoop][columnLoop] = ((Integer)loopHashSet.next()).intValue();
                  
                  finished = false;
               }
            }
         }
      }
      while(!finished);
   }
}