Menu
Topics Index
...
`

Weekend Hack - 22 Jun 2013 - Results

Thanks to Shaik Nyamath and Pramod Jain for spending so much time, coming up with original and innovative answers and for submitting them. Thanks to many others who have tried to get the solution.
We have reviewed the solutions as per the criteria mentioned at Weekend Hack and included the comments below. Given the experience of the participants, they were really innovative and clean. Few minor comments found are included below in the order of the submission. These comments are not intended to point out the mistakes in the solutions but to learn from them.

The winner of the Weekend Hack 22 Jun 2013 - 1 is Shaik Nyamath. He will get a recharge or gift voucher worth Rs. 175.

To complete given Sudoku puzzle

Write a program to complete given Sudoku puzzle.

Input (Two Dimensional matrix) Output (Two Dimensional matrix)
0 0 6 5 0 8 4 0 0
5 2 0 0 0 0 0 0 0
0 8 7 0 0 0 0 3 1
0 0 3 0 1 0 0 8 0
9 0 0 8 6 3 0 0 5
0 5 0 0 9 0 6 0 0
1 3 0 0 0 0 2 5 0
0 0 0 0 0 0 0 7 4
0 0 5 2 0 6 3 0 0
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
0 0 0 2 0 0 0 6 3
3 0 0 0 0 5 4 0 1
0 0 1 0 0 3 9 8 0
0 0 0 0 0 0 0 9 0
0 0 0 5 3 8 0 0 0
0 3 0 0 0 0 0 0 0
0 2 6 3 0 0 5 0 0
5 0 3 7 0 0 0 0 8
4 7 0 0 0 1 0 0 0
8 5 4 2 1 9 7 6 3
3 9 7 8 6 5 4 2 1
2 6 1 4 7 3 9 8 5
7 8 5 1 2 6 3 9 4
6 4 9 5 3 8 1 7 2
1 3 2 9 4 7 8 5 6
9 2 6 3 8 4 5 1 7
5 1 3 7 9 2 6 4 8
4 7 8 6 5 1 2 3 9

Solution 1 - Submitted on Sun Jun 23 20:28:51 2013

class CompleteSudokuPuzzle {

    public static void main(String s[]) {
        int[][] sudoku = {{0, 0, 0, 2, 0, 0, 0, 6, 3}, {3, 0, 0, 0, 0, 5, 4, 0, 1}, {0, 0, 1, 0, 0, 3, 9, 8, 0}, {0, 0, 0, 0, 0, 0, 0, 9, 0}, {0, 0, 0, 5, 3, 8, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 3, 0, 0, 5, 0, 0}, {5, 0, 3, 7, 0, 0, 0, 0, 8}, {4, 7, 0, 0, 0, 1, 0, 0, 0}};
        solveSudoku(sudoku);
        for (int[] array1d : sudoku) {
            for (int element : array1d) {
                System.out.print(element + " ");
            }
            System.out.println();
        }
    }

    public static void solveSudoku(int[][] sudoku) {
        solved(sudoku, 0, 0);
    }

    private static boolean solved(int[][] elements, int row, int col) //method to get the solved puzzle.
    {
        if (row > 8) //as the grid is 9x9 matrix,col and row max value will be 9 i.e 0-8
        {
            row = 0; // if the row value is >8 then it makes row =0 and moves on the next col.
            col = col + 1; // now as row>8 a new col is started,with row =0.
            if (col > 8) // when col is > 8 then thats the end of the matrix.
            {
                return true; // if the condition is passed returns true.
            }
        }
        if (elements[row][col] != 0) // if the respective position is not zero then it move on to nxt row.
        {
            return solved(elements, row + 1, col); // just moves to the next row where until it finds a position wit value=0
        }
        for (int value = 1; value <= 9; value++) //till the value is 9
        {
            if (checkPosibility(elements, value, row, col)) // if there occurs any zero then it checks for validity and if returns true then it gives the 'value' to the respective position.
            {
                elements[row][col] = value;
                if (solved(elements, row + 1, col)) // if there occurs no zero then it just proceed to nxt row.
                {
                    return true;
                }
            }
        }
        elements[row][col] = 0;
        return false;
    }

    private static boolean checkPosibility(int[][] elements, int value, int row, int col) // this checks the posibility 
    {
        for (int i = 0; i < 9; i++) //since the Grid size is 9x9
        {
            if (elements[i][col] == value) // row taking from 0-8 and the respective column is considered,then the value is assigned in place of 0 accordingly
            {
                return false;
            }
        }
        for (int i = 0; i < 9; i++) {
            if (elements[row][i] == value) //same the case here 
            {
                return false;
            }
        }
        int rowstart = row - (row % 3); //value is intialised for 3x3 grid row,will have 9 regions. 
        int colstart = col - (col % 3); //this is the col value for 3x3 grid 
        // This checks the specified row and col to make sure that each digit appears once and only once in the 3x3 grid
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (elements[rowstart + i][colstart + j] == value) // If a number has been reused then the Sudoku is invalid
                {
                    return false;
                }
            }
        }
        // If all the tests pass, then the sudoku is valid thus returns true.
        return true;
    }
}

Review Comments

Overall Rating (out of 10): 7

Solution 2 - Submitted on Sun Jun 23 23:35:27 2013

class CompleteSudokuPuzzle {

    public static void main(String s[]) {
        int[][] sudoku = {{0, 0, 0, 2, 0, 0, 0, 6, 3}, {3, 0, 0, 0, 0, 5, 4, 0, 1}, {0, 0, 1, 0, 0, 3, 9, 8, 0}, {0, 0, 0, 0, 0, 0, 0, 9, 0}, {0, 0, 0, 5, 3, 8, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 3, 0, 0, 5, 0, 0}, {5, 0, 3, 7, 0, 0, 0, 0, 8}, {4, 7, 0, 0, 0, 1, 0, 0, 0}};
        solveSudoku(sudoku);
        for (int[] array1d : sudoku) {
            for (int element : array1d) {
                System.out.print(element + " ");
            }
            System.out.println();
        }
    }

    public static void solveSudoku(int[][] sudoku) {
        setSingleOptionFields(sudoku);
        backtrack(sudoku, sudoku);
    }

    // Function to get All possible values for the given cell in the sudoku
    public static int[] getAllPossibleValues(int row, int column, int[][] sudoku) {
        boolean[] valuesNotPossible = new boolean[10];
        int count = getEmptySlots(row, column, sudoku, valuesNotPossible);
        int[] possibleValues = new int[count];
        // Getting all possibles values into an array 'possibleValues'
        for (int i = 1, j = 0; i < 10; i++) {
            if (valuesNotPossible[i] == false) {
                possibleValues[j] = i;
                j++;
            }
        }
        return possibleValues;
    }

    //Function to populate cells of sudoku where there is single option to fill cell using corresponding row,column and grid elements
    public static void setSingleOptionFields(int[][] sudoku) {
        //'isFurtherSettingPossible' is a boolean variable which tells whether further single option filling of sudoku is possible or not. 
        boolean isFurtherSettingPossible = false;
        while (true) {
            for (int row = 0; row < 9; row++) {
                for (int column = 0; column < 9; column++) {
                    if (sudoku[row][column] == 0) {
                        boolean[] valuesNotPossible = new boolean[10];
                        int count = getEmptySlots(row, column, sudoku, valuesNotPossible);
                        if (count == 1) {
                            for (int i = 1; i < 10; i++) {
                                if (valuesNotPossible[i] == false) {
                                    sudoku[row][column] = i;
                                    isFurtherSettingPossible = true;
                                }
                            }
                        }
                    }
                }
            }
            if (isFurtherSettingPossible == false) {
                break;
            }
            isFurtherSettingPossible = false;
        }
    }

    // Function to return number of elements possible at a given cell
    // boolean array is getting changed inside the function (It helps us to know the values possible at a given cell)
    public static int getEmptySlots(int row, int column, int[][] sudoku, boolean[] valuesNotPossible) {
        // Checking for elements 1 to 9 in given row and column
        for (int i = 0; i < 9; i++) {
            valuesNotPossible[sudoku[row][i]] = true;
            valuesNotPossible[sudoku[i][column]] = true;
        }
        // Checking for elements 1 to 9 in grid position of cell
        for (int i = (row / 3) * 3, rowLimit = i + 3; i < rowLimit; i++) {
            for (int j = (column / 3) * 3, columnLimit = j + 3; j < columnLimit; j++) {
                valuesNotPossible[sudoku[i][j]] = true;
            }
        }
        int count = 0;
        for (int i = 1; i < 10; i++) {
            if (valuesNotPossible[i] == false) {
                count++;
            }
        }
        return count;
    }

    // Backtracking function of sudoku
    // Function which selects one of the possible values for a given cell and if that selection cannot lead to correct answer then it will backtrack and take some other value to get correct solution
    public static boolean backtrack(int[][] sudoku, int[][] initialsudoku) {
        boolean isFinalAnswerFound = false;
        //making a copy of array (as the changes if done to the incoming array in the function changes the array that has been passed) 
        int[][] copiedSudoku = new int[9][9];
        copyArray(sudoku, copiedSudoku);
        setSingleOptionFields(copiedSudoku);
        if (isSudokuSolved(copiedSudoku, initialsudoku)) {
            return true;
        }
        boolean isSomeValueTaken = false;
        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                if (copiedSudoku[row][column] == 0) {
                    int[] possibleValues = getAllPossibleValues(row, column, copiedSudoku);
                    for (int possibleValue : possibleValues) {
                        copiedSudoku[row][column] = possibleValue;
                        isSomeValueTaken = true;
                        if (backtrack(copiedSudoku, initialsudoku) && isFinalAnswerFound == false) {
                            isFinalAnswerFound = true;
                        }
                        if (isFinalAnswerFound) {
                            return true;
                        }
                    }
                    if (isSomeValueTaken == false) {
                        return false;
                    }
                }
            }
        }
        return false;
    }

    // Function to check whether the given solution of sudoku is correct or not 
    // If the solution is correct then copying the final answer into initialsudoku array.
    public static boolean isSudokuSolved(int[][] sudoku, int[][] initialsudoku) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (sudoku[i][j] == 0)
                    return false;
            }
        }
        copyArray(sudoku, initialsudoku);
        return true;
    }

    //Function to copy double dimensional array into another double dimensional array
    public static void copyArray(int[][] originalArray, int[][] copiedArray) {
        for (int i = 0; i < originalArray.length; i++)
            copiedArray[i] = originalArray[i].clone();
    }
}

Review Comments

Overall Rating (out of 10): 6

© meritcampus 2019

All Rights Reserved.

Open In App