CODU Sudoku

-

Problem Description

(TCS Codevita-2020 CODU Sudoku)

CODU is solving a 7x7 sudoku. Help him in solving the unique Sudoku.

Rules are as follows

1. There are 7 regions colored differently. Each region must have a single occurrence of numbers between range [1, 7].

2. Regions don't have a fix shape and it can change from input to input.

3. Each row must have a single occurrence of numbers between range [1, 7] across all input.

4. Each column must have a single occurrence of numbers between range [1, 7] across all input.

Some numbers in some rows, columns and regions will be given. These will be between [1, 7].

Zero (0) denotes that the number is covered. Uncovering it will give a number between [1, 7].

Your task is to fill the numbers [1,7] where there is a 0 such that the 7x7 Sudoku is solved.

7x7 Sudoku is said to be solved when every region, every column, every row has exactly one occurrence of numbers [1,7].

Constraints
7 < Known/Given numbers in Entire Sudoku < 14

Input
Input consists of 14 lines.

First 7 lines denote the positions of numbers [1,7] in respective row and column.

Next 7 lines denote the shape of the regions inside the Sudoku. These will be denoted by 7 unique characters between alphabets [a-z].

Output
Print the solved Sudoku.

7 lines, each line containing 7 space separated integers honoring all the conditions.

Time Limit
1

Example 1

Input

0 0 0 0 0 6 0

0 0 0 0 0 0 0

2 6 5 1 7 4 3

0 0 0 3 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

a a a b b b b

a a a a b b c

d d d e e b c

d d d d e e c

f f f h e e c

f f h h e c c

f f h h h h c

Output

1 2 4 5 3 6 7

3 5 6 7 1 2 4

2 6 5 1 7 4 3

4 7 1 3 2 5 6

7 1 2 6 4 3 5

5 4 3 2 6 7 1

6 3 7 4 5 1 2

Example 2

Input

0 0 0 0 0 0 0

0 0 0 0 4 0 0

3 0 0 6 0 0 0

0 0 0 0 6 0 1

5 0 0 0 0 0 3

0 0 1 0 0 0 2

2 0 0 0 0 0 5

r r r b b b b

g r r r r b o

g g g g b b o

p p g o o o o

p p g d o l l

p p p d l l l

d d d d d l l

Note that the shape of the regions will vary  from input to input.

Output

7 1 3 4 5 2 6

1 6 5 2 4 3 7

3 5 2 6 1 7 4

4 2 7 3 6 5 1

5 7 4 1 2 6 3

6 3 1 5 7 4 2

2 4 6 7 3 1 5

Solution of CODU Sudoku Problem

In this case, I have used backtracking to solve this problem.
  • Taking input from the user
  • Defining function like print_board() to print the output, get_pos() to get the unmasked  position, valid_board() to check weather the board is satisfying all the constrains or not, and solve() to solve the sudoku.
  • At last print the initial board and the solved board 


python code
1

python code
2

python code
3

python code
4

python code
5

   

Note: To Access the code please click the link. Anyone wants the code in c++ then let me know.


Output of the python code

python output
Output-I
Output-II




Comments

Post a Comment

Popular posts from this blog

Distance measurement using opencv

-
Image
In Covid-19 pandemic, we all know about the importance of Social Distancing . Right now, It is the only thing that can help to reduce the number of affected people. So I have decided to make a social distancing checker using python. The main idea is to measure the distance of object in the image and if the distance between two objects are less than some predefined pixel value then 'green' dot at the center of the bounding-box will convert to 'red' dot . The output of the code will like this- social distancing checker Python code for Distance Measurement I am providing the python code to measure the distance of the object in the image or each frame of a video. Later I will discuss some key points related to the code. Key points to be Noted: Everything will be the same like object detection (discussed in Part-I and Part-II ) as I have implemented distance measurement based on object detection. We will filter out only the  'person' object   from the obje
Read more

Object Detection (Part I)

-
Image
The most fundamental computer technology related to Computer vision and Image Processing is Object Detection. It deals with detecting the   semantic object of a certain class in digital images and videos. Have a look on the images, bellow. Object detection with YOLO Detecting home objects Here, we can see that the model can detect the home objects (chair, bag, laptop, bottle, laptop, bowl, cup etc.) and also the outer-home objects ( bus, bi-cycle, human, car etc.).  Object Detection Object Detection is a supervised learning technique by which the model can detect or predict the object present in the digital images or videos. We can make our own object detecting tool using python with the help of Computer vision with deep learning model ( Here we have used YOLO model ). In this post we are going to create our own object detecting model in python.  As this is the PART-I, I will keep this very simple but FPS(Frames Per Seconds)  will be very low due to its simplicity. In the next post
Read more

Invisible Cloak using OpenCV

-
Image
Have you ever seen Harry Potter’s   Invisible Cloak   If not then let's have a look.     Was it wonderful? Do you surprised how this can be possible? If yes, then this post is going to help you. You will be able to make such invisible cloak by your own but yes, not in real way but it is all about graphics . Algorithm behind the idea First, we take the background frame ( for some second ) and store in the memory. Then, we will take the frame with cloth. Then, detect and segment the portion of the cloth of pre-determined color. For Example here we will use Red. [ known as Color Detection and Image Segmentation ] Then, that segment will be replaced by the background , we have stored in the memory, segment. At last, create the final image to make the magic. Note: All the things will be done in python due to the availability of the various libraries mainly numpy . Python Code: First of all, importing all the required libraries.   To make a vid
Read more