# 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 &lt; 9; i++)
{
if (arr[i].length != 9)
return false;
for (int j = 0; j &lt; 9; j++)
if (arr[i][j] &lt; 1 || arr[i][j] &gt; 9)
return false;
}

int[]	counts = new int[9];
int	good_count = 0;
Arrays.fill(counts, 0);

// rows
for (int i = 0; i &lt; 9; i++)
{
good_count++;
for (int j = 0; j &lt; 9; j++)
{
counts[arr[i][j] - 1]++;
if (counts[arr[i][j] - 1] != good_count)
return false;
}
}

// columns
for (int j = 0; j &lt; 9; j++)
{
good_count++;
for (int i = 0; i &lt; 9; i++)
{
counts[arr[i][j] - 1]++;
if (counts[arr[i][j] - 1] != good_count)
return false;
}
}

// blocks
for (int i = 0; i &lt; 3; i++)
{
for (int j = 0; j &lt; 3; j++)
{
good_count++;
for (int r = i * 3; r &lt; i * 3 + 3; r++)
{
for (int c = j * 3; c &lt; j * 3 + 3; c++)
{
counts[arr[r][c] - 1]++;
if (counts[arr[r][c] - 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 &lt; 9; k++) // row
if (v == arr[i][k])
return false;
for (int k = 0; k &lt; 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 &lt; 3; ++k) // box
for (int m = 0; m &lt; 3; ++m)
if (v == arr[r + k][c + m])
return false;
return true; // valid
}

public static boolean solve(int[][] arr)
{
for (int i = 0; i &lt; 9; i++)
{
for (int j = 0; j &lt; 9; j++)
{
if (arr[i][j] != 0)
continue;
for (int v = 1; v &lt;= 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(&quot;no solution&quot;);
else
for (int i = 0; i &lt; 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 &lt;= 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;
}
```