fork download
copy 
  1.  
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4.  
  5. #define S 7
  6. #define M 4
  7. #define N (S*S) / M
  8.  
  9. int cell(int grid[S][S], int x, int y)
  10. {
  11.     if (x < 0 || x >= S) return 0;
  12.     if (y < 0 || y >= S) return 0;
  13.  
  14.     return grid[y][x];
  15. }
  16.  
  17. int solve(int *repo, int grid[S][S], int x, int y)
  18. {
  19.     if (y == S) {  
  20.         int i, j;
  21.  
  22.         for (i = 0; i < 7; i++) {
  23.             for (j = 0; j < 7; j++) {
  24.                 //putchar(".RGYB"[grid[j][i]]);
  25.                 //putchar(".RGYB"[grid[j][i]]);
  26.                 putchar(" XO-["[grid[j][i]]);
  27.                 putchar(" XO-]"[grid[j][i]]);
  28.             }
  29.             putchar(10);
  30.         }
  31.         putchar(10);
  32.  
  33.         return 1;
  34.     } else {
  35.         int nextx = x + 1;
  36.         int nexty = y;
  37.         int res = 0;
  38.         int i;
  39.  
  40.         if (nextx == 7) {
  41.             nextx = 0;
  42.             nexty++;
  43.         }
  44.  
  45.         //Seeded part of the grid - see comments in main()
  46.         if((x < 2) && (y < 2)) {
  47.             res += solve(repo, grid, nextx, nexty);
  48.         }
  49.         else {
  50. 	        for (i = 0; i < M + 1; i++) {
  51. 	            if (repo[i] == 0) continue;
  52. 	            if (i && cell(grid, x - 1, y - 1) == i) continue;
  53. 	            if (i && cell(grid, x + 0, y - 1) == i) continue;
  54. 	            if (i && cell(grid, x + 1, y - 1) == i) continue;
  55. 	            if (i && cell(grid, x - 1, y + 0) == i) continue;
  56.  
  57. 	            grid[y][x] = i;
  58. 	            repo[i]--;
  59.  
  60. 	            res += solve(repo, grid, nextx, nexty);
  61.  
  62. 	            grid[y][x] = 0;
  63. 	            repo[i]++;
  64. 	        }
  65.         }
  66.  
  67.         return res;
  68.     }
  69. }
  70.  
  71. //http://p...content-available-to-author-only...e.com/a/44681/13148
  72. int main()
  73. {
  74.     int repo[M + 1] = {1, N, N, N, N};
  75.     int grid[S][S] = {{0}};
  76.     int n;
  77.  
  78.     //n = solve(repo, grid, 0, 0);
  79.  
  80.     //Seed the grid to reduce color permutations and rotations/reflections:
  81.     // - There is only one empty cell, so at least three grid corners must be full of prisoners
  82.     // - Let's rotate the grid so that the top left corner is one of those corners
  83.     // - The upper left 2x2 cells must contain all 4 groups (colors) so no groups are in adjacent cells
  84.     grid[0][0] = 1;
  85.     grid[0][1] = 2;
  86.     grid[1][0] = 3;
  87.     grid[1][1] = 4;
  88.     repo[1]--;
  89.     repo[2]--;
  90.     repo[3]--;
  91.     repo[4]--;
  92.     n = solve(repo, grid, 2, 0);
  93.  
  94.     printf("%d cells, %d groups of %d prisoners: %d\n", S*S, M, N, n);
  95.  
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0s 2168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
XX--XX[]OO[]OO
OO[]OO--XX--XX
XX--XX[]OO[]OO
OO[]OO  --XX--
--XX--XX[]OO[]
[]OO[]OO--XX--
--XX--XX[]OO[]

XX--XX--OO[]OO
OO[]OO[]XX--XX
XX--XX--OO[]OO
[]OO[]  XX--XX
--XX--OO[]OO[]
[]OO[]XX--XX--
--XX--OO[]OO[]

49 cells, 4 groups of 12 prisoners: 2
https://ideone.com/B0MHvd
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!