Создание судоку на Java

Question

Я создаю программу, которая изобретает новую головоломку судоку. Сначала я планировал сделать это, придумав новую головоломку, а затем удалив случайные числа. Однако алгоритм, который я использую (см. Ниже) для создания новой головоломки, может занять до 5 минут. У кого-нибудь есть более быстрые решения?

Алгоритм создания

---

    for (int x = 0; x < boardWidth; x++) //boardWidth is the number of fillable squares wide and high the board is. (9 for a standard Sudoku board)
    {
      for (int y = 0; y < boardWidth; y++)
      {
        int errorCount = 0;
        do
        {
          boardVals[y][x] = (byte)(rand.nextInt(boardWidth) + 1);
          errorCount++;
          if (errorCount > Math.pow(boardWidth, 4)) //If the square has been tried to be filled up to boardWidth^4 times (6,561 for a standard Sudoku board), it clears the board and starts again.
          {
            resetBoard();
            x = 0; y = 0; break;
          }
        }while (!boardIsOK()); //boardIsOK() is a method that checks to see if the board is solvable, ignoring unfilled squares.
      }
    }

Методы:

---

  private boolean boardIsOK()
  {
    for (int i=0; i < boardWidth; i++)
    {
      if (!setIsOK(getRow(i)))
      {
        return false;
      }
      if (!setIsOK(getCol(i)))
      {
        return false;
      }
    }
    for (int x=0; x < boardSegs; x++)
    {
      for (int y=0; y < boardSegs; y++)
      {
        if (!areaIsOK(getSquare(x,y)))
        {
          return false;
        }
      }
    }
    return true;
  }



  private byte[] getRow(int index)
  {
    return boardVals[index];
  }

  private byte[] getCol(int index)
  {
    byte[] b = new byte[boardWidth];
    for (int i=0; i < boardWidth; i++)
      b[i] = boardVals[i][index];
    return b;
  }

  private byte[][] getSquare(int xIndex, int yIndex)
  {
    byte w = (byte)(boardWidth / boardSegs), b[][] = new byte[w][w];
    for (int x=0; x < b.length; x++)
    {
      for (int y=0; y < b[x].length; y++)
      {
        b[y][x] = boardVals[y + (yIndex * w)][x + (xIndex * w)];
      }
    }
    return b;
  }

  private boolean setIsOK(byte[] set)
  {
    for (int i=0; i < set.length - 1; i++)
    {
      for (int j=i + 1; j < set.length; j++)
      {
        if (set[i] == set[j] && set[i] != NULL_VAL && set[j] != NULL_VAL)
        {
          return false;
        }
      }
    }
    return true;
  }

  private boolean areaIsOK(byte[][] area)
  {
    int size = 0;
    for (int i=0; i < area.length; i++)
    {
      size += area[i].length;
    }
    byte[] b = new byte[size];
    for (int x=0, i=0; x < area.length; x++)
    {
      for (int y=0; y < area[x].length; y++, i++)
      {
        b[i] = area[x][y];
      }
    }
    return setIsOK(b);
  }

resetBoard () просто заполняет доску NULL_VAL.

Answer 1

Здесь возможно несколько подходов к оптимизации. Во-первых, вы должны добавить некоторую бухгалтерию в каждую ячейку, имея набор «еще возможных чисел» для каждой из 81 ячейки. Вместо произвольного случайного числа возьмите случайное число из этого набора при заполнении следующей ячейки.

И не останавливайтесь, когда у вас было 6 561 неудачных попыток. Остановитесь, когда один из 81 сета станет пустым. В этом случае вы не должны выбрасывать доску и начинать все сначала, а сделать один шаг назад и попробовать другое значение для предыдущей ячейки. Попробуйте сделать полный возврат алгоритм из этого.

Answer 2

Я бы порекомендовал взглянуть на статью Dancing Links Д. Кнута (gzipped postscript). С его методом вы можете получить действительно быстрый решатель судоку, а затем решить свою доску, чтобы проверить, все ли в порядке.

Для идеи Project Euler 96 моя реализация на Java дает решение (т. Е. Решить 50 судоку) в:

real   0m0.357s
user   0m0.350s
sys    0m0.010s

(Ubuntu Linux 2.6.32-26-сервер x86_64 GNU / Linux, работающий на процессоре Intel® Atom (TM) 330 с частотой 1,60 ГГц)

Answer 3

Не думаю, что удаление случайных чисел - хорошая идея.

Опубликуйте здесь другие методы: boadIsOK() и resetBoard() и прочитайте несколько статей, как создать головоломку ( 1 ).