Recursive solution to Sudoku generator

Question

I'm trying to code an algorithm that creates a legal Sudoku board in either Java or Javascript. Neither work, and I'm not entirely sure why.

Essentially, the problem in both programs is that either x or y is getting incremented more than it should (skipping the square). I can't for the life of me figure out how this is happening. I can provide the HTML that completes the JS solution if need be.

My best guess is it has to do with how I've created a stack using recursion, but as far as I can tell, it should work. In my old code there was an incorrect for loop, I'm aware of this. I pasted an old version, it's fixed now.

Java:

import java.util.*;

public class SudokuGenerator
{
//credit:cachao
//https://mcmap.net/q/1160001/-recursive-solution-to-sudoku-generator
public static final int BOARD_WIDTH = 9;
public static final int BOARD_HEIGHT = 9;

public SudokuGenerator() {
    board = new int[BOARD_WIDTH][BOARD_HEIGHT];
}
//Recursive method that attempts to place every number in a square
public int[][] nextBoard()
{
    nextBoard(0,0);
    return board;
}

public void nextBoard(int x, int y)
{
    int nextX = x;
    int nextY = y;
    //int[] toCheck = Collections.shuffle(Arrays.asList({1,2,3,4,5,6,7,8,9}));
    int[] toCheck = {1,2,3,4,5,6,7,8,9};
    Collections.shuffle(Arrays.asList(toCheck));

    for(int i=0;i<toCheck.length;i++)
    {
        if(legalMove(x, y, toCheck[i]))
        {
            board[x][y] = toCheck[i];
            if(x == 8)
            {
                if(y == 8)
                    break;//We're done!  Yay!
                else
                {
                    nextX = 0;
                    nextY++;
                }
            }
            else
            {
                nextX++;
            }
            nextBoard(nextX, nextY);
        }
    }
    board[x][y] = 0;
}

public boolean legalMove(int x, int y, int current) {
    for(int i=0;i<9;i++) {
        if(current == board[x][i])
            return false;
    }
    for(int i=0;i<9;i++) {
        if(current == board[i][y])
            return false;
    }
    int cornerX = 0;
    int cornerY = 0;
    if(x > 2)
        if(x > 5)
            cornerX = 6;
        else
            cornerX = 3;
    if(y > 2)
        if(y > 5)
            cornerY = 6;
        else
            cornerY = 3;
    for(int i=cornerX;i<10 && i<cornerX+3;i++)
        for(int j=cornerY;j<10 && j<cornerY+3;j++)
            if(current == board[i][j])
                return false;
    return true;
}

public void print()
{
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
            System.out.print(board[i][j] + "  ");
        System.out.println();
    }
}

public static void main(String[] args)
{
    SudokuGenerator sg = new SudokuGenerator();
    sg.nextBoard();
    sg.print(); 
}
int[][] board;
}

Javascript:

//Recursive method that attempts to place every number in a square
function driver()
{
    board = new Array(10);
    for(var i=0;i<9;i++)
        board[i] = new Array(10);
    nextBoard(0,0);
    print();
}

function nextBoard(x, y)
{
    var nextX = x;
    var nextY = y;
    for(var i=1;i<10;i++) {
        console.log(y + " " + x + " " + i);
        document.getElementById(y + " " + x).innerHTML = i;
        if(legalMove(x, y, i)) {
            board[x][y] = i;
            if(x === 8) {
                if(y === 8)
                    return board;//We're done!  Yay!
                else {
                    nextX = 0;
                    nextY++;
                }
            }
            else
                nextX++;
            nextBoard(nextX, nextY);
        }
    }
    //This is needed for legalMove to work, otherwise [x][y] == 9
    board[x][y] = undefined;
}

function legalMove(x, y, current) {
    for(var i=0;i<9;i++) {
        if(current === board[x][i])
            return false;
    }
    for(var i=0;i<9;i++) {
        if(current === board[i][y])
            return false;
    }
    var cornerX = 0;
    var cornerY = 0;
    if(x > 2)
        if(x > 5)
            cornerX = 6;
        else
            cornerX = 3;
    if(y > 2)
        if(y > 5)
            cornerY = 6;
        else
            cornerY = 3;
    for(var i=cornerX;i<10 && i<cornerX+3;i++)
        for(var j=cornerY;j<10 && j<cornerY+3;j++)
            if(current === board[i][j])
                return false;
    return true;
}

function print() {
    for(var i=0;i<9;i++)
        for(var j=0;j<9;j++)
        {
            document.getElementById(i + " " + j).innerHTML = board[i][j];
            console.log(board[i][j]);           
        }
}

var board;

Headspring

Put the code in the question instead of a pastebin. – Mouthwatering

Answer 1

Java:

1. You should initialize your board variable, you may want to initialize it in a constructor:

   public class SudokuGenerator {
   
       public static final int BOARD_WIDTH = 9;
       public static final int BOARD_HEIGHT = 9;
   
       public SudokuGenerator() {
           board = new int[BOARD_WIDTH][BOARD_HEIGHT];
       }
   }
   

2. I believe that your loop iterator in the function nextBoard it is wrong:

   for(int i=1;i<10;i++){ ... }

   I think that you want to iterate from 0 to 9.

3. In the function nextBoard, you also need to check the variable:

   int[] toCheck = {1,2,3,4,5,6,7,8,9};

   You get an java.lang.ArrayIndexOutOfBoundsException, you should initialize it from 0 to 8, otherwise you try to access the board row number 9 and you get a runtime error.

4. Another problem that you need to solve is that x is being set to nine in nextBoard() function. Call the function nextBoard(int x, int y) "manually" with these parameteres: nextBoard(7,3) and you will understand why x is being set to nine. Check specifically the values of the variable nextX.

I believe it will really help you if you use a debugger to check this kind of errors, here you have a nice tutorial with a video explanation(in case your are using the Eclipse IDE).

Hope it helps.

Corporative

Try to check this errors and then post a more specific question. – Corporative

I've already fixed these errors. Like I said, that was old code. If you'd like to explain how x and/or y are getting set to nine, that'd be great! – Headspring

Perfect @SomeKittens. I have updated my question now, I hope it helps. – Corporative

Answer 2

In the Java code: I'll translate it to psuedocode:

for all z values:
    If for current (x,y), the number 'z' is legal then:
        insert z to current (x,y)
        if finished
            hooray!
        else 
            go to next square
    else try next number

But what if you can't put any number there as it ends up being illegal (aka a board where you can't insert any number in a specific square)?

You don't address that. What you need to do is implement it via backtracking:

for all z values:
    If for current (x,y) the number 'z' is legal then:
        insert z to current (x,y)
        go to next(x,y)
            try to complete the board    // recursive call
        if you completed the board       // == the result of the recursion is legal
            return the completed board
    If all z values have been attempted
        return "cannot complete board"
    increment z, try again with current (x,y)

Argosy

I see what you're doing there, and I understand. I thought I had already handled it by using a recursive stack. If square P was legal at 4, then moved on to square Q, where nothing was legal, wouldn't the recursion move back to P and then try it at 5? – Headspring

It wouldn't - you have no part in the code that does backtracking. The heart of the problem is a decision: if it worked, nice, otherwise, try the next option. You don't have a clause to handle "what if my guess was legal, but I can't solve it from there?" - which basically means you need to save the current board, try it with the first legal guess, and if there is no solution, treat it as if it was a wrong guess – Argosy

I've made the changes you suggest and the problem persists. I still don't fully understand why, after a failed recursive call, the function stops running. – Headspring

You need your recursive call to accept the x and y values, the number, and a board to work on. That way, you just send a .clone() of the board with the legal guess (mark square 0, 0 as -1 if you fail, for instance). Do the end condition first, then the iteration (if x == 8, then try with x == 0 and y++, and the such) at the start, then do something like: int[][] board = recursive call using this.clone() for next x, y... if board[0][0] == -1, call recursively and increment value – Argosy

Answer 3

Java:

Your loop iterator in nextBoard range from 1 to 9. I don't think you meant that. Same in the function legalMove.... initialize cornerX and cornerY to 0.

Determined

Whoops, looks like I pasted an old version of my code. I'll fix that. – Headspring

Answer 4

interesting question, I just noticed this one bug in the Java code: isn't the call to Collection.shuffle() useless since the toCheck array will remain unmodifed (unshuffled) after this call? Here is my quick fix (and I'm sure there are more clever ways to do it):

List<Integer> lst = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
Collections.shuffle(lst);
for (int i=0; i<lst.size(); i++)
    toCheck[i] = lst.get(i);

Firebrand

Wow, what a blast from the past. You're right, we discovered that as I was presenting in front of the class. Embarrassing. – Headspring

Answer 5

In Java array indexes are zero-based. In nextBoard you loop over 1..9 for i and use it as an index into toCheck which will skip the first element at index 0 and go past the end of the array. This will throw ArrayIndexOutOfBoundsException if the line containing toCheck[i] is reached with i equal to 9.

Stubbs

I've fixed that, but the problem still exists. It looks like x and/or y is getting set to nine somehow, and I don't know why. – Headspring

Answer 6

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;


public class SudokuNrupen {

     public static int[][] p;
     public static int tmp[] ;
     public static int tmp2D[][] ;


    public static void main(String[] args){

        tmp = new int[9];
        tmp2D = new int[3][3];
        p = new int[9][9];

         System.out.print("Enter the name of he file below ");
         Scanner scan = new Scanner (System.in);
         String name = scan.nextLine();
         File file = new File( name );

         if ( file.exists()){   
            try {
                Scanner inFile = new Scanner( file );
                for(int i=0; i<9; i++){
                     for(int j=0; j<9; j++){
                         if(inFile.hasNextInt()){
                             p[i][j] = inFile.nextInt();
                         }
                     }
                 }   
            inFile.close();
            } catch (FileNotFoundException ex) {
                Logger.getLogger(SudokuNrupen.class.getName()).log(Level.SEVERE, null, ex);
            }
       }

      display(p);
      solve(p);
      System.out.println("Solved Sudoku is:");
      display(p);      


     }

     public static void display(int [][] p)
    {
        for(int i=0; i<p.length;i++)
        {
            for(int j=0; j<p[i].length;j++)
            {
                System.out.print("   ");
                if(p[i][j]<10)     System.out.print(p[i][j] + " ");
                else                    System.out.print(p[i][j]);
                System.out.print("  ");
            }
            System.out.println();
        }    
    }  

    public static boolean solve(int [][] p)
    {
        if(!isValidSudoku(p))
        {
             return false;
        }
        if(isComplete(p)==true)
        {
            return true;
        }
        for(int i=0; i<9; i++)
        {
            for(int j=0 ; j<9 ; j++)
            {
                if(p[i][j]==0) 
                {
                    int k=1;
                    while(k<=9)
                    {
                        p[i][j]=k;
                        if(solve(p))
                        {
                            return true;
                        }
                        else    k++;
                    }    
                    p[i][j]=0; 
                    return false; 
                }
            }
        }
        return true;
    }


    public static boolean isComplete(int [][]p)
    {
        for(int i=0; i<9; i++)
        {
            for(int j=0 ; j<9 ; j++)
            {
                if(p[i][j]==0){
                    return false;
                }
            }
        }
        return true;
    }    


    public static boolean isRepeated(int [] a)
    {
        for(int i=0; i<8; i++)
        {
            if((a[i]!=0 || a[i+1]!=0))
            {
                     if(a[i]==a[i+1]){
                         return true;
                     }
            }  
        }
        return false;    
    }


 public static boolean isDuplicateEx0(int [][]p)
    {

        for(int i=0; i<p[0].length; i++)
        {
            for(int j=0 ; j<9 ; j++)
            {
                tmp[j]=p[i][j];
            }
            Arrays.sort(tmp);

            System.out.println(Arrays.toString(tmp));

            if(isRepeated(tmp)==true)
            {
                System.out.println("Duplicates are found in row");
                return true;
            }

        }

        display(p);
        for(int j=0; j<p[0].length; j++)
        {
            for(int i=0 ; i<9 ; i++)
            {
                tmp[i]=p[i][j];
            }
            Arrays.sort(tmp);

            if(isRepeated(tmp)==true)
            {
                System.out.println("Duplicates are found in columns");
                return true;
            }

        }

        display(p);

        for(int z=0;z<9;z++){
            tmp[z]=0;
        }

        int x=0,y=0;

        for(int i=0; i<3;i++)
        {   
            y=0;
            for(int j=0;j<3;j++)
            {
                tmp2D[x][y]=p[i][j];
                y++;
            }
            x++;
        }
        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
            }
        }
        Arrays.sort(tmp);
        if(isRepeated(tmp)==true)
        {
            return true;
        }

        for(int z=0;z<9;z++){
            tmp[z]=0;
        }
        x=0;
        y=0;

        for(int i=0; i<3;i++)
        {   
            y=0;
            for(int j=3;j<6;j++)
            {
                tmp2D[x][y]=p[i][j];
                y++;
            }
            x++;
        }
        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
            }
        }
        Arrays.sort(tmp);
        if(isRepeated(tmp)==true)
        {
            return true;
        }


        for(int z=0;z<9;z++){
            tmp[z]=0;
        }
        x=0;
        y=0;

        for(int i=0; i<3;i++)
        {   
            y=0;
            for(int j=6;j<9;j++)
            {
                tmp2D[x][y]=p[i][j];
                y++;
            }
            x++;
        }
        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
            }
        }
        Arrays.sort(tmp);
        if(isRepeated(tmp)==true)
        {
            return true;
        }

        for(int z=0;z<9;z++){
            tmp[z]=0;
        }
        x=0;
        y=0;

        for(int i=3; i<6;i++)
        {   
            y=0;
            for(int j=0;j<3;j++)
            {
                tmp2D[x][y]=p[i][j];
                y++;
            }
            x++;
        }
        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
            }
        }
        Arrays.sort(tmp);
        if(isRepeated(tmp)==true)
        {
            return true;
        }

        for(int z=0;z<9;z++){
            tmp[z]=0;
        }
        x=0;
        y=0;

        for(int i=3; i<6;i++)
        {   
            y=0;
            for(int j=3;j<6;j++)
            {
                tmp2D[x][y]=p[i][j];
                y++;
            }
            x++;
        }
        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
            }
        }
        Arrays.sort(tmp);
        if(isRepeated(tmp)==true)
        {
            return true;
        }

        for(int z=0;z<9;z++){
            tmp[z]=0;
        }
        x=0;
        y=0;

        for(int i=3; i<6;i++)
        {   
            y=0;
            for(int j=6;j<9;j++)
            {
                tmp2D[x][y]=p[i][j];
                y++;
            }
            x++;
        }
        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
            }
        }
        Arrays.sort(tmp);
        if(isRepeated(tmp)==true)
        {
            return true;
        }

        for(int z=0;z<9;z++){
            tmp[z]=0;
        }
        x=0;
        y=0;

        for(int i=6; i<9;i++)
        {   
            y=0;
            for(int j=0;j<3;j++)
            {
                tmp2D[x][y]=p[i][j];
                y++;
            }
            x++;
        }
        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
            }
        }
        Arrays.sort(tmp);
        if(isRepeated(tmp)==true)
        {
            return true;
        }

        for(int z=0;z<9;z++){
            tmp[z]=0;
        }
        x=0;
        y=0;

        for(int i=6; i<9;i++)
        {   
            y=0;
            for(int j=3;j<6;j++)
            {
                tmp2D[x][y]=p[i][j];
                y++;
            }
            x++;
        }
        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
            }
        }
        Arrays.sort(tmp);
        if(isRepeated(tmp)==true)
        {
            return true;
        }

        for(int z=0;z<9;z++){
            tmp[z]=0;
        }
        x=0;
        y=0;

        for(int i=6; i<9;i++)
        {   
            y=0;
            for(int j=6;j<9;j++)
            {
                tmp2D[x][y]=p[i][j];
                y++;
            }
            x++;
        }
        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
            }
        }
        Arrays.sort(tmp);
        if(isRepeated(tmp)==true)
        {
            return true;
        }


        return false;
    }



     public static boolean isValidSudoku(int [][] p)
     {
           return (!isDuplicateEx0(p));  
     }
}

Divisibility

Please update your previous answer, rather than creating a whole new answer. – Gangway