Program to check whether we can fill square where each row and column will hold distinct elements in Python

https://www.tutorialspoint.com/program-to-check-whether-we-can-fill-square-where-each-row-and-column-will-hold-distinct-elements-in-python

10-10-2020
|

Question

Program to check whether we can fill square where each row and column will hold distinct elements in Python

Python Server Side Programming Programming

Suppose we have one n × n matrix containing values from 0 to n. Here 0 represents an unfilled square, we have to check whether we can fill empty squares such that in each row and each column every number from 1 to n appears exactly once.

So, if the input is like

0	0	2
2	0	1
1	2	3

then the output will be True, as we can set the matrix to

3	1	2
2	3	1
1	2	3

To solve this, we will follow these steps −

Define a function find_empty_cell() . This will take matrix, n
for i in range 0 to n, do
- for j in range 0 to n, do
  - if matrix[i, j] is same as 0, then
    - return(i, j)
return(-1, -1)
Define a function is_feasible() . This will take matrix, i, j, x
if x in ith row of matrix, then
- return False
if x in jth column in any row of matrix, then
- return False
return True
Define a function is_complete() . This will take matrix, n
for each row in matrix, do
- if row has some duplicate elements, then
  - return False
- for col in range 0 to n, do
  - if col has some duplicate elements, then
    - return False
- return True
- From the main method do the following −
- n := row count of matrix
- (i, j) = find_empty_cell(matrix, n)
- if (i, j) is same as (-1, -1), then
  - if is_complete(matrix, n) is true, then
    - return True
  - otherwise,
    - return False
- for x in range 1 to n + 1, do
  - if is_feasible(matrix, i, j, x) is true, then
    - matrix[i, j] := x
    - if solve(matrix) is true, then
      - return True
    - matrix[i, j] := 0
- return False

Let us see the following implementation to get better understanding −

Example

Live Demo

class Solution:
   def solve(self, matrix):
      n = len(matrix)
      def find_empty_cell(matrix, n):
         for i in range(n):
            for j in range(n):
               if matrix[i][j] == 0:
                  return (i, j)
         return (-1, -1)
      def is_feasible(matrix, i, j, x):
         if x in matrix[i]:
            return False
         if x in [row[j] for row in matrix]:
            return False
         return True
      def is_complete(matrix, n):
         for row in matrix:
            if set(row) != set(range(1, n + 1)):
               return False
         for col in range(n):
            if set(row[col] for row in matrix) != set(range(1, n + 1)):
               return False
         return True
      (i, j) = find_empty_cell(matrix, n)

      if (i, j) == (-1, -1):
         if is_complete(matrix, n):
            return True
         else:
            return False
      for x in range(1, n + 1):
         if is_feasible(matrix, i, j, x):
            matrix[i][j] = x
            if self.solve(matrix):
               return True
            matrix[i][j] = 0
      return False
ob = Solution()
matrix = [
   [0, 0, 2],
   [2, 0, 1],
   [1, 2, 3]
]
print(ob.solve(matrix))

Input

matrix = [
   [0, 0, 2],
   [2, 0, 1],
   [1, 2, 3] ]

Output

True

Arnab Chakraborty

Published on 09-Oct-2020 19:09:48

Previous Page Print Page