Sudoku type grid generator

Question

I'm trying to make a program which prints different sized grids (n by n grids). These grids cannot have the same number in any column or row (like a Sudoku). My bruteSolve() method runs through every combination and then isValid() checks if the rows and columns add up & multiply up to a certain number too - if they do, then the program prints the grid.

However, this program takes too long and I want one where I could do say, 10 * 10 grids fairly quickly. How would I be able to change the code so it does it much faster?

import java.util.ArrayList;
import java.util.Arrays;


public class MagicSquareSolver2 {

static ArrayList<Integer> numbers;

static int n;

static int [] [] grid;

static int count;


public static void main (String [] args){

    n = 4;  

    grid = new int [n] [n] ;

    bruteSolve(0,0,n);
}

public static void bruteSolve(int a, int b, int n){

    for  (int i=1; i<n+1; i++){
        grid [a][b] = i;
        if (b==n-1 && a==n-1){ 
            if (isValid(grid)){count++;
            System.out.println(Arrays.deepToString(grid));System.out.println(count);
        }
        }
        else if (b==n-1){
            bruteSolve(a+1,0,n);
        }
        else{
            bruteSolve(a, b+1,n);
        }
    }

}



public static boolean isValid (int [] [] grid) {

    int factorial = 1;
    int fibonacci = 0;
    int totalX1 = 1;
    int totalY1 = 1;
    int totalX2 = 0;
    int totalY2 = 0;

    for (int i=n; i>0; i--){
        factorial = factorial * i;
    }

    for (int i=n; i>0; i--){
        fibonacci = fibonacci +i;
    }

    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            totalY1= totalY1 * grid[i][j]; //checks all columns
            totalX1= totalX1 * grid[j][i]; // checks all rows
            totalX2 = totalX2 + grid[j][i];
            totalY2 = totalY2 + grid[i][j];
        }
        if (totalX1 != factorial || totalY1 != factorial || totalX2 != fibonacci || totalY2 != fibonacci) { return false; }
        totalX1 = 1;
        totalY1 = 1;
        totalX2 = 0;
        totalY2 = 0;
    }

    return true;

}

}

You should look at the papers in this answer: codereview.stackexchange.com/questions/106571/… — VoiceOfUnreason, Commented Oct 7, 2015 at 2:28

TheCoffeeCup · Accepted Answer · 2015-10-06 22:03:52Z

A couple of things:

Indentation

Indentation seems a little off in your question. Is this because of formatting issues when copy and pasting from your IDE, or is it your code? Most IDEs have a format function that formats the code for you. In eclipse, that is found in Source -> Format or the keyboard shortcut Ctrl+Shift+F.

Spacing

You have what I call overspacing:

static int [] [] grid;

and underspacing:

for  (int i=1; i<n+1; i++){

Again, formatting in an IDE will usually fix that.

After formatting, your code will look like:

import java.util.ArrayList;
import java.util.Arrays;

public class MagicSquareSolver2 {

    static ArrayList<Integer> numbers;

    static int n;

    static int[][] grid;

    static int count;

    public static void main(String[] args) {

        n = 4;

        grid = new int[n][n];

        bruteSolve(0, 0, n);
    }

    public static void bruteSolve(int a, int b, int n) {

        for (int i = 1; i < n + 1; i++) {
            grid[a][b] = i;
            if (b == n - 1 && a == n - 1) {
                if (isValid(grid)) {
                    count++;
                    System.out.println(Arrays.deepToString(grid));
                    System.out.println(count);
                }
            } else if (b == n - 1) {
                bruteSolve(a + 1, 0, n);
            } else {
                bruteSolve(a, b + 1, n);
            }
        }

    }

    public static boolean isValid(int[][] grid) {

        int factorial = 1;
        int fibonacci = 0;
        int totalX1 = 1;
        int totalY1 = 1;
        int totalX2 = 0;
        int totalY2 = 0;

        for (int i = n; i > 0; i--) {
            factorial = factorial * i;
        }

        for (int i = n; i > 0; i--) {
            fibonacci = fibonacci + i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalY1 = totalY1 * grid[i][j]; // checks all columns
                totalX1 = totalX1 * grid[j][i]; // checks all rows
                totalX2 = totalX2 + grid[j][i];
                totalY2 = totalY2 + grid[i][j];
            }
            if (totalX1 != factorial || totalY1 != factorial
                    || totalX2 != fibonacci || totalY2 != fibonacci) {
                return false;
            }
            totalX1 = 1;
            totalY1 = 1;
            totalX2 = 0;
            totalY2 = 0;
        }

        return true;

    }

}

