Code Pumpkin

Sudoku checker (By traversing each cell only once)

March 31, 2017
Posted by Pumpkin
Subscribe

sudoku

Sudoku is a logic-based combinatorial number-placement puzzle. Given a partially filled 9×9 2D array i.e. grid[9][9], the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.

For Detailed understanding about Sudoku, have a look at wikipedia

This post is about checking correctness of Sudoku solution, and not for generating solution for incomplete sudoku problem. If you are looking for java program to solve sudoku, please check my post Sudoku Solver using Recursive Backtracking.

If you are interested in java programs for other board games like Sudoku SolverTic Tac ToeSnake N Lader and N Queen Problem, you can check out my posts in Board Games section.
 

Approach for checking correctness of Sudoku Solution

  1. Traverse through each cell of sudoku, and while traversing confirm that the same number is not present in corresponding row, column or 3X3 subgrid.
  2. Declare solution is incorrect, if we find same number in corresponding row, column or 3X3 subgrid.
  3. Declare solution is incorrect, if we find any UNASSIGNED cell.
  4. Solution is correct in rest of the cases.

Traditional approach for checking valid number in any cell

9×9 int array is used to store all the elements of sudoku. Instance variable sudoku can be initialized using any of the below two constructors.

All the cells of completely solved sudoku array must have assigned valid values. sudoku solution having UNASSIGNED i.e. 0 value in any of its cell, is considered to be incomplete or wrong.


class Sudoku
{
    private int[][] sudoku;
    private static final int UNASSIGNED = 0;
     
    public Sudoku()
    {
        sudoku = new int[9][9];
    }
     
    public Sudoku(int sudoku[][])
    {
        this.sudoku= sudoku;
    }
     
    //TO-DO Methods
}

Valid number for any cell can be checked by comparing it to all the cells of corresponding row, column and 3X3 subgrid. If we find duplicate number either in row, column or subgrid, then given number is not valid in the cell and we will declare solution as incorrect.

containsInRow()containsInCol() and containsInBox() methods are used to check if number is present in current row, current column and current 3X3 subgrid or not.

isAllowed() method uses above three methods to check if it is safe to assign number in the cell. If any of above three method return true, it means particular number is not allowed in that cell.


private boolean containsInRow(int row,int number)
{
	for(int i=0;i<9;i++)
	{
		if(sudoku[row][i]==number)
		{
			return true;
		}
	}
	return false;
}
 

 
private boolean containsInCol(int col,int number)
{
	for(int i=0;i<9;i++)
	{
		if(sudoku[i][col]==number)
		{
			return true;
		}
	}
	return false;
}
 
 
private boolean containsInBox(int row, int col,int number)
{
	int r = row - row%3;
	int c = col - col%3;
	for(int i = r ; i< r+3 ; i++)
	{
		for(int j = c; j < c+3 ; j++)
		{
			if(sudoku[i][j]==number)
			{
				return true;
			}
		}
		 
	}
	return false;
}
 
private boolean isAllowed(int row, int col,int number)
{
	return !(containsInRow(row, number) || containsInCol(col, number) || containsInBox(row, col, number));
}


 

Approach to check valid number by traversing each cell only once

In above approach, we need to iterate through all the elements of respective row, column and subgrid multiple times. There are many duplicate comparision operations e.g. we will compare a[0][1] with a[0][2] while calling isAllowed(0,1,anyNumber) and also in isAllowed(0,2,AnyNumber). Hence it is not very efficient.

In programming interview round, my friend was asked to create SudokuChecker program by tranversing each cell only once. He was asked to eleminate those duplicate comparisions. There was no bound on space complexity

We can achieve this using 27 different HashSets (9 for each row, 9 for each column and 9 for each 3X3 subgrid).

We will start traversing from top left cell to right and add number to respective HashSet of row, column and 3X3 subgrid. HashSet returns false, if we add duplicate number into it. So if any of the HashSet return false, it means that number is already present in that row, column or subgrid and hence Solution is incorrect.

Here is the complete java class of Sudoku checker using HashSets.


import java.util.ArrayList;
import java.util.HashSet;
 
class Sudoku{
    private int[][] sudoku;
    private static final int UNASSIGNED = 0;
     
    public Sudoku()
    {
        sudoku = new int[9][9];
    }
     
    Sudoku(int[][] sudoku)
    {
        this.sudoku = sudoku;
    }
     
    private HashSet< Integer > rowSet = null;
    private HashSet< Integer > colSet = null;
    private HashSet< Integer > boxSet = null;
    private ArrayList< HashSet < Integer > > arrList = new ArrayList< HashSet < Integer > >();
     
    public boolean isAllowed(int row, int col) {
 
        rowSet = arrList.get(row);
        colSet = arrList.get(9 + col);
 
        int box = 3 * (row / 3) + (col / 3);
        boxSet = arrList.get(18 + box);
 
        return (rowSet.add(sudoku[row][col]) && colSet.add(sudoku[row][col]) && boxSet.add(sudoku[row][col]));
    }
 
    public boolean isCorrectSolution()
    {
        for (int i = 0; i < 27; i++)
        {
            arrList.add(new HashSet< Integer >());
        }
 
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if(!isAllowed(i, j) || sudoku[i][j] == UNASSIGNED)
                {
                    return false;
                }
            }
        }
        return true;
    }
}

main() method


public class SukoduChecker {
    public static void main(String[] args)
    {
        int[][] inputSudoku = {
                { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
                { 4, 5, 6, 7, 8, 9, 1, 2, 3 },
                { 7, 8, 9, 1, 2, 3, 4, 5, 6 },
                { 2, 3, 4, 5, 6, 7, 8, 9, 1 },
                { 5, 6, 7, 8, 9, 1, 2, 3, 4 },
                { 8, 9, 1, 2, 3, 4, 5, 6, 7 },
                { 3, 4, 5, 6, 7, 8, 9, 1, 2 },
                { 6, 7, 8, 9, 1, 2, 3, 4, 5 },
                { 9, 1, 2, 3, 4, 5, 6, 7, 8 } };
         
        Sudoku sc = new Sudoku(inputSudoku);
         
        if(sc.isCorrectSolution())
        {
            System.out.println("Solution is Correct");
        }
        else
        {
            System.out.println("Incorrect Solution");
        }
    }
}
     

Download Complete Java Program »

Tags: , , , , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank