I was giving hackerrank test for some company recently and came across the following question. I searched and found out that it's unsolvable(NP-hard) for the given constraint. Please let me know if you know how to solve this one.
Problem
Calculate the number of ways to color an N * M grid using K colors. Adjacent squares in the grid should have different colors. Squares are considered adjacent if they share an edge.
Constraint : 1<=N,W,K<=10^5
Thanks
Some mathematical background:
https://math.stackexchange.com/questions/642921/chromatic-polynomial-of-a-grid-graph
I should note that finding the chromatic polynomial (i.e. a formula where you can plug in different different K to get the number of colorings) is open as you said, but this problem isn't asking for the chromatic polynomial, just for its value at a particular K. So maybe you are supposed to do a DP and calculate NumColorings(K) in terms of NumColorings(K-1).