API tools faq
paste
Advertisement
CaptainSpaceCat

Sudoku (Java Edition) - Board

CaptainSpaceCat
Aug 2nd, 2016
185
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 14.28 KB | None | 0 0
raw download clone embed print report
  1. import java.lang.Math;
  2. import java.util.ArrayList;
  3.  
  4. public class Board {
  5.  
  6.   private int[][] board;
  7.   private boolean valid;
  8.   private boolean[][] perms;
  9.  
  10.   public Board() {
  11.     board = new int[9][9];
  12.     boolean success = false;
  13.     //this.generateNewBoard();
  14.     while (!success) {
  15.       try {
  16.         //System.out.println("Attempting to generate board...");
  17.         success = this.generateNewBoard();
  18.         if (success) {
  19.           //System.out.println("Board successfully generated!");
  20.         }
  21.       } catch (Exception ignore) {}
  22.     }
  23.     setPerms();
  24.     validate();
  25.   }
  26.  
  27.   public Board(Board b) {
  28.     board = new int[9][9];
  29.     for (int y = 0; y < 9; y++) {
  30.       for (int x = 0; x < 9; x++) {
  31.         board[x][y] = b.getValue(x, y);
  32.       }
  33.     }
  34.     setPerms();
  35.     validate();
  36.   }
  37.  
  38.   public Board(Board b, boolean[][] p) {
  39.     board = new int[9][9];
  40.     for (int y = 0; y < 9; y++) {
  41.       for (int x = 0; x < 9; x++) {
  42.         board[x][y] = b.getValue(x, y);
  43.       }
  44.     }
  45.     perms = p;
  46.     validate();
  47.   }
  48.  
  49.   public Board(String b) {
  50.     board = new int[9][9];
  51.     int n = 0;
  52.     for (int y = 0; y < 9; y++) {
  53.       for (int x = 0; x < 9; x++) {
  54.         board[x][y] = Integer.parseInt(b.substring(n, n+1));
  55.         n++;
  56.       }
  57.     }
  58.     setPerms();
  59.     validate();
  60.   }
  61.  
  62.   public String toString() {
  63.     String result = "";
  64.     for (int y = 0; y < 9; y++) {
  65.       for (int x = 0; x < 9; x++) {
  66.         if (board[x][y] > 0) {
  67.           result += "" + board[x][y];
  68.         } else {
  69.           result += " ";
  70.         }
  71.         if (x == 2 || x == 5) {
  72.           result += " ";
  73.         }
  74.       }
  75.       result += "\n";
  76.       if (y == 2 || y == 5) {
  77.         result += "\n";
  78.       }
  79.     }
  80.     return result;
  81.   }
  82.  
  83.   public String getBoardCode() {
  84.     String result = "";
  85.     for (int y = 0; y < 9; y++) {
  86.       for (int x = 0; x < 9; x++) {
  87.         result += "" + board[x][y];
  88.       }
  89.     }
  90.     return result;
  91.   }
  92.  
  93.   public boolean validate() {
  94.     for (int y = 0; y < 9; y++) {
  95.       for (int x = 0; x < 9; x++) {
  96.         int total = 0;
  97.         if (board[x][y] == 0) {
  98.           valid = false;
  99.           return false;
  100.         }
  101.         for (int i = 0; i < 9; i++) {
  102.           if (board[x][i] == board[x][y]) {
  103.             total++;
  104.           }
  105.           if (board[i][y] == board[x][y]) {
  106.             total++;
  107.           }
  108.           if (board[(x/3)*3+i%3][(y/3)*3+i/3] == board[x][y]) {
  109.             total++;
  110.           }
  111.         }
  112.         if (total != 3) {
  113.           valid = false;
  114.           return false;
  115.         }
  116.       }
  117.     }
  118.     valid = true;
  119.     return true;
  120.   }
  121.  
  122.   public boolean isValid() {
  123.     return valid;
  124.   }
  125.  
  126.   public int getValue(int x, int y) {
  127.     return board[x][y];
  128.   }
  129.  
  130.   public void puzzle(int difficulty) {
  131.     ArrayList<int[]> coords = new ArrayList<int[]>();
  132.     ArrayList<int[]> rejectedCoords = new ArrayList<int[]>();
  133.     for (int y = 0; y < 9; y++) {
  134.       for (int x = 0; x < 9; x++) {
  135.         coords.add(new int[] {x, y});
  136.       }
  137.     }
  138.     switch (difficulty) {
  139.       case 1:
  140.         while (coords.size() > 36) {
  141.         int[] choice = coords.remove((int)(Math.random()*coords.size()));
  142.         //System.out.println("Removing " + board[choice[0]][choice[1]] + " from board at: " + choice[0] + ":" + choice[1]);
  143.         int temp = board[choice[0]][choice[1]];
  144.         board[choice[0]][choice[1]] = 0;
  145.         int[][] tempBoard = copyBoard();
  146.         boolean test = solve();
  147.         board = tempBoard;
  148.         if (!test) {
  149.           board[choice[0]][choice[1]] = temp;
  150.           break;
  151.         }}
  152.         break;
  153.       case 2:
  154.         while (coords.size() > 31) {
  155.         int[] choice = coords.remove((int)(Math.random()*coords.size()));
  156.         //System.out.println("Removing " + board[choice[0]][choice[1]] + " from board at: " + choice[0] + ":" + choice[1]);
  157.         int temp = board[choice[0]][choice[1]];
  158.         board[choice[0]][choice[1]] = 0;
  159.         int[][] tempBoard = copyBoard();
  160.         boolean test = solve();
  161.         board = tempBoard;
  162.         if (!test) {
  163.           board[choice[0]][choice[1]] = temp;
  164.           break;
  165.         }}
  166.         break;
  167.       case 3:
  168.         while (coords.size() > 0) {
  169.         int[] choice = coords.remove((int)(Math.random()*coords.size()));
  170.         //System.out.println("Removing " + board[choice[0]][choice[1]] + " from board at: " + choice[0] + ":" + choice[1]);
  171.         int temp = board[choice[0]][choice[1]];
  172.         board[choice[0]][choice[1]] = 0;
  173.         int[][] tempBoard = copyBoard();
  174.         boolean test = solve();
  175.         board = tempBoard;
  176.         if (!test) {
  177.           board[choice[0]][choice[1]] = temp;
  178.         }}
  179.         break;
  180.       case 4:
  181.         while (coords.size() > 0) {
  182.         int[] choice = coords.remove((int)(Math.random()*coords.size()));
  183.         //System.out.println("Removing " + board[choice[0]][choice[1]] + " from board at: " + choice[0] + ":" + choice[1]);
  184.         int temp = board[choice[0]][choice[1]];
  185.         board[choice[0]][choice[1]] = 0;
  186.         int[][] tempBoard = copyBoard();
  187.         boolean test = solve();
  188.         board = tempBoard;
  189.         if (!test) {
  190.           board[choice[0]][choice[1]] = temp;
  191.           rejectedCoords.add(choice);
  192.         }}
  193.         for (int i = 0; i < 1; i++) {
  194.           int[] choice = rejectedCoords.remove((int)(Math.random()*rejectedCoords.size()));
  195.           board[choice[0]][choice[1]] = 0;
  196.         }
  197.         break;
  198.       case 5:
  199.         while (coords.size() > 0) {
  200.         int[] choice = coords.remove((int)(Math.random()*coords.size()));
  201.         //System.out.println("Removing " + board[choice[0]][choice[1]] + " from board at: " + choice[0] + ":" + choice[1]);
  202.         int temp = board[choice[0]][choice[1]];
  203.         board[choice[0]][choice[1]] = 0;
  204.         int[][] tempBoard = copyBoard();
  205.         boolean test = solve();
  206.         board = tempBoard;
  207.         if (!test) {
  208.           board[choice[0]][choice[1]] = temp;
  209.           rejectedCoords.add(choice);
  210.         }}
  211.         for (int i = 0; i < 2; i++) {
  212.           int[] choice = rejectedCoords.remove((int)(Math.random()*rejectedCoords.size()));
  213.           board[choice[0]][choice[1]] = 0;
  214.         }
  215.         break;
  216.     }
  217.     setPerms();
  218.     //board = tempBoard;
  219.   }
  220.  
  221.   public void setPerms() {
  222.     perms = new boolean[9][9];
  223.     for (int y = 0; y < 9; y++) {
  224.       for (int x = 0; x < 9; x++) {
  225.         //System.out.println(b.getValue(x, y));
  226.         if (board[x][y] == 0) {
  227.           perms[x][y] = true;
  228.         } else {
  229.           perms[x][y] = false;
  230.         }
  231.       }
  232.     }
  233.   }
  234.  
  235.   public boolean[][] getPerms() {
  236.     return perms;
  237.   }
  238.  
  239.   public boolean getPerm(int x, int y) {
  240.     return perms[x][y];
  241.   }
  242.  
  243.   public void reset() {
  244.     for (int y = 0; y < 9; y++) {
  245.       for (int x = 0; x < 9; x++) {
  246.         if (perms[x][y]) {
  247.           board[x][y] = 0;
  248.         }
  249.       }
  250.     }
  251.   }
  252.  
  253.   public void setValue(int x, int y, int val) {
  254.     board[x][y] = val;
  255.   }
  256.  
  257.   private int[][] copyBoard() {
  258.     int[][] response = new int[9][9];
  259.     for (int y = 0; y < 9; y++) {
  260.       for (int x = 0; x < 9; x++) {
  261.         response[x][y] = board[x][y];
  262.       }
  263.     }
  264.     return response;
  265.   }
  266.  
  267.   public boolean solve() {
  268.     boolean[][][] pNums = new boolean[9][9][9];
  269.     for (int y = 0; y < 9; y++) {
  270.       for (int x = 0; x < 9; x++) {
  271.         for (int i = 0; i < 9; i++) {
  272.           pNums[x][y][i] = (board[x][y] == 0 || board[x][y] == i);
  273.         }
  274.       }
  275.     }
  276.    
  277.     while (!validate()) {
  278.       boolean changed = false;
  279.       for (int y = 0; y < 9; y++) {
  280.         for (int x = 0; x < 9; x++) {
  281.           if (board[x][y] == 0) {
  282.             if (eliminateImpossible(x, y, pNums)) {
  283.               changed = true;
  284.             }
  285.           }
  286.         }
  287.       }
  288.       if (!changed) {
  289.         return false;
  290.       }
  291.     }
  292.     return true;
  293.   }
  294.  
  295.   private boolean eliminateImpossible(int x, int y, boolean[][][] pNums) {
  296.     for (int i = 0; i < 9; i++) {
  297.       if (board[x][i] > 0) {
  298.         pNums[x][y][board[x][i]-1] = false;
  299.       }
  300.       if (board[i][y] > 0) {
  301.         pNums[x][y][board[i][y]-1] = false;
  302.       }
  303.       if (board[(x/3)*3+i%3][(y/3)*3+i/3] > 0) {
  304.         pNums[x][y][board[(x/3)*3+i%3][(y/3)*3+i/3]-1] = false;
  305.       }
  306.     }
  307.     int t = 0;
  308.     int n = -1;
  309.     for (int i = 0; i < 9; i++) {
  310.       if (pNums[x][y][i]) {
  311.         t++;
  312.         n = i;
  313.       }
  314.     }
  315.     if (t == 1) {
  316.       //System.out.println("Number " + (n+1) + " isolated at: " + x + ":" + y);
  317.       board[x][y] = n+1;
  318.       return true;
  319.     } else if (t == 0) {
  320.       //System.err.println("ERROR: No available choices at: " + x + ":" + y);
  321.     }
  322.     return false;
  323.   }
  324.  
  325.   public boolean generateNewBoard() {
  326.     board = new int[9][9];
  327.     boolean[][][] pNums = new boolean[9][9][9];
  328.     for (int y = 0; y < 9; y++) {
  329.       for (int x = 0; x < 9; x++) {
  330.         for (int i = 0; i < 9; i++) {
  331.           pNums[x][y][i] = true;
  332.         }
  333.       }
  334.     }
  335.     for (int i = 0; i < 9; i++) {
  336.       //System.out.println("Isolating number: " + (i+1) + "...");
  337.                                 //keeps tabs on which cels have been scanned
  338.                                 //0 = isolate, 1 = lines, 2 = holes
  339.       boolean[][] scanTab = {{true, true, true, true, true, true, true, true, true}, {true, true, true, true, true, true, true, true, true}};
  340.       scanBoard(i, pNums, scanTab);
  341.       while (!checkIsoTab(scanTab[0])) {
  342.         chooseNextNumber(i, scanTab[0], pNums);
  343.         scanBoard(i, pNums, scanTab);
  344.       }
  345.       //System.out.println("Number " + (i+1) + " isolated.");
  346.       //System.out.println(this.toString());
  347.     }
  348.     return true;
  349.   }
  350.  
  351.   private boolean checkIsoTab(boolean[] isoTab) {
  352.     for (boolean b: isoTab) {
  353.       if (b) {
  354.         return false;
  355.       }
  356.     }
  357.     return true;
  358.   }
  359.  
  360.   private void chooseNextNumber(int num, boolean[] isoTab, boolean[][][] pNums) {
  361.     for (int i = 0; i < 9; i++) {
  362.       if (isoTab[i]) {
  363.         //System.out.println("Scanning complete. Randomizing next available sector...");
  364.         int[][] options = getAvailableCells(i, num, pNums);
  365.         int[] choice = options[(int)(Math.random()*(options.length))];
  366.         isolateNumber(choice[0], choice[1], num, pNums, isoTab);
  367.         break;
  368.       }
  369.     }
  370.   }
  371.  
  372.   private int[][] getAvailableCells(int sector, int num, boolean[][][] pNums) {
  373.     ArrayList<int[]> coords = new ArrayList<int[]>();
  374.     for (int v = 0; v < 3; v++) {
  375.       for (int i = 0; i < 3; i++) {
  376.         if (pNums[(sector%3)*3+i][(sector/3)*3+v][num]) {
  377.           coords.add(new int[] {(sector%3)*3+i, (sector/3)*3+v});
  378.         }
  379.       }
  380.     }
  381.     return coords.toArray(new int[coords.size()][2]);
  382.   }
  383.  
  384.   private void isolateNumber(int x, int y, int num, boolean[][][] pNums, boolean[] isoTab) {
  385.     isoTab[getSectorFromCoords(x, y)] = false;
  386.     for (int i = 0; i < 9; i++) {
  387.       pNums[x][i][num] = false;
  388.       pNums[i][y][num] = false;
  389.       pNums[x][y][i] = false;
  390.       pNums[(x/3)*3+i%3][(y/3)*3+i/3][num] = false;
  391.     }
  392.     pNums[x][y][num] = true;
  393.     board[x][y] = num+1;
  394.     //System.out.println("Isolated sector: " + getSectorFromCoords(x, y));
  395.   }
  396.  
  397.   private void scanBoard(int num, boolean[][][] pNums, boolean[][] scanTab) {
  398.     boolean clean = false;
  399.     //System.out.println("Scanning...");
  400.     checkLines(num, pNums, scanTab, false);
  401.     checkIsolate(num, pNums, scanTab, true);
  402.   }
  403.  
  404.   private void checkIsolate(int num, boolean[][][] pNums, boolean[][] scanTab, boolean recur) {
  405.     boolean clean = true;
  406.     for (int i = 0; i < 9; i++) {
  407.       int x, y;
  408.       if (scanTab[0][i]) {
  409.         int t = 0;
  410.         for (int k = 0; k < 9; k++) {
  411.           x = (i%3)*3+k%3;
  412.           y = i/3+k/3;
  413.           for (int n = 0; n < 9; n++) {
  414.             if (pNums[x][y][n]) {
  415.               t++;
  416.             }
  417.           }
  418.           if (t == 1 && pNums[x][y][num]) {
  419.             isolateNumber(x, y, num, pNums, scanTab[0]);
  420.             clean = false;
  421.           }
  422.         }
  423.       }
  424.     }
  425.     if (!clean && recur) {
  426.       checkLines(num, pNums, scanTab, true);
  427.     }
  428.   }
  429.  
  430.   private void checkLines(int num, boolean[][][] pNums, boolean[][] scanTab, boolean recur) {
  431.     boolean clean = true;
  432.     for (int i = 0; i < 9; i++) {
  433.       if (scanTab[1][i]) {
  434.         int[] rowData = containsRow(i, num, pNums, true);
  435.         if (rowData != null) {
  436.           clean = false;
  437.           scanTab[1][i] = false;
  438.           clearLine(i, num, pNums, rowData);
  439.           //System.out.println("Line cleared in sector: " + i);
  440.         }
  441.       }
  442.     }
  443.     if (!clean && recur) {
  444.       checkIsolate(num, pNums, scanTab, true);
  445.     }
  446.   }
  447.  
  448.   private int[] containsRow(int sector, int num, boolean[][][] pNums, boolean state) {
  449.     int[] xPoints = {-1, -1, -1, -1, -1, -1, -1, -1, -1};
  450.     int[] yPoints = {-1, -1, -1, -1, -1, -1, -1, -1, -1};
  451.     int cells = 0;
  452.     for (int v = 0; v < 3; v++) {
  453.       for (int i = 0; i < 3; i++) {
  454.         if (pNums[(sector%3)*3+i][(sector/3)*3+v][num] == state) {
  455.           xPoints[cells] = (sector%3)*3+i;
  456.           yPoints[cells] = (sector/3)*3+v;
  457.           cells++;
  458.         }
  459.       }
  460.     }
  461.     if (state) {
  462.       if (xPoints[0] == -1) {
  463.         return null;
  464.       }
  465.       for (int i = 1; i < 9; i++) {
  466.         if (xPoints[i] == -1 && i > 1) {
  467.           return new int[] {1, xPoints[0]};
  468.         }
  469.         if (xPoints[i] != xPoints[0]) {
  470.           break;
  471.         }
  472.       }
  473.       for (int i = 1; i < 9; i++) {
  474.         if (yPoints[i] == -1 && i > 1) {
  475.           return new int[] {0, yPoints[0]};
  476.         }
  477.         if (yPoints[i] != yPoints[0]) {
  478.           break;
  479.         }
  480.       }
  481.       return null;
  482.     } else {
  483.       return null;
  484.     }
  485.   }
  486.  
  487.   private void clearLine(int sector, int num, boolean[][][] pNums, int[] rowData) {
  488.     if (rowData[0] == 0) {
  489.       for (int i = 0; i < 9; i++) {
  490.         if (getSectorFromCoords(i, rowData[1]) != sector) {
  491.           pNums[i][rowData[1]][num] = false;
  492.         }
  493.       }
  494.     } else if (rowData[0] == 1) {
  495.       for (int i = 0; i < 9; i++) {
  496.         if (getSectorFromCoords(rowData[1], i) != sector) {
  497.           pNums[rowData[1]][i][num] = false;
  498.         }
  499.       }
  500.     }
  501.   }
  502.  
  503.   private int getSectorFromCoords(int x, int y) {
  504.     return (y/3)*3 + (x/3);
  505.   }
  506.  
  507. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!