university-skills

Basic Skills acquired in semesters in Programming

View on GitHub

WEEK 9

Backtracking Problems - 20th April 2022

  1. Nqueen’s Problem
    Given a chess board having cells, you need to place N queens on the board in such a way that no queen attacks any other queen.

  2. Graph Coloring
    You are given a graph with N nodes and M undirected edges. This graph does not contain self loops and multiple edges between same pair of nodes. You plan to give this to Monk for his birthday so you wish to colour it. You want to colour all the nodes of the graph in either red or blue colour such that each edge has endpoints of different colours. As Monk loves red colour, you also want the number of nodes with red colour to be maximum. Output the maximum number of red coloured nodes you can get in the graph after colouring every vertex under the given constraint. If no such colouring is possible output “NO” (without quotes).