HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Sudoku type grid generator

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewjavastackoverflowperformancesudoku
typesudokugridgenerator

Problem

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 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; i0; 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;

}

}

Solution

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

Code Snippets

static int [] [] grid;
for  (int i=1; i<n+1; i++){
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;

    }

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

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

}

Context

StackExchange Code Review Q#106771, answer score: 5

Revisions (0)

No revisions yet.