Board coloring problem description, Programming Languages

Assignment Help:

Board Coloring

Problem Description

In this problem you are given a board in which some of the elements are placed as shown in diagram below. Each element represents a color.
Fill the other elements in the board, such that none of the adjacent elements (vertically, horizontally and diagonally) should be of the same color.
Find out the minimum number of colors that should be used to fill the blank spaces in the board, so that the above condition is met.
Color representation is -: 0, 1, 2, 3, 4, 5, 6, 7.........................
There is sample board:

641_board_coloring.png

            For Example:

Given Board :

821_board_coloring_1.png

Matrix representation of board is :
[ _ 1 _ _ ]
[ 2 _ _ _ ]
[ _ _ 2 _ ]
[ 2 _ _ _ ]
here blank space is represented by '_' .
Minimum colors to fill this board (given in the picture)is 4.

Instruction to work with Open PBT Client:

  1. Specify the work directory path in the 'Work directory Path' field. The path should correspond to your solution Work directory.
  2. Download the support files by clicking the Get Dev Files.
  3. You will find the problem directories containing:
    • problem.h file
    • problem.c file

in your project directory.

  1. Code the solution in.c file inside the problem directory
  2. All required files will be downloaded to your work directory. Creating additional files is strongly discouraged.

Step 1:

In your Solution File:

  • Implement your logic in function int color(char board[4][4])
  • char   board[4][4]board is 2 dimensional matrix of order M X M where M = 4.
  • You can create more functions if required, but those functions should be in the same file.

 

Step 2:

In your solution keep in mind the following constraints.

  1. In this problem you have to write a program that finds the minimum number of colors needed to fill a board in which some of the elements are placed in advance.
  2. Function color() will take 2 dimension board as a input.
  3. Function color() returns the minimum number of colors that could fill the board meeting the given condition.
  4. Board is a 2 dimensional of M X M where M = 4 else return 0
  5. Fill the other elements in the board, such that none of the adjacent elements (vertically, horizontally and diagonally) should be of the same color.

The Prototype of the function is

int color(char board[4][4])
This function takes following arguments.

  • board is 2 dimensional matrix of order M X M where M = 4.
  • This function returns minimum no of color by which board can be filled.

The constraints are:

  1. Board is a 2 dimensional of M X M where M = 4 else return 0
  2. Fill the other elements in the board, such that none of the adjacent elements (vertically, horizontally and diagonally) should be of the same color.

Example 1

Input


{ 2 0 _ 1 }
{ _ 1 _ _ }
{ _ 2 _ 0 }
{ _ _ _ 1 }

Output


5
Explanation:
We need a minimum 5 different colors to complete the board.

Example 2

Input


{ 2 0 _ 1 3}
{ _ 1 _ _ 2}
{ _ 2 _ 0 1}
{ _ _ _ 1 2}
{ _ _ _ _ 0}

Output


0


Explanation:
Size of the board is greater than 4X4.

Example 3

Input


{ _ 0 }
{ 1 _ }

Output


0


Explanation:
Size of the board is less than 4X4.

For C solutions

Header File

:

boardcoloring.h

Function Name

:

int color(char board1[4][4])

File Name

:

boardcoloring.c

For C++ solutions

Header File

:

boardcoloring.h

Class Name

:

BoardColoring

Function Name

:

int color(char board1[4][4])

File Name

:

boardcoloring.c

General Instructions

    *

The file / class names, functions, method signatures, header files are to be used as mentioned in the problem statement. Do not use your own names or change the method signatures and fields. You can add any number of additional methods.

    *

For C solutions, change the value of "C_OR_CPP" macro in header file as 1 and for C++ solutions change the value as 2.

    *

Incase of iostream.h specify as iostream only.

    *

Command line options for the main() function are not supported currently.


Related Discussions:- Board coloring problem description

Components of dot net framework 3-5, Components of .NET Framework 3.5 .NET ...

Components of .NET Framework 3.5 .NET Framework Conceptual Overview Presents the .NET Structure and its elements. Installing the .NET Framework Provides information about .NET Stru

How would you install a multiple layered security product, Problem: (i)...

Problem: (i) All Security authentication mechanism that run on the TRU64 Unix Operating system run under the Security Integration Architecture ( SIA ) layer. Explain with diag

Return value in an array, A specification of a function TOARR is given belo...

A specification of a function TOARR is given below. function TOARR(n in Int, s in Stack of Int) return in Array of Int pre n ≥ 0. post The returned value is an array of size

ActionScript, looking for help with a flash game assignment.

looking for help with a flash game assignment.

Outline the norms to be designing a web page, Question: (a) Outline th...

Question: (a) Outline the six norms to be considered before designing a Web page. (b) Write a program such that when a user right-clicks anywhere on a Web page, the follow

Vb assignment, Design an application that opens and analyses word files. R...

Design an application that opens and analyses word files. Requirements: Create an application that analyses text documents. It should open a text file, read each word into an ap

Introduction to javascript, This is the programming language of the Web. It...

This is the programming language of the Web. It is mainly used for validating forms. JavaScript & Java can be associated to each other. There exist several other differences betwee

Java.., create a program that can determine the number of students that are...

create a program that can determine the number of students that are doing their final year for a particular program (e.g. BCOM Information Systems), calculate the required credits

Write a program to read the file, Suppose you have a ?le orase of city and ...

Suppose you have a ?le orase of city and country names, like this: Cluj, Romania Debrecen, Hungary Klagenfurt, Austria Berlin, Germany Szeged, Hungary Budapest, Hungary Lintz, A

Add external style sheet in html code, On a single XHTML page, include the ...

On a single XHTML page, include the following two div container elements in the body. Using an external stylesheet, add style to the div elements such that one div has some overlap

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd