Четырехцветная теорема

Question

Я пытаюсь написать код, который будет использовать четырехцветную теорему для областей цвета, определенных матрицей смежности. Матрица смежности будет выглядеть следующим образом:

A B C D 

A 0 1 0 1 
B 1 0 1 0 
C 0 1 0 1 
D 1 0 1 0 

Так для этого примера А не смежна с собой или C, но она находится рядом с B и D.

Программа Я пишу должен использовать рекурсию и back-tracing, чтобы назначить 4 цвета (или меньше) определенным областям.

До сих пор мой алгоритм выглядит следующим образом:

global int[] colors = <region one color,region two, region three, region four > 
public static int color(row,column) 
    if out of bounds ?? 
    loop(!colored) 
    { 
     case 1: are any adjacent regions this color? assign 
     case 2: are any adjacent regions this color? assign. 
     case 3: are any adjacent regions this color? assign. 
     case 4: are any adjacent regions this color? assign. 
     case 5: if nothing found, steal closest (in #) region's color and call method from there 
    } 

Но у меня есть несколько вопросов:

1. Что бы этот метод возвращения?
2. Будет ли это работать и иметь рекурсию/обратную трассировку, как это должно быть?
3. Что бы вывести, если данная строка/столбец выходит за пределы?

Спасибо!

Answer 1

Ваш псевдокод больше похож на local search, чем на рекурсию/обратную трассировку. Логическим возвратом будет void, так как локальный поиск не может доказать отсутствие решения, поэтому отказ указывается запуском навсегда. (Сама окраска, если она найдена, возвращается через глобальные переменные.)

Рекурсия/обратное отслеживание будет более похоже на это.

boolean extend-coloring(partial-coloring): 
    if every vertex has a color, then return true 
    let v be a vertex without a color 
    for each color c, 
     if v has no neighbors of color c, 
      apply color c to v in partial-coloring 
      if extend-coloring(partial-coloring), then return true 
      remove color c from v 
    return false 

Корень призывание является extend-coloring(empty-coloring), где empty-coloring не назначает ни одной вершины цвет. Возвращаемое значение указывает, удалась ли попытка расширения частичной раскраски.