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][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 < 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][c + m])
					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;
	}

References

Sudoku
Backtracking

Comments

comments