/* Sudoku.java applet for solving Sudoku puzzles.

(C) 2005, Matt Mahoney, matmahoney (at) yahoo.com
This is free software under GPL, http://www.gnu.org/licenses/gpl.txt

Sudoku is a puzzle in which the object is to complete a 9 by 9
grid by filling in number from 1 to 9 such that no number appears
twice in any row, column, or 3 by 3 box.  A puzzle is partially
filled in at the start.  See http://www.sudoku.com/

This program solves Sudoku puzzles.  This applet displays a 9 by 9 
grid and 4 buttons at the bottom: Guess, Hint, Solve, Clear.
The user enters a puzzle by clicking on the boxes in the 9 by 9 grid 
or typing in the numbers.  Only numbers which can legally appear can
be entered.  Buttons work as follows:

Guess: fills in a random blank spot with a random number, provided
it is legal.  There is no guarantee that the result will have a 
solution.

Hint: adds one more number which can be definitely placed, if possible,
or else does nothing.  If successful, the new number is highlighted
in yellow and the button also turns yellow.  If it fails, the button
turns gray.  If the puzzle is solved, the button turns green.
If no solution is possible, the button turns red.

Solve: Tries to solve the puzzle.  If successful, all the numbers
are filled in and the button turns green.  If there is more than
one solution, only the first one found is displayed.  If no solution
is possible, the button turns red.  If it takes too long, the
button turns orange.  Try entering a few more numbers.

Clear: erases all numbers and turns the buttons gray.

Numbers can be entered with the mouse.  A left click counts up and
right counts down, skipping illegal numbers.  Clicking the mouse
also positions the cursor (highlighted in yellow) allowing numbers
to be typed in.  Illegal numbers are entered as spaces.  Any nonnumeric
key enters a space and advances the cursor.  The cursor can be moved
with the arrow keys.  The backspace and delete keys erase the last
entry.
*/

import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.util.Random;

