Tech Master Tutorials

# Backtrack Solutions

Sudoku Problem : Returning true if the sudoku can be filled completely or else returning false.

```
public class SudokuProblem {

/* 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. */

private static  int NSquare;
private static  int N;
private static int UNASSIGNED=0;
private static int unAssignedRow=-1;
private static int unAssignedCol=-1;

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}};

//		int grid[][] = new int[][]{
//				{5, 3, 0, 0, 7, 0, 0, 0, 0},
//				{6, 0, 0, 1, 9, 5, 0, 0, 0},
//				{0, 9, 8, 0, 0, 0, 0, 6, 0},
//				{8, 0, 0, 0, 6, 0, 0, 0, 3},
//				{4, 0, 0, 8, 0, 3, 0, 0, 1},
//				{7, 0, 0, 0, 2, 0, 0, 0, 6},
//				{0, 6, 0, 0, 0, 0, 2, 8, 0},
//				{0, 0, 0, 4, 1, 9, 0, 0, 5},
//				{0, 0, 0, 0, 8, 0, 0, 7, 9}};

//		int grid[][] = new int[][]{{0, 0, 0,0},{0, 0, 0,0},{0, 0, 0,0},{0, 0, 0,0}};

//		int grid[][] = new int[][]{{1, 0, 0,0},
//									{0, 0, 2,0},
//									{0, 3, 0,0},
//									{0, 0, 0,4}};
//		int grid[][] = new int[][]{
//				{1, 2, 3, 0, 0, 0, 0, 0, 0},
//				{0, 0, 0, 0, 0, 0, 1, 2, 3},
//				{0, 0, 0, 1, 2, 3, 0, 0, 0},
//				{2, 3, 1, 0, 0, 0, 0, 0, 0},
//				{0, 0, 0, 0, 0, 0, 2, 3, 1},
//				{0, 0, 0, 2, 3, 1, 0, 0, 0},
//				{3, 1, 2, 0, 0, 0, 0, 0, 0},
//				{0, 0, 0, 0, 0, 0, 3, 1, 2},
//				{0, 0, 0, 3, 1, 2, 0, 0, 0}};
if (SolveMagicSquare(grid) == 1)
printGrid(grid);
else
System.out.println("No solution exists");
//			printGrid(grid);

}

/* Takes a partially filled-in grid and attempts to assign values to
all unassigned locations in such a way to meet the requirements
for Sudoku solution (non-duplication across rows, columns, and boxes) */
public static int SolveMagicSquare(int[][] grid){
NSquare=grid.length;
N=(int) Math.sqrt(NSquare);

// If there is no unassigned location, we are done
if (!FindUnassignedLocation(grid)){
return 1; // success!
}
//These are variables to hold values for specific recurive calls
int row=unAssignedRow;
int col=unAssignedCol;

// consider digits 1 to 9
for (int num = 1; num <= NSquare; num++)
{
// if looks promising
if (isSafe(grid, row, col, num))
{
// make tentative assignment
grid[row][col] = num;

// return, if success, yay!
if (SolveMagicSquare(grid)==1){
return 1;
}

// failure, unmake & try again
grid[row][col] = UNASSIGNED;
}
}
return 0; // this triggers backtracking
}

static boolean FindUnassignedLocation(int grid[][])
{
for (int row = 0; row < grid.length; row++){
for (int col = 0; col < grid[row].length; col++){
if (grid[row][col] == UNASSIGNED){
unAssignedRow=row;
unAssignedCol=col;
return true;
}
}
}
return false;
}

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

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

/* Returns a boolean which indicates whether any assigned entry
within the specified 3x3 box matches the given number. */
static boolean UsedInBox(int grid[][], int boxStartRow, int boxStartCol, int num)
{
for (int row = 0; row < N; row++){
for (int col = 0; col < N; 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. */

// Checks whether it will be legal to assign num to the given row,col
static boolean isSafe(int grid[][], int row, int col, int num)
{
/* Check if 'num' is not already placed in current row,
current column and current 3x3 box */
return ((!UsedInRow(grid, row, num) && !UsedInCol(grid, col, num)) &&
!UsedInBox(grid, row - row%N , col - col%N, num));
}

/* A utility function to print grid  */
static void printGrid(int grid[][])
{
for (int row = 0; row < NSquare; row++)
{
for (int col = 0; col < NSquare; col++){
System.out.printf("%2d", grid[row][col]);
}
System.out.printf("\n");
}
}
}

```