DFS solving sudoku
<p>I'm working on 16*16 sudoku problem with DFS algorithm. Java code looks like:</p>

<pre><code>    public class dfs {

    public boolean dfs(int[][] puzzle,int i,int j){
        if(i==15&amp;&amp;j&gt;=16) return true;
        if(j==16){
            //System.out.println(String.valueOf(i));

            return dfs(puzzle,i+1,0);  //{j=0; i++;
        }
        if(puzzle[i][j]!=-1){
            return dfs(puzzle,i,j+1);  //next cell in the same row
        }
        else{
            for(int num=1;num&lt;=16;num++){
                //System.out.println("trying"+i+","+j+","+num);
                if(valid(puzzle,i,j,num)){
                    //System.out.println(String.valueOf(num));
                    puzzle[i][j]=num;
                    if(dfs(puzzle,i,j+1)){
                        return true;

                    }
                }
                //else return false;
            }
        }
        return false;
    }
    public boolean valid(int[][] puzzle,int x,int y,int num){
        for(int i=0;i&lt;16;i++){
            if(puzzle[i][y]==num) {
                //System.out.println("a");
                return false;
            }
        }
        for(int j=0;j&lt;16;j++){
            if(puzzle[x][j]==num){
                //System.out.println("b");
                return false;
            }
        }
        int c=(x/4)*4;
        int r=(y/4)*4;
        for(int i=0;i&lt;4;i++){
            for(int j=0;j&lt;4;j++){
                if(puzzle[c+i][r+j]==num){
                    //System.out.println("c");
                    return false;
                }
            }

        }
        return true;

    }
}
</code></pre>

<p>And the main method is:</p>

<pre><code> public static void main(String[] args) {
        sudoku sudokuPuzzleGenerator = new sudoku();
        long start = System.currentTimeMillis();
        int numOfSudokuMatrix = 1;
        List&lt;int[][]&gt; sudoku = new ArrayList&lt;int[][]&gt;();
        for (int count = 1; count &lt;= numOfSudokuMatrix; count++) {
            int[][] randomMatrix = sudokuPuzzleGenerator.generatePuzzleMatrix();
            int hole = 81;
            while (hole &gt; 0) {
                Random randomGenerator = new Random();
                int x = randomGenerator.nextInt(16);
                int y = randomGenerator.nextInt(16);
                if (randomMatrix[x][y] != -1) {
                    randomMatrix[x][y] = -1;
                    hole--;
                }
            }
            for(int i=0;i&lt;16;i++){
                for(int j=0;j&lt;16;j++){
                    System.out.print(randomMatrix[i][j] + " ");
                }
                System.out.println();
            }
            sudoku.add(randomMatrix);
        }
        System.out.println();


        long start2 = System.currentTimeMillis();
        for (int[][] p:sudoku) {
            dfs d=new dfs();
            boolean b=d.dfs(p,0,0);
            for (int rowNum = 0; rowNum &lt; 16; rowNum++) {
                for (int colNum = 0; colNum &lt; 16; colNum++) {
                    System.out.print(p[rowNum][colNum] + " ");
                }
                System.out.println();
            }
        }
        Long end2 = System.currentTimeMillis();
        Long time2 = end2 - start2;
        System.out.println("It took: " + time2  + " milliseconds.");

    }
</code></pre>

<p>When I run the code, it often terminates before all blank spaces be filled, leaving many -1 in the puzzle. I'm not sure where the problem is. I will be really thankful for any help!</p>