/*
C++ program that finds c-colorings of m x n grids avoiding right triangles
by Nils Molina

README

In the beginning of the program there is a series of #define statements

#define xdim *
#define ydim *
#define cdim *

Change the first, second and third asterisks to the values of m, n and c,
respectively.

If you compile and run, the program will, given enough time, find if there are
any c-colorings of m x n without right triangles. If there are, it will output
one of these c-colorings. If there are not, it will say there are no
c-colorings.

The program below is configured to find a 5-coloring of 6x8 without any right
triangles. For other grid sizes the program may be too slow. One way of speeding
up the program is adding hadd() statements below, in the part of the program
marked "hadd statements HERE." For example, if you know that any coloring of
of your grid will have two red and two blue points on the second row, you add
the following hadd statements:
    
hadd(0,1,1);
hadd(1,1,1);
hadd(2,1,2);
hadd(2,1,2);

Each hadd statement has the following syntax:

hadd(COLNUMBER-1, ROWNUMBER-1, COLORNUMBER).

You can hadd as many "forced points" to the grid as you want. The only
restriction is that you cannot hadd a point at position (0,0), and you have to
assume point (0,0) has color number 1.
*/

#define xdim 6
#define ydim 8
#define cdim 5

#include <iostream>

using namespace std;

int complete;

int a[xdim][ydim];

int onrow[ydim][cdim+1];
int oncol[xdim][cdim+1];

bool can[xdim][ydim][cdim+1];
int cancount[xdim][ydim];

int uix;
int ux[xdim * ydim * (cdim+1)];
int uy[xdim * ydim * (cdim+1)];
int uc[xdim * ydim * (cdim+1)];

void remove(int x, int y, int c) {
    if(can[x][y][c]) {
        can[x][y][c] = 0;
        cancount[x][y]--;
        ux[uix] = x;
        uy[uix] = y;
        uc[uix] = c;
        uix++;
    }
}

void undo(int nix) {
    while(uix != nix) {
        uix--;
        can[ux[uix]][uy[uix]][uc[uix]] = 1;
        cancount[ux[uix]][uy[uix]]++;
    }
}

int mx, my, minv;
int findmin() {
    minv = cdim+1;
    for(int x = 0; x < xdim; x++) for(int y = 0; y < ydim; y++) if(!a[x][y])
        if(cancount[x][y] < minv) {
            minv = cancount[x][y];
            mx = x;
            my = y;
        }
}

void print() {
    for(int i = 0; i < ydim; i++, cout << endl) for(int j = 0; j < xdim; j++)
        cout << a[j][i] << " ";
}

void search(int x, int y, int c) {
    if(onrow[y][c]==1) { //if create a row pair
        int i;
        for(i = 0; a[i][y] != c; i++) ; //find it
        for(int j = 0; j < ydim; j++) { //scan down
            remove(i, j, c);
            remove(x, j, c);
        }
    } else if(onrow[y][c] > 1) //if join row pair
        for(int j = 0; j < ydim; j++)
            remove(x, j, c);
    else //if becomes alone on this row
        for(int j = 0; j < xdim; j++)
            if(oncol[j][c]) remove(j,y,c);
            
    if(oncol[x][c]==1) { //if create a col pair
        int i;
        for(i = 0; a[x][i] != c; i++) ; //find it
        for(int j = 0; j < xdim; j++) { //scan across
            remove(j, i, c);
            remove(j, y, c);
        }
    } else if(oncol[x][c] > 1) //if join col pair
        for(int j = 0; j < xdim; j++)
            remove(j, y, c);
    else //if becomes alone on this column
        for(int j = 0; j < ydim; j++)
            if(onrow[j][c]) remove(x,j,c);
}

void hadd(int x, int y, int c) { //permanently puts certain elements in place    
    search(x,y,c);
    a[x][y] = c;
    onrow[y][c]++;
    oncol[x][c]++;
    complete++;
}

void add(int x, int y, int c) {    
    int nix = uix;
    search(x,y,c);
    a[x][y] = c;
    onrow[y][c]++;
    oncol[x][c]++;
    complete++;
    if(complete == xdim*ydim) {
        cout << xdim << " x " << ydim << " has a " << cdim << "-coloring" << endl;
        print();
        cin >> mx;
        exit(0);
    }
    
    findmin();
    if(minv >= 1) for(int mc = 1; mc <= cdim; mc++) if(can[mx][my][mc]) {
        add(mx,my,mc);
        remove(mx,my,mc);
        if(--minv == 0) break;
    }
    
    a[x][y] = 0;
    onrow[y][c]--;
    oncol[x][c]--;
    complete--;
    undo(nix); //roll back changes to can[][][]
} 

int main() {
    for(int i = 0; i < xdim; i++) for(int j = 0; j < ydim; j++) {
        cancount[i][j] = cdim;
        for(int k = 1; k <= cdim; k++)
            can[i][j][k] = 1;
    }
    
    //hadd statements HERE
    
    //end of hadd statements
    
    add(0,0,1);
    
    cout << xdim << " x " << ydim << " has no " << cdim << "-coloring." << endl;
    cin >> mx; //to prevent window closing
    return 0;
}