CODEWITHSUNDEEP
javacreationsudoku
Ky -
Ky -

Reputation: 32163

Creating a Sudoku in Java

I'm creating a program that invents a new Sudoku puzzle. The way I initially planned on doing this is by inventing a new puzzle and then removing random numbers. However, the algorithm I use (seen below) to create a new puzzle can take up to 5 minutes to make one. Does anyone have any faster solutions?

Creation Algorithm

    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.
      }
    }

Methods:

  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() simply fills the board with NULL_VAL.

Upvotes: 1

Views: 5707

Answers (3)

user180100
user180100

Reputation:

I would recommend taking a look at D. Knuth's Dancing Links (gzipped postscript) paper. With his method, you can have a really fast sudoku solver and then you can solve your board to check if it's OK.

As an idea, for Project Euler problem 96, my Java implementation gives the solution (i.e. solve the 50 sudokus) in:

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

(Ubuntu Linux 2.6.32-26-server x86_64 GNU/Linux, running on an "Intel(R) Atom(TM) CPU 330 @ 1.60GHz")

Upvotes: 2

Doc Brown
Doc Brown

Reputation: 20054

There are several optimization approaches possible here. First, you should add some bookkeeping to each cell, having a set of the "still possible numbers" for each of the 81 cells. Instead of taking an arbitrary random number, take a random number from this set when you fill the next cell.

And don't stop when you had 6,561 unsuccessful tries. Stop when one of the 81 sets goes empty. When this is the case, you should not throw the board away and start over again, but go one step backwards and try another value for the previous cell. Try to make a complete backtracking algo from that.

Upvotes: 5

user219882
user219882

Reputation: 15844

I don't think that removing random numbers is a good idea.

Post here the other methods: boadIsOK() and resetBoard() and read some articles how to create the puzzle (1).

Upvotes: 0

Related Questions