1

新しい数独パズルを発明するプログラムを作成しています。私が最初にこれを行うことを計画した方法は、新しいパズルを発明し、乱数を削除することでした. ただし、新しいパズルを作成するために使用するアルゴリズム (以下を参照) では、1 つ作成するのに最大 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 で埋めます。

4

3 に答える 3

5

ここでは、いくつかの最適化アプローチが可能です。最初に、81 個のセルのそれぞれに「まだ可能な数字」のセットを持つように、各セルに簿記を追加する必要があります。任意の乱数を取得する代わりに、次のセルに入力するときにこのセットから乱数を取得します。

6,561 回失敗してもやめないでください。81 セットの 1 つが空になったら停止します。このような場合は、ボードを捨てて最初からやり直すのではなく、1 歩戻って前のセルに別の値を試してください。そこから完全なバックトラッキングアルゴリズムを作成してみてください。

于 2010-12-18T08:33:18.767 に答える
2

D. Knuth のDancing Links (gziped postscript) paper を参照することをお勧めします。彼の方法では、非常に高速な数独ソルバーを使用でき、ボードを解いて問題がないかどうかを確認できます。

アイデアとして、Project Euler problem 96の場合、私の Java 実装は次のソリューション (つまり、50 個の数独を解く) を提供します。

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

(Ubuntu Linux 2.6.32-26-server x86_64 GNU/Linux、「Intel(R) Atom(TM) CPU 330 @ 1.60GHz」で実行)

于 2010-12-18T08:53:30.457 に答える
0

乱数を削除することは良い考えではないと思います。

ここに他の方法を投稿してください:boadIsOK()そしてresetBoard()、パズルの作成方法に関するいくつかの記事を読んでください ( 1 ).

于 2010-12-18T08:28:31.393 に答える