public class Puzzle { private int[][][] foo = new int[9][9][10]; public Puzzle(int[][][] known) { copy_knowns(known); } public Puzzle() { init_planes(); foo[5][0][0] = 1; foo[7][0][0] = 2; foo[8][0][0] = 7; foo[3][1][0] = 4; foo[1][2][0] = 8; foo[6][2][0] = 6; foo[7][2][0] = 9; foo[2][3][0] = 3; foo[3][3][0] = 1; foo[4][3][0] = 2; foo[0][4][0] = 1; foo[3][4][0] = 7; foo[5][4][0] = 3; foo[8][4][0] = 5; foo[4][5][0] = 8; foo[5][5][0] = 6; foo[6][5][0] = 1; foo[1][6][0] = 5; foo[2][6][0] = 1; foo[7][6][0] = 8; foo[5][7][0] = 4; foo[0][8][0] = 2; foo[1][8][0] = 7; foo[3][8][0] = 9; } private void copy_knowns(int[][][] known) { int x = 0; int y = 0; int z = 0; for (x = 0; x < 9; x++) { for(y = 0; y < 9; y++) { for(z = 0; z < 10; z++) foo[x][y][z] = known[x][y][z]; } } } public void setCube(int[][][] known) { copy_knowns(known); } public int[][][] getCube() { return (foo); } public void setKnown(int x, int y, int known) { foo[x][y][0] = known; } public int getKnown(int x, int y) { return (foo[x][y][0]); } // Initially populates the planes with their respective symbols. // These planes will be pruned away by other functions in the program // until only the answers remain. private void init_planes() { int x = 0; int y = 0; int z = 1; for (x = 0; x < 9; x++) { for(y = 0; y < 9; y++) { for(z = 0; z < 10; z++) foo[x][y][z] = z; } } } public int auto_advance() { int cycles = 0; int z = 0; int t_z_1 = 0; int t_z_2 = 0; int density = 0; Puzzle test1 = new Puzzle(foo); Puzzle test2 = new Puzzle(foo); while ((prune_possibilities() > 0) && (collapse_into_zero() > 0)) { cycles++; } if (test_sudoku() == 1) { for (int y = 0; y < 9; y++) { for(int x = 0; x < 9; x++) { if (foo[x][y][0] == 0) { for(z = 1; z < 10; z++) { if (foo[x][y][z] != 0) { density++; t_z_2 = z; } } } else density = 0; if (density == 2) { z = 1; Sudoku.count_guess(2); while(t_z_1 == 0) { if (foo[x][y][z] != 0) t_z_1 = z; else z++; } test1.setKnown(x, y, t_z_1); test2.setKnown(x, y, t_z_2); if (test1.auto_advance() == 0) { copy_knowns(test1.getCube()); return 0; } if (test2.auto_advance() == 0) { copy_knowns(test2.getCube()); return 0; } } density = 0; } } } return test_sudoku(); } // This is the root-routine of a group of functions that is designed to discard // symbols from the nth level, where n is any level other than the 0th. private int prune_possibilities() { int matches = 0; for(int target = 1; target <= 9; target++) { for(int x = 0; x < 9; x++) { for(int y = 0; y < 9; y++) { if (foo[x][y][0] == 0) { if (check_box(x, y, 0, target) != 0) matches += prune_box(x, y, target); if (check_row(y, 0, target) != 0) matches += prune_row(y, target); if (check_col(x, 0, target) != 0) matches += prune_col(x, target); } else matches += kill_trunk(x, y); } } } return matches; } // This function is the root of a group of functions that looks for symbols that // prune_possibilities has isolated as correct. It then collapses these symbols // into the 0th plane, thereby giving them the status of 'correct answer'. private int collapse_into_zero() { int x = 0; int y = 0; int z = 0; int target = 0; int candidates = 0; int collapsed = 0; for(x = 0; x < 9; x++) { for(y = 0; y < 9; y++) { z = 0; if (foo[x][y][z] == 0) { candidates = 0; for(z = 1; z <= 9; z++) { if ((check_box(x, y, z, z) == 1) && (foo[x][y][z] == z)) { copy_to_0th(x, y, z); collapsed++; } } for(z = 1; z <= 9; z++) { if (foo[x][y][z] != 0) { candidates++; target = z; } } if(candidates == 1) { copy_to_0th(x, y, target); candidates = 0; collapsed++; } } } } return collapsed; } private int copy_to_0th(int x, int y, int target) { foo[x][y][0] = target; return kill_trunk(x, y); } // This function evaluates the 0th plane to determine if the puzzle has been // solved and if so, if it was solved correctly. Returns 1 on failure. public int test_sudoku() { int temp1 = 0; int x = 0; int y = 0; for (x = 0; x < 9; x++) { for(y = 0; y < 9; y++) { if (foo[x][y][0] == 0) return 1; } } for (x = 0; x < 9; x++) { for(y = 0; y < 9; y++) { temp1 += foo[x][y][0]; } if (temp1 != 45) return 1; temp1 = 0; } for (y = 0; y < 9; y++) { for(x = 0; x < 9; x++) { temp1 += foo[x][y][0]; } if (temp1 != 45) return 1; temp1 = 0; } return 0; } // This function will check for a given symbol (target) in every row of the 0th plane. // Function returns the number of matches found. private int check_row(int row, int z, int target) { int matches = 0; for(int x = 0; x < 9; x++) { if(foo[x][row][z] == target) matches++; } return matches; } // This function will check for a given symbol (target) in every columb of the 0th plane. // Function returns the number of matches found. private int check_col(int col, int z, int target) { int matches = 0; for(int y = 0; y < 9; y++) { if(foo[col][y][z] == target) matches++; } return matches; } // This function will check the 0th plane of the cube to determine if a // given symbol (target) cannot occupy a space in the box. private int check_box(int col, int row, int z, int target) { int matches = 0; int rsection = row / 3 * 3; int csection = col / 3 * 3; for(int x = 0; x < 3; x++) { for(int y = 0; y < 3; y++) { if(foo[x+csection][y+rsection][z] == target) matches++; } } return matches; } // This function prunes a row of the nth (target) plane of possible options. private int prune_row(int row, int target) { for(int x = 0; x < foo.length; x++) { if(foo[x][row][0] != target) foo[x][row][target] = 0; } return 1; } // This function prunes a columb of the nth (target) plane of possible options. private int prune_col(int col, int target) { for(int y = 0; y < foo.length; y++) { if(foo[col][y][0] != target) foo[col][y][target] = 0; } return 1; } // If there exists a symbol in a given box at the 0th plane, this function will // remove all other possible symbols from that box on the symbol's plane. private int prune_box(int col, int row, int target) { int rsection = row / 3 * 3; int csection = col / 3 * 3; for(int x = csection; x < csection+3; x++) { for(int y = rsection; y < rsection+3; y++) { if(foo[x][y][0] != target) foo[x][y][target] = 0; } } return 1; } // This function eliminates all of the possible symbols that exist in the // nth plane above plane zero. All of the symbols except the known correct one. private int kill_trunk(int x, int y) { int target = foo[x][y][0]; for(int z = 1; z <= 9; z++) { foo[x][y][z] = 0; } foo[x][y][target] = target; return 1; } /************************************************************************************ * * * The functions below aren't useful for anything other than printing outputs * * * ************************************************************************************/ // This fuction returns nothing, but issues a printout of the requested plane. public void print_plane(int z) { System.out.println("Plane " + z); System.out.println("-------------------"); for(int y = 0; y < 9; y++) { for(int x = 0; x < 9; x++) { System.out.print(foo[x][y][z]+" "); if ((x+1) % 3 == 0) System.out.print(" "); } System.out.println(""); if ((y+1) % 3 == 0) System.out.println(""); } System.out.println("\n"); } // This fuction returns nothing, but issues a printout of the entire cube. public void print_sudoku() { for(int y = 0; y < 27; y++) { for(int x = 0; x < 27; x++) { System.out.print(foo[x%9][y%9][1+(3*(y/9))+(x/9)]+" "); if ((x+1) % 3 == 0) System.out.print(" "); if ((x+1) % 9 == 0) System.out.print(" "); } System.out.println(""); if ((y+1) % 3 == 0) System.out.println(""); if ((y+1) % 9 == 0) System.out.println(""); } print_plane(0); } // Returns nothing, and prints a matrix that represents the number of possible valid // answers for each cell. public void print_u_density() { int x = 0; int y = 0; int z = 1; int density = 0; for (y = 0; y < 9; y++) { for(x = 0; x < 9; x++) { if (foo[x][y][0] == 0) { for(z = 1; z < 10; z++) { if (foo[x][y][z] != 0) density++; } } else density = 0; System.out.print(density + " "); if ((x+1) % 3 == 0) System.out.print(" "); density = 0; } System.out.println(""); if ((y+1) % 3 == 0) System.out.println(" "); } } }