Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.lang.Math;
- import java.util.ArrayList;
- public class Board {
- private int[][] board;
- private boolean valid;
- private boolean[][] perms;
- public Board() {
- board = new int[9][9];
- boolean success = false;
- //this.generateNewBoard();
- while (!success) {
- try {
- //System.out.println("Attempting to generate board...");
- success = this.generateNewBoard();
- if (success) {
- //System.out.println("Board successfully generated!");
- }
- } catch (Exception ignore) {}
- }
- setPerms();
- validate();
- }
- public Board(Board b) {
- board = new int[9][9];
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- board[x][y] = b.getValue(x, y);
- }
- }
- setPerms();
- validate();
- }
- public Board(Board b, boolean[][] p) {
- board = new int[9][9];
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- board[x][y] = b.getValue(x, y);
- }
- }
- perms = p;
- validate();
- }
- public Board(String b) {
- board = new int[9][9];
- int n = 0;
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- board[x][y] = Integer.parseInt(b.substring(n, n+1));
- n++;
- }
- }
- setPerms();
- validate();
- }
- public String toString() {
- String result = "";
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- if (board[x][y] > 0) {
- result += "" + board[x][y];
- } else {
- result += " ";
- }
- if (x == 2 || x == 5) {
- result += " ";
- }
- }
- result += "\n";
- if (y == 2 || y == 5) {
- result += "\n";
- }
- }
- return result;
- }
- public String getBoardCode() {
- String result = "";
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- result += "" + board[x][y];
- }
- }
- return result;
- }
- public boolean validate() {
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- int total = 0;
- if (board[x][y] == 0) {
- valid = false;
- return false;
- }
- for (int i = 0; i < 9; i++) {
- if (board[x][i] == board[x][y]) {
- total++;
- }
- if (board[i][y] == board[x][y]) {
- total++;
- }
- if (board[(x/3)*3+i%3][(y/3)*3+i/3] == board[x][y]) {
- total++;
- }
- }
- if (total != 3) {
- valid = false;
- return false;
- }
- }
- }
- valid = true;
- return true;
- }
- public boolean isValid() {
- return valid;
- }
- public int getValue(int x, int y) {
- return board[x][y];
- }
- public void puzzle(int difficulty) {
- ArrayList<int[]> coords = new ArrayList<int[]>();
- ArrayList<int[]> rejectedCoords = new ArrayList<int[]>();
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- coords.add(new int[] {x, y});
- }
- }
- switch (difficulty) {
- case 1:
- while (coords.size() > 36) {
- int[] choice = coords.remove((int)(Math.random()*coords.size()));
- //System.out.println("Removing " + board[choice[0]][choice[1]] + " from board at: " + choice[0] + ":" + choice[1]);
- int temp = board[choice[0]][choice[1]];
- board[choice[0]][choice[1]] = 0;
- int[][] tempBoard = copyBoard();
- boolean test = solve();
- board = tempBoard;
- if (!test) {
- board[choice[0]][choice[1]] = temp;
- break;
- }}
- break;
- case 2:
- while (coords.size() > 31) {
- int[] choice = coords.remove((int)(Math.random()*coords.size()));
- //System.out.println("Removing " + board[choice[0]][choice[1]] + " from board at: " + choice[0] + ":" + choice[1]);
- int temp = board[choice[0]][choice[1]];
- board[choice[0]][choice[1]] = 0;
- int[][] tempBoard = copyBoard();
- boolean test = solve();
- board = tempBoard;
- if (!test) {
- board[choice[0]][choice[1]] = temp;
- break;
- }}
- break;
- case 3:
- while (coords.size() > 0) {
- int[] choice = coords.remove((int)(Math.random()*coords.size()));
- //System.out.println("Removing " + board[choice[0]][choice[1]] + " from board at: " + choice[0] + ":" + choice[1]);
- int temp = board[choice[0]][choice[1]];
- board[choice[0]][choice[1]] = 0;
- int[][] tempBoard = copyBoard();
- boolean test = solve();
- board = tempBoard;
- if (!test) {
- board[choice[0]][choice[1]] = temp;
- }}
- break;
- case 4:
- while (coords.size() > 0) {
- int[] choice = coords.remove((int)(Math.random()*coords.size()));
- //System.out.println("Removing " + board[choice[0]][choice[1]] + " from board at: " + choice[0] + ":" + choice[1]);
- int temp = board[choice[0]][choice[1]];
- board[choice[0]][choice[1]] = 0;
- int[][] tempBoard = copyBoard();
- boolean test = solve();
- board = tempBoard;
- if (!test) {
- board[choice[0]][choice[1]] = temp;
- rejectedCoords.add(choice);
- }}
- for (int i = 0; i < 1; i++) {
- int[] choice = rejectedCoords.remove((int)(Math.random()*rejectedCoords.size()));
- board[choice[0]][choice[1]] = 0;
- }
- break;
- case 5:
- while (coords.size() > 0) {
- int[] choice = coords.remove((int)(Math.random()*coords.size()));
- //System.out.println("Removing " + board[choice[0]][choice[1]] + " from board at: " + choice[0] + ":" + choice[1]);
- int temp = board[choice[0]][choice[1]];
- board[choice[0]][choice[1]] = 0;
- int[][] tempBoard = copyBoard();
- boolean test = solve();
- board = tempBoard;
- if (!test) {
- board[choice[0]][choice[1]] = temp;
- rejectedCoords.add(choice);
- }}
- for (int i = 0; i < 2; i++) {
- int[] choice = rejectedCoords.remove((int)(Math.random()*rejectedCoords.size()));
- board[choice[0]][choice[1]] = 0;
- }
- break;
- }
- setPerms();
- //board = tempBoard;
- }
- public void setPerms() {
- perms = new boolean[9][9];
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- //System.out.println(b.getValue(x, y));
- if (board[x][y] == 0) {
- perms[x][y] = true;
- } else {
- perms[x][y] = false;
- }
- }
- }
- }
- public boolean[][] getPerms() {
- return perms;
- }
- public boolean getPerm(int x, int y) {
- return perms[x][y];
- }
- public void reset() {
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- if (perms[x][y]) {
- board[x][y] = 0;
- }
- }
- }
- }
- public void setValue(int x, int y, int val) {
- board[x][y] = val;
- }
- private int[][] copyBoard() {
- int[][] response = new int[9][9];
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- response[x][y] = board[x][y];
- }
- }
- return response;
- }
- public boolean solve() {
- boolean[][][] pNums = new boolean[9][9][9];
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- for (int i = 0; i < 9; i++) {
- pNums[x][y][i] = (board[x][y] == 0 || board[x][y] == i);
- }
- }
- }
- while (!validate()) {
- boolean changed = false;
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- if (board[x][y] == 0) {
- if (eliminateImpossible(x, y, pNums)) {
- changed = true;
- }
- }
- }
- }
- if (!changed) {
- return false;
- }
- }
- return true;
- }
- private boolean eliminateImpossible(int x, int y, boolean[][][] pNums) {
- for (int i = 0; i < 9; i++) {
- if (board[x][i] > 0) {
- pNums[x][y][board[x][i]-1] = false;
- }
- if (board[i][y] > 0) {
- pNums[x][y][board[i][y]-1] = false;
- }
- if (board[(x/3)*3+i%3][(y/3)*3+i/3] > 0) {
- pNums[x][y][board[(x/3)*3+i%3][(y/3)*3+i/3]-1] = false;
- }
- }
- int t = 0;
- int n = -1;
- for (int i = 0; i < 9; i++) {
- if (pNums[x][y][i]) {
- t++;
- n = i;
- }
- }
- if (t == 1) {
- //System.out.println("Number " + (n+1) + " isolated at: " + x + ":" + y);
- board[x][y] = n+1;
- return true;
- } else if (t == 0) {
- //System.err.println("ERROR: No available choices at: " + x + ":" + y);
- }
- return false;
- }
- public boolean generateNewBoard() {
- board = new int[9][9];
- boolean[][][] pNums = new boolean[9][9][9];
- for (int y = 0; y < 9; y++) {
- for (int x = 0; x < 9; x++) {
- for (int i = 0; i < 9; i++) {
- pNums[x][y][i] = true;
- }
- }
- }
- for (int i = 0; i < 9; i++) {
- //System.out.println("Isolating number: " + (i+1) + "...");
- //keeps tabs on which cels have been scanned
- //0 = isolate, 1 = lines, 2 = holes
- boolean[][] scanTab = {{true, true, true, true, true, true, true, true, true}, {true, true, true, true, true, true, true, true, true}};
- scanBoard(i, pNums, scanTab);
- while (!checkIsoTab(scanTab[0])) {
- chooseNextNumber(i, scanTab[0], pNums);
- scanBoard(i, pNums, scanTab);
- }
- //System.out.println("Number " + (i+1) + " isolated.");
- //System.out.println(this.toString());
- }
- return true;
- }
- private boolean checkIsoTab(boolean[] isoTab) {
- for (boolean b: isoTab) {
- if (b) {
- return false;
- }
- }
- return true;
- }
- private void chooseNextNumber(int num, boolean[] isoTab, boolean[][][] pNums) {
- for (int i = 0; i < 9; i++) {
- if (isoTab[i]) {
- //System.out.println("Scanning complete. Randomizing next available sector...");
- int[][] options = getAvailableCells(i, num, pNums);
- int[] choice = options[(int)(Math.random()*(options.length))];
- isolateNumber(choice[0], choice[1], num, pNums, isoTab);
- break;
- }
- }
- }
- private int[][] getAvailableCells(int sector, int num, boolean[][][] pNums) {
- ArrayList<int[]> coords = new ArrayList<int[]>();
- for (int v = 0; v < 3; v++) {
- for (int i = 0; i < 3; i++) {
- if (pNums[(sector%3)*3+i][(sector/3)*3+v][num]) {
- coords.add(new int[] {(sector%3)*3+i, (sector/3)*3+v});
- }
- }
- }
- return coords.toArray(new int[coords.size()][2]);
- }
- private void isolateNumber(int x, int y, int num, boolean[][][] pNums, boolean[] isoTab) {
- isoTab[getSectorFromCoords(x, y)] = false;
- for (int i = 0; i < 9; i++) {
- pNums[x][i][num] = false;
- pNums[i][y][num] = false;
- pNums[x][y][i] = false;
- pNums[(x/3)*3+i%3][(y/3)*3+i/3][num] = false;
- }
- pNums[x][y][num] = true;
- board[x][y] = num+1;
- //System.out.println("Isolated sector: " + getSectorFromCoords(x, y));
- }
- private void scanBoard(int num, boolean[][][] pNums, boolean[][] scanTab) {
- boolean clean = false;
- //System.out.println("Scanning...");
- checkLines(num, pNums, scanTab, false);
- checkIsolate(num, pNums, scanTab, true);
- }
- private void checkIsolate(int num, boolean[][][] pNums, boolean[][] scanTab, boolean recur) {
- boolean clean = true;
- for (int i = 0; i < 9; i++) {
- int x, y;
- if (scanTab[0][i]) {
- int t = 0;
- for (int k = 0; k < 9; k++) {
- x = (i%3)*3+k%3;
- y = i/3+k/3;
- for (int n = 0; n < 9; n++) {
- if (pNums[x][y][n]) {
- t++;
- }
- }
- if (t == 1 && pNums[x][y][num]) {
- isolateNumber(x, y, num, pNums, scanTab[0]);
- clean = false;
- }
- }
- }
- }
- if (!clean && recur) {
- checkLines(num, pNums, scanTab, true);
- }
- }
- private void checkLines(int num, boolean[][][] pNums, boolean[][] scanTab, boolean recur) {
- boolean clean = true;
- for (int i = 0; i < 9; i++) {
- if (scanTab[1][i]) {
- int[] rowData = containsRow(i, num, pNums, true);
- if (rowData != null) {
- clean = false;
- scanTab[1][i] = false;
- clearLine(i, num, pNums, rowData);
- //System.out.println("Line cleared in sector: " + i);
- }
- }
- }
- if (!clean && recur) {
- checkIsolate(num, pNums, scanTab, true);
- }
- }
- private int[] containsRow(int sector, int num, boolean[][][] pNums, boolean state) {
- int[] xPoints = {-1, -1, -1, -1, -1, -1, -1, -1, -1};
- int[] yPoints = {-1, -1, -1, -1, -1, -1, -1, -1, -1};
- int cells = 0;
- for (int v = 0; v < 3; v++) {
- for (int i = 0; i < 3; i++) {
- if (pNums[(sector%3)*3+i][(sector/3)*3+v][num] == state) {
- xPoints[cells] = (sector%3)*3+i;
- yPoints[cells] = (sector/3)*3+v;
- cells++;
- }
- }
- }
- if (state) {
- if (xPoints[0] == -1) {
- return null;
- }
- for (int i = 1; i < 9; i++) {
- if (xPoints[i] == -1 && i > 1) {
- return new int[] {1, xPoints[0]};
- }
- if (xPoints[i] != xPoints[0]) {
- break;
- }
- }
- for (int i = 1; i < 9; i++) {
- if (yPoints[i] == -1 && i > 1) {
- return new int[] {0, yPoints[0]};
- }
- if (yPoints[i] != yPoints[0]) {
- break;
- }
- }
- return null;
- } else {
- return null;
- }
- }
- private void clearLine(int sector, int num, boolean[][][] pNums, int[] rowData) {
- if (rowData[0] == 0) {
- for (int i = 0; i < 9; i++) {
- if (getSectorFromCoords(i, rowData[1]) != sector) {
- pNums[i][rowData[1]][num] = false;
- }
- }
- } else if (rowData[0] == 1) {
- for (int i = 0; i < 9; i++) {
- if (getSectorFromCoords(rowData[1], i) != sector) {
- pNums[rowData[1]][i][num] = false;
- }
- }
- }
- }
- private int getSectorFromCoords(int x, int y) {
- return (y/3)*3 + (x/3);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement