Java Sudoku Generator(easiest solution)

Question

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

Crier

Answer 1

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/

Form

Hi Tassinari, Can you give the sneak peek of the Puzzle Generator you have? I've been struggling to create my algorith for SUdoku puzzle gebnerator :( Thanks in advanc – Consequent

second link is not accessible. pls upload content else where – Synecology

Answer 2

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;*/
        }

    }
}

Burlburlap

try this code.this code generates a Sudoku question.the user have to solve the puzzle and enter each element manually,the answer will be compared with the required result and displays if your answer is correct or not. – Burlburlap

Answer 3

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);
    }

}

Energetic

Just thought of this... When the array is initialized it will be full of zeros, which kind of screws things up. Maybe it would be better to use 1...10 for the possible sudoku values, instead of 0...9. When you are done generating you can just decrement each value. – Energetic

Just thought of something else... I obviously don't know anything about sudoku :) Apparently 0 isn't a valid value in a sudoku puzzle! Who knew? I cleaned up the above code though, and it seemed to work after I fixed all the obvious mistakes :) You just need to write the constraints properly. – Energetic

Ok, actually got this working, so here's some code. It works, but it only tests columns and rows. You'll have to figure out the region test yourself :) If you decide to convert it to a 2d array for this test check out the toString() method. Once you add that, this will generate all valid sudoku grids. I'll edit the original answer to include the new code. – Energetic

Answer 4

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();
    }
}
}

Unduly