SHOW:
|
|
- or go back to the newest paste.
| 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 | grid[row][col] = digit; | |
| 56 | } | |
| 57 | ||
| 58 | public void UnassignFromGrid(int row, int col, int digit) {
| |
| 59 | AssignDigitToColumn(digit, col, 0); | |
| 60 | AssignDigitToRow(digit, row, 0); | |
| 61 | AssignDigitToBox(digit, boxFromPosition(row, col), 0); | |
| 62 | grid[row][col] = 0; | |
| 63 | } | |
| 64 | ||
| 65 | public boolean isDigitAssigned(int row, int col, int digit) {
| |
| 66 | return isDigitOnRow(row, digit) || isDigitOnCol(col, digit) | |
| 67 | || isDigitOnBox(boxFromPosition(row, col), digit); | |
| 68 | } | |
| 69 | private void search(int row, int col) {
| |
| 70 | if (row == 9) {
| |
| 71 | solved = Arrays.copyOf(grid, 9); | |
| 72 | solved = true; | |
| 73 | return; | |
| 74 | } | |
| 75 | if (solution[row][col] != 0) {
| |
| 76 | if (col == 8) | |
| 77 | search(row + 1, 0); | |
| 78 | else | |
| 79 | search(row, col + 1); | |
| 80 | return; | |
| 81 | } | |
| 82 | for (int digits = 1; digits < 10; digits++) {
| |
| 83 | if (!isDigitAssigned(row, col, digits)) {
| |
| 84 | AssignToGrid(row, col, digits); | |
| 85 | if (col == 8) | |
| 86 | search(row + 1, 0); | |
| 87 | else | |
| 88 | search(row, col + 1); | |
| 89 | UnassignFromGrid(row, col, digits); | |
| 90 | } | |
| 91 | - | public void solve() {
|
| 91 | + | |
| 92 | } | |
| 93 | ||
| 94 | public int[][] solve() {
| |
| 95 | search(0, 0); | |
| 96 | return solved; | |
| 97 | } | |
| 98 | } |
