M coloring problem

DiffPush Tier Recursion · Try Out All Combos O(m^N) — every tower may try every channel · O(N) for the color array and recursion depth

Assigning Radio Channels to Tower Neighbours

A county tower network must assign one of m available radio channels to every tower so that directly linked towers never broadcast on the same channel. The engineer walks the tower list in order, tries each channel on the current tower, and only accepts the assignment when none of its linked neighbours already holds that channel; a dead end retracts the channel and tries the next one.

Input: A boolean adjacency matrix graph of N x N, the number of colors m, and the number of vertices N.

Output: true when every vertex can receive one of m colors without any edge joining equal colors.

Constraints

1 <= N <= 20
1 <= m <= N
graph[i][j] is 1 exactly when towers i and j are linked

Examples

Example 1

Input: {"graph":[[false,true,true,true],[true,false,true,false],[true,true,false,true],[true,false,true,false]],"m":3,"N":4}
Output: true
This wheel-plus-chord graph is 3-colorable — a full palette lets every linked pair differ.

Example 2

Input: {"graph":[[false,true,true,true],[true,false,true,false],[true,true,false,true],[true,false,true,false]],"m":2,"N":4}
Output: false
Vertices 0, 1, 2 form a triangle, which no 2-coloring can satisfy.

Solve this in your browser →

Also on LeetCode ↗