Advertisement
Guest User

Sudoku

a guest
Jun 8th, 2012
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.26 KB | None | 0 0
  1. public class Solver {
  2.  
  3.     int[][] grid        = new int[9][9];
  4.     int[][] solution    = new int[9][9];
  5.  
  6.     int[][] colDigits   = new int[9][9];
  7.     int[][] rowDigits   = new int[9][9];
  8.     int[][] boxDigits   = new int[9][9];
  9.  
  10.     boolean solved      = false;
  11.  
  12.     public Solver(int[][] table) {
  13.         solved = false;
  14.         for (int i = 0; i < 9; i++) {
  15.             for (int j = 0; j < 9; j++) {
  16.                 if (table[i][j] != 0)
  17.                     AssignToGrid(i, j, table[i][j]);
  18.                 grid[i][j] = table[i][j];
  19.             }
  20.         }
  21.     }
  22.  
  23.     private boolean isDigitOnRow(int row, int digit) {
  24.         return colDigits[row][digit - 1] != 0;
  25.     }
  26.  
  27.     private boolean isDigitOnCol(int col, int digit) {
  28.         return rowDigits[col][digit - 1] != 0;
  29.     }
  30.  
  31.     private boolean isDigitOnBox(int box, int digit) {
  32.         return boxDigits[box][digit - 1] != 0;
  33.     }
  34.  
  35.     private int boxFromPosition(int row, int col) {
  36.         return (row / 3) * 3 + col / 3;
  37.     }
  38.  
  39.     private void AssignDigitToColumn(int digit, int col, int set) {
  40.         rowDigits[col][digit - 1] = set;
  41.     }
  42.  
  43.     public void AssignDigitToRow(int digit, int row, int set) {
  44.         colDigits[row][digit - 1] = set;
  45.     }
  46.  
  47.     public void AssignDigitToBox(int digit, int box, int set) {
  48.         boxDigits[box][digit - 1] = set;
  49.     }
  50.  
  51.     public void AssignToGrid(int row, int col, int digit) {
  52.         AssignDigitToColumn(digit, col, 1);
  53.         AssignDigitToRow(digit, row, 1);
  54.         AssignDigitToBox(digit, boxFromPosition(row, col), 1);
  55.     }
  56.  
  57.     public void UnassignFromGrid(int row, int col, int digit) {
  58.         AssignDigitToColumn(digit, col, 0);
  59.         AssignDigitToRow(digit, row, 0);
  60.         AssignDigitToBox(digit, boxFromPosition(row, col), 0);
  61.     }
  62.  
  63.     public boolean isDigitAssigned(int row, int col, int digit) {
  64.         return isDigitOnRow(row, digit) || isDigitOnCol(col, digit)
  65.             || isDigitOnBox(boxFromPosition(row, col), digit);
  66.     }
  67.     private void search(int row, int col) {
  68.         if (row == 9) {
  69.             solved = true;
  70.             return;
  71.         }
  72.         if (solution[row][col] != 0) {
  73.             if (col == 8)
  74.                 search(row + 1, 0);
  75.             else
  76.                 search(row, col + 1);
  77.             return;
  78.         }
  79.         for (int digits = 1; digits < 10; digits++) {
  80.             if (!isDigitAssigned(row, col, digits)) {
  81.                 AssignToGrid(row, col, digits);
  82.                 if (col == 8)
  83.                     search(row + 1, 0);
  84.                 else
  85.                     search(row, col + 1);
  86.                 UnassignFromGrid(row, col, digits);
  87.             }
  88.         }
  89.     }
  90.  
  91.     public void solve() {
  92.         search(0, 0);
  93.     }
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement