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
//http://stackoverflow.com/questions/9959172/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;

Answer 1

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)

Answer 2

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.

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.