After some edits in spacing that are not fixed by the IDE:

import java.util.ArrayList;
import java.util.Arrays;

public class MagicSquareSolver2 {

    static ArrayList<Integer> numbers;
    static int n;
    static int[][] grid;
    static int count;

    public static void main(String[] args) {
        n = 4;
        grid = new int[n][n];
        bruteSolve(0, 0, n);
    }

    public static void bruteSolve(int a, int b, int n) {
        for (int i = 1; i < n + 1; i++) {
            grid[a][b] = i;
            if (b == n - 1 && a == n - 1) {
                if (isValid(grid)) {
                    count++;
                    System.out.println(Arrays.deepToString(grid));
                    System.out.println(count);
                }
            } else if (b == n - 1) {
                bruteSolve(a + 1, 0, n);
            } else {
                bruteSolve(a, b + 1, n);
            }
        }
    }

    public static boolean isValid(int[][] grid) {
        int factorial = 1;
        int fibonacci = 0;
        int totalX1 = 1;
        int totalY1 = 1;
        int totalX2 = 0;
        int totalY2 = 0;

        for (int i = n; i > 0; i--) {
            factorial = factorial * i;
        }
        for (int i = n; i > 0; i--) {
            fibonacci = fibonacci + i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalY1 = totalY1 * grid[i][j]; // checks all columns
                totalX1 = totalX1 * grid[j][i]; // checks all rows
                totalX2 = totalX2 + grid[j][i];
                totalY2 = totalY2 + grid[i][j];
            }
            if (totalX1 != factorial || totalY1 != factorial
                    || totalX2 != fibonacci || totalY2 != fibonacci) {
                return false;
            }
            totalX1 = 1;
            totalY1 = 1;
            totalX2 = 0;
            totalY2 = 0;
        }
        return true;
    }

}

`static` variables

No, no, no. Rarely should you use static variables, such as a public static final class constant, or something that needs to be static when there is no other option available. You can easily redesign your code to not need static variables:

import java.util.Arrays;

public class MagicSquareSolver2 {

    public static void main(String[] args) {
        int n = 4;
        int[][] grid = new int[n][n];
        bruteSolve(0, 0, n, grid);
    }

    public static void bruteSolve(int a, int b, int n, int[][] grid) {
        for (int i = 1, count = 0; i < n + 1; i++) {
            grid[a][b] = i;
            if (b == n - 1 && a == n - 1) {
                if (isValid(grid, n)) {
                    count++;
                    System.out.println(Arrays.deepToString(grid));
                    System.out.println(count);
                }
            } else if (b == n - 1) {
                bruteSolve(a + 1, 0, n, grid);
            } else {
                bruteSolve(a, b + 1, n, grid);
            }
        }
    }

    public static boolean isValid(int[][] grid, int n) {
        int factorial = 1;
        int fibonacci = 0;
        int totalX1 = 1;
        int totalY1 = 1;
        int totalX2 = 0;
        int totalY2 = 0;

        for (int i = n; i > 0; i--) {
            factorial = factorial * i;
        }
        for (int i = n; i > 0; i--) {
            fibonacci = fibonacci + i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalY1 = totalY1 * grid[i][j]; // checks all columns
                totalX1 = totalX1 * grid[j][i]; // checks all rows
                totalX2 = totalX2 + grid[j][i];
                totalY2 = totalY2 + grid[i][j];
            }
            if (totalX1 != factorial || totalY1 != factorial
                    || totalX2 != fibonacci || totalY2 != fibonacci) {
                return false;
            }
            totalX1 = 1;
            totalY1 = 1;
            totalX2 = 0;
            totalY2 = 0;
        }
        return true;
    }

}

What I did with your variables:

static ArrayList<Integer> numbers;

You didn't even use this...
static int n;

Just simply put this in the main method, and added a int n argument to your isValid() method.
static int[][] grid;

Just simply put this in the main method, and added a int[][] grid argument into your bruteSolve() method.
static int count;

You only really need this in your bruteSolve() method; actually just the for loop, so I just put it there.

Naming

What's a? How about b? What is n? Why are they one-letter names?

One-letter variable names are not good, as they are confusing to understand. The only place you should use them is, for example, a for loop counter.

Change:

a into num1
b into num2
n into size (or, optional: remove the n variable completely, and directly use either grid.size or the number itself, or change it into a constant, as I will do)

Final Code

import java.util.Arrays;

public class MagicSquareSolver2 {

    public static final int SIZE = 4;

    public static void main(String[] args) {
        int[][] grid = new int[SIZE][SIZE];
        bruteSolve(0, 0, grid);
    }

    public static void bruteSolve(int num1, int num2, int[][] grid) {
        for (int i = 1, count = 0; i < SIZE + 1; i++) {
            grid[num1][num2] = i;
            if (num2 == SIZE - 1 && num1 == SIZE - 1) {
                if (isValid(grid)) {
                    count++;
                    System.out.println(Arrays.deepToString(grid));
                    System.out.println(count);
                }
            } else if (num2 == SIZE - 1) {
                bruteSolve(num1 + 1, 0, grid);
            } else {
                bruteSolve(num1, num2 + 1, grid);
            }
        }
    }

    public static boolean isValid(int[][] grid) {
        int factorial = 1;
        int fibonacci = 0;
        int totalX1 = 1;
        int totalY1 = 1;
        int totalX2 = 0;
        int totalY2 = 0;

        for (int i = SIZE; i > 0; i--) {
            factorial = factorial * i;
        }
        for (int i = SIZE; i > 0; i--) {
            fibonacci = fibonacci + i;
        }

        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                totalY1 = totalY1 * grid[i][j]; // checks all columns
                totalX1 = totalX1 * grid[j][i]; // checks all rows
                totalX2 = totalX2 + grid[j][i];
                totalY2 = totalY2 + grid[i][j];
            }
            if (totalX1 != factorial || totalY1 != factorial
                    || totalX2 != fibonacci || totalY2 != fibonacci) {
                return false;
            }
            totalX1 = 1;
            totalY1 = 1;
            totalX2 = 0;
            totalY2 = 0;
        }
        return true;
    }

}

Looks good now!

These are good hints, however I think you missed the main point of the question - can the performance be improved and how? — Sva.Mu, Commented Oct 7, 2015 at 19:41
@Sva.Mu I am currently thinking about it; be patient! Also, I can't seem to understand your each line of code and what it does. Just to confirm, your code will check a n by n board to see if each row and column has any duplicate numbers, correct? — TheCoffeeCup, Commented Oct 8, 2015 at 1:11
This is not "my" question :-) but I think this is what OP meant, yes. — Sva.Mu, Commented Oct 8, 2015 at 3:42
@Sva.Mu also, from what I can see when I run the program, is that it generates all possible combinations of a n x n Sudoku Grid, taking into account of all the Sudoku rules: "each row, column and box may not contain the digits 1-9 (or 1 to x in this case) more than once". — TheCoffeeCup, Commented Oct 8, 2015 at 18:22
I guess we have a misunderstanding here as the question was posted by Hisham, not by me - I just read your answer and noticed it doesn't really answer the performance question. — Sva.Mu, Commented Oct 8, 2015 at 18:36

Stack Exchange Network

Sudoku type grid generator

1 Answer 1

Indentation

Spacing

`static` variables

Naming

Final Code

Your Answer

Not the answer you're looking for? Browse other questions tagged
java
performance
sudoku
or ask your own question.

Linked

Hot Network Questions

Sudoku type grid generator

1 Answer 1

Indentation

Spacing

static variables

Naming

Final Code

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged javaperformancesudoku or ask your own question.

Linked

Related

Hot Network Questions

`static` variables

Not the answer you're looking for? Browse other questions tagged
java
performance
sudoku
or ask your own question.