Julius Baer Singapore Interview Programming Challenge: How to write a Java Program to validate whether a Sudoku is valid or not?

Introduction: Julius Baer Singapore have asked me to write this Java Program about Sudoku in Interview Programming Question. They gave around 1.5 Hours to complete the Program.

What is Sudoku?

Sudoku is a number game which is played on a 9x9 sudoku board.

Properties of Sudoku:

1. The sudoku board is broken down into nine 3x3 squares.
2. Sudoku board must contain the digits 1 through 9 only.
3. Every Row must have the digits 1 through 9 only and all Unique Number.
4. Every Column must have the digits 1 through 9 only and all Unique Number.

Problem: How to write a Java Program to validate whether a Sudoku is valid or not?

Solution: This Java Program will tell whether a Sudoku is valid or not.

Input: This Program will take input like this.

int[][] board ={

{4, 1, 7, 5, 2, 3},

{2, 5, 3, 9, 8, 6},

{9, 8, 6, 1, 7, 4},

{6, 9, 1, 8, 5, 7},

{5, 3, 2, 4, 6, 9},

{7, 4, 8, 2, 3, 1}

};

Java Program:

package com.juliusbaer.toolbox.hiring.service;

import com.juliusbaer.toolbox.hiring.service.constants.Constants;

import java.util.ArrayList;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

public class Sudoku {

 public static final int SUDOKU_VALIDATION_SUCCESS = 0;

  public static final int SUDOKU_VALIDATION_NEGATIVE_FOUND = 1001;

  public static final int SUDOKU_VALIDATION_DUPLICATE_FOUND = 1002;

  public static final int SUDOKU_VALIDATION_ROW_COLUMN_MISMATCH = 1003;

  public int validate(int[][] board){

    return validateSudoku(board);

  }

  public int validate(int[][] board, int sizeOfSquire){

    try{

      int rowIndex = 0;

      int columnIndex = 0;

      for(int i=0;i<board.length;) {

        rowIndex = i;

        for (int j = 0; j < board.length;) {

          columnIndex = j;

          System.out.println("rowIndex : "+ rowIndex + " , columnIndex : "+ columnIndex);

          int[][] subSquireArray = getSubSquireArray(board, rowIndex, columnIndex, sizeOfSquire);

          int response = validateSudoku(subSquireArray);

          if(Constants.SUDOKU_VALIDATION_SUCCESS != response){

            return response;

          }

          j = j + 3;

        }

        i = i + sizeOfSquire;

      }

    }catch (Exception e){

      e.printStackTrace();

    }

    return Constants.SUDOKU_VALIDATION_SUCCESS;

  }

  private int[][] getSubSquireArray(int[][] board, int rowIndex, int columnIndex, int sizeOfSquire){

    int[][] outPut = new int[sizeOfSquire][sizeOfSquire];

    int row = 0;

    for(int i=rowIndex;i< rowIndex + sizeOfSquire;i++){

      int column = 0;

      for(int j=columnIndex;j<columnIndex+sizeOfSquire;j++){

        outPut[row][column] = board[i][j];

        column = column + 1;

      }

      row = row + 1;

    }

    //System.out.println("outPut : "+ outPut);

    return outPut;

  }

  private int validateSudoku(int[][] board) {

    List<Set<Integer>> rows = new ArrayList<>();

    for(int i=0;i<board.length;i++){

      Set<Integer> rowSet = new HashSet<>();

      for(int j=0;j<board.length;j++){

        int data = board[i][j];

        if(data >= 1 && data <= 9){

          boolean isDuplicate = rowSet.add(data);

          if(!isDuplicate){

            return Constants.SUDOKU_VALIDATION_DUPLICATE_FOUND;

          }

        }else{

          return Constants.SUDOKU_VALIDATION_NEGATIVE_FOUND;

        }

      }

      rows.add(rowSet);

    }

    List<Set<Integer>> columns = new ArrayList<>();

    for(int i=0;i<board.length;i++){

      Set<Integer> columnSet = new HashSet<>();

      for(int j=0;j<board.length;j++){

        int data = board[j][i];

        if(data >= 1 && data <= 9){

          boolean isDuplicate = columnSet.add(data);

          if(!isDuplicate){

            return Constants.SUDOKU_VALIDATION_DUPLICATE_FOUND;

          }

        }else{

          return Constants.SUDOKU_VALIDATION_NEGATIVE_FOUND;

        }

      }

      columns.add(columnSet);

    }

    if(rows.size() != columns.size()){

      return Constants.SUDOKU_VALIDATION_ROW_COLUMN_MISMATCH;

    }

    return Constants.SUDOKU_VALIDATION_SUCCESS;

  }

}

Java Unit Testing:

package com.juliusbaer.toolbox.hiring;

import com.juliusbaer.toolbox.hiring.service.Sudoku;

import com.juliusbaer.toolbox.hiring.service.constants.Constants;

import org.junit.jupiter.api.BeforeEach;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

