Sudoku Checker and Solver
Sudoku is a puzzle where we need to fill a 9×9 grid with digits from 1 to 9 such that each column, each row, and each of the nine 3×3 blocks contains all of the 1-9 digits.
Sudoku Checker
The problem is to check whether a given 9×9 array of integers from 1 to 9 is a valid solution to a Sudoku puzzle. For example, the following is a valid solution:
5 3 4 | 6 7 8 | 9 1 2 6 7 2 | 1 9 5 | 3 4 8 1 9 8 | 3 4 2 | 5 6 7 ------+-------+------ 8 5 9 | 7 6 1 | 4 2 3 4 2 6 | 8 5 3 | 7 9 1 7 1 3 | 9 2 4 | 8 5 6 ------+-------+------ 9 6 1 | 5 3 7 | 2 8 4 2 8 7 | 4 1 9 | 6 3 5 3 4 5 | 2 8 6 | 1 7 9
import java.util.Arrays;
public class SudokoChecker
{
public static boolean check(int[][] arr)
{
if (arr.length != 9)
return false;
for (int i = 0; i < 9; i++)
{
if (arr[i].length != 9)
return false;
for (int j = 0; j < 9; j++)
if (arr[i][j] < 1 || arr[i][j] > 9)
return false;
}
int[] counts = new int[9];
int good_count = 0;
Arrays.fill(counts, 0);
// rows
for (int i = 0; i < 9; i++)
{
good_count++;
for (int j = 0; j < 9; j++)
{
counts[arr[i][j] - 1]++;
if (counts[arr[i][j] - 1] != good_count)
return false;
}
}
// columns
for (int j = 0; j < 9; j++)
{
good_count++;
for (int i = 0; i < 9; i++)
{
counts[arr[i][j] - 1]++;
if (counts[arr[i][j] - 1] != good_count)
return false;
}
}
// blocks
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
good_count++;
for (int r = i * 3; r < i * 3 + 3; r++)
{
for (int c = j * 3; c < j * 3 + 3; c++)
{
counts[arr[r] - 1]++;
if (counts[arr[r] - 1] != good_count)
return false;
}
}
}
}
return true;
}
public static void main(String[] args)
{
int[][] arr =
{
{5, 3, 4, 6, 7, 8, 9, 1, 2},
{6, 7, 2, 1, 9, 5, 3, 4, 8},
{1, 9, 8, 3, 4, 2, 5, 6, 7},
{8, 5, 9, 7, 6, 1, 4, 2, 3},
{4, 2, 6, 8, 5, 3, 7, 9, 1},
{7, 1, 3, 9, 2, 4, 8, 5, 6},
{9, 6, 1, 5, 3, 7, 2, 8, 4},
{2, 8, 7, 4, 1, 9, 6, 3, 5},
{3, 4, 5, 2, 8, 6, 1, 7, 9}
};
System.out.println(check(arr));
}
}
Sudoku Solver
Given a Sudoku puzzle represented by a 9-by-9 array of integers from 0 to 9, find a solution by replacing all 0’s with a number from 1 to 9: each row, column, and block should contain each integer from 1 to 9 exactly once. The 0’s are placeholders, representing the blank spaces.
import java.util.Arrays;
public class SudokuSolver
{
public static boolean isValid(int i, int j, int v, int[][] arr)
{
for (int k = 0; k < 9; k++) // row
if (v == arr[i][k])
return false;
for (int k = 0; k < 9; k++) // column
if (v == arr[k][j])
return false;
int r = (i / 3) * 3;
int c = (j / 3) * 3;
for (int k = 0; k < 3; ++k) // box
for (int m = 0; m < 3; ++m)
if (v == arr[r + k])
return false;
return true; // valid
}
public static boolean solve(int[][] arr)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (arr[i][j] != 0)
continue;
for (int v = 1; v <= 9; v++)
{
if (isValid(i, j, v, arr))
{
arr[i][j] = v;
if (solve(arr))
return true;
}
}
arr[i][j] = 0; // reset backtrack
return false;
}
}
return true;
}
public static void main(String[] args)
{
int[][] arr =
{
{0, 0, 0, 6, 7, 8, 9, 1, 2},
{0, 7, 2, 0, 9, 5, 3, 4, 8},
{0, 9, 8, 3, 0, 2, 5, 6, 7},
{8, 0, 9, 7, 6, 0, 4, 2, 3},
{4, 2, 0, 8, 5, 3, 0, 9, 1},
{7, 1, 3, 0, 2, 4, 8, 0, 6},
{9, 6, 1, 5, 0, 7, 2, 8, 0},
{2, 8, 7, 4, 1, 0, 6, 3, 0},
{3, 4, 5, 2, 8, 6, 0, 0, 0}
};
if (!solve(arr))
System.out.println("no solution");
else
for (int i = 0; i < arr.length; i++)
System.out.println(Arrays.toString(arr[i]));
}
}
The solve method above can be replaced by the following one, which is more efficient by avoid redundant checks. The method should be called using “solve(0, 0, arr)”.
public static boolean solve(int i, int j, int[][] arr)
{
int next_i = i;
int next_j = j;
if (j == 8)
{ // next row
next_i = i + 1;
next_j = 0;
}
else
next_j = j + 1;
// skip
if (arr[i][j] != 0)
{
if (next_i == 9)
return true;
return solve(next_i, next_j, arr);
}
// fill up
for (int v = 1; v <= 9; v++)
{
if (isValid(i, j, v, arr))
{
arr[i][j] = v;
if (next_i == 9)
return true;
if (solve(next_i, next_j, arr))
return true;
}
}
// reset for backtrack
arr[i][j] = 0;
return false;
}