4
\$\begingroup\$

This was my first time attempting a project like this, so I figured it would improve readability, and would also just be nice If I allowed each stage to be visualized.

Also, this only generates them, I haven't done any solving code, so it can't know if a puzzle has multiple solutions. I didn't forget, I just want to perfect this part first.

First up is the Main.java class. it contains the vast majority of my code, and is divided up into several methods whose purposes should be pretty obvious. also, I'd like to mention that while I don't have it implemented here, my code could scale up puzzles other sizes as well.

package com.kestrel.sudoku.generate;

import java.util.Random;

public class Main4
{
    public static int[] seed = new int[81];
    public static int[] cells = new int[81];
    public static int[] finalPuzzle = new int[81];

    public static void main(String[] args)
    {
        genSeed();
        genSudoku();
        genResult();

        printSeed();
        System.out.println();
        printSudoku();
        System.out.println();
        printResult();

    }

    public static boolean genSudoku()
    {
        Random r = new Random();

        for(int y = 0; y < 9; y++)
        {
            for(int x = 0; x < 9; x++)
            {
                if(cells[9 * y + x] == 0)
                {
                    for(int i = 0; i < 9; i++)
                    {
                        int n = r.nextInt(9) + 1;

                        if(isSafe(x, y, n))
                        {
                            cells[9 * y + x] = n;

                            if(genSudoku())
                            {
                                return true;
                            }
                            else
                            {
                                cells[9 * y + x] = 0;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    public static boolean isSafe(int x, int y, int n)
    {
        for (int i = 0; i < 9; i++)
        {
            if(cells[9 * y + i] == n)
            {
                return false;
            }
        }

        for (int i = 0; i < 9; i++)
        {
            if(cells[9 * i + x] == n)
            {
                return false;
            }
        }

        for (int a = 0 ; a < 3; a++)
        {
            for (int b = 0 ; b < 3; b++)
            {

                if (cells[9 * (y - y % 3) + (x - x % 3) + (9 * a + b)] == n)
                {
                    return false;
                }
            }
        }
        return true;
    }

    public static void fill(int[] a, int num)
    {
        for (int i = 0; i < a.length; i++)
        {
            cells[i] = num;
        }
    }

    public static void genSeed()
    {
        Random r = new Random();

        for(int i = 0; i < 9; i++)
        {
            int n = r.nextInt(81);
            if(seed[n] == 1 || seed[80 - n] == 1 )
            {
                i--;
            }
            else
            {
                seed[n] = 1;
                seed[80 - n] = 1;
            }
        }
    }

    public static void genResult()
    {
        for(int y = 0; y < 9; y++) 
         { 
             for (int x = 0; x < 9; x++)
             {
                 if(seed[9 * y + x] == 1)
                 {
                     finalPuzzle[9 * y + x] = cells[9 * y + x];
                 }
                 else
                 {
                     finalPuzzle[9 * y + x] = 0;
                 }
             }
         }
    }

    public static void printSeed()
    {
        for(int y = 0; y < 9; y++) 
         { 
             for (int x = 0; x < 9; x++)
             {
                 System.out.print(seed[9 * y + x] + " ");
                 if(x % 3 == 2 && x < 8)
                 {
                     System.out.print("| ");
                 }
             }
             System.out.println();
             if(y % 3 == 2 && y < 8)
             {
                 System.out.println("---------------------");
             }
         } 
    }

    public static void printSudoku() 
    { 
         for(int y = 0; y < 9; y++) 
         { 
             for (int x = 0; x < 9; x++)
             {
                 System.out.print(cells[9 * y + x] + " ");
                 if(x % 3 == 2 && x < 8)
                 {
                     System.out.print("| ");
                 }
             }
             System.out.println();
             if(y % 3 == 2 && y < 8)
             {
                 System.out.println("---------------------");
             }
         } 
    }

    public static void printResult() 
    { 
         for(int y = 0; y < 9; y++) 
         { 
             for (int x = 0; x < 9; x++)
             {
                 if(seed[9 * y + x] == 1)
                 {
                     System.out.print(finalPuzzle[9 * y + x] + " ");
                 }
                 else
                 {
                     System.out.print("  ");
                 }

                 if(x % 3 == 2 && x < 8)
                 {
                     System.out.print("| ");
                 }
             }
             System.out.println();
             if(y % 3 == 2 && y < 8)
             {
                 System.out.println("---------------------");
             }
         } 
    }
}

One part that I'm really not happy with is that I couldn't figure out any solution other than a recursive function for generating the full Sudoku. I'm guess It might just be because I'm still semi-new to programming, but It just looks really ugly. at one point, I thought I had a solution, a double for loop where one would increment, and the other would decrement, and they shared a variable, but I just couldn't get it to work. I guess the other thing I should mention is the lack of 2d arrays in my code. I don't like them either. I'd rather just do the math. I don't know if it's faster, (its probably not) but I think that's just kinda my coding style at this point. plus, I didn't have to iterate over every single cell this way. only the ones I wanted to. I think that should be it. Looking at it now... I think I could probably get rid of some duplicate code in the isSafe() and printX() functions. so... how did I do?

\$\endgroup\$
  • \$\begingroup\$ What is the purpose of the class Cell? It is never used in the main program? \$\endgroup\$ – Benjamin Kuykendall Mar 11 at 22:02
  • \$\begingroup\$ ... you are correct. One of the previous versions used it, and I guess I got confused. My project basically looks like a whole bunch of main#.java files, and then whatever else they use, with pretty much zero indication of what uses what. I'll fix that. \$\endgroup\$ – HamBone41801 Mar 11 at 22:54
  • \$\begingroup\$ genSudoku() is actually also a puzzle solving function, in addition to being a puzzle generating function. So you can use that to verify that the final puzzle has a solution (although there may be more than 1 solution). However it is quite inefficient and I suggest looking at other sudoku solvers for inspiration (some are on this site even). \$\endgroup\$ – JS1 Mar 13 at 7:43
2
\$\begingroup\$

For generating one Sudoku, you should only create a single random number generator. It should be configurable so that you can pass a predictable random number generator during tests. Like this:

public class SudokuGenerator {

    private final Random rnd;

    public SudokuGenerator(Random rnd) {
        this.rnd = rnd;
    }

    public Sudoku generate() {
        …
    }
}

The current genSolve code looks frightening and inefficient. Having a 3-times nested for loops combined with 3 intermingled if statements and calling this method recursively sounds like a bad design. There must be something simpler. I don't know what, but it must exist.

A fairly advanced Sudoku generator is available as part of Simon Tatham's Puzzle Collection. The code is written in C but has lots of explaining comments, so you should be able to get some ideas.

\$\endgroup\$
  • \$\begingroup\$ Yeah, it was pretty much a nightmare to get working. Trust me, if I could have gotten that damn for-loop-thing to work, I 100% would have used it instead. The issue was that it just didn't "remember" stuff like the resursive one did. I tried to implement it with a stack, but no dice. \$\endgroup\$ – HamBone41801 Mar 12 at 1:35
2
\$\begingroup\$
  1. The fill method is never used.

  2. State should not be public static. By passing the relevant data to the relevant methods, you can make a lot more sense of your code, and allow more reusability of methods.

  3. None of your methods save main need be public.

  4. Choosing a data structure is not a matter of coding style! If you are going to use a 1D array to represent a grid, a rather unintuitive choice, it better help you write elegant code. There are a few places were we can use this 1D structure to our advantage: looping over n instead of x, y in genSodoku and genResult for instance.

  5. genSoduku is implemented very inefficiently. Instead of looping to find the next empty value, just pass it to the recursive call.

  6. In the same method, you need to use a random permutation instead of a random generator. Random.nextInt samples "with replacement"; thus some numbers might not be considered. I used Collections.shuffle to do same "without replacement" instead.

  7. genSeed is ill-documented. Explain why you are selecting numbers likes this.

  8. In genResult multiply cells[n] and seed[n] to get the same result.

  9. Consolidate printing into a single printBoard method that take a 9-by-9 table.

import java.util.Random;
import java.util.stream.IntStream;
import java.util.stream.Collectors;
import java.util.Collections;
import java.util.List;

public class Main4 {

    public static void main(String[] args) {
        int[] seed = genSeed();
        int[] cells = genSudoku();
        int[] finalPuzzle = genResult(seed, cells);

        printBoard(seed);
        printBoard(cells);
        printBoard(finalPuzzle);
    }

    private static int[] genSudoku() {
        int[] cells = new int[81];
        genHelper(cells, 0);
        return cells;
    }

    private static List<Integer> getPermutation() {
        List<Integer> choices = IntStream.rangeClosed(1,9)
            .boxed().collect(Collectors.toList());
        Collections.shuffle(choices);
        return choices;
    }

    private static boolean genHelper(int[] cells, int n) {
        if (n == 81) {
            return true;
        }

        List<Integer> choices = getPermutation();
        for (int k : choices) {
            if(isSafe(cells, n, k)) {
                cells[n] = k;
                if(genHelper(cells, n + 1)){
                    return true;
                }
            }
        }

        cells[n] = 0;
        return false;
    }

    private static boolean isSafe(int[] cells, int n, int k) {
        int y = n / 9, x = n % 9;

        for (int i = 0; i < 9; i++) {
            if(cells[9 * y + i] == k || cells[9 * i + x] == k) {
                return false;
            }
        }

        for (int a = 0 ; a < 3; a++) {
            for (int b = 0 ; b < 3; b++) {
                if (cells[9 * (y - y % 3) + (x - x % 3) + (9 * a + b)] == k) {
                    return false;
                }
            }
        }
        return true;
    }

    private static int[] genSeed() {
        int[] seed = new int[81];
        Random r = new Random();

        for(int i = 0; i < 9; i++) {
            int n = r.nextInt(81);
            if(seed[n] == 1 || seed[80 - n] == 1 ) {
                i--;
            } else {
                seed[n] = 1;
                seed[80 - n] = 1;
            }
        }
        return seed;
    }

    private static int[] genResult(int[] seed, int[] cells) {
        int[] finalPuzzle = new int[81];
        for(int n = 0; n < 81; n++) {
            finalPuzzle[n] = seed[n] * cells[n];
        }
        return finalPuzzle;
    }

    private static void printBoard(int[] board) {
        for(int y = 0; y < 9; y++) { 
            for (int x = 0; x < 9; x++) {
                System.out.print(board[9 * y + x] + " ");
                if(x % 3 == 2 && x < 8) {
                    System.out.print("| ");
                }
            }
            System.out.println();
            if(y % 3 == 2 && y < 8) {
                System.out.println("---------------------");
            }
        }
        System.out.println();
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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