http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx
Всего задач 5.
Здесь опубликую решение первой из них.
Решение выполнено на MATLAB.
Вот она.
«В этой головоломке необходимо заштриховывать клетки — каждая из клеток на поле должна быть либо черной, либо белой. Несколько черных клеток уже закрашены за вас. Каждая колонка и каждый ряд имеют рядом с собой последовательность цифр. Цифры определяют длину цепочек черных клеток в ряду и расположены в том порядке, в котором размещаются эти цепочки. К примеру, последовательность «2 1 6» означает, что в ряду содержится три цепочки черных клеток разной длины — в две, одну и шесть клеток соответственно, разделенные между собой как минимум одной белой клеткой».
Это обычный японский кроссворд.
Сразу же видим, что горизонтали 7 и 22 могут быть построены только одним способом.
Поэтому в загадке закрашенные клетки на 22 горизонтали совершенно избыточны.
Алгоритмы решения япоских кроссвордов известны, но они подходят для решения человеком и относительно сложны для реализации на компьютере.
Я сделал по другому.
Вот решение (обе картинки повёрнуты на 90 градусов против часовой стрелки).
Если взять финальный кадр, изменить палитру на чёрно-белую, то получается вот что:
Скормив картинку распознавателю QR-кодов получаем текст
Тип кода: QRCODE
Данные: www.gchq.gov.uk/puzz
Есть два наблюдения по решению:
1) На картинке есть несколько нераспознанных клеток. По заданным условиям невозможно определить, они должны быть закрашены или нет. Но распознаватель QR-кодов, используя коррекцию ошибок, пропускает эти неясности и всё равно формирует правильный ответ.
2) Если исходные условия (изначально закрашенные клетки) не указывать алгоритму — результат получается такой-же.
Мой алгоритм работает так:
Фаза 1: Для каждой горизонтали и для каждой вертикали формируется список всех возможных вариантов расположения клеток, которые бы удовлетворяли условиям.
Дальше выполнение итерационное. Забегая вперёд скажу, что это 6 итераций.
Фаза 2:
Берём первую строку, смотрим, какие клетки заполнены во всех вариантах, которые мы получили на фазе 1 для первой строки.
Проставляем эти клетки на поле и отбрасываем из списка вариантов вертикалей те вертикали, у которых на первой позиции (пересечение с первой горизонталью) нет заполненной клетки.
Список вариантов для всех вертикалей сокращается.
Выполняем ту же операцию, но не по отношению к клеткам, а к пропускам. Опять прореживаем список вариантов вертикалей.
Выполняем эти два шага для всех 25 горизонталей.
Предпринимаем те-же шаги, но для вертикалей.
И опять возвращаемся к началу фазы 2. При обработки вертикалей какие-то варианты горизонталей уже были отброшены, и у нас опять появились клетки, которые гарантированно заполнены во всех вариантах горизонталей
Повторяем фазу 2 итерационно несколько раз.
В какой то момент окажется, что за всю итерацию фазы 2 не было найдено ни одной новой заполненной клетки или нового пропуска.
Это и есть окончание алгоритма.
Ссылки
http://ain.ua/2015/12/13/621338
http://42.tut.by/476694
http://veselka.mobi/06nov13/news1.html
Тексты: 2 файла, первый генерирует файл со списком вариантов (на моём компьютере — полторы минуты), второй — решает (мгновенно)
FillVariants.m
function FillVariants
clear all
clear global
global SquareDim;
MaskHoriz = int8([]);
MaskVerti = int8([]);
SquareDim = 25;
%%%%%%%%%%%%%%%%%%%%%%%
D.seq = [7 3 1 1 7 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 1 2 2 1 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 3 1 3 1 1 3 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 3 1 1 6 1 3 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 3 1 5 2 1 3 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 1 2 1 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [7 1 1 1 1 1 7 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [3 3 ]; MaskHoriz = vertcat
(MaskHoriz, D);
D.seq = [1 2 3 1 1 3 1 1 2]; MaskHoriz =
vertcat (MaskHoriz, D);
D.seq = [1 1 3 2 1 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [4 1 4 2 1 2 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 1 1 1 1 4 1 3 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [2 1 1 1 2 5 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [3 2 2 6 3 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 9 1 1 2 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [2 1 2 2 3 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [3 1 1 1 1 5 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 2 2 5 ]; MaskHoriz = vertcat (MaskHoriz,
D);
D.seq = [7 1 2 1 1 1 3 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 1 2 1 2 2 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 3 1 4 5 1 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 3 1 3 10 2 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 3 1 1 6 6 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [1 1 2 1 1 2 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [7 2 1 2 5 ]; MaskHoriz = vertcat (MaskHoriz, D);
D.seq = [7 2 1 1 7 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 1 2 2 1 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 3 1 3 1 3 1 3 1]; MaskVerti =
vertcat (MaskVerti, D);
D.seq = [1 3 1 1 5 1 3 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 3 1 1 4 1 3 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 1 1 2 1 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [7 1 1 1 1 1 7 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 1 3 ]; MaskVerti = vertcat (MaskVerti,
D);
D.seq = [2 1 2 1 8 2 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [2 2 1 2 1 1 1 2 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 7 3 2 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 2 3 1 1 1 1 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [4 1 1 2 6 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [3 3 1 1 1 3 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 2 5 2 2 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [2 2 1 1 1 1 1 2 1]; MaskVerti =
vertcat (MaskVerti, D);
D.seq = [1 3 3 2 1 8 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [6 2 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [7 1 4 1 1 3 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 1 1 1 4 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 3 1 3 7 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 3 1 1 1 2 1 1 4]; MaskVerti =
vertcat (MaskVerti, D);
D.seq = [1 3 1 4 3 3 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [1 1 2 2 2 6 1 ]; MaskVerti = vertcat (MaskVerti, D);
D.seq = [7 1 3 2 1 1 ]; MaskVerti = vertcat (MaskVerti, D);
for i = 1 : SquareDim
for j = 1 : length (MaskHoriz(i).seq)
if (j == 1) MaskHoriz(i).seq2(j * 2 - 1) =
0;
else
MaskHoriz(i).seq2(j * 2 - 1) = 1;
end;
MaskHoriz(i).seq2(j * 2 ) = MaskHoriz(i).seq(j);
end;
for j = 1 : length (MaskVerti(i).seq)
if (j == 1) MaskVerti(i).seq2(j * 2 - 1) =
0;
else
MaskVerti(i).seq2(j * 2 - 1) = 1;
end;
MaskVerti(i).seq2(j * 2 ) = MaskVerti(i).seq(j);
end;
end;
%%%%
AvailVariantsHoriz = int8([]);
AvailVariantsVerti = int8([]);
for i = 1 : SquareDim
t.data = int8 (AvailVariantNext ([], i,
MaskHoriz(i).seq2, [], 1));
AvailVariantsHoriz = vertcat
(AvailVariantsHoriz, t);
[s, ~] = size (t.data);
disp (sprintf ('Обработка
горизонтали %d, построено вариантов %d', i, s));
t.data = int8 (AvailVariantNext ([], i,
MaskVerti(i).seq2, [], 1));
AvailVariantsVerti = vertcat
(AvailVariantsVerti, t);
[s, ~] = size (t.data);
disp (sprintf ('Обработка
вертикали %d, построено вариантов %d', i, s));
end;
%%%
save variants.dat AvailVariantsHoriz AvailVariantsVerti SquareDim
end %
FillVariants
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function AvailVariants = AvailVariantNext ...
(AvailVariants, LineNo,
LineMask, CurrentLine, StartHole)
global SquareDim;
SegmentQuantity = length
(LineMask) / 2;
for i = StartHole : SegmentQuantity % количество сегментов
while (sum (LineMask) <= SquareDim)
if (i <
SegmentQuantity) % не последняя дырка
AvailVariants =
AvailVariantNext (AvailVariants, LineNo, LineMask, CurrentLine, i + 1);
else
r = ConvertLine
(SegmentQuantity, LineMask, SquareDim);
AvailVariants =
vertcat (AvailVariants, r);
end;
LineMask (i * 2 - 1) =
LineMask (i * 2 - 1) + 1;
end;
end;
end % AvailVariantNext
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function ret =
ConvertLine (SegmentQuantity, InputLine, SquareDim);
ret (1:SquareDim) = 0;
m = 1;
for k = 1 : SegmentQuantity * 2
mStop = (m + InputLine (k) - 1);
if mod (k, 2) == 0
ret (m : mStop) = 1;
end;
m = m + InputLine (k);
end;
end % ConvertLine
RunProc.m
function RunProc
clear all
clear global
global Handle0 Handle1 Handle2;
global Color0 Color1 Color2
Color0 = [0.8; 0.8; 0.8];
Color1 = [0.5; 0.5; 1.0];
Color2 = [0.0; 1.0; 0.0];
load ('variants.dat', '-mat');
SquareField (1:SquareDim, 1:SquareDim) =
-1;
% Заданные заполненные клетки
% Можно закомментировать --
результат не меняется
SquareField (4, 4:5) = 2;
SquareField (4, 13:14) = 2;
SquareField (4, 22) = 2;
SquareField (9, 7:8) = 2;
SquareField (9, 11) = 2;
SquareField (9, 15:16) = 2;
SquareField (9, 19) = 2;
SquareField (17, 7) = 2;
SquareField (17, 12) = 2;
SquareField (17, 17) = 2;
SquareField (17, 21) = 2;
SquareField (22, 4:5) = 2;
SquareField (22, 10:11) = 2;
SquareField (22, 16) = 2;
SquareField (22, 21:22) = 2;
PlotSize = 100;
hold off
[x, y] = find (SquareField == 0);
c = (Color0 * linspace (1, 1, length
(x)))';
Handle0 = scatter (x, y, PlotSize, c, 's');
axis ([0 SquareDim + 1 0 SquareDim + 1]);
xlabel 'Горизонтали'
ylabel 'Вертикали'
hold on
[x, y] = find (SquareField == 1);
c = (Color1 * linspace (1, 1, length
(x)))';
Handle1 = scatter (x, y, PlotSize, c, 'filled', 's');
axis ([0 SquareDim + 1 0 SquareDim + 1]);
[x, y] = find (SquareField == 2);
c = (Color2 * linspace (1, 1 , length
(x)))';
Handle2 = scatter (x, y, PlotSize, c, 'filled', 's');
axis ([0 SquareDim + 1 0 SquareDim + 1]);
pause (0.001)
pos = get (gcf, 'Position');
width = pos (3); height = pos(4);
mov = zeros (height, width, 1, 1, 'uint8');
set (Handle1, 'XData', 1, 'YData', 1, 'CData', Color1');
f = getframe (gcf);
imindex = 1;
[mov(:, :, 1, imindex),
map]=rgb2ind(f.cdata, 256);
set (Handle1, 'XData', [-1], 'YData', [-1], 'CData', Color1');
f = getframe (gcf);
for i = 1:2 mov(:, :, 1,
imindex)=rgb2ind(f.cdata, map); imindex = imindex + 1; end;
%%%%%
i = 1;
while 1 == 1
disp (sprintf ('НОВАЯ
ИТЕРАЦИЯ %d -- ПРОРЕЖИВАНИЕ ГОРИЗОНТАЛЕЙ\\ВЕРТИКАЛЕЙ', i));
disp (' ');
PlotSetted = 0;
pause (0.5);
[SquareField, AvailVariantsVerti,
PlotSettedTemp] = Thinning (SquareDim, AvailVariantsHoriz, AvailVariantsVerti,
SquareField, 'H', PlotSetted);
PlotSetted = PlotSetted +
PlotSettedTemp;
DrawGraph(SquareField);
f = getframe (gcf);
mov (:, :, 1, imindex) = rgb2ind (f.cdata, map); imindex =
imindex + 1;
pause (0.5);
[SquareField, AvailVariantsHoriz,
PlotSettedTemp] = Thinning (SquareDim, AvailVariantsVerti, AvailVariantsHoriz,
SquareField, 'V', PlotSetted);
PlotSetted = PlotSetted +
PlotSettedTemp;
DrawGraph(SquareField);
f = getframe (gcf);
mov (:, :, 1, imindex) = rgb2ind (f.cdata, map); imindex =
imindex + 1;
disp (' ');
if PlotSetted ~= 0
disp (sprintf ('Ячеек
заполнено (пусто-не пусто) -- %d', PlotSetted));
disp (' ');
disp (' ');
else
disp ('За итерацию
ничего нового не заполнено -- алгоритм завершён');
for b = 1:5 mov (:, :, 1, imindex) =
rgb2ind (f.cdata, map); imindex = imindex + 1; end;
break;
end;
i = i + 1;
end;
imwrite (mov, map, 'animation.gif', 'DelayTime', 0.5, 'LoopCount', inf);
end % RunProc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function DrawGraph
(SquareField)
global Handle0 Handle1;
global Color0 Color1;
[x, y] = find (SquareField (:, :) == 0);
c = (Color0 * linspace (1, 1, length
(x)))';
set (Handle0, 'XData', x, 'YData', y, 'CData', c);
[x, y] = find (SquareField (:, :) == 1);
c = (Color1 * linspace (1, 1, length
(x)))';
set (Handle1, 'XData', x, 'YData', y, 'CData', c);
pause (0.001)
end % DrawGraph
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [SquareField,
Target, PlotSetted] = Thinning (SquareDim, Source, Target, SquareField, Dir,
PlotSetted)
for i = 1 : SquareDim
if (Dir == 'H') disp (sprintf
('Обрабатываем
горизонталь № %d', [i]));
else disp (sprintf ('Обрабатываем
вертикаль № %d', [i])); end;
[VariantCount, ~] = size
(Source(i).data);
Freq = sum (Source(i).data, 1);
% Клетки, которые всегда заполнены
SolidFilledCells = find (Freq ==
VariantCount);
if Dir == 'H' AlreadyFilledCells = find (sign
(SquareField (i, :)) == 1);
else AlreadyFilledCells = find (sign
(SquareField (:, i)) == 1);
end;
SolidFilledCells = setdiff
(SolidFilledCells, AlreadyFilledCells);
if Dir == 'H' SquareField (i, SolidFilledCells) = 1;
else
SquareField (SolidFilledCells, i) = 1;
end;
PlotSetted =
PlotSetted + length (SolidFilledCells);
disp (sprintf (' Установлено %d гарантированно заполненных
клеток', length (SolidFilledCells)));
for j = 1 : length
(SolidFilledCells)
LinesForDel = find
(Target(SolidFilledCells(j)).data (:, i) == 0);
Target(SolidFilledCells(j)).data(LinesForDel, :) = [];
end;
% Клетки, которые всегда пусты
SolidEmptiedCells = find (Freq == 0);
if Dir == 'H'
AlreadyEmptiedCells = find (SquareField (i, :) == 0);
else
AlreadyEmptiedCells = find (SquareField (:, i) == 0);
end;
SolidEmptiedCells = setdiff
(SolidEmptiedCells, AlreadyEmptiedCells);
if Dir == 'H' SquareField (i,
SolidEmptiedCells) = 0;
else
SquareField (SolidEmptiedCells, i) = 0;
end;
PlotSetted = PlotSetted + length
(SolidEmptiedCells);
disp (sprintf (' Установлено %d гарантированно пустых
клеток', length (SolidEmptiedCells)));
for j = 1 : length (SolidEmptiedCells)
LinesForDel = find (Target(SolidEmptiedCells(j)).data
(:, i) ~= 0);
Target(SolidEmptiedCells(j)).data(LinesForDel, :) = [];
end;
end;
end
