public class SudokuTestSolver {
int Unassigned = 0;
public boolean solveSudoku(int[][] grid) {
int x = 0;
int y = 0;
// If there is no unassigned location, we are done
if (!findUnassignedLocation(grid, x, y)) {
return true;
}
for (int num = 1; num <= 9; num++) {
if (isSafe(grid, x, y, num)) {
grid[x][y] = num;
if (solveSudoku(grid)) {
return true;
}
grid[x][y] = Unassigned;
}
}
return false;
}
public boolean findUnassignedLocation(int[][] grid, int x, int y) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (grid[x][y] == 0) {
return true;
}
}
}
return false;
}
public boolean usedInRow(int[][] grid, int x, int num) {
for (int y = 0; y < 9; y++) {
if (grid[x][y] == num) {
return true;
}
}
return false;
}
public boolean usedInCol(int[][] grid, int y, int num) {
for (int x = 0; x < 9; x++) {
if (grid[x][y] == num) {
return true;
}
}
return false;
}
public boolean usedInBox(int[][] grid, int boxStartRow, int boxStartCol, int num) {
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (grid[x + boxStartRow * 3][y + boxStartCol * 3] == num) {
return true;
}
}
}
return false;
}
public boolean isSafe(int grid[][], int x, int y, int num) {
return !usedInRow(grid, x, num) &&
!usedInCol(grid, y, num) &&
!usedInBox(grid, x - x%3 , y - y%3, num);
}
public void printGrid(int grid[][]) {
for (int x = 0; x < 9; x++) {
for (int y = 0; y < 9; y++)
System.out.print(grid[x][y] + " ");
System.out.println();
}
}
public static void main(String[] args) {
int grid[][] = {{3, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0}};
SudokuTestSolver s = new SudokuTestSolver();
int grid2[][] = new int[9][9];
for (int x = 0; x < 9; x++) {
for (int y = 0; y < 9; y++) {
grid2[x][y] = grid[x][y];
}
}
if (s.solveSudoku(grid2) == true) {
s.printGrid(grid2);
}
else {
System.out.println("Can not be solved");
}
}//end main
}//end class