By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
462,230 Members | 669 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 462,230 IT Pros & Developers. It's quick & easy.

help!! Solving Sudoku via recursion and backtracking

P: 4
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
  1. // class SudokuBoard, will be called by class Sudoku
  2.  
  3. import java.util.Scanner;
  4. import java.io.*;
  5.  
  6. public class SudokuBoard {
  7.  
  8.     private int[][] board = new int[9][9];
  9.  
  10.     // it reads the established sudoku board from a scanner, which
  11.        will be given when the class Sudoku calls upon the  method.
  12.     public void readBoardFromScanner(Scanner s) {
  13.  
  14.     for (int i=0; i<9; i++) 
  15.         for (int j=0; j<9;j++) 
  16.         board[i][j] = s.nextInt();                   
  17.     }
  18.  
  19.     public void printBoard() {
  20.  
  21.     System.out.println("The Board is:");
  22.  
  23.     for(int i=0; i<9; i++){
  24.         for (int j=0; j<9; j++){  
  25.         System.out.print(board[i][j]+" "); 
  26.         }
  27.         System.out.println(" ");
  28.     }
  29.  
  30.     }
  31.  // checks the row to see if a given # is okay
  32.     public boolean rowCheck(int i, int number) throws Exception {
  33.  
  34.     for (int j = 0; j < 9 ; j++)
  35.         if (board[i][j] == number )
  36.         return false;
  37.  
  38.     return true;
  39.     }
  40. // checks the column to see if a given # is okay
  41.     public boolean columnCheck(int j, int number) throws Exception {
  42.  
  43.     for (int i = 0; i < 9; i++)
  44.         if (board[i][j] == number )
  45.         return false;
  46.  
  47.     return true;
  48.     }
  49. // checks the 3*3 box to see if a given # is okay
  50.     public boolean smallBoxCheck(int i, int j, int number) throws Exception { 
  51.  
  52.     int k = (i/3);
  53.     int l = (j/3);
  54.  
  55.     int row = k * 3;
  56.     int col = l * 3; 
  57.  
  58.     // the above steps are for round-offs so that i=6,7,8 can start
  59.     // altogether with row starting point 6, i=4,5,6 with row starting
  60.     // point 4, etc. Same logic with columns. 
  61.  
  62.     for (int x = 0; x < 3; x++)
  63.         for (int y = 0; y < 3; y++)
  64.         if(board[row+x][col+y] == number )
  65.             return false;
  66.  
  67.     return true;
  68.     }
  69. // the active part begins here
  70.     public void solve(int i, int j) throws Exception {
  71.  
  72.     if ( i > 8 )
  73.         throw new Exception ( "Solution Found" ) ;
  74.     else
  75.         {
  76.             while( board[i][j] != 0 ) {
  77.                  if ( ++j > 8 )
  78.               {
  79.                                          j = 0;
  80.                              i ++;
  81.  
  82.                                         if ( i > 8 )
  83.                      throw new Exception ("Solution Found");
  84.               }
  85.         }
  86.  
  87.             for (int num = 1; num < 10; num++) {
  88.  
  89.                           if (columnCheck(i,num) && rowCheck(i,num) && smallBoxCheck(i,j,num)) {
  90.             board[i][j] = num;
  91.  
  92. // after setting the number, call the next recursive call
  93.             if ( j < 8 )
  94.                 solve( i, j+1);
  95.             else 
  96.                 solve (i+1, 0);
  97.             }
  98.         }
  99.  
  100. // no solutions found, set the spot to 0 and backtrack
  101.         board[i][j] = 0;            
  102.         }
  103.     }
  104.  
  105. // Start solving at 0,0
  106.     public void startSolve() {
  107.     try {
  108.         solve(0,0);
  109.     }
  110.  
  111.     catch (Exception exception )
  112.         { }
  113.     }
  114. }
  115.  
  116.  
  117. and then, here is the call from the class Sudoku :
  118.  
  119. import java.io.*;
  120. import java.util.Scanner;
  121.  
  122. public class Sudoku {
  123.  
  124.     public static void main (String[] args) throws FileNotFoundException {
  125.  
  126.     Scanner text;
  127.     text = setFileScanner("board1");
  128.  
  129.     SudokuBoard sb = new SudokuBoard();
  130.  
  131.     sb.readBoardFromScanner(text);
  132.  
  133.     sb.printBoard(); // print the original board
  134.  
  135.     sb.startSolve(); // solve the board
  136.  
  137.     sb.printBoard(); // supposed to print the "solved" board
  138.  
  139.     }
  140.  
  141.     public static Scanner setFileScanner(String fileName) throws FileNotFoundException {
  142.  
  143.         File randomName = new File(fileName);
  144.         Scanner t = new Scanner(randomName);
  145.         return t;
  146.     }
  147.  
  148. }
  149.  
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.
Dec 11 '08 #1
Share this Question
Share on Google+
3 Replies

P: 4
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
Dec 11 '08 #2

Nepomuk
Expert 2.5K+
P: 3,112
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)
Dec 11 '08 #3

P: 4
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!
Dec 11 '08 #4

Post your reply

Sign in to post your reply or Sign up for a free account.