Java Sudoku Generator(easiest solution)

In my last question seen here: Sudoku - Region testing I asked how to check the 3x3 regions and someone was able to give me a satisfactory answer (although it involved a LOT of tinkering to get it working how I wanted to, since they didn't mention what the class table_t was.)

I finished the 开发者_StackOverflowproject and was able to create a sudoku generator, but it feels like it's contrived. And I feel like I've somehow overcomplicated things by taking a very brute-force approach to generating the puzzles.

Essentially my goal is to create a 9x9 grid with 9- 3x3 regions. Each row / col / region must use the numbers 1-9 only once.

The way that I went about solving this was by using a 2-dimensional array to place numbers at random, 3 rows at a time. Once the 3 rows were done it would check the 3 rows, and 3 regions and each vertical col up to the 3rd position. As it iterated through it would do the same until the array was filled, but due to the fact that I was filling with rand, and checking each row / column / region multiple times it felt very inefficient.

Is there an "easier" way to go about doing this with any type of data construct aside from a 2d array? Is there an easier way to check each 3x3 region that might coincide with checking either vert or horizontal better? From a standpoint of computation I can't see too many ways to do it more efficiently without swelling the size of the code dramatically.

I built a sudoku game a while ago and used the dancing links algorithm by Donald Knuth to generate the puzzles. I found these sites very helpful in learning and implementing the algorithm

http://en.wikipedia.org/wiki/Dancing_Links

http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/

http://garethrees.org/2007/06/10/zendoku-generation/

import java.util.Random;
import java.util.Scanner;

public class sudoku {

    /**
     * @antony
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int p = 1;
        Random r = new Random();
        int i1=r.nextInt(8);
        int firstval = i1;
        while (p == 1) {
            int x = firstval, v = 1;
            int a[][] = new int[9][9];
            int b[][] = new int[9][9];
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if ((x + j + v) <= 9)
                        a[i][j] = j + x + v;
                    else
                        a[i][j] = j + x + v - 9;
                    if (a[i][j] == 10)
                        a[i][j] = 1;
                    // System.out.print(a[i][j]+" ");
                }
                x += 3;
                if (x >= 9)
                    x = x - 9;
                // System.out.println();
                if (i == 2) {
                    v = 2;
                    x = firstval;
                }
                if (i == 5) {
                    v = 3;
                    x = firstval;
                }

            }
            int eorh;
            Scanner in = new Scanner(System.in);
            System.out
                    .println("hey lets play a game of sudoku:take down the question and replace the 0's with your digits and complete the game by re entering your answer");
            System.out.println("enter your option 1.hard  2.easy");
            eorh = in.nextInt();
            switch (eorh) {
            case 1:
                b[0][0] = a[0][0];
                b[8][8] = a[8][8];
                b[0][3] = a[0][3];
                b[0][4] = a[0][4];
                b[1][2] = a[1][2];
                b[1][3] = a[1][3];
                b[1][6] = a[1][6];
                b[1][7] = a[1][7];
                b[2][0] = a[2][0];
                b[2][4] = a[2][4];
                b[2][8] = a[2][8];
                b[3][2] = a[3][2];
                b[3][8] = a[3][8];
                b[4][2] = a[4][2];
                b[4][3] = a[4][3];
                b[4][5] = a[4][5];
                b[4][6] = a[4][6];
                b[5][0] = a[5][0];
                b[5][6] = a[5][6];
                b[6][0] = a[6][0];
                b[6][4] = a[6][4];
                b[6][8] = a[6][8];
                b[7][1] = a[7][1];
                b[7][2] = a[7][2];
                b[7][5] = a[7][5];
                b[7][6] = a[7][6];
                b[8][4] = a[8][4];
                b[8][5] = a[8][5];
                b[0][0] = a[0][0];
                b[8][8] = a[8][8];

                break;
            case 2:
                b[0][3] = a[0][3];
                b[0][4] = a[0][4];
                b[1][2] = a[1][2];
                b[1][3] = a[1][3];
                b[1][6] = a[1][6];
                b[1][7] = a[1][7];
                b[1][8] = a[1][8];
                b[2][0] = a[2][0];
                b[2][4] = a[2][4];
                b[2][8] = a[2][8];
                b[3][2] = a[3][2];
                b[3][5] = a[3][5];
                b[3][8] = a[3][8];
                b[4][0] = a[4][0];
                b[4][2] = a[4][2];
                b[4][3] = a[4][3];
                b[4][4] = a[4][4];
                b[4][5] = a[4][5];
                b[4][6] = a[4][6];
                b[5][0] = a[5][0];
                b[5][1] = a[5][1];
                b[5][4] = a[5][4];
                b[5][6] = a[5][6];
                b[6][0] = a[6][0];
                b[6][4] = a[6][4];
                b[6][6] = a[6][6];
                b[6][8] = a[6][8];
                b[7][0] = a[7][0];
                b[7][1] = a[7][1];
                b[7][2] = a[7][2];
                b[7][5] = a[7][5];
                b[7][6] = a[7][6];
                b[8][2] = a[8][2];
                b[8][4] = a[8][4];
                b[8][5] = a[8][5];
                break;
            default:
                System.out.println("entered option is incorrect");
                break;
            }

            for (int y = 0; y < 9; y++) {
                for (int z = 0; z < 9; z++) {
                    System.out.print(b[y][z] + " ");
                }
                System.out.println("");
            }
            System.out.println("enter your answer");
            int c[][] = new int[9][9];
            for (int y = 0; y < 9; y++) {
                for (int z = 0; z < 9; z++) {
                    c[y][z] = in.nextInt();
                }
            }
            for (int y = 0; y < 9; y++) {
                for (int z = 0; z < 9; z++)
                    System.out.print(c[y][z] + " ");
                System.out.println();
            }
            int q = 0;
            for (int y = 0; y < 9; y++) {
                for (int z = 0; z < 9; z++)
                    if (a[y][z] == c[y][z])
                        continue;
                    else {
                        q++;
                        break;
                    }
            }
            if (q == 0)
                System.out
                        .println("the answer you have entered is correct well done");
            else
                System.out.println("oh  wrong answer better luck next time");
            System.out
                    .println("do you want to play a different game of sudoku(1/0)");
            p = in.nextInt();
            firstval=r.nextInt(8);
            /*if (firstval > 8)
                firstval -= 9;*/
        }

    }
}

