EightSisters marriage assignment problem

EightSisters.java

// Solution for [2015-09-11] Challenge #231 [Hard] Eight Husbands for Eight Sisters
//
// https://www.reddit.com/r/dailyprogrammer/comments/3kj1v9/20150911_challenge_231_hard_eight_husbands_for/
//
// NOTE: This is ugly Java - lots of global variables, etc.

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

public class EightSisters {

  static boolean flagSingleStep = false;
  static boolean flagExplain = false;
  static List< int[] > foundSolutions = new ArrayList<int[]>();

  public static void main(String[] args) {
    flagSingleStep = true;
    findall();
    // check("jhbifdecag");
  }

  public static void findall() {
    buildPairs(1);
    System.out.println("count = " + count);
    System.out.printf("solutions found: %d\n", foundSolutions.size());
    for (int i = 0; i < foundSolutions.size(); ++i) {
      System.out.printf("  %2d: ", i+1);
      showSolution( foundSolutions.get(i) );
      System.out.println();
    }
  }
  
  static final int N = 10; // number of brothers / sisters

  static int[][] rank =
    {
               {0, 0, 0, 0, 0, 0,  0, 0, 0, 0, 0},
       /* A */ {0, 7, 1, 5, 2, 10, 8, 3, 4, 9, 6},  // b d g h c j a f i e,
       /* B */ {0, 5, 2, 9, 10, 8, 1, 4, 7, 3, 6},  // f b i g a j h e c d,
       /* C */ {0, 10, 1, 9, 6, 7, 8, 4, 5, 2, 3},  // b i j g h d e f c a,
       /* D */ {0, 2, 7, 5, 9, 3, 1, 8, 10, 4, 6},  // f a e i c j b g d h,
       /* E */ {0, 3, 6, 7, 2, 4, 1, 8, 10, 5, 9},  // f d a e i b c g j h,
       /* F */ {0, 3, 8, 4, 1, 6, 2, 9, 10, 7, 5},  // d f a c j e i b g h,
       /* G */ {0, 7, 4, 3, 6, 1, 5, 2, 10, 8, 9},  // e g c b f d a i j h,
       /* H */ {0, 6, 3, 4, 9, 5, 1, 8, 7, 2, 10},  // f i b c e a h g d j,
       /* I */ {0, 2, 7, 5, 10, 6, 4, 8, 9, 1, 3},  // i a j f c e b g h d,
       /* J */ {0, 6, 5, 3, 9, 4, 2, 8, 1, 10, 7},  // h f c e b a j g d i,

       /* a */ {0, 9, 5, 2, 7, 3, 6, 8, 10, 4, 1},  // J C E I B F D G A H,
       /* b */ {0, 6, 8, 4, 5, 7, 10, 9, 2, 1, 3},  // I H J C D A E B G F,
       /* c */ {0, 6, 2, 1, 7, 10, 4, 9, 5, 3, 8},  // C B I F H A D J G E,
       /* d */ {0, 10, 9, 5, 4, 6, 1, 2, 8, 7, 3},  // F G J D C E I H B A,
       /* e */ {0, 5, 9, 4, 1, 8, 10, 2, 6, 7, 3},  // D G J C A H I E B F,
       /* f */ {0, 8, 5, 3, 7, 1, 6, 9, 2, 10, 4},  // E H C J B F D A G I,
       /* g */ {0, 6, 8, 10, 9, 4, 2, 3, 7, 5, 1},  // J F G E I A H B D C,
       /* h */ {0, 6, 3, 2, 8, 1, 9, 7, 4, 5, 10},  // E C B H I A G D F J,
       /* i */ {0, 2, 8, 10, 6, 5, 3, 4, 7, 9, 1},  // J A F G E D H B I C,
       /* j */ {0, 2, 3, 4, 8, 1, 10, 7, 9, 6, 5},  // E A B C J I G D H F,
    };


  static int count = 0;
  // notok[m][f] == 0 means the marriage m with f has not been ruled out.
  static int[][] notok  = new int[2*N+1][N+1];

  // assign[m] = sister assigned to brother m
  static int[]   assign = new int[N+1];

  public static char toChar(int i) {
    char start;
    if (i <= N) {
      start = (int) 'A' - 1;
    } else {
      start = (int) 'a' - N - 1;
    }
    return (char) ( start + i );
  }

  public static void explain(int m1, int f1, int m2, int f2) {
    char m1c = toChar(m1);
    char f1c = toChar(N+f1);
    char m2c = toChar(m2);
    char f2c = toChar(N+f2);
    System.out.printf("pair 1: %c %c    pair 2: %c %c\n", m1c, f1c, m2c, f2c);
    System.out.printf("%c rank of %c: %2d  rank of %c: %2d\n", m1c, f1c, rank[m1][f1],   f2c, rank[m1][f2]);
    System.out.printf("%c rank of %c: %2d  rank of %c: %2d\n", f2c, m2c, rank[N+f2][m2], m1c, rank[N+f2][m1]);
    System.out.println();
    System.out.printf("%c rank of %c: %2d  rank of %c: %2d\n", m2c, f2c, rank[m2][f2],   f1c, rank[m2][f1]);
    System.out.printf("%c rank of %c: %2d  rank of %c: %2d\n", f1c, m1c, rank[N+f1][m1], m2c, rank[N+f1][m2]);
  }

  public static boolean allStable() {
    for (int m1 = 1; m1 <= N; ++m1) {
      for (int m2 = m1+1; m2 <= N; ++m2) {
        int f1 = assign[m1];
        int f2 = assign[m2];

        if (unstable(m1, f1, m2, f2)) {
          if (flagExplain) {
            explain(m1, f1, m2, f2);
          }
          return false;
        }
      }
    }
    return true;
  }

