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

Introduction to Computer Vision

-
Image
  Do you ever think, how Facebook can automatically tag your friend when you upload an image, how your smart phone can recognize you, using it's very advanced and accurate  Face recognition feature.  Have you ever thought how a picture is processed by computer , how a picture  is stored in computer  etc.   These are very few examples, many more will be discussed as we go on, of Computer Vision. Well, In this post we are going to discuss about Computer Vision. So let's get started. What is C omputer Vision ? Computer Vision is a  interdisciplinary field that helps computer to make high-level understanding from digital images and videos to automate the task that human visuals do. It use some techniques  by which computer can understand many useful information from an image and perform some action based on that information. We see an image and our brain can understand the message, delivered by the image. Machines do exactly the same thing. ...
Read more

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-II)

-
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. In the previous post, I have shown you how to detect object very easily with less than 15 lines of code. But our concern is about the FPS(Frames Per Second). Check out the  Object Detection (PART-I)    if you have not seen yet.  In this post, we are going to optimize the previous post so that we can improve the FPS. In this case also we are gong to use YOLO  model again. There are 80 different classes that can be detected using YOLO model. such as-       person, bicycle, car, motorcycle, airplane, bus, train, truck, boat, traffic light, fire hydrant, stop_sign, parking meter, bench, bird, cat, dog, horse, sheep, cow, elephant, bear, zebra, giraffe, b...
Read more