Текст задачи:
На улице стоят пять домов. Англичанин живет в красном доме. У испанца есть собака. В зеленом доме пьют кофе. Украинец пьет чай. Зеленый дом стоит сразу справа от белого дома. Тот, кто курит Old Gold, разводит улиток. В желтом доме курят Kool. В центральном доме пьют молоко. Норвежец живет в первом доме. Сосед того, кто курит Chesterfield, держит лису. В доме по соседству с тем, в котором держат лошадь, курят Kool. Тот, кто курит Lucky Strike, пьет апельсиновый сок. Японец курит Parliament. Норвежец живет рядом с синим домом. Каждый из домов покрашен в отдельный цвет, в каждом доме живет представитель отдельной национальности, у каждого — свой питомец, своя любимая марка сигарет и напиток
Требуется:
Реализовать на 1с алгоритм выводящий возможный вариант расположения домов, цветов, национальностей, питомцев, напитков и марок сигарет.
Решение:
Предлагаемое решение основано рекурсивном просчитывании каждого варианта вглубь.
Т.е. предполагаем что в доме например живет Англичанин. Это рождает новую ветку решения. В этой ветке последовательно заполняем все пустые значения возможными вариантами и проверяем на условия. Каждый вариант рождает новую ветку решения.
Когда перебраны все варианты для ветки, проверяем правильность решения (заполненность всей таблицы и соответствие условиям). Если решение не найдено переходим к следующей ветке.
Сначала переведем текст задачи в набор условий. Набором будет ТаблицаЗначений. Прописываем только условия, явно указанные в тексте задачи. При этом результат условия должен быть уникален для всей таблицы.
Функция ПолучитьТаблицуУсловий()
//тип|значение ЕСЛИ ТипДом|ТипУсловия = ЗначениеУсловия
//Тип и Значение должны быть уникальны
ТаблицаУсловий = Новый ТаблицаЗначений;
ТаблицаУсловий.Колонки.Добавить("Тип");
ТаблицаУсловий.Колонки.Добавить("Значение");
ТаблицаУсловий.Колонки.Добавить("ТипДома");
ТаблицаУсловий.Колонки.Добавить("ТипУсловия");
ТаблицаУсловий.Колонки.Добавить("ЗначениеУсловия");
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "Национальность";
НовоеУсловие.Значение = "Англичанин";
НовоеУсловие.ТипДома = "текущий";
НовоеУсловие.ТипУсловия = "Цвет";
НовоеУсловие.ЗначениеУсловия = "Красный";
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "Национальность";
НовоеУсловие.Значение = "Испанец";
НовоеУсловие.ТипДома = "текущий";
НовоеУсловие.ТипУсловия = "Питомец";
НовоеУсловие.ЗначениеУсловия = "Собака";
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "Цвет";
НовоеУсловие.Значение = "Зеленый";
НовоеУсловие.ТипДома = "текущий";
НовоеУсловие.ТипУсловия = "Напиток";
НовоеУсловие.ЗначениеУсловия = "Кофе";
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "Национальность";
НовоеУсловие.Значение = "Украинец";
НовоеУсловие.ТипДома = "текущий";
НовоеУсловие.ТипУсловия = "Напиток";
НовоеУсловие.ЗначениеУсловия = "Чай";
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "Цвет";
НовоеУсловие.Значение = "Белый";
НовоеУсловие.ТипДома = "справа";
НовоеУсловие.ТипУсловия = "Цвет";
НовоеУсловие.ЗначениеУсловия = "Зеленый";
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "МаркаСигарет";
НовоеУсловие.Значение = "OldGold";
НовоеУсловие.ТипДома = "текущий";
НовоеУсловие.ТипУсловия = "Питомец";
НовоеУсловие.ЗначениеУсловия = "Улитки";
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "МаркаСигарет";
НовоеУсловие.Значение = "Kool";
НовоеУсловие.ТипДома = "текущий";
НовоеУсловие.ТипУсловия = "Цвет";
НовоеУсловие.ЗначениеУсловия = "Желтый";
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "Питомец";
НовоеУсловие.Значение = "Лошадь";
НовоеУсловие.ТипДома = "соседний";
НовоеУсловие.ТипУсловия = "МаркаСигарет";
НовоеУсловие.ЗначениеУсловия = "Kool";
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "Питомец";
НовоеУсловие.Значение = "Лиса";
НовоеУсловие.ТипДома = "соседний";
НовоеУсловие.ТипУсловия = "МаркаСигарет";
НовоеУсловие.ЗначениеУсловия = "Chesterfield";
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "МаркаСигарет";
НовоеУсловие.Значение = "LuckyStrike";
НовоеУсловие.ТипДома = "текущий";
НовоеУсловие.ТипУсловия = "Напиток";
НовоеУсловие.ЗначениеУсловия = "Сок";
НовоеУсловие = ТаблицаУсловий.Добавить();
НовоеУсловие.Тип = "МаркаСигарет";
НовоеУсловие.Значение = "Parlament";
НовоеУсловие.ТипДома = "текущий";
НовоеУсловие.ТипУсловия = "Национальность";
НовоеУсловие.ЗначениеУсловия = "Японец";
возврат ТаблицаУсловий;
КонецФункции
Теперь создадим функцию, которая для строки таблицы условий ставит конкретное значение. Проверяем как прямое так и обратное условие. Например прямое: если дом = желтый, то сигареты = kool и обратное: если сигареты = kool, то дом = желтый.
Функция ВыполнитьУсловие(условие,ДомДляПроверкиУсловия,Дом)
Если ДомДляПроверкиУсловия = неопределено Тогда
возврат ложь;
КонецЕсли;
Если ДомДляПроверкиУсловия[условие.ТипУсловия] = условие.ЗначениеУсловия И ПустаяСтрока(Дом[условие.Тип]) Тогда
возврат УстановитьЗначение(Дом, условие.Тип, условие.Значение);
//и обратное
ИначеЕсли ДомДляПроверкиУсловия[условие.Тип] = условие.Значение И ПустаяСтрока(Дом[условие.ТипУсловия]) Тогда
возврат УстановитьЗначение(Дом, условие.ТипУсловия, условие.ЗначениеУсловия);
КонецЕсли;
возврат ложь;
КонецФункции
Далее создаем процедуру которая для текущего состояния решения определит все значения по таблице условий. После выполнения каждого условия опять вызываем рекурсивно процедуру определения значений. Например мы знаем, что "В доме по соседству с тем, в котором держат лошадь, курят Kool" и "В желтом доме курят Kool". Если мы в текущей итерации поставили сигареты = Kool, т.к. в соседнем доме лощадь, то мы сразу же должны и установить цвет в желтый.
//Проставляет зависимые значения по всем домам
Процедура ОпределитьЗначения(ТаблицаУсловий, ТекущаяТаблица)
Для каждого Дом из ТекущаяТаблица Цикл
ОпределитьЗначенияДома(ТаблицаУсловий,ТекущаяТаблица, Дом);
КонецЦикла;
КонецПроцедуры
//Проставляет зависимые значения для конкретного дома
Процедура ОпределитьЗначенияДома(ТаблицаУсловий, ТекущаяТаблица, Дом)
//после изменения любого реквизита заново пересчитываем всю таблицу
Для каждого условие из ТаблицаУсловий Цикл
Если условие.ТипДома = "текущий" Тогда
ДомДляПроверкиУсловия = Дом;
Если ВыполнитьУсловие(условие,ДомДляПроверкиУсловия,Дом) Тогда
ОпределитьЗначения(ТаблицаУсловий,ТекущаяТаблица);
КонецЕсли;
ИначеЕсли условие.ТипДома = "справа" Тогда
ДомДляПроверкиУсловия = СоседСправа(Дом);
Если ВыполнитьУсловие(условие,ДомДляПроверкиУсловия,Дом) Тогда
ОпределитьЗначения(ТаблицаУсловий,ТекущаяТаблица);
КонецЕсли;
ИначеЕсли условие.ТипДома = "слева" Тогда
ДомДляПроверкиУсловия = СоседСлева(Дом);
Если ВыполнитьУсловие(условие,ДомДляПроверкиУсловия,Дом) Тогда
ОпределитьЗначения(ТаблицаУсловий,ТекущаяТаблица);
КонецЕсли;
ИначеЕсли условие.ТипДома = "соседний" Тогда
ДомДляПроверкиУсловия = СоседСправа(Дом);
Если НЕ ВыполнитьУсловие(условие,ДомДляПроверкиУсловия,Дом) Тогда
ДомДляПроверкиУсловия = СоседСлева(Дом);
Если ВыполнитьУсловие(условие,ДомДляПроверкиУсловия,Дом) Тогда
ОпределитьЗначения(ТаблицаУсловий,ТекущаяТаблица);
КонецЕсли;
Иначе
ОпределитьЗначения(ТаблицаУсловий,ТекущаяТаблица);
КонецЕсли;
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Переходим непосредственно к перебору вариантов решения.
Алгоритм такой:
- Ставим очередное возможное значение для типа
- Проверяем по всей таблице решения не нарушились ли условия. Если условия не выполняются, то переходим к п.1.
- Определяем все зависимые значения во всей таблице решения.
- Переходим к следующему типу значений (Цвет, Животное и т.д.) и повторяем с п.1
- Когда перебрали все типы проверяем вся ли таблица решения заполнена и все ли условия выполнены. Если решение не найдено, то повторяем с п.1 опять для каждого типа
Процедура РешитьЗадачуНаСервере()
УстановитьНачальныеЗначения();
ТаблицаУсловий = ПолучитьТаблицуУсловий();
Если НЕ ТаблицаУсловийВерна(ТаблицаУсловий) Тогда
возврат;
КонецЕсли;
ТекущаяТаблица = Объект.Дома.Выгрузить();
Решение = НайтиРешение(ТаблицаУсловий,ТекущаяТаблица);
Если Решение = неопределено Тогда
Сообщить("Решения нет",СтатусСообщения.ОченьВажное);
Иначе
Объект.Дома.Загрузить(Решение);
Сообщить("Задача решена!");
КонецЕсли;
КонецПроцедуры
Функция НайтиРешение(ТаблицаУсловий,ТекущаяТаблица)
//каждое решение - отдельная таблица производная от текущей
Решение = ТекущаяТаблица.Скопировать();
ОпределитьЗначения(ТаблицаУсловий,Решение);
СтруктураВозможныхЗначений = ПолучитьСтруктуруВозможныхЗначений();
Для каждого Дом из Решение Цикл
//порядок вызова проверок может быть любой, на результат не влияет
ПроверитьВозможныеЗначения(ТаблицаУсловий, Дом, "Цвет", СтруктураВозможныхЗначений.Цвета);
ПроверитьВозможныеЗначения(ТаблицаУсловий, Дом, "Напиток", СтруктураВозможныхЗначений.Напитки);
ПроверитьВозможныеЗначения(ТаблицаУсловий, Дом, "Национальность", СтруктураВозможныхЗначений.Национальность);
ПроверитьВозможныеЗначения(ТаблицаУсловий, Дом, "Питомец", СтруктураВозможныхЗначений.Питомцы);
ПроверитьВозможныеЗначения(ТаблицаУсловий, Дом, "МаркаСигарет", СтруктураВозможныхЗначений.Сигареты);
КонецЦикла;
Если ПроверитьРешение(ТаблицаУсловий,Решение) Тогда
возврат Решение;
КонецЕсли;
возврат неопределено;
КонецФункции
//Перебирает возможные варианты значения и проверяет есть ли решение при данном значении
Процедура ПроверитьВозможныеЗначения(ТаблицаУсловий, Дом, Тип, МассивВозможныхЗначений)
Если НЕ ПустаяСтрока(Дом[Тип]) Тогда
возврат;
КонецЕсли;
Для каждого возможноеЗначение из МассивВозможныхЗначений Цикл
//если подошло, дальше не подставляем
Если ПроверитьГипотезу(ТаблицаУсловий, Дом, Тип, возможноеЗначение) Тогда
прервать;
КонецЕсли;
Конеццикла;
ОпределитьЗначения(ТаблицаУсловий, Дом.Владелец());
КонецПроцедуры
Код проверки гипотезы. Ставит значение и проверяет не нарушаются ли при этом условия задачи.
//Проверяет, будут ли истины уловия если мы установим значение
Функция ПроверитьГипотезу(ТаблицаУсловий, Дом, Тип, Значение)
//что будет если мы поставим такой тип
Если УстановитьЗначение(Дом, Тип, Значение) Тогда
Если НЕ ПроверитьВыполнениеУсловий(ТаблицаУсловий, Дом.Владелец()) Тогда
Дом[Тип] = "";
возврат Ложь;
КонецЕсли;
возврат Истина;
КонецЕсли;
возврат Ложь;
КонецФункции
Функция ПроверитьВыполнениеУсловий(ТаблицаУсловий, ТекущаяТаблица)
Для каждого Дом из ТекущаяТаблица Цикл
Если не ПроверитьДом(ТаблицаУсловий, Дом) Тогда
возврат Ложь;
КонецЕсли;
КонецЦикла;
возврат Истина;
КонецФункции
Функция ПроверитьДом(ТаблицаУсловий, Дом)
Для каждого условие из ТаблицаУсловий Цикл
Если условие.ТипДома = "текущий" Тогда
ДомДляПроверкиУсловия = Дом;
Если не ПроверитьУсловие(условие,ДомДляПроверкиУсловия, Дом) Тогда
возврат ложь;
КонецЕсли;
ИначеЕсли условие.ТипДома = "справа" Тогда
ДомДляПроверкиУсловия = СоседСправа(Дом);
Если не ПроверитьУсловие(условие,ДомДляПроверкиУсловия, Дом) Тогда
возврат ложь;
КонецЕсли;
ИначеЕсли условие.ТипДома = "слева" Тогда
ДомДляПроверкиУсловия = СоседСлева(Дом);
Если не ПроверитьУсловие(условие,ДомДляПроверкиУсловия, Дом) Тогда
возврат ложь;
КонецЕсли;
ИначеЕсли условие.ТипДома = "сосоедний" Тогда
ДомДляПроверкиУсловия = СоседСправа(Дом);
Если НЕ ПроверитьУсловие(условие,ДомДляПроверкиУсловия, Дом) Тогда
ДомДляПроверкиУсловия = СоседСлева(Дом);
Если не ПроверитьУсловие(условие,ДомДляПроверкиУсловия, Дом) Тогда
возврат ложь;
КонецЕсли;
КонецЕсли;
КонецЕсли;
КонецЦикла;
возврат Истина;
КонецФункции
Функция ПроверитьУсловие(условие, ДомДляПроверкиУсловия, Дом)
Если ДомДляПроверкиУсловия = неопределено
ИЛИ ПустаяСтрока(ДомДляПроверкиУсловия[условие.ТипУсловия])
ИЛИ ПустаяСтрока(Дом[условие.Тип]) Тогда
возврат Истина; //пустые значения пропускаем
КонецЕсли;
Если Дом[условие.Тип] = условие.Значение Тогда //если стоит проверяемое значение то проверим его условие
Если ДомДляПроверкиУсловия[условие.ТипУсловия] = условие.ЗначениеУсловия Тогда
возврат Истина;
КонецЕсли;
//обратная проверка
ИначеЕсли Дом[условие.ТипУсловия] = условие.ЗначениеУсловия Тогда //если стоит проверяемое значение то проверим его условие
Если ДомДляПроверкиУсловия[условие.Тип] = условие.Значение Тогда
возврат Истина;
КонецЕсли;
Иначе
возврат Истина;
КонецЕсли;
возврат Ложь;
КонецФункции
И наконец проверка самого решения.
Функция ПроверитьРешение(ТаблицаУсловий, ТекущаяТаблица)
//1. Все ячейки таблицы должны быть заполнены
//2. Должны быть выполнены условия
Для каждого дом из ТекущаяТаблица Цикл
Для каждого колонка из ТекущаяТаблица.Колонки Цикл
Если ПустаяСтрока(Дом[колонка.Имя]) Тогда
возврат ложь;
КонецЕсли;
КонецЦикла;
КонецЦикла;
возврат ПроверитьВыполнениеУсловий(ТаблицаУсловий, ТекущаяТаблица);
КонецФункции
