Rozbicie macierzy na dwie

Witam
Piszę program rozwiązujący problem transportowy algorytmem genetycznym.
Problem na jaki się natknąłem występuje przy krzyżowaniu rodziców. Otóż podążam za książką algorytmy genetyczne + struktury danych = programy ewolucyjne Zbigniewa Michalewicza. Mamy macierz (tam jest nazwana REM), która składa się z 0 i 1 oraz w każdym wierszu i kolumnie posiada parzystą liczbę jedynek. Musimy ją rozbić na 2 macierze tych samych rozmiarów (REM1, REM2), gdzie REM = REM1 + REM2 i liczba jedynek w wierszach i kolumnach REM1 i REM2 jest taka sama i równa połowie ilości jedynek w odpowiadających wierszach i kolumnach REM.
Dla przykładu

REM
1 0 1 1 1
0 0 0 0 0
0 1 1 1 1
1 1 0 0 0

REM1
0 0 1 0 1
0 0 0 0 0
0 1 0 1 0
1 0 0 0 0

REM2
1 0 0 1 0
0 0 0 0 0
0 0 1 0 1
0 1 0 0 0

Siedzę już drugi dzień próbując rozgryźć ten algorytm, jednak za każdym razem jak coś wymyślę pojawia się kolejny przypadek, który niszczy cały mój dotychczasowy tok myślenia.
Ma ktoś może pomysł na to, bądź rozwiązywał kiedyś ten lub podobny problem?

użyj operatora XOR wynik też będzie mieć parzystą liczbę jedynek.

mógłbyś trochę to rozwinąć?

wiem co to jest XOR, ale nie wiem jak to się ma do problemu
mam rozbić macierz na dwie, a nie dodać dwie macierze w jedną

a poza tym, posługując się znowu tym przykładem z pierwszego postu dwie takie macierze na przykład po xorze też dają tą pierwszą macierz, a to nie jest dobre rozwiązanie

REM1
1 0 1 1 1
0 0 0 0 0
0 0 0 0 0
1 1 0 0 0

REM2
0 0 0 0 0
0 0 0 0 0
0 1 1 1 1
0 0 0 0 0

@wojtasjz jaka jest treść zadania (oryginalna z tej książki wrzuć może jakiś skan)??

Wszystko inne mi już działa poza właśnie rozbijaniem tej nieszczęsnej macierzy

swoją drogą można do rozwiązania wykorzystać http://pl.wikipedia.org/wiki/Kolorowanie_grafu
jako wierzchołki grafu bierzesz wszystkie jedynki a jako krawędzie bierzesz sąsiednie jedynki (w pionie i poziomie)

podejrzeważ że dla tego specyficznego przypadku można to zrobić prościej, ale jakbyś nic nie znalazł to zawsze można to zrobić tak jak napisałem

@wojtasjz na skanie 1 masz opis jak tworzone są macierze REM...

kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru.

tu też pojawia się problem, bo w niektórych przypadkach sąsiednie jedynki mogą znaleźć się w jednej macierzy

nemomemo napisał(a):

@wojtasjz na skanie 1 masz opis jak tworzone są macierze REM...

jest opis jak tworzona jest główna macierz REM i z tym nie mam problemu

udało mi się, a raczej mojemu bratu, rozwiązać już to, temat do zamknięcia.
jakby ktoś chciał kod to PW