public class Sudoku extends Applet implements ActionListener,
    MouseListener, KeyListener {

  // Buttons along the bottom of the 9 by 9 grid
  Panel buttonPanel=new Panel();
  Button guessButton=new Button("Guess");
  Button hintButton=new Button("Hint");
  Button solveButton=new Button("Solve");
  Button clearButton=new Button("Clear");

  int width, height;  // Grid dimensions in pixels
  int[][] puzzle=new int[9][9];  // Number in grid, 0 = blank
  Graphics gr;  // global graphics
  int solveCount=0;  // Number of iterations of solve()
  int cursor=-1;  // if 0-80, position on 9x9 grid

  // Build the GUI
  public void init() {
    width=getBounds().width-3;  // Grid dimensions
    height=getBounds().height*5/6-3;
    setBackground(Color.WHITE);
    setLayout(new BorderLayout());
    add("South", buttonPanel);
    buttonPanel.setLayout(new FlowLayout());
    setFont(new Font("SansSerif", Font.BOLD, width/12));
    buttonPanel.setFont(new Font("SanSerif", Font.BOLD, 14));
    buttonPanel.add(guessButton);
    guessButton.addActionListener(this);
    guessButton.setBackground(Color.GRAY);
    buttonPanel.add(hintButton);
    hintButton.addActionListener(this);
    hintButton.setBackground(Color.GRAY);
    buttonPanel.add(solveButton);
    solveButton.addActionListener(this);
    solveButton.setBackground(Color.GRAY);
    buttonPanel.add(clearButton);
    clearButton.addActionListener(this);
    clearButton.setBackground(Color.GRAY);
    addMouseListener(this);
    addKeyListener(this);
    gr=getGraphics();
  }

  // Return values for hint() and solve()
  final int SOLVED=1;  // return value if no blanks remain in puzzle
  final int HINTED=2;  // return value if a number is added unambiguously
  final int CANT_HINT=3;  // return value if there is no square that
    // can be filled with only one legal value
  final int CANT_SOLVE=4;  // return value if there are blanks for which
    // no number could be legally placed, or there is a row, column
    // or 3x3 box and a number not already in that region that cannot
    // be legally placed in any of the remaining blank spots.
  final int TIMEOUT=5;  // return value if solve() takes too long.

  final int SOLVE_LIMIT=1000;  // max iterations until timeout

  // Draw the puzzle
  public void paint(Graphics g) {

    // Draw cursor
    if (cursor>=0 && cursor<81) {
      g.setColor(Color.YELLOW);
      g.fillRect(cursor%9*width/9, cursor/9*height/9, width/9, height/9);
      g.setColor(Color.BLACK);
    }

    // Draw the grid lines
    g.setColor(Color.BLACK);
    for (int i=0; i<=9; ++i) {
      g.drawLine(0, height*i/9, width, height*i/9);  // horizontal
      g.drawLine(width*i/9, 0, width*i/9, height);  // vertical
      if (i%3==0) {  // draw bold lines around 3x3 boxes
        g.drawLine(0, height*i/9+1, width, height*i/9+1);
        g.drawLine(0, height*i/9+2, width, height*i/9+2);
        g.drawLine(width*i/9+1, 0, width*i/9+1, height);
        g.drawLine(width*i/9+2, 0, width*i/9+2, height);
      }
    }

    // Fill in the numbers
    for (int i=0; i<9; ++i) {
      for (int j=0; j<9; ++j) {
        if (puzzle[i][j]>0) {
          g.drawString(puzzle[i][j]+"", 
            width*(j*3+1)/27, height*(i*5+4)/45);
        }
      }
    }
  }

  // Bye bye
  public void destroy() {
    gr.dispose();
  }

  // Respond to button press
  public void actionPerformed(ActionEvent e) {

    // Clear: Erase all numbers
    if (e.getSource()==clearButton) {
      for (int i=0; i<9; ++i)
        for (int j=0; j<9; ++j)
          puzzle[i][j]=0;
      colorButton(solveButton, CANT_HINT);
      colorButton(hintButton, CANT_HINT);
      cursor=-1;
    }

    // Hint: Find a square where only one number will fit.  Color the
    // button according to result.
    else if (e.getSource()==hintButton) {
      int result=hint(puzzle);
      colorButton(hintButton, result);
    }

    // Solve: Try to solve the puzzle, color button according to result.
    else if (e.getSource()==solveButton) {
      solveCount=0;
      int[][] newPuzzle = new int[9][9];
      copy(puzzle, newPuzzle);
      colorButton(solveButton, solve(newPuzzle));
      cursor=-1;
    }

    // New: create a new puzzle
    else if (e.getSource()==guessButton) {
      Random rnd=new Random();
      for (int i=0; i<1000; ++i) {
        int x=(rnd.nextInt()&0xfffffff)%9;
        int y=(rnd.nextInt()&0xfffffff)%9;
        int val=(rnd.nextInt()&0xfffffff)%9+1;
        if (puzzle[x][y]==0 && isLegal(x, y, val, puzzle)) {
          puzzle[x][y]=val;
          break;
        }
      }
    }

    repaint();
  }

  // Change button background color: solved=green, hinted=yellow,
  // cant_hint=gray, cant_solve=red, timeout=orange
  void colorButton(Button button, int colorcode) {
    Color[] table = {
      Color.BLACK, Color.GREEN, Color.YELLOW, Color.GRAY, Color.RED,
        Color.ORANGE};
    button.setBackground(table[colorcode]);
  }

  // Ignore mouse entry, exit, click, release  
  public void mouseEntered(MouseEvent e) {}
  public void mouseExited(MouseEvent e) {}
  public void mouseReleased(MouseEvent e) {}
  public void mouseClicked(MouseEvent e) {}

  // When the mouse is pressed in a square, change the number to the 
  // next value (left button) or previous value (right button).
  // Put the cursor there.
  public void mousePressed(MouseEvent e) {
    int x = e.getX()*9/width;  // coordinates of square clicked
    int y = e.getY()*9/height;
    if (x<0 || x>=9 || y<0 || y>=9)
      return;
    do {
      cursor=y*9+x;
      if (e.isMetaDown())  // right button, count down
        puzzle[y][x] = (puzzle[y][x] + 9) % 10;
      else
        puzzle[y][x] = (puzzle[y][x] + 1) % 10;
    } while (!isLegal(y, x));
    colorButton(solveButton, CANT_HINT);
    repaint();
    requestFocus();
  }

  // Respond to arrow keys by moving the cursor
  public void keyPressed(KeyEvent e) {
    switch(e.getKeyCode()) {
      case KeyEvent.VK_UP:    cursor=(cursor+72)%81; break;
      case KeyEvent.VK_DOWN:  cursor=(cursor+9 )%81; break;
      case KeyEvent.VK_LEFT:  cursor=(cursor+80)%81; break;
      case KeyEvent.VK_RIGHT: cursor=(cursor+1 )%81; break;
      case KeyEvent.VK_BACK_SPACE:  // back up and erase
      case KeyEvent.VK_DELETE:
        cursor=(cursor+80)%81;
        puzzle[cursor/9][cursor%9]=0;
        break;
      default: return;
    }
    repaint();
  }

  // Respond to number keys by entering the number at the cursor 
  // if legal, or else entering a space.  Then advance the cursor.
  public void keyTyped(KeyEvent e) {
    if (cursor<0 || cursor>80)
      return;
    char c=e.getKeyChar();
    int digit=0;
    if (c>='1' && c<='9')
      digit=c-'0';
    if (!isLegal(cursor/9, cursor%9, digit, puzzle))
      digit=0;
    puzzle[cursor/9][cursor%9]=digit;
    if (c>=32)
      cursor=(cursor+1)%81;  // advance cursor
    repaint();
  }

  // Ignore key release
  public void keyReleased(KeyEvent e) {}

  // Test whether val is legal at puzzle[y][x]
  boolean isLegal(int y, int x, int val, int[][] puzzle) {
    if (val==0)  // blank is OK
      return true;
    for (int i=0; i<9; ++i) {  // test for val in row and column
      if (i!=x && puzzle[y][i]==val)
        return false;
      if (i!=y && puzzle[i][x]==val)
        return false;
    }
    for (int i=y/3*3; i<y/3*3+3; ++i)  // test for val in 3x3 box
      for (int j=x/3*3; j<x/3*3+3; ++j)
        if (i!=y && j!=x && puzzle[i][j]==val)
          return false;
    return true;
  }

  // Test whether the number at puzzle[x][y] is legal
  boolean isLegal(int y, int x) {
    return isLegal(y, x, puzzle[y][x], puzzle);
  }

  // Try to fill in one blank square in puzzle
  int hint(int[][] puzzle) {

    // First check if any blank spots have only one legal value
    boolean foundBlank = false;
    for (int i=0; i<9; ++i) {
      for (int j=0; j<9; ++j) {
        if (puzzle[i][j]==0) {
          foundBlank = true;
          int val=0;  // 1-9 if only val, 10 if more than one possible
          for (int k=1; k<=9; ++k) {
            if (isLegal(i, j, k, puzzle)) {
              if (val==0)
                val=k;
              else if (val>0) {
                val=10;
                break;
              }
            }
          }
          if (val==0)
            return CANT_SOLVE;
          else if (val<10) {
            puzzle[i][j] = val;
            cursor=i*9+j;
            return HINTED;
          }
        }
      }
    }
    if (!foundBlank)
      return SOLVED;

    // Next, check each region (row, column, 3x3 box) for numbers
    // not already placed that can only go in one place.
    for (int i=1; i<=9; ++i) {  // number to test
      for (int j=0; j<9; ++j) {  // row
        int k;
        for (k=0; k<9; ++k)  // test if i is in this row
          if (puzzle[j][k]==i)
            break;
        if (k==9) {  // no, test if only one blank spot will take i
          int pos=-1;  // 0-8 = where, 9 = more than one place is legal
          for (k=0; k<9; ++k) {
            if (puzzle[j][k]==0 && isLegal(j, k, i, puzzle)) {
              if (pos==-1)
                pos = k;
              else if (pos>=0) {
                pos = 9;
                break;
              }
            }
          }
          if (pos==-1)
            return CANT_SOLVE;
          else if (pos<9) {
            cursor=j*9+pos;
            puzzle[j][pos] = i;
            return HINTED;
          }
        }
      }

      // Test columns
      for (int j=0; j<9; ++j) {  // column
        int k;
        for (k=0; k<9; ++k)  // test if i is in this column
          if (puzzle[k][j]==i)
            break;
        if (k==9) {  // no, test if only one blank spot will take i
          int pos=-1;  // 0-8 = where, 9 = more than one place is legal
          for (k=0; k<9; ++k) {
            if (puzzle[k][j]==0 && isLegal(k, j, i, puzzle)) {
              if (pos==-1)
                pos = k;
              else if (pos>=0) {
                pos = 9;
                break;
              }
            }
          }
          if (pos==-1)
            return CANT_SOLVE;
          else if (pos<9) {
            cursor=pos*9+j;
            puzzle[pos][j] = i;
            return HINTED;
          }
        }
      }

      // Test 3x3 box
      for (int jx=0; jx<9; jx+=3) {  // box x,y coordinates (0, 3, or 6)
        for (int jy=0; jy<9; jy+=3) {
          int k;
          for (k=0; k<9; ++k)  // test if i is in box
            if (puzzle[jx+k/3][jy+k%3]==i)
              break;
          if (k==9) {  // no, test if only one blank spot will take i
            int pos=-1;  // 0-8 = where, 9 = more than one place is legal
            for (k=0; k<9; ++k) {
              int kx=jx+k/3;  // x,y position within box (0,0 to 2,2)
              int ky=jy+k%3;
              if (puzzle[kx][ky]==0 && isLegal(kx, ky, i, puzzle)) {
                if (pos==-1)
                  pos = k;
                else if (pos>=0) {
                  pos = 9;
                  break;
                }
              }
            }
            if (pos==-1)
              return CANT_SOLVE;
            else if (pos<9) {
              cursor=(jx+pos/3)*9+(jy+pos%3);
              puzzle[jx+pos/3][jy+pos%3] = i;
              return HINTED;
            }
          }
        }
      }
    }
    return CANT_HINT;
  }

  // Copy a puzzle
  void copy(int[][] from, int[][] to) {
    for (int i=0; i<9; ++i)
      for (int j=0; j<9; ++j)
        to[i][j]=from[i][j];
  }

  // Solve the puzzle, return SOLVED, CANT_SOLVE, or TIMEOUT
  int solve(int[][] puzzleIn) {

    // Time limit exceeded?
    copy(puzzleIn, puzzle);
    if (++solveCount>=SOLVE_LIMIT)
      return TIMEOUT;

    // Show that we're working
    update(gr);

    // Fill in as many squares as possible
    int result;
    do {
      result=hint(puzzleIn);
    } while (result==HINTED);

    // If solved, update puzzle with solution
    if (result==SOLVED) {
      copy(puzzleIn, puzzle);
      return SOLVED;
    }

    // Depth first search
    if (result==CANT_HINT) {
      for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
          if (puzzleIn[i][j]==0) {
            for (int k=1; k<=9; ++k) {
              if (isLegal(i, j, k, puzzle)) {
                int[][] guess=new int[9][9];
                copy(puzzleIn, guess);
                guess[i][j]=k;
                int r=solve(guess);
                if (r==TIMEOUT)
                  copy(puzzleIn, puzzle);
                if (r==SOLVED || r==TIMEOUT)
                  return r;
              }
            }
          }
        }
      }
    }               
    return CANT_SOLVE;
  }
}