Java Programming: I need lots of help. Currently Im working on a program that wi

Question

Java Programming:

I need lots of help. Currently Im working on a program that will use backtracking to help solve the following problem:

Im trying to use my three methods to help solve a Sudoku problem using backtracking. Im trying to write a method that will implement the backtracking process but Im having trouble with the logic. So far I have my three rules for Sudoku in the following methods:

public static boolean columnValid(int [ sudokuBoard, int col, int checkValue) int checkRow; for (checkRow= 0; checkRow

Explanation / Answer

Hi,

Solving Sudoku is not a new concept to us and yes we will be using a lot of BackTracking!!!

I have added rest of the logic with your provided code snippet.We basically go through below algorithms for solving :-

first check If the board is full then it is solved correctly.

if not then we need to find next unassigned position

we assign a value [i.e. checkValue in your case] and check its validity.

if valid we go forward searching next unassigned position untill we found a correct solution or reach a point where no possible solution exist for that checkValue in that position .

We backtrack till that position and start again with next number as checkValue.

Check the below code for Details:

public class SudokuSolution {
  
  
   private final static int N=9;
   private final static int UNASSIGNED=0;
   static int rowCurrent = 0, colCurrent = 0;
   public static void main(String [] args)
   {
       int[][] grid = new int[][]{{3, 0, 6, 5, 0, 8, 4, 0, 0},
           {5, 2, 0, 0, 0, 0, 0, 0, 0},
           {0, 8, 7, 0, 0, 0, 0, 3, 1},
           {0, 0, 3, 0, 1, 0, 0, 8, 0},
           {9, 0, 0, 8, 6, 3, 0, 0, 5},
           {0, 5, 0, 0, 9, 0, 6, 0, 0},
           {1, 3, 0, 0, 0, 0, 2, 5, 0},
           {0, 0, 0, 0, 0, 0, 0, 7, 4},
           {0, 0, 5, 2, 0, 6, 3, 0, 0}};
                      
       if (SolveSudoku(grid) == true)
           printGrid(grid);
       else
           System.out.println("No solution exists");
      

      
   }
  
  

  
   private static void printGrid(int[][] grid) {
      
       for (int row = 0; row < N; row++)
       {
       for (int col = 0; col < N; col++)
           System.out.print(grid[row][col]+" ");
            System.out.println();
       }
      
   }

   /* Searches the grid to find an entry that is still unassigned. If
   found, the reference parameters row, col will be set the location
   that is unassigned, and true is returned. If no unassigned entries
   remain, false is returned. */
   static boolean FindUnassignedLocation(int sudokuboard[][], int row, int col)
   {
       for (row = 0; row < N; row++)
           for (col = 0; col < N; col++)
               if (sudokuboard[row][col] == UNASSIGNED)
               {
                  
                   rowCurrent=row;
                   colCurrent=col;
                  
                  
                   return true;
               }
       return false;
   }

   private static boolean SolveSudoku(int[][] grid) {
       int row = 0, col = 0;

       // If there is no unassigned location, we are done
       if (!FindUnassignedLocation(grid, row, col))
       return true; // success!

       // consider digits 1 to 9
       for (int num = 1; num <= 9; num++)
       {
           // if looks promising
           if (isSafe(grid, rowCurrent, colCurrent, num))
           {
               // make tentative assignment
               grid[rowCurrent][colCurrent] = num;
               int rowTemp=rowCurrent;
               int colTemp=colCurrent;
              
               // return, if success, yay!
               if (SolveSudoku(grid))
                   return true;

               // failure, unmake & try again
               rowCurrent=rowTemp;
               colCurrent=colTemp;
               grid[rowCurrent][colCurrent] = UNASSIGNED;
              
           }
       }
       return false; // this triggers backtracking
   }

  

   /* Returns a boolean which indicates whether any assigned entry
   within the specified 3x3 box matches the given number. */
   static boolean subboxValid(int grid[][], int boxStartRow, int boxStartCol, int num)
   {
       for (int row = 0; row < 3; row++)
           for (int col = 0; col < 3; col++)
               if (grid[row+boxStartRow][col+boxStartCol] == num)
                   return true;
       return false;
   }

   /* Returns a boolean which indicates whether it will be legal to assign
   num to the given row,col location. */
   static boolean isSafe(int grid[][], int row, int col, int checkValue)
   {
       /* Check if 'num' is not already placed in current row,
       current column and current 3x3 box */
      
      
      
       return !rowValid(grid, row, checkValue) &&
           !colValid(grid, col, checkValue) &&
           !subboxValid(grid, row - row%3 , col - col%3, checkValue);
   }

   /* Returns a boolean which indicates whether any assigned entry
   in the specified row matches the given number. */
   static boolean rowValid(int sudokuBoard[][], int row, int checkValue)
   {
      
       for (int col = 0; col < N; col++)
           if (sudokuBoard[row][col] == checkValue)
               return true;
       return false;
   }

   /* Returns a boolean which indicates whether any assigned entry
   in the specified column matches the given number. */
   static boolean colValid(int sudokuBoard[][], int col, int checkValue)
   {
      
       for (int row = 0; row < N; row++)
           if (sudokuBoard[row][col] == checkValue)
               return true;
       return false;
   }

  

}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.