Q:

A matrix is given to you and eight vacant spaces are there. You have to fill the places with the digits 1 to 8 in a way that there are not any adjacent places filled with its next digits

0

Fill 8 numbers in a matrix

A matrix is given to you and eight vacant spaces are there. You have to fill the places with the digits 1 to 8 in a way that there are not any adjacent places filled with its next digits.

Fill 8 numbers in a matrix (1)

 

    Input:
    An matrix given to you
    
    E.g.
    0 -1 -1 0
    -1 -1 -1 -1
    0 -1 -1 0
    
    Here -1 indicates the vacant places in the matrix.
    
    Output:
    Print the matrix with the numbers.

Example

    If the matrix is this:
    0 -1 -1 0
    -1 -1 -1 -1
    0 -1 -1 0

    Output:
    0 3 5 0
    7 1 8 2
    0 4 6 0
Fill 8 numbers in a matrix (2)

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Placing the proper numbers in the right place is a try and error process and to solve it we use the backtracking process. To solve the matrix we have to follow the following steps.

  1. Start with a vacant place.
  2. Check how many numbers are left to fit for the place.
  3. Start with any of the remaining numbers and check that its next numbers are not in its adjacent places.
  4. Place the proper number in that vacant place and go for the adjacent vacant place.

If the matrix is this,

Fill 8 numbers in a matrix (Result)

And we start with the vacant place (1,2) and put the number 1 and if we will go (1,3), (2,3), (2,2), (2,4), (2,1) points followed by (1,2) and putting the numbers 3, 7, 2, 5. Then there are two vacant places but we will not fill those places with the numbers 8 or 6.

Fill 8 numbers in a matrix (3)

 

So using the backtracking method, in the place of (2,3) will put the next number 6 and again applying the same method to fill all the vacant places with the numbers.

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

int x[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int y[8] = { -1, 1, 0, 0, -1, -1, 1, 1 };

//check the validity of the point
bool is_valid(int row, int col, int a, int b)
{
    return (a >= 0 && a < row && b >= 0 && b < col);
}

bool all_visited(int* mat, int row, int col)
{
    int count = 0;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (*(mat + i * col + j) == -1) {
                return false;
            }
        }
    }
    return true;
}

bool print_matrix(int* mat, int row, int col)
{
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cout << *(mat + i * col + j) << " ";
        }
        cout << endl;
    }
    return true;
}

bool is_safe(int* mat, int row, int col, int curr_row, int curr_col, int curr)
{
    for (int j = 0; j < 8; j++) {
        int x_axis = curr_row + x[j];
        int y_axis = curr_col + y[j];

        //checking for the next numbers
        if (is_valid(row, col, x_axis, y_axis) && *(mat + x_axis * col + y_axis) != -1 && *(mat + x_axis * col + y_axis) != 0 && ((curr > 1 && (*(mat + x_axis * col + y_axis) == curr - 1 || *(mat + x_axis * col + y_axis) == curr + 1)) || (curr == 1 && *(mat + x_axis * col + y_axis) == curr + 1))) {
            return false;
        }
    }
    return true;
}

bool fill_matrix(int* mat, int row, int col, int curr_row, int curr_col, bool* visited, int prev)
{
    int flag = 0;

    for (int i = 1; i <= 8; i++) {
        //if the point is not visited
        if (!visited[i] && is_safe(mat, row, col, curr_row, curr_col, i)) {
            visited[i] = true;
            *(mat + curr_row * col + curr_col) = i;
            if (all_visited(mat, row, col))
                return true;
            for (int j = 0; j < 8; j++) {
                //go for the adjacents points
                int x_axis = curr_row + x[j];
                int y_axis = curr_col + y[j];
                if (is_valid(row, col, x_axis, y_axis) && *(mat + x_axis * col + y_axis) == -1 && fill_matrix(mat, row, col, x_axis, y_axis, visited, i)) {
                    return true;
                }
            }
            visited[i] = false;
            *(mat + curr_row * col + curr_col) = -1;
        }
    }
    return false;
}

int main()
{
    int mat[3][4] = { { 0, -1, -1, 0 },
        { -1, -1, -1, -1 },
        { 0, -1, -1, 0 } };

    int flag = 0, prev = -1;
    bool visited[9];

    for (int i = 0; i < 9; i++) {
        visited[i] = false;
    }

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            if (mat[i][j] == -1) {
                fill_matrix(&mat[0][0], 3, 4, i, j, visited, prev);
                flag = 1;
                break;
            }
        }
        if (flag)
            break;
    }

    //print the matrix
    print_matrix(&mat[0][0], 3, 4);
    return 0;
}

Output

 
0 6 4 0
2 8 1 7
0 5 3 0

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | Backtracking

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now
A set is given. You have to make K subsets by whic... >>
<< There is a set contains N no. of unsorted characte...