Skip to content

watersort — солвер головоломки на Go ​

Задача. Решить головоломку с переливанием жидкостей, когда часть колб закрыта, часть цветов скрыта, а некоторые колбы открываются только после выполнения условий.

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

Что сделал ​

Солвер на чистом Go, без зависимостей. Понимает:

  • колбы на четыре слота;
  • доску в виде текстового файла с директивами;
  • скрытые слоты ? и «известный цвет, который не переливается с верхним» ?з;
  • закрытые колбы, которые открываются после N выполненных запросов;
  • очередь запросов с альтернативами: з|тз значит «зелёный или тёмно-зелёный».

Восемь режимов поиска: requests, open, done, collect, reveal, sort, counts и проверка достижимости. Режим counts отдельно считает известные, скрытые и пустые слоты — это нужно, чтобы проверять разбор доски до запуска поиска.

Доказательство ​

  • go build и go test ./... без внешних зависимостей.
  • Разбор доски и поиск разделены, поэтому ошибка в формате не выглядит как «решения нет».
  • Восемь режимов покрывают реальные задачи, а не одну демо-головоломку.

Что дальше ​

  • Эвристика для больших досок: сейчас честный перебор упирается в размер.
  • Генератор досок для проверки солвера на случайных конфигурациях.