rendered paste body#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#define ROWS 9#define COLUMNS 9bool map[ROWS][COLUMNS] = {0};int sum_of_cops = 0;int debug = 0;int counter = 0;bool check_if_valid(int row, int column){ int sum, i; sum = 0; // more than 2 cops on the road? for (i=0; i<COLUMNS; i++) { sum += map[row][i]; } if (sum > 2) { if (debug == 1) { printf("ERROR: row #%d has more than 2 cops!\n", row); } return false; } sum = 0; for (i=0; i<ROWS; i++) { sum += map[i][column]; } if (sum > 2) { if (debug == 1) { printf("ERROR: column #%d has more than 2 cops!\n", column); } return false; } sum = 0; // is cop 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 not 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; 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 column){ counter++; if (map[row][column] == 1) { if (row == ROWS-1 && column == COLUMNS-1) { map[row][column] = 0; sum_of_cops -= 1; return false; } else if ( row < ROWS && column == COLUMNS-1) { try(row+1, 0); map[row][column] = 0; sum_of_cops -= 1; } else { try(row, column+1); map[row][column] = 0; sum_of_cops -= 1; } return false; } map[row][column] = 1; //print_map(); if (!check_if_valid(row, column)) { map[row][column] = 0; if (row == ROWS-1 && column == COLUMNS-1) { map[row][column] = 0; sum_of_cops -= 1; return false; } else if ( row < ROWS && column == COLUMNS-1) { try(row+1, 0); map[row][column] = 0; sum_of_cops -= 1; } else { try(row, column+1); map[row][column] = 0; sum_of_cops -= 1; } } else { sum_of_cops += 1; if (sum_of_cops == 18) { if (check_for_success() == 1) { print_map(); map[row][column] = 0; sum_of_cops -= 1; return true; } else { map[row][column] = 0; sum_of_cops -= 1; return false; } } else { if (row == ROWS-1 && column == COLUMNS-1) { map[row][column] = 0; sum_of_cops -= 1; return false; } else if ( row < ROWS && column == COLUMNS-1) { try(row+1, 0); map[row][column] = 0; sum_of_cops -= 1; } else { try(row, column+1); map[row][column] = 0; sum_of_cops -= 1; } } } 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; for (i=0; i<ROWS; i++) { for (j=0; j<COLUMNS; j++) { if (debug == 1) { printf("hi there!\n"); } try(i,j); } } printf("counter: %d\n", counter); return 0;}