Question

JAVA

Sudoku.java

This class does the work of solving the Sudoku puzzle, as well as containing the main method to provide a text-based user interface. Stores a Board object which it uses in solving. It should also track statistics about the solving process: the number of recursive calls made, and the number of "backups" that had to be done.

public Sudoku( Scanner sc )

Constructor for the Sudoku class. Initializes the board and other instance variables.

public boolean solve( Location loc )

Recursively solves the board from the current configuration, using the backtracking algorithm described above. Returns true if a solution was found from the current configuration, false otherwise. Should only assign valid values to board locations, and should not overwrite locations that had values in the original board configuration.

public int getRecursionCount()

Returns the recursion count after the puzzle has been solved (or discovered to be unsolvable.)

public int getBackupCount()

Returns the backup count after the puzzle has been solved (or discovered to be unsolvable.)

public Board getBoard()

Returns the Sudoku board.

public static void main( String[] args )

The main method. Prompts the user for a file name, creates a Scanner using that file, creates a Sudoku object, prints the initial board, calls the solve method, and then prints the results, including the recursion count and backup count. Transcript below:

Enter the path to the sudoku file: test1.txt Initial configuration of the sudoku +-------+-------+-------+ | - 7 6 | - 8 9 | - - 4 | | - - 4 | 3 - 2 | - 1 - | | - 1 - | - - 6 | 8 3 - | +-------+-------+-------+ | 7 - 8 | - 9 3 | - - 5 | | 2 3 - | - - - | - 6 7 | | 9 - - | 6 7 - | 3 - 8 | +-------+-------+-------+ | - 8 3 | 4 - - | - 9 - | | - 5 - | 9 - 1 | 6 - - | | 1 - - | 5 6 - | 4 7 - | +-------+-------+-------+ Successful! Final configuration of the sudoku +-------+-------+-------+ | 3 7 6 | 1 8 9 | 2 5 4 | | 8 9 4 | 3 5 2 | 7 1 6 | | 5 1 2 | 7 4 6 | 8 3 9 | +-------+-------+-------+ | 7 6 8 | 2 9 3 | 1 4 5 | | 2 3 5 | 8 1 4 | 9 6 7 | | 9 4 1 | 6 7 5 | 3 2 8 | +-------+-------+-------+ | 6 8 3 | 4 2 7 | 5 9 1 | | 4 5 7 | 9 3 1 | 6 8 2 | | 1 2 9 | 5 6 8 | 4 7 3 | +-------+-------+-------+ Recursion count = 94 Backup count = 7

Answer 1

/*

test1.txt file consists of following data

- 7 6 - 8 9 - - 4
- - 4 3 - 2 - 1 -
- 1 - - - 6 8 3 -
7 - 8 - 9 3 - - 5
2 3 - - - - - 6 7
9 - - 6 7 - 3 - 8
- 8 3 4 - - - 9 -
- 5 - 9 - 1 6 - -
1 - - 5 6 - 4 7 -

*/

/* Sudoku program */

