board coloring, C/C++ Programming

n this problem u given a board in which some of the elements are placed as shown in diagram below .each element represent a color .fill the other elements in the board such that none of the adjacent element shud be of the same color find out the minimum number of colors that shud b used to fill the blank spaces in the board so that the above condition is met
diagram:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Posted Date: 8/29/2012 1:27:55 AM | Location : United States







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:

For Example:

Given Board :

The matrix representation of board is :
[ _ 1 _ _ ]
[ 2 _ _ _ ]
[ _ _ 2 _ ]
[ 2 _ _ _ ]
In the above example the blank space is represented by ''_'' .
The minimum number of colors needed to fill the board in the example is 4.

Instruction to work with Open PBT Client:

Specify the work directory path in the ''Work Directory Path'' field. The path should correspond to your solution project directory.
Download the support files by clicking the Get Dev Files.
You will find the following three folders:
bin
src
lib
in your work directory.
Code the solution in . java file inside the src folder
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 public int color(char[][] board) in class BoardColoring .
char[][] board : board is 2 dimensional matrix of order M X M where M = 4.

You can create more methods but, do it in the same class.

Step 2:
In your solution keep in mind the following constraints.

In this problem you have to write a program to find the minimum no of colors to fill a board where some of the elements of different color are already placed.
Method color() will take 2 D board as a input.
Method color() will return minimum no of colors which can fill the board with given condition.
The board should be a 2-dimensional M X M matrix, where M =4 otherwise return 0
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 method is:

public int color(char[][] board).
This method takes following arguments.

board is 2 dimensional matrix of order M X M where M = 4.

This method returns minimum no of color by which board can be filled.

The constraints are:

The board should be a 2-dimensional M X M matrix, where M =4 otherwise return 0
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 Java solutions
Package Name : test.boardcoloring
File Name : BoardColoring.java
Class Name : BoardColoring
Method Names : public int color(char[][] board)
Posted by diana | Posted Date: 9/4/2012 4:23:52 AM


Related Discussions:- board coloring, Assignment Help, Ask Question on board coloring, Get Answer, Expert's Help, board coloring Discussions

Write discussion on board coloring
Your posts are moderated
Related Questions

create two array names and grade .in first array you have to store thease 10 names 1.a,2.3.r,4.s,5.l,6.k,7.n,8.b,9.z,10.d you have to enter grades for thease students.te program mu

P o i n t e r d e c l a r a t i o n f o r me m b e r f un c t i o n : M e t h o d 1 : W h e n C l a ss i s n o t

Shell sort - C Program: Write a program to define shell sort. void main() {                  //program for sorting by select sort int a[20],i,k,j,n;   clrscr();

Presently we are using several spreadsheets to give weekly activity and income reports. Much of the information is being frequently re-keyed into several spreadsheets - we are look


Write a program of constructors and destructors Make a class drugs having encapsulated data for medicine name, whether solid or liquid, price and purpose of use. From this clas

#questionhow can i add new customer and alot him a new unique id ..

Write a C function to solve the system of linear equations A x = y where A is an N by N matrix in the format of pointer-to-pointers and y is a vector in the format of a pointer. Th

the problem description. The order of the C Program should be as follows: Variables and constants Use #define statements to define the constants. Use arr