java算法.txt

0表示空

import java.util.Random;
public class Sodoku {
  private byte matrix[][] = null;
  private byte buff[][] = null;
  private byte log[] = null;
  private Random seed = new Random();
  public Sodoku() {
  }
  private void initMatrix() {
    seed.setSeed(System.currentTimeMillis());
    matrix = new byte[9][9];
    buff = new byte[9][9];
    for (byte i = 0; i < 9; i++) {
      for (byte j = 0; j < 9; j++) {
        buff[i][j] = j;
      }
    }
  }
  public byte[][] getNewMatrix() {
    byte[][] r = new byte[9][9];
    byte[][] a = null;
    do {
      a = generateMatrix();
    }
    while (a == null);
    for (byte i = 0; i < 9; i++) {
      System.arraycopy(a[i], 0, r[i], 0, 9);
    }
    a = null;
    return r;
  }
  private byte[][] generateMatrix() {
    initMatrix();
    for (byte i = 1; i <= 9; i++) {
      log = new byte[9];
      byte block = 0;
      byte tryTimes = 0;
      for (; block < 9; block++) {
        if (!setRandomPos(block, i)) {
          tryTimes++;
          if (tryTimes > 50) {
            return null;
          }
          block = -1;
          resetThisRound(i);
        }
      }
      goNextRound();
    }
    buff = null;
    log = null;
    return matrix;
  }
  public byte[][] setMask(byte[][] m, int maskNum) {
    byte[] t = new byte[81];
    for (byte i = 0; i < t.length; i++) {
      t[i] = i;
    }
    for (byte i = 0; i < maskNum; i++) {
      byte index = (byte) getRandom(0, t.length - 1);
      m[t[index] % 9][t[index] / 9] = 0;
      t[index] = t[t.length - 1];
      byte[] z = new byte[t.length - 1];
      System.arraycopy(t, 0, z, 0, z.length);
      t = z;
      z = null;
    }
    t = null;
    return m;
  }
  private boolean isIllegalPos(byte x, byte y, byte number) {
    for (byte i = 0; i < 9; i++) {
      if (matrix[i][y] == number || matrix[x][i] == number) {
        return false;
      }
    }
    return true;
  }
  private void resetThisRound(byte number) {
    for (byte i = 0; i < 9; i++) {
      for (byte j = 0; j < 9; j++) {
        if (matrix[i][j] == number) {
          matrix[i][j] = 0;
        }
      }
    }
  }
  private void goNextRound() {
    for (byte j = 0; j < 9; j++) {
      for (byte i = 0; i < buff[j].length; i++) {
        if (buff[j][i] == log[j]) {
          buff[j][i] = buff[j][buff[j].length - 1];
          byte[] tmp = new byte[buff[j].length - 1];
          System.arraycopy(buff[j], 0, tmp, 0, tmp.length);
          buff[j] = tmp;
          tmp = null;
          break;
        }
      }
    }
  }
  private boolean setRandomPos(byte block, byte number) {
    byte pos = 0;
    byte position = 0;
    byte[] tmp = new byte[buff[block].length];
    System.arraycopy(buff[block], 0, tmp, 0, tmp.length);
    do {
      if (tmp.length == 0) {
        return false;
      }
      pos = (byte) getRandom(0, tmp.length - 1);
      position = tmp[pos];
      byte[] tmp2 = new byte[tmp.length - 1];
      tmp[pos] = tmp[tmp.length - 1];
      System.arraycopy(tmp, 0, tmp2, 0, tmp2.length);
      tmp = tmp2;
      tmp2 = null;
    }
    while (!isIllegalPos( (byte) (block % 3 * 3 + position % 3),
                         (byte) (block / 3 * 3 + position / 3),
                         number));
    matrix[block % 3 * 3 + position % 3][block / 3 * 3 +
        position / 3] = number;
    log[block] = position;
    return true;
  }
  private int getRandom(int min, int max) {
    Random r = new Random(seed.nextLong());
    int l = r.nextInt();
    if (l < 0) {
      l = -l;
    }
    int t = min + (l % (max - min + 1));
    return t;
  }
  public void outputMatrix() {
    for (byte i = 0; i < 9; i++) {
      for (byte j = 0; j < 9; j++) {
        System.out.print(matrix[j][i] + " ");
      }
      System.out.println();
    }
  }
  public void outputMatrix(byte[][] m) {
    for (byte i = 0; i < 9; i++) {
      for (byte j = 0; j < 9; j++) {
        System.out.print(m[j][i] + " ");
      }
      System.out.println();
    }
  }
}