CODEWITHSUNDEEP
javaalgorithmrecursion
Rvngizswt
Rvngizswt

Reputation: 33

Four Color Theorem

I have been trying to write a code that would use the four color theorem to color regions defined by an adjacency matrix. An adjacency matrix would look like:

    A B C D

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

So for this example A is not adjacent to itself or C, but it is adjacent to B and D.

The program I am writing has to use recursion and back-tracing to assign 4 colors (or less) to the defined regions.

So far my algorithm is as follows:

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
  }

But I have a few questions:

  1. What would this method return?
  2. Would this work and have recursion/backtracing like it should?
  3. What would I output if the given row/column are out of bounds?

Thank you!

Upvotes: 1

Views: 1511

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65437

Your pseudocode looks more like local search than recursion/backtracking. The logical return would be void, since local search cannot prove the absence of a solution, so failure is indicated by running forever. (The coloring itself, if found, is returned via the global variables.)

Recursion/backtracking would be more like this.

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

The root invocation is extend-coloring(empty-coloring), where empty-coloring assigns no vertex a color. The return value indicates whether the attempt to extend the partial coloring succeeded.

Upvotes: 1

Related Questions