else for i:=1 to 4 do

if A[x+dx[i],y+dy[i]]=0 then Solve(x+dx[i],y+dy[i],k+1);

A[x,y]:=0;

end;

begin

Init;

Solve(xn,yn,1);

end.

4. Задача о парламенте

На острове Новой Демократии каждый из жителей организовал партию, которую сам и возглавил. Ко всеобщему удивлению, даже в самой малочисленной партии оказалось не менее двух человек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предполагалось по Конституции острова, президенты всех партий.

Посовещавшись, островитяне решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии.

Помогите островитянам организовать такой, как можно более малочисленный парламент, в котором будут представлены члены всех партий.

Исходные данные: каждая партия и ее президент имеют один и тот же порядковый номер от 1 до N (4£N£150). Вам даны списки всех N партий острова Новой Демократии. Выведите предлагаемый Вами парламент в виде списка номеров ее членов. Например, для четырех партий:

Президенты	Члены партий
1	2,3,4
2	3
3	1,4,2
4	2

Список членов парламента 2 (состоит из одного члена).

Задача относится к классу NP-полных задач. Ее решение - полный перебор всех вариантов. Покажем, что ряд эвристик позволяет сократить перебор для некоторых наборов исходных данных.

Представим информацию о партиях и их членах с помощью следующего зрительного образа - таблицы. Для примера из формулировки задачи она имеет вид:

Тогда задачу можно переформулировать следующим образом. Найти минимальное число столбцов, таких, что множество единиц из них “покрывают” множество всех строк. Очевидно, что для примера это один столбец - второй. Поговорим о структурах данных.

Const Nmax=150;

Type Nint=0..Nmax+1;

Sset=Set of 0..Nmax;

Person=record

man:Nint;{номержителя}

number:Nint;{число партий, которые он представляет}

part:Sset;{партии}

end;

Var A:array[Nint] of Person;

Логика формирования исходных данных (фрагмент реализации).

function Num(S:Sset):Nint;{подсчитывает количество элементов в множестве}

var i,ch:Nint;

begin ch:=0;