# Sudoku type grid generator

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/… Oct 7, 2015 at 2:28
• you could use *= and += to make your code less verbose.
– MAG
Oct 7, 2015 at 5:51

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:

1. static ArrayList<Integer> numbers;

You didn't even use this...

2. static int n;

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

3. static int[][] grid;

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

4. 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:

1. a into num1
2. b into num2
3. 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? 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? Oct 8, 2015 at 1:11
• This is not "my" question :-) but I think this is what OP meant, yes. 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". 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. Oct 8, 2015 at 18:36