rendered paste body#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#define ROWS 9#define COLUMNS 9bool 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;}