#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ROWS 9
#define COLUMNS 9

bool map[ROWS][COLUMNS] = {0};

//int debug = 0;

bool check_if_valid(int row, int column)
{
    int sum, i;
    sum = 0;

    // would there be more than 2 cops on the road?

    for (i=0; i<COLUMNS; i++)
    {
        sum += map[row][i];
    }
    if (sum > 1)
    {
//        if (debug == 1)
//        {
//            printf("ERROR: row #%d would have more than 2 cops!\n", row);
//        }
        return false;
    }
    sum = 0;

    for (i=0; i<ROWS; i++)
    {
        sum += map[i][column];
    }
    if (sum > 1)
    {
//        if (debug == 1)
//        {
//            printf("ERROR: column #%d would have more than 2 cops!\n", column);
//        }
        return false;
    }
    sum = 0;

    // would cop be lonely?

    if (row == 0) // top
    {
       if (column == 0) // top left
                        // will never get checked, as a cop is already at this position
       {
           sum =
                                                             map[row][column+1]
                                      + map[row+1][column] + map[row+1][column+1];
       }
       else if (column < COLUMNS-1) // top
       {
           sum =
                 map[row][column-1]                        + map[row][column+1]
               + map[row+1][column-1] + map[row+1][column] + map[row+1][column+1];
       }
       else if (column == COLUMNS-1) // top right
       {
           sum =
                 map[row][column-1]
               + map[row+1][column-1] + map[row+1][column];
       }
    }
    else if (row < ROWS-1) // middle rows
    {
       if (column == 0) // left
       {
           sum =                        map[row-1][column] + map[row-1][column+1]
                                                           + map[row][column+1]
                                      + map[row+1][column] + map[row+1][column+1];
       }
       else if (column < COLUMNS-1) // no border
       {
           sum = map[row-1][column-1] + map[row-1][column] + map[row-1][column+1]
               + map[row][column-1]                        + map[row][column+1]
               + map[row+1][column-1] + map[row+1][column] + map[row+1][column+1];
       }
       else if (column == COLUMNS-1) // right
       {
           sum = map[row-1][column-1] + map[row-1][column]
               + map[row][column-1]
               + map[row+1][column-1] + map[row+1][column];
       }
    }
    else if (row == ROWS-1) // bottom
    {
       if (column == 0) // bottom left
       {
           sum =                        map[row-1][column] + map[row-1][column+1]
                                                           + map[row][column+1]
               ;
       }
       else if (column < COLUMNS-1) // bottom
       {
           sum = map[row-1][column-1] + map[row-1][column] + map[row-1][column+1]
               + map[row][column-1]                        + map[row][column+1]
               ;
       }
       else if (column == COLUMNS-1) // bottom right
       {
           sum = map[row-1][column-1] + map[row-1][column]
               + map[row][column-1]
               ;
       }
    }

    if (sum != 0)
    {
//        if (debug == 1)
//        {
//            printf("ERROR: cop in row #%d, column #%d would not be lonely!\n", row, column);
//        }
        return false;
    }

    return true;
}

bool check_for_success(void)
{
    int i,j
        , index_of_first_cop
        , index_of_second_cop
        , sum_of_streets_with_4_vacant_crossings = 0;

//  printf("CHECKING FOR SUCCESS...\n");

    // check horizontal streets

    for (j=0; j<ROWS; j++)
    {
        index_of_first_cop = -1;
        index_of_second_cop = -1;

        for (i=0; i<COLUMNS; i++)
        {
            if (index_of_first_cop == -1)
            {
                if (map[j][i] == 1)
                {
                    index_of_first_cop = i;
                }
            }
            else
            {
                if (map[j][i] == 1)
                {
                    index_of_second_cop = i;
                    break;
                    // there can't be a third cop, because check_if_valid would have objected then
                }
            }
        }
        // check if there are 2 cops
        if ((index_of_first_cop == -1) || (index_of_second_cop == -1))
        {
            return false;
        }
        // check for 4 vacant crossings
        if (index_of_second_cop - index_of_first_cop == 5)
        {
            sum_of_streets_with_4_vacant_crossings += 1;
            if (sum_of_streets_with_4_vacant_crossings > 3)
            {
                return false;
            }
        }
    }

    // check vertical streets

    for (i=0; i<COLUMNS; i++)
    {
        index_of_first_cop = -1;
        index_of_second_cop = -1;

        for (j=0; j<ROWS; j++)
        {
            if (index_of_first_cop == -1)
            {
                if (map[j][i] == 1)
                {
                    index_of_first_cop = j;
                }
            }
            else
            {
                if (map[j][i] == 1)
                {
                    index_of_second_cop = j;
                    break;
                    // there can't be a third cop, because check_if_valid would have objected then
                }
            }
        }
        // check if there are 2 cops
        if ((index_of_first_cop == -1) || (index_of_second_cop == -1))
        {
            return false;
        }
        // check for 4 vacant crossings
        if (index_of_second_cop - index_of_first_cop == 5)
        {
            sum_of_streets_with_4_vacant_crossings += 1;
            if (sum_of_streets_with_4_vacant_crossings > 3)
            {
                return false;
            }
        }
    }

    if (sum_of_streets_with_4_vacant_crossings != 3)
    {
        return false;
    }

    return true;
}

void print_map(void)
{
    int i,j;

    printf("\n");
    for (i=0; i<ROWS; i++)
    {
        for (j=0; j<COLUMNS; j++)
        {
            printf(" %d", map[i][j]);
        }
        printf("\n\n");
    }
}

bool try(int row, int level)
{
    int i,j;

//  printf("level: %d\n", level);
//  print_map();

    if (level==17)
    {
        if (check_for_success())
        {
            print_map();
//            return true;
            exit(0);
        }
        else
        {
            return false;
        }
    }

    for (i=row; i<ROWS; i++)
    {
        for (j=0; j<COLUMNS; j++)
        {
            if (map[i][j] == 1)
            {
                continue;
            }
            else
            {
                if (check_if_valid(i,j))
                {
                    map[i][j] = 1;
                    try(i,level+1);
                    map[i][j] = 0;
                }
            }
        }
    }

    return false;
}

int main(int argc, char *argv[])
{
    int i,j;

//    if (argc > 1)
//    {
//        debug = 1;
//    }

    // hardcoded cops
    map[0][0] = 1;
    map[4][3] = 1;

    try(0,1); 

    return 0;
}