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;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) { return false; } sum = 0; for (i=0; i<ROWS; i++) { sum = map[i][column]; } if (sum > 2) { 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] + 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) { 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; // 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){ if (map[row][column] == 1) { return false; } map[row][column] = 1; if (!check_if_valid(row, column)) { map[row][column] = 0; return false; } 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) { return false; } else if ( row < ROWS && column == COLUMNS-1) { try(row+1, 0); } else { try(row, column+1); } } }}int main(void){ int i,j; // hardcoded cops map[0][0] = 1; map[4][3] = 1; for (i=0; i<ROWS; i++) { for (j=0; j<COLUMNS; j++) { try(i,j); } } return 0;}