Advertisement
CaptainSpaceCat

Sudoku (Java Edition) - Board

Aug 2nd, 2016
134
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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
RAW Paste Data Copied
Advertisement