Граф раскраски всех возможных решений, особый случай - PullRequest
Новая
       19

Граф раскраски всех возможных решений, особый случай

1 голос
/ 05 мая 2019

Я пытаюсь решить проблему с сеткой. скажем (3xn). Использование 3 цветов. Я хочу количество всех возможных решений. Соседние ячейки сетки могут иметь одинаковый цвет. Единственное ограничение:

No one single row or column can have all cells having the same colour.

Как лучше всего решить эту проблему примерно для 25000 столбцов?

Я решил тот, где ни одна соседняя клетка не должна иметь одинаковый цвет. И для 3 строк и 2 столбцов, которые дали 54 решения. где я только что изменил код с этого сайта и просто проверьте крайние случаи.

например нижний конец: 

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

И, наконец, решить это как: 

 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(isLeftOk(r, c, n) && isRightOk(r, c, n) &&  isTopOk(r, c, n) &&  isBottomOk(r, c, n));
    }

В результате. Я ожидаю, что у меня будет решение, которое будет работать для всех 3xn сеток с максимум 25000 столбцов, использующих 3 цвета.

...