10 мар. 2010 г.

Задачка: Груши

В ящике 4 x 4 лежат груши (16 шт.)

Какие 6 груш необходимо убрать, так, чтобы в каждой строке и каждом столбце было чётное число груш.


внимание! комментарии содержат ответ.

9 комментариев:

Andrey комментирует...

"Какие 6 груш необходимо ..."

rmst комментирует...
Этот комментарий был удален автором.
rmst комментирует...
Этот комментарий был удален автором.
rmst комментирует...

1111
1100
1010
1001

xonix комментирует...

:-use_module(library(clpfd)).

solve(GG) :-
GG = [
[A,B,C,D],
[E,F,G,H],
[I,J,K,L],
[M,N,O,P]
],
append(GG, Vars),
Vars ins 0..1,

sum(Vars,#=,10),

( A + B + C + D) mod 2 #= 0,
( E + F + G + H) mod 2 #= 0,
( I + J + K + L) mod 2 #= 0,
( M + N + O + P) mod 2 #= 0,

( A + E + I + M) mod 2 #= 0,
( B + F + J + N) mod 2 #= 0,
( C + G + K + O) mod 2 #= 0,
( D + H + L + P) mod 2 #= 0,

label(Vars).

solve :- forall(solve(GG),format('~n~w~n~w~n~w~n~w~n-------',GG)).

[0, 0, 1, 1]
[0, 1, 0, 1]
[1, 0, 0, 1]
[1, 1, 1, 1]
-------
[0, 0, 1, 1]
[0, 1, 0, 1]
[1, 1, 1, 1]
[1, 0, 0, 1]
-------
[0, 0, 1, 1]
[0, 1, 1, 0]
[1, 0, 1, 0]
[1, 1, 1, 1]
-------
[0, 0, 1, 1]
[0, 1, 1, 0]
[1, 1, 1, 1]
[1, 0, 1, 0]
-------
[0, 0, 1, 1]
[1, 0, 0, 1]
[0, 1, 0, 1]
[1, 1, 1, 1]
-------
[0, 0, 1, 1]
[1, 0, 0, 1]
[1, 1, 1, 1]
[0, 1, 0, 1]
-------
[0, 0, 1, 1]
[1, 0, 1, 0]
[0, 1, 1, 0]
[1, 1, 1, 1]
-------
[0, 0, 1, 1]
[1, 0, 1, 0]
[1, 1, 1, 1]
[0, 1, 1, 0]
-------
[0, 0, 1, 1]
[1, 1, 1, 1]
[0, 1, 0, 1]
[1, 0, 0, 1]

... (и т.д.)

Владимир Долженко комментирует...

@Andrey:
спасибо за корректировку

@xonix
bravo! физтех :)

Александр комментирует...

@xonix: А что это за язык? Красиво выражает задачу.

У меня тут топорный брут-форс на С, но задачу решает, хотя и не столь изящно.

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

int b[16];

int f() {
  int a;
  if (b[0] + b[1] + b[2] + b[3] + b[4] + b[5] + b[6] + b[7] +
      b[8] + b[9] + b[10] + b[11] + b[12] + b[13] + b[14] + b[15] != 10)
    return 0;
  a = b[0] + b[1] + b[2] + b[3]; if (a & 1) return 0;
  a = b[4] + b[5] + b[6] + b[7]; if (a & 1) return 0;
  a = b[8] + b[9] + b[10] + b[11]; if (a & 1) return 0;
  a = b[12] + b[13] + b[14] + b[15]; if (a & 1) return 0;
  a = b[0] + b[4] + b[8] + b[12]; if (a & 1) return 0;
  a = b[1] + b[5] + b[9] + b[13]; if (a & 1) return 0;
  a = b[2] + b[6] + b[10] + b[14]; if (a & 1) return 0;
  a = b[3] + b[7] + b[11] + b[15]; if (a & 1) return 0;
  return 1;
}

int main() {
  int i;
  int c = 0;
  for (i = 0; i < 16; ++i) b[1];
  for (i = 0; i < (1 << 16); ++i) {
    int j;
    for (j = 0; j < 16; ++j) b[j] = (i & (1 << j)) ? 1 : 0;
    if (f()) {
      int j;
      printf("#%d:\n", ++c);
      for (j = 0; j < 16; ++j) {
        printf("%d ", b[j]);
        if ((j & 0x03) == 0x03) printf("\n");
      }
      printf("\n");
    }
  }
  return 0;
}

Владимир Долженко комментирует...

@Александр

судя по блогу xonix'а это пролог - но, могу и ошибаться

xonix комментирует...

@Владимир Долженко

Именно так =)