I think you can use a 1D array, in much the same way a 1D array can model a binary tree. For example, to look at the value below a number, add 9 to the index.

I just made this up, but could something like this work?

private boolean makePuzzle(int [] puzzle,  int i)
{
     for (int x = 0; x< 10 ; x++)
     {
           if (//x satisfies all three conditions for the current square i)
           {
                puzzle[i]=x;
                if (i==80) return true //terminal condition, x fits in the last square
                else
                    if makePuzzle(puzzle, i++);//find the next x
                         return true; 
           }// even though x fit in this square, an x couldn't be 
             // found for some future square, try again with a new x
     }
     return false; //no value for x fit in the current square
 } 

 public static void main(String[] args ) 
 {
  int[] puzzle = new int[80];
  makePuzzle(puzzle,0);
  // print out puzzle here
 }       

Edit: its been a while since I've used arrays in Java, sorry if I screwed up any syntax. Please consider it pseudo code :)

Here is the code as described below in my comment.

public class Sudoku
{
    public int[] puzzle = new int[81];
    private void makePuzzle(int[] puzzle, int i)
    {
        for (int x = 1; x< 10 ; x++)
        {
            puzzle[i]=x;
            if(checkConstraints(puzzle))
            {
                if (i==80)//terminal condition
                {
                    System.out.println(this);//print out the completed puzzle
                        puzzle[i]=0;
                    return;
                }
                else
                    makePuzzle(puzzle,i+1);//find a number for the next square                          
            }
            puzzle[i]=0;//this try didn't work, delete the evidence 
        }       
    }
    private boolean checkConstraints(int[] puzzle)
    {
        int test;
     //test that rows have unique values    
      for (int column=0; column<9; column++)
        {
            for (int row=0; row<9; row++)
            {
                test=puzzle[row+column*9];
                for (int j=0;j<9;j++)
                {
                    if(test!=0&&  row!=j&&test==puzzle[j+column*9])
                        return false;
                }
            }
        }
        //test that columns have unique values
        for  (int column=0; column<9; column++) 
        {
             for(int row=0; row<9; row++)
            {
                test=puzzle[column+row*9];
                for (int j=0;j<9;j++)
                {
                    if(test!=0&&row!=j&&test==puzzle[column+j*9])
                        return false;
                }
            }
        }
        //implement region test here
        int[][] regions = new int[9][9];
        int[] regionIndex ={0,3,6,27,30,33,54,57,60};
        for (int region=0; region<9;region++) //for each region
        {

            int j =0;
            for (int k=regionIndex[region];k<regionIndex[region]+27; k=(k%3==2?k+7:k+1))
                {
                    regions[region][j]=puzzle[k];
                    j++;
                }
        }
        for (int i=0;i<9;i++)//region counter
        {
            for (int j=0;j<9;j++)
            {
                for (int k=0;k<9;k++)
                {
                    if (regions[i][j]!=0&&j!=k&&regions[i][j]==regions[i][k])
                    return false;
                }

            }
        }
    return true;

    }
    public String toString()
    {
        String string= "";
        for (int i=0; i <9;i++)
        {
            for  (int j = 0; j<9;j++)
            {
                string = string+puzzle[i*9+j];
            }
            string =string +"\n";
        }
        return string;
    }
    public static void main(String[] args)
    {
        Sudoku sudoku=new Sudoku();
        sudoku.makePuzzle(sudoku.puzzle, 0);
    }

}

Try this code:

package com;
public class Suduku{
    public static void main(String[] args ){
        int k=0;
        int fillCount =1;
        int subGrid=1;
        int N=3;
        int[][] a=new int[N*N][N*N];
    for (int i=0;i<N*N;i++){
        if(k==N){
            k=1;
            subGrid++;
            fillCount=subGrid;
        }else{
            k++;
            if(i!=0)
            fillCount=fillCount+N;
        }
        for(int j=0;j<N*N;j++){
            if(fillCount==N*N){
                a[i][j]=fillCount;
                fillCount=1;
                System.out.print("  "+a[i][j]);
            }else{
                a[i][j]=fillCount++;
                System.out.print("  "+a[i][j]);
            }
        }
        System.out.println();
    }
}
}