Sudoku solver bug

Question

I don't know what I'm doing wrong, and I've been staring at this code all day. This is a "standard" Sudoku solver in Java, that takes a int[][] with 0's where the empty spaces are. Given I'm only passing in a board with 35 holes, this should be able to solve the vast majority of problems, but can only solve ~66%. In the others, there are a few (usually 2 or 4) empty spaces left, that are impossible to solve (i.e. an improper number has been written into board.) Almost always, it'll be a 9 that's missing.

I understand that such a simple solution will not solve all Sudokus. I'm deliberately giving it easy ones.

import java.util.ArrayList;
import java.util.List;

public class SudokuSolver
{
    public SudokuSolver()
    {
        init();
    }

    public boolean solve()
    {
        /* Each method checks (in different ways) to see if it can find a new number
            If said method does find a number, it sets off a chain reaction, starting back at the beginning.
        */
        int countdown = 20;
        while(!solved() && --countdown > 0)
        {
            if(given())
                continue;
            if(findSingletons())
                continue;
            if(zerosLeft() <= 4)
                justGuess();
        }
        return solved();
    }

    public boolean given()
    {
        boolean repeat = false;
        //Iterate through every given number
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j] != 0 && !found[i][j])
                {
                    repeat = true;
                    foundNum(i, j, board[i][j]);
                }
            }
        }
        //Call given every time a new number is found
        return repeat;
    }

    public boolean findSingletons()
    {
        boolean repeat = false;
        //LOTS of iteration, but I'm out of ideas.
        int[] values;
        ArrayList<Integer> singletons = new ArrayList<Integer>();
        for(int i=0;i<9;i++)
        {
            values = new int[10];
            singletons.clear();
            for(int j=0;j<9;j++)
                for(int k=0;k<possible[i][j].size();k++)
                    values[possible[i][j].get(k)]++;
            for(int j=1;j<10;j++)
                if(values[j] == 1)
                    singletons.add(j);
            for(int j=0;j<9;j++)
                for(int k=0;k<singletons.size();k++)
                    if(possible[i][j].contains(singletons.get(k)))
                    {
                        foundNum(i, j, singletons.get(k));
                        repeat = true;
                    }
        }

        for(int i=0;i<9;i++)
        {
            values = new int[10];
            singletons.clear();
            for(int j=0;j<9;j++)
                for(int k=0;k<possible[j][i].size();k++)
                    values[possible[j][i].get(k)]++;
            for(int j=1;j<10;j++)
                if(values[j] == 1)
                    singletons.add(j);
            for(int j=0;j<9;j++)
                for(int k=0;k<singletons.size();k++)
                    if(possible[j][i].contains(singletons.get(k)))
                    {
                        foundNum(j, i, singletons.get(k));
                        repeat = true;
                    }
        }

        int[] corners = {0,3,6};
        for(int a=0;a<3;a++)
            for(int l=0;l<3;l++)
                for(int i=corners[a];i<corners[a]+3;i++)
                {
                    values = new int[10];
                    singletons.clear();
                    for(int j=corners[l];j<corners[l]+3;j++)
                        for(int k=0;k<possible[i][j].size();k++)
                            values[possible[i][j].get(k)]++;
                    for(int j=1;j<10;j++)
                        if(values[j] == 1)
                            singletons.add(j);
                    for(int j=0;j<9;j++)
                        for(int k=0;k<singletons.size();k++)
                            if(possible[i][j].contains(singletons.get(k)))
                            {
                                foundNum(i, j, singletons.get(k));
                                repeat = true;
                            }
                }
        return repeat;
    }

    public void justGuess()
    {
        outer:
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(board[i][j] == 0)
                {
                    foundNum(i, j, possible[i][j].get(0));
                    break outer;
                }
    }

    public void foundNum(int x, int y, int numFound)
    {

        if(board[x][y] != 0 && board[x][y] != numFound)
        {
            throw new RuntimeException("Attempting to place a number where one was already found");
        }

        board[x][y] = numFound;
        possible[x][y].clear();
        possible[x][y].add(numFound);
        found[x][y] = true;

        for(int i=0;i<9;i++) {
            if(i != x)
                if(possible[i][y].indexOf(numFound) != -1)
                    possible[i][y].remove(possible[i][y].indexOf(numFound));
        }
        for(int i=0;i<9;i++) {
            if(i != y)
                if(possible[x][i].indexOf(numFound) != -1)
                    possible[x][i].remove(possible[x][i].indexOf(numFound));
        }
        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(i != x && j != y)
                    if(possible[i][j].indexOf(numFound) != -1)
                        possible[i][j].remove(possible[i][j].indexOf(numFound));
    }

    public boolean solved() {
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(!found[i][j])
                    return false;
        return true;
    }

    public void reset(int[][] board)
    {
        this.board = board;
        init();
    }

    public void init()
    {
        possible = new ArrayList[9][9];
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
            {
                possible[i][j] = new ArrayList<Integer>();
                for(int k=1;k<10;k++)
                    possible[i][j].add(k);
            }
        found = new boolean[9][9];
    }

    public void print()
    {
        for(int i=0;i<9;i++)
        {
            if(i%3==0 && i != 0)
                System.out.println("-  -  -  | -  -  -  |  -  -  -");
            for(int j=0;j<9;j++)
            {
                if(j%3==0 & j != 0)
                    System.out.print("| ");
                System.out.print(board[i][j] + "  ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private int zerosLeft()
    {
        int empty = 0;
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(board[i][j] == 0)
                    empty++;
        return empty;
    }

    private void data(int difficulty)
    {
        int empty = 0;
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(board[i][j] == 0)
                    empty++;
        System.out.println(empty);
    }

    public static void main(String[] args)
    {
        SudokuGenerator sg = new SudokuGenerator();
        SudokuSolver ss = new SudokuSolver();
        int[][] tempBoard = {{4, 0, 1, 0, 9, 7, 0, 5, 8 },
                        {2, 0, 0, 5, 3, 1, 4, 0, 6 },
                        {5, 0, 6, 4, 0, 2, 0, 3, 9 },
                        {0, 9, 0, 0, 0, 4, 3, 0, 2 },
                        {0, 0, 0, 9, 0, 0, 6, 4, 7 },
                        {7, 0, 4, 0, 0, 0, 9, 0, 5 },
                        {0, 0, 7, 0, 0, 3, 8, 9, 4 },
                        {8, 5, 0, 1, 4, 9, 7, 0, 0 },
                        {9, 0, 3, 8, 7, 6, 0, 0, 0 }};
        ss.reset(tempBoard);
        System.out.println(ss.solve());
        ss.print();
        ss.data(35);
    }

    int[][] board;
    ArrayList<Integer>[][] possible;
    boolean[][] found;
}

I'm still new to programming, so any advice other than solving this would be welcome. (Particularly optimizing possible. That's the most profane code I've written to date.)

Thanks!

Answer 1

I started reading your code, but it feels longer than it should be, and those loops get pretty messy. Nothing jumps out at me immediately. You did say you don't just want solutions, but advice.

You've gotta figure out if the problem is with your design (it doesn't work for solving Sudoku) or if there's just a simple bug somewhere in the implementation. Maybe go through and write comments on what each loop is accomplishing, the "rubber duck test", whereby being forced to explain everything, you'll stop yourself and realize something is unnecessary, or isn't what it needs to be. That helps with design problems.

If the problem is implementation, do you know how to formally debug an application? Set breakpoints and walk through it instruction by instruction? If you've got a little bug, but you don't see where, that's the way to go. Find a really simple example case that fails, then run that test and break it at the beginning. Step through, and follow along the logic. Hopefully, you'll see where it goes awry. Writing JUnit tests or log statements is great, but when you've got a tricky bug, you've gotta do some real breakpoint debugging.

Your general framework is good, you've got some objects to hold the data, and a nice clean solve method which calls a few different methods and loops through them. But each of those methods, wow, they're sure messy. That kind of code, lots of tight loops using the same variable names, lots of array manipulation, its so easy to flub something and get a bug and it makes it really hard to read and find the bug.

Eclipse makes it pretty easy to debug java, if you haven't before. Lots of good tutorials on google, so I won't bother ^_~

Answer 2

You do not seem to implement a backtracking mechanism. There a some times that you have to guess numbers if you do not have the correct heuristic implemented.

Heuristics are "tricks of the trade", here is a list of common ones for sudoku.

If you only programmed a few of them, you will get into dead-ends and will have to guess. This makes it more difficult since will have to take into account that those guesses might be wrong. Backtracking is a strategy that will allow you to "rollback" a few guesses and make different ones. Think of it as a tree of possibilities to make some kind of bruteforce to solve the sudoku.

So your 2 possibilities are to implement more heuristics or find a way to make a wider range of guesses