help!! Solving Sudoku via recursion and backtracking

deanchhsw

Hello, I'm trying to build a program that solves sudokus and prints out the result on the screen. Here's the code for the class SudokuBoard. this will later be called in a class Sudoku. I'm a newbie, so making this took me hours and hours of time...

Expand|Select|Wrap|Line Numbers

 
// class SudokuBoard, will be called by class Sudoku
 
import java.util.Scanner;

import java.io.*;
 
public class SudokuBoard {
 
    private int[][] board = new int[9][9];
 
    // it reads the established sudoku board from a scanner, which

       will be given when the class Sudoku calls upon the  method.

    public void readBoardFromScanner(Scanner s) {
 
    for (int i=0; i<9; i++) 

        for (int j=0; j<9;j++) 

        board[i][j] = s.nextInt();                   

    }
 
    public void printBoard() {
 
    System.out.println("The Board is:");
 
    for(int i=0; i<9; i++){

        for (int j=0; j<9; j++){  

        System.out.print(board[i][j]+" "); 

        }

        System.out.println(" ");

    }
 
    }

 // checks the row to see if a given # is okay

    public boolean rowCheck(int i, int number) throws Exception {
 
    for (int j = 0; j < 9 ; j++)

        if (board[i][j] == number )

        return false;
 
    return true;

    }

// checks the column to see if a given # is okay

    public boolean columnCheck(int j, int number) throws Exception {
 
    for (int i = 0; i < 9; i++)

        if (board[i][j] == number )

        return false;
 
    return true;

    }

// checks the 3*3 box to see if a given # is okay

    public boolean smallBoxCheck(int i, int j, int number) throws Exception { 
 
    int k = (i/3);

    int l = (j/3);
 
    int row = k * 3;

    int col = l * 3; 
 
    // the above steps are for round-offs so that i=6,7,8 can start

    // altogether with row starting point 6, i=4,5,6 with row starting

    // point 4, etc. Same logic with columns. 
 
    for (int x = 0; x < 3; x++)

        for (int y = 0; y < 3; y++)

        if(board[row+x][col+y] == number )

            return false;
 
    return true;

    }

// the active part begins here

    public void solve(int i, int j) throws Exception {
 
    if ( i > 8 )

        throw new Exception ( "Solution Found" ) ;

    else

        {

            while( board[i][j] != 0 ) {

                 if ( ++j > 8 )

              {

                                         j = 0;

                             i ++;
 
                                        if ( i > 8 )

                     throw new Exception ("Solution Found");

              }

        }
 
            for (int num = 1; num < 10; num++) {
 
                          if (columnCheck(i,num) && rowCheck(i,num) && smallBoxCheck(i,j,num)) {

            board[i][j] = num;
 
// after setting the number, call the next recursive call

            if ( j < 8 )

                solve( i, j+1);

            else 

                solve (i+1, 0);

            }

        }
 
// no solutions found, set the spot to 0 and backtrack

        board[i][j] = 0;            

        }

    }
 
// Start solving at 0,0

    public void startSolve() {

    try {

        solve(0,0);

    }
 
    catch (Exception exception )

        { }

    }

}
 
and then, here is the call from the class Sudoku :
 
import java.io.*;

import java.util.Scanner;
 
public class Sudoku {
 
    public static void main (String[] args) throws FileNotFoundException {
 
    Scanner text;

    text = setFileScanner("board1");
 
    SudokuBoard sb = new SudokuBoard();
 
    sb.readBoardFromScanner(text);
 
    sb.printBoard(); // print the original board
 
    sb.startSolve(); // solve the board
 
    sb.printBoard(); // supposed to print the "solved" board
 
    }
 
    public static Scanner setFileScanner(String fileName) throws FileNotFoundException {
 
        File randomName = new File(fileName);

        Scanner t = new Scanner(randomName);

        return t;

    }
 
}

Okay, now, the second sb.printBoard(); still gives me the original board on the screen. I don't really understand what I did wrong, but it seems that none of the "solution" numbers are replacing the zeroes(blanks) within the original board. What am I doing wrong here? Thank you so much.

deanchhsw

I'm sorry, I didn't know that I shouldn't post questions here, if somebody(admin?) would kindly move it to an appropriate thread, I'll be grateful

Nepomuk

Actually, this is the right place. (Of course, someone may have already moved it here, I don't know.) However, you didn't use the [code]...[/code] tags. I've added them for you this time, but please use them yourself from now on.

Now, to help you with your code. First of all, you shouldn't really be using Exceptions like that. When using recursion, you should stop at a certain point, but not by throwing an exception but by not calling itself again.

Also, your algorithm looks weird to me - what exactly are you trying to do there? Could you write it in pseudo code or describe it in words?

If you would like to look at a finished solution (you may not want to, that's your choice), you can check the Sudoku howto Part A, B and C.

Greetings,
Nepomuk (Moderator)

deanchhsw

Okay, I'll describe what it does in words:

Class Sudoku exists to do the following:

read the file which includes a sudoku board and convert it into a scanner,
which will be then sent into class SudokuBoard as an argument within a
method that will read from scanner and convert them into an private array board[][]

and execute methods within SudokuBoard, which is just for the simplicity's sake.

Class SudokuBoard does the following:

read the Scanner file given by SudokuBoard and convert/stow them into a private array int[][] board; (the method readBoardFromScanner does this)

then, the methods rowCheck, columnCheck and smallBoxCheck will check whether numbers 0-9 fit into a cell. These methods will all be run in conjunction, and when all of these hold true, I will be placing that number into the cell(in the method solve).

Finally, the method solve:
it's supposed to do the following, i don't know if it did exactly that:

find a spot on the board which is zero, if there are no such spots,
return the board.

for each number from 1-9,
check to see if the boolean conditions from above three "checkers" are true.
if they are, set that number into the given cell. (since this will be in a loop, every number from 1-9 will be checked, yes?) and then solve the next cell.

I wasn't sure how to make the solver stop when it reaches the end of the board,
so I threw an exception. If that's not the way it's supposed to do it, how should I go about the problem? If I leave out that exception, it will go into an infinite loop since it doesn't know when to stop.

I will go look at the solutions you have given me now, and see if I can answer my own questions; but in the meantime, any help is appreciated. Thank you very very much for your time!

help!! Solving Sudoku via recursion and backtracking

re: help!! Solving Sudoku via recursion and backtracking

re: help!! Solving Sudoku via recursion and backtracking

re: help!! Solving Sudoku via recursion and backtracking

/bytes/development

/bytes/it

/bytes/about