public class SudokuTest {

private Sudoku sudoku;

@BeforeEach

public void setup() {

sudoku = new Sudoku();

}

@Test

public void testValidateSudokuSmaller() {

int[][] board =

{

{4, 1, 7, 5, 2, 3},

{2, 5, 3, 9, 8, 6},

{9, 8, 6, 1, 7, 4},

{6, 9, 1, 8, 5, 7},

{5, 3, 2, 4, 6, 9},

{7, 4, 8, 2, 3, 1}

};

assertEquals(Constants.SUDOKU_VALIDATION_SUCCESS,sudoku.validate(board));

}

@Test

public void testValidateSudokuSmallerSubset() {

int[][] board =

{

{4, 1, 7, 5, 2, 3},

{2, 5, 3, 9, 8, 6},

{9, 8, 6, 1, 7, 4},

{6, 9, 1, 8, 5, 7},

{5, 3, 2, 4, 6, 9},

{7, 4, 8, 2, 3, 1}

};

assertEquals(Constants.SUDOKU_VALIDATION_SUCCESS,sudoku.validate(board,3));

}

@Test

public void testValidateSudoku() {

int[][] board =

{

{4, 1, 7, 5, 2, 3, 6, 9, 8},

{2, 5, 3, 9, 8, 6, 1, 4, 7},

{9, 8, 6, 1, 7, 4, 3, 2, 5},

{6, 9, 1, 8, 5, 7, 4, 3, 2},

{5, 3, 2, 4, 6, 9, 8, 7, 1},

{7, 4, 8, 2, 3, 1, 5, 6, 9},

{3, 7, 9, 6, 1, 5, 2, 8, 4},

{8, 6, 5, 7, 4, 2, 9, 1, 3},

{1, 2, 4, 3, 9, 8, 7, 5, 6}

};

assertEquals(Constants.SUDOKU_VALIDATION_SUCCESS,sudoku.validate(board));

}

@Test

public void testValidateSubsetSquire() {

int[][] board =

{

{4, 1, 7, 5, 2, 3, 6, 9, 8},

{2, 5, 3, 9, 8, 6, 1, 4, 7},

{9, 8, 6, 1, 7, 4, 3, 2, 5},

{6, 9, 1, 8, 5, 7, 4, 3, 2},

{5, 3, 2, 4, 6, 9, 8, 7, 1},

{7, 4, 8, 2, 3, 1, 5, 6, 9},

{3, 7, 9, 6, 1, 5, 2, 8, 4},

{8, 6, 5, 7, 4, 2, 9, 1, 3},

{1, 2, 4, 3, 9, 8, 7, 5, 6}

};

assertEquals(Constants.SUDOKU_VALIDATION_SUCCESS,sudoku.validate(board, 3));

}

@Test

public void testSudokuInvalid() {

int[][] board =

{

{8, 1, 7, 5, 2, 3, 6, 9, 8},

{2, 5, 3, 9, 8, 6, 1, 4, 7},

{9, 8, 6, 1, 7, 4, 3, 2, 5},

{6, 9, 1, 8, 5, 7, 4, 3, 2},

{5, 3, 2, 4, 6, 9, 8, 7, 1},

{7, 4, 8, 2, 3, 1, 5, 6, 9},

{3, 7, 9, 6, 1, 5, 2, 8, 4},

{8, 6, 5, 7, 4, 2, 9, 1, 3},

{1, 2, 4, 3, 9, 8, 7, 5, 6}

};

assertEquals(Constants.SUDOKU_VALIDATION_DUPLICATE_FOUND,sudoku.validate(board));

}

@Test

public void testSudokuNegativeNumber() {

int[][] board =

{

{8, 1, -7, 5, 2, 3, 6, 9, 8},

{2, 5, 3, 9, 8, 6, 1, 4, 7},

{9, 8, 6, 1, 7, 4, 3, 2, 5},

{6, 9, 1, 8, 5, 7, 4, 3, 2},

{5, 3, 2, 4, 6, 9, 8, 7, 1},

{7, 4, 8, 2, 3, 1, 5, 6, 9},

{3, 7, 9, 6, 1, 5, 2, 8, 4},

{8, 6, 5, 7, 4, 2, 9, 1, 3},

{1, 2, 4, 3, 9, 8, 7, 5, 6}

};

assertEquals(Constants.SUDOKU_VALIDATION_NEGATIVE_FOUND,sudoku.validate(board));

}

@Test

public void testSudokuSubsetValid() {

int[][] board =

{

{8, 1, 7, 5, 2, 3, 6, 9, 8},

{2, 5, 3, 9, 8, 6, 1, 4, 7},

{9, 8, 6, 1, 7, 4, 3, 2, 5},

{6, 9, 1, 8, 5, 7, 4, 3, 2},

{5, 3, 2, 4, 6, 9, 8, 7, 1},

{7, 4, 8, 2, 3, 1, 5, 6, 9},

{3, 7, 9, 6, 1, 5, 2, 8, 4},

{8, 6, 5, 7, 4, 2, 9, 1, 3},

{1, 2, 4, 3, 9, 8, 7, 5, 6}

};

assertEquals(Constants.SUDOKU_VALIDATION_SUCCESS,sudoku.validate(board, 3));

}

@Test

public void testRowColumnNotEquals() {

int[][] board =

{

{8, 1, 7, 5, 2, 3, 6, 9, 4},

{2, 5, 3, 9, 8, 6, 1, 4, 7},

{9, 8, 6, 1, 7, 4, 3, 2, 5},

{6, 9, 1, 8, 5, 7, 4, 3, 2},

{5, 3, 2, 4, 6, 9, 8, 7, 1},

{7, 4, 8, 2, 3, 1, 5, 6, 9},

{3, 7, 9, 6, 1, 5, 2, 8, 4},

{8, 6, 5, 7, 4, 2, 9, 1, 3}

};

assertEquals(Constants.SUDOKU_VALIDATION_ROW_COLUMN_MISMATCH,sudoku.validate(board, 3));

}

}