  public static void moveto(int r, int c) {
    System.out.printf("\033[%d;%dH", r, c);
  }

  public static void displayState(int m) {

    System.out.print("\033[H\033[2J"); 

    // display assign
    System.out.print("assign: ");
    for (int i = 1; i <= m; ++i) {
      System.out.format("%3d", assign[i]);
    }

    if (m >= N) {
      if (allStable()) {
        System.out.print(" STABLE");
      } else {
        System.out.print(" NOT STABLE");
      }
    }
    System.out.println();

    // display notok
    System.out.print("\nnotok\n");

    // display notok for N = 1..N
    System.out.print("     ");
    for (int i = N+1; i <= N+N; ++i) {
      System.out.printf(" %c ", toChar(i) );
    }
    System.out.println();

    for (int i = 1; i <= N; ++i) {
      System.out.printf(" %c -", toChar(i) );
      for (int j = 1; j <= N; ++j) {
        System.out.printf("%3d", notok[i][j]);
      }
      System.out.printf(" %3d\n", notok[i][0]);
    }

    System.out.printf("\n\n");

    // display notok for N = N+1..N+N
    System.out.print("     ");
    for (int i = 1; i <= N; ++i) {
      System.out.printf(" %c ", toChar(i) );
    }
    System.out.println();

    for (int i = N+1; i <= N+N; ++i) {
      System.out.printf(" %c -", toChar(i) );
      for (int j = 1; j <= N; ++j) {
        System.out.printf("%3d", notok[i][j]);
      }
      System.out.printf(" %3d\n", notok[i][0]);
    }

    /// display solutions

    moveto(3, 50);
    System.out.printf("steps: %5d", count);

    moveto(6, 50);
    System.out.printf("found solutions: %d", foundSolutions.size());

    for (int i = 0; i < foundSolutions.size(); ++i) {
      moveto(i+8, 50);
      showSolution( foundSolutions.get(i) );
    }

    moveto(26, 0);

    System.out.print("\n\n\nHit return:");
    String input = System.console().readLine();
  }

  public static void showSolution(int[] sol) {
    for (int m = 1; m <= N; ++m) {
      System.out.printf(" %c ", toChar( N + sol[m] ) );
    }
  }

  public static boolean unstable(int m1, int f1, int m2, int f2) {
    boolean unstable = 
       (rank[m1][f2] < rank[m1][f1] && rank[N+f2][m1] < rank[N+f2][m2])
        ||
       (rank[m2][f1] < rank[m2][f2] && rank[N+f1][m2] < rank[N+f1][m1]);
    return unstable;
  }

  public static void displaySolution() {
    for (int m = 1; m <= N; ++m) {
      System.out.printf(" %c", toChar( assign[m] + N ));
    }
    System.out.println();
    // System.out.println( Arrays.toString(assign) );
  }

  public static void check(String s) {

    // int[] sol = { 0, 8, 10, 2, 5, 6, 4, 7, 9, 1, 3 };
    //                            e, f
    //int[] sol = { 0, 10, 9, 8, 5, 6, 4, 7,  2, 3, 1 };
    int[] sol = new int[N+1];

    for (int m = 1; m <= N; ++m) {
      char c = s.charAt(m-1);
      int f = c - 'a' + 1;
      sol[m] = f;
    }

    System.out.print("Checking: ");
    showSolution(sol);
    System.out.println();

    flagExplain = true;
    for (int m = 1; m <= N; ++m) {
      assign[m] = sol[m];
    }
    System.out.println("allStable = " + allStable() );
    flagExplain = false;
  }

  // m in [1..N]
  public static void buildPairs(int m) {

    if (m > N) {
      foundSolutions.add(assign.clone());
      return;
    }

    int i;

    for (int f = 1; f <= N; ++f) {
      if (notok[m][f] != 0 || notok[N+f][m] != 0) {
        continue;
      }

      count++;
      assign[m] = f;

      if (flagSingleStep) displayState(m);

      // no other male can be assigned to f
      for (int m2 = m+1; m2 <= N; ++m2) {
        if ( notok[m2][f] == 0 ) {
          notok[m2][f] = m;
          notok[m2][0]++;
        }
      }

      // no other female can be assigned to m
      for (int f2 = 1; f2 <= N; ++f2) {
        if ( f2 != f && notok[N+f2][m] == 0 ) {
          notok[N+f2][m] = m;
          notok[N+f2][0]++;
        }
      }

      for (int m2 = m+1 ; m2 <= N; ++m2) {
        for (int f2 = 1; f2 <= N; ++f2) {
          if ( notok[m2][f2] == 0 || notok[N+f2][m2] == 0 ) {
            if (unstable(m, f, m2, f2)) {
              if (notok[m2][f2] == 0) {
                notok[m2][f2] = m;
                notok[m2][0]++;
              }
              if (notok[N+f2][m2] == 0) {
                notok[N+f2][m2] = m;
                notok[N+f2][0]++;
              }
            }
          }
        }
      }

      boolean cont = true;
      for (i = m+1; i <= N+N; ++i) {
        if (notok[i][0] >= N) {
          cont = false;
          break;
        }
      }

      if (cont) {
        buildPairs(m+1);
      }

      // retract constraints

      for (i = m+1; i <= N+N; ++i) {
        for (int j = 1; j <= N; ++j) {
          if (notok[i][j] == m) {
            notok[i][j] = 0;
            notok[i][0]--;
          }
        }
      }

    }
  }
}