c++ - Calculate the number of ways to color an N * M grid using K colors

Question

I wanna ask you how to 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. Is there a fast algorithm to do that?

Answer 1

NOTE: I am assuming that we do not have use every color. If we do, additional checks can easily be applied.

Here is some code that can solve your problem (I think)... It uses a brute force / backtracking algo. Here is the output for 3 colors, and 2 by 3 grid. It prints every combination that it found. For this input, the answer is 54.

Enter number of colors: 3
Enter number of rows: 2
Enter number of columns: 3
121
212

121
213

123
212

121
232

123
231

123
232

131
212

131
213

132
213

121
312

121
313

123
312

131
312

131
313

132
313

131
323

132
321

132
323

212
121

212
123

213
121

212
131

213
131

213
132

231
123

232
121

232
123

212
321

212
323

213
321

231
312

231
313

232
313

231
323

232
321

232
323

312
121

312
123

313
121

312
131

313
131

313
132

321
132

323
131

323
132

312
231

313
231

313
232

321
212

321
213

323
212

321
232

323
231

323
232

There are 54 different combinations of 3 colors.

Here is a Java code:

import java.util.*;

public class ColorChoices
{
    int[][] grid;
    int numberOfColors;
    int numberOfRows;
    int numberOfColumns;
    int numberOfCombinations;

    public static void main(String[] args)
    {
        ColorChoices solution = new ColorChoices();
        solution.begin();

    }

    void begin()
    {
        numberOfCombinations = 0;
        Scanner consoleInput = new Scanner(System.in);
        System.out.print("Enter number of colors: ");
        numberOfColors = consoleInput.nextInt();
        System.out.print("Enter number of rows: ");
        numberOfRows = consoleInput.nextInt();
        System.out.print("Enter number of columns: ");
        numberOfColumns = consoleInput.nextInt();
        grid = new int[numberOfRows][numberOfColumns];

        solve(0, 0);

        System.out.println("There are " + numberOfCombinations + " different combinations of " + numberOfColors + " colors.");
    }

    void solve(int r, int c)
    {
        for(int i = 1; i <= numberOfColors; i++)
        {   
            if(valid(r, c, i))
            {
                grid[r][c] = i;
                if(r == numberOfRows - 1 && c == numberOfColumns - 1) 
                {
                    printBoard();
                    numberOfCombinations++;
                }
                else if(r == numberOfRows - 1) solve(0, c + 1);
                else solve(r + 1, c);
            }
        }
        grid[r][c] = 0;
    }

    boolean valid(int r, int c, int n)
    {
        return(leftOK(r, c, n) && rightOK(r, c, n) &&  topOK(r, c, n) &&  bottomOK(r, c, n));
    }

    boolean leftOK(int r, int c, int n)
    {
        if(c == 0) return true;
        if(grid[r][c - 1] != n) return true;
        return false;
    }

    boolean rightOK(int r, int c, int n)
    {
        if(c == numberOfColumns - 1) return true;
        if(grid[r][c + 1] != n) return true;
        return false;
    }

    boolean topOK(int r, int c, int n)
    {
        if(r == 0) return true;
        if(grid[r - 1][c] != n) return true;
        return false;
    }

    boolean bottomOK(int r, int c, int n)
    {
        if(r == numberOfRows - 1) return true;
        if(grid[r + 1][c] != n) return true;
        return false;
    }

    void printBoard()
    {
        for(int i = 0; i < numberOfRows; i++)
        {
            for(int j = 0; j < numberOfColumns; j++)
            {
                System.out.print(grid[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }
}