import java.io.*;
import java.util.*;
class Sudoku
{
   int recursionCount=0;                   // variable to store recursion count
   int backupCount=0;                       // variable to store backup count
   int [][] sudoku=new int[9][9];           // 2D array to store configuration of sudoku
   Sudoku(String fileName)
   {
       initializeSudokuArray(fileName);   // method that fills 2D array with values in text file
   }
   public void initializeSudokuArray(String fileName)
   {
       try
       {
           File file = new File("./"+fileName);
           BufferedReader br = new BufferedReader(new FileReader(file));
           String str="";
           int line=0;
           while ((str=br.readLine())!=null)
           {
               String [] values=str.split(" ");
               for(int i=0;i<values.length;i++)
               {
                       if(values[i].equals("-"))
                           sudoku[line][i]=0;
                       else
                       sudoku[line][i]=Integer.parseInt(values[i]);
               }
               line++;
           }
       }
       catch(Exception e)
       {
      
       }
   }
   public boolean solve()                   // recursive solution to solve sudoku
   {
       int row=-1,col=-1;
       for(int i=0;i<9;i++)
       {
           for(int j=0;j<9;j++)
           {
               if(sudoku[i][j]==0)           // check for any 0 value present in sudoku representing incompleteness of sudoku
               {
                   row=i;                   // if found store its row and col
                   col=j;
                   break;
               }
           }
           if(row!=-1)
               break;
       }
       if(row==-1)                       // if row==-1 indicates sudoku ic configured successfully
           return true;
       recursionCount++;               // whenever solve() method is visited, then increment recursive count
       for(int i=1;i<=9;i++)
       {
           if(isSafe(sudoku,row,col,i))       // check for suitable values from 1 to 9 to be placed in current place
           {
               sudoku[row][col]=i;              
               if(solve())
                   return true;
               backupCount++;           // if current configuration doesnt leads us to solution then increment backup count and reset value in sudoku
               sudoku[row][col]=0;
           }
       }
       return false;
   }
   public boolean isSafe(int sudoku[][],int row,int col,int value)
   {
       for(int i=0;i<9;i++)
       {
           if(sudoku[i][col]==value)           // chech whether a value is not present in row wise
               return false;
       }
       for(int i=0;i<9;i++)
       {
           if(sudoku[row][i]==value)           // chech whether a value is not present in column wise
               return false;
       }
       row=row-row%3;
       col=col-col%3;
       for(int i=row;i<row+3;i++)               // chech whether a value is not present in 3X3 grid
       {
           for(int j=col;j<col+3;j++)
           {
               if(sudoku[i][j]==value)
                   return false;
           }
       }
       return true;
   }
   public int getRecursionCount()
   {
       return recursionCount;
   }
   public int getBackUpCount()
   {
       return backupCount;
   }
   public void printSudoku()
   {
       for(int i=0;i<9;i++)
       {
           for(int j=0;j<9;j++)
               System.out.print(sudoku[i][j]+" ");
           System.out.println();
       }
       System.out.println();
   }
}
class Main
{
   public static void main(String args[])
   {
       Scanner s=new Scanner(System.in);
       System.out.print("Enter the file name(along with extension): ");
       String fileName=s.next();
       File file=new File("./"+fileName);
       if(file.exists())
       {
           Sudoku sudoku=new Sudoku(fileName);
           if(sudoku.solve())
           {
               System.out.println("Initial configuration of the sudoku");
               sudoku.printSudoku();
               System.out.println("Successful!!!");
               System.out.println("Final configuration of the sudoku");
               sudoku.printSudoku();
               System.out.println("Recursion Count: "+sudoku.getRecursionCount());
               System.out.println("BackUp Count: "+sudoku.getBackUpCount());
           }
           else
               System.out.println("No solution exists");
       }
       else
       {
           System.out.println("File doesnt exists");
       }
      
   }
}

Output is as follows:

if file exists then following will be the output

if file doesnot exists then following will be the output

Note: I dont know how you get 94 as recursion count in question. But this code gives recursion count as 48 which is correct according to program. Please look at correct value of recursion Count once. Thank you.

Enter the file name (along with extension): testi.txt Initial configuration of the sudoku 3 7 6 1 8 9 2 5 4 8 9 4 3 5 2 7 1 6 5 1 2 7 4 6 8 39 7 6 8 2 9 3 1 4 5 2 3 5 8 1 4 9 6 7 9 4 1 6 7 5 3 2 8 6 8 3 4 2 7 5 9 1 4 5 7 9 3 1 6 8 2 1 2 9 5 6 8 4 7 3 Successful!!! Final configuration of the sudoku 3 7 6 1 8 9 2 5 4 8 9 4 3 5 2 7 1 6 5 1 2 7 4 6 8 39 7 6 8 2 9 3 1 4 5 2 3 5 8 1 4 9 6 7 9 4 1 6 7 5 3 2 8 6 8 3 4 2 7 5 9 1 4 5 7 9 3 1 6 8 2 1 2 9 5 6 8 4 7 3 Recursion Count: 48 Backup Count: 7

Enter the file name (along with extension): test2.txt File doesnt exists