Question

Write a JAVA program to solve a sudoku! Given a partially filled 9×9 2D array ‘grid[9][9]’, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.

I have posted 3 input files: sudoku1.txt, sudoku2.txt and sudoku3.txt

Problem Analysis & Design - Think about how you will need to solve this problem. You should do an object oriented solution which creates a Sudoku class to hold and manipulate a puzzle, and a main program to control things. Think about the data and methods needed for the Sudoku class. Read through all the phases below for some ideas on how to break things down.

Step 1: Create a main program which should handle the input processing details. Make it so that it will get the name of an input file from the user (test files have been given to you), create a puzzle object, read from the file to initialize the puzzle, display the initial puzzle on the screen then the solved puzzle. The last two operations should call methods in your Sudoku class to do the work. Write the bodies of these methods. Compile, run and test.

Step 2: In your Sudoku class, create a two-dimensional array of 9 rows and 9 columns. Initialize this array with values from the Sudoku text files by passing the scanner object to the constructor.

Step 3: Write a toString()method to return the contents of the 2-dimensional array as a string.

Step 4: Write a method call checkConflict() that returns true if a conflict exist and false if not. A conflict is detected when a new number placed at a particular location already exist within that row, column or sub-grid of size 3×3.

Step 5: Implement the recursive backtracking solution for solving Sudoku sudokuSolver() . The algorithm is given below.

Backtracking Algorithm
Like all other Backtracking problems, we can solve Sudoku by one by one assigning numbers to empty cells (empty cell is indicated by value 0). Before assigning a number, we check whether it is safe to assign. We basically check that the same number is not present in current row, current column and current 3X3 subgrid. After checking for safety, we assign the number, and recursively check whether this assignment leads to a solution or not. If the assignment doesn’t lead to a solution, then we try next number for current empty cell. And if none of number (1 to 9) lead to solution, we return false.

  Find row, col of an unassigned cell

  If there is none, return true

  For digits from 1 to 9

    a) If there is no conflict for digit at row,col

        assign digit to row,col and recursively try fill in rest of grid

    b) If recursion successful, return true

    c) Else, remove digit and try another

If all digits have been tried and nothing worked, return false

Answer 1