Загадка Survo
Сурво головоломка является своим родом логической головоломки представлена (в апреле 2006) и изучен Сеппо Мустоненом . [1] Название головоломки связано с системой Survo Мустонена , которая представляет собой общую среду для статистических вычислений и связанных областей. [2]
В головоломке Survo задача состоит в том, чтобы заполнить таблицу размером m × n целыми числами 1, 2, ..., m · n так, чтобы каждое из этих чисел появлялось только один раз, а их суммы по строкам и столбцам были равны целым числам, указанным на нижняя и правая часть таблицы. Часто некоторые целые числа легко приводятся в таблице, чтобы гарантировать уникальность решения и / или облегчить задачу. [2]
В некоторой степени головоломки Survo напоминают головоломки Судоку и Какуро . Однако числа, используемые в решении, не ограничиваются 1, 2, ..., 9, а размер сетки головоломки обычно очень мал. Решение головоломок Survo также связано с созданием магических квадратов . [3]
Степени сложности в решении головоломок Сурвы сильно меняются. Простые головоломки, предназначенные для школьников, представляют собой чистые упражнения на сложение и вычитание, а более сложные - требуют еще и хорошей логики. Самые сложные головоломки Survo невозможно решить без компьютеров. [4]
Некоторые свойства системы Survo, такие как редакционные вычисления и операция COMB, например создание ограниченных целочисленных разделов , поддерживают решение головоломок Survo.
Загадки Survo регулярно публикуются в Финляндии издательством Ilta-Sanomat и научным журналом Университета Хельсинки с сентября 2006 года. Решение задач Survo было одной из трех основных тем на национальных вступительных экзаменах в финские университеты по информатике (2009 г.) ). [5]
Пример
Вот простая головоломка Survo с 3 строками и 4 столбцами:
| А | B | C | D | ||
| 1 | 6 | 30 | |||
| 2 | 8 | 18 | |||
| 3 | 3 | 30 | |||
| 27 | 16 | 10 | 25 |
Цифры 3, 6 и 8 даются легко. Задача состоит в том, чтобы расставить оставшиеся числа 1-12 (3 × 4 = 12) на свои места, чтобы суммы были правильными.
У головоломки есть уникальное решение, которое можно найти поэтапно следующим образом: пропущенные числа 1,2,4,5,7,9,10,11,12. Обычно лучше начинать со строки или столбца с наименьшим количеством пропущенных номеров. В данном случае таковы столбцы A, B и C.
Столбец A не подходит, так как сумма 19 пропущенных чисел может быть представлена в соответствии с правилами несколькими способами (например, 19 = 7 + 12 = 12 + 7 = 9 + 10 = 10 + 9). В столбце B сумма пропущенных чисел равна 10, имея только одно разделение 10 = 1 + 9, поскольку другие варианты 10 = 2 + 8 = 3 + 7 = 4 + 6 не принимаются из-за чисел, уже присутствующих в таблице. Число 9 нельзя поместить в строку 2, так как тогда сумма в этой строке превысит значение 18. Следовательно, единственный выбор - начать решение с
| А | B | C | D | ||
| 1 | 6 | 30 | |||
| 2 | 8 | 1 | 18 | ||
| 3 | 9 | 3 | 30 | ||
| 27 | 16 | 10 | 25 |
Теперь столбец A имеет только одну альтернативу 27 - 8 = 19 = 7 + 12 = 12 + 7. Число 7 не может быть в строке 1, потому что сумма пропущенных чисел в этой строке будет 30 - 7 - 6 = 17, а это не допускает разрешенного раздела. Таким образом, мы имеем
| А | B | C | D | ||
| 1 | 12 | 6 | 30 | ||
| 2 | 8 | 1 | 18 | ||
| 3 | 7 | 9 | 3 | 30 | |
| 27 | 16 | 10 | 25 |
подразумевая, что последнее число в последней строке будет 30-7-9-3 = 11:
| А | B | C | D | ||
| 1 | 12 | 6 | 30 | ||
| 2 | 8 | 1 | 18 | ||
| 3 | 7 | 9 | 3 | 11 | 30 |
| 27 | 16 | 10 | 25 |
В первой строке сумма пропущенных чисел составляет 30 - 12 - 6 = 12. Единственное возможное разделение - 12 = 2 + 10, поэтому число 2 будет в столбце C; 10 в этой позиции слишком много для суммы столбца.
| А | B | C | D | ||
| 1 | 12 | 6 | 2 | 10 | 30 |
| 2 | 8 | 1 | 18 | ||
| 3 | 7 | 9 | 3 | 11 | 30 |
| 27 | 16 | 10 | 25 |
Решение затем легко завершается как
| А | B | C | D | ||
| 1 | 12 | 6 | 2 | 10 | 30 |
| 2 | 8 | 1 | 5 | 4 | 18 |
| 3 | 7 | 9 | 3 | 11 | 30 |
| 27 | 16 | 10 | 25 |
Таким образом, базовой арифметики и простых рассуждений достаточно для решения простых головоломок Survo, подобных этой.
Свойства головоломок Survo
Правила головоломок Survo проще, чем в судоку . Сетка всегда прямоугольная или квадратная и обычно намного меньше, чем в судоку и какуро .[6]
Стратегии решения меняются в зависимости от сложности головоломки.[6] В простейшей форме, как в следующем случае 2 × 3 (степень сложности 0)
| 3 | 9 | ||
| 6 | 12 | ||
| 9 | 7 | 5 |
Головоломки Survo - подходящие упражнения на сложение и вычитание.[6]
Открытая головоломка 3 × 4 Survo (сложность 150)
| 24 | ||||
| 15 | ||||
| 39 | ||||
| 21 год | 10 | 18 | 29 |
где ни одно из чисел не дается легко, намного сложнее. И у него есть только одно решение.
Проблему можно упростить, легко указав некоторые числа, например, как
| 7 | 5 | 24 | ||
| 1 | 8 | 15 | ||
| 11 | 39 | |||
| 21 год | 10 | 18 | 29 |
что делает задачу практически тривиальной (степень сложности 0).[6]
Оценка степени сложности
Измерение степени сложности основано на количестве «мутаций», необходимых для первой решающей программы, созданной Мустоненом в апреле 2006 года. Эта программа работает с использованием частично рандомизированного алгоритма.[7]
Программа начинает с случайной вставки отсутствующих чисел в таблицу, а затем пытается получить вычисленные суммы строк и столбцов как можно ближе к истинным, систематически меняя элементы в таблице. Это испытание приводит либо к правильному решению, либо (как в большинстве случаев) в тупик, где несоответствие между вычисленными и истинными суммами не может быть уменьшено систематически. В последнем случае "мутация" производится путем случайного обмена двумя или более числами. После этого систематическая процедура плюс мутация повторяется до тех пор, пока не будет найдено истинное решение. В большинстве случаев среднее количество мутаций работает как грубая мера уровня сложности решения головоломки Survo. Этот показатель (MD) вычисляется как среднее количество мутаций, когда головоломка решается 1000 раз, начиная с рандомизированной таблицы.Распределение количества мутаций приближается к геометрическому распределению.
Эти числовые значения часто преобразуются в пятизвездочную шкалу следующим образом: [8]
MD
| 0–30 | * |
| 31 - 150 | ** |
| 151–600 | *** |
| 601–1500 | **** |
| 1500 - | ***** |
Степень сложности, указанная в качестве значения MD, довольно неточна и может даже вводить в заблуждение, если решение найдено с помощью умных выводов или творческих догадок. Эта мера работает лучше, когда требуется, чтобы решатель также доказал уникальность решения.
Откройте головоломки Survo
Загадка Survo называется открытой, если даны лишь предельные суммы. Две открытые головоломки размером m × n считаются существенно разными, если одна из них не может быть преобразована в другую путем перестановки строк и столбцов или перестановки, когда m = n . В этих головоломках суммы строк и столбцов различны. Количество существенно различных и однозначно решаемых m × n головоломок Survo обозначается S ( m , n ). [7]
Рейо Сунд первым обратил внимание на перечень открытых головоломок Survo. Он вычислил S (3,3) = 38, изучив все 9! = 362880 возможных таблиц 3 × 3 стандартными комбинаторными программными модулями и программными модулями обработки данных Survo . После этого Мустонен нашел S (3,4) = 583, начав со всех возможных разбиений предельных сумм и используя первую программу-решатель. Петтери Каски вычислил S (4,4) = 5327, преобразовав задачу в задачу о точном покрытии .
Летом 2007 года Мустонен разработал новую программу-решатель, которая подтверждает предыдущие результаты. Следующие значения S ( m , n ) были определены этой новой программой: [9]
| м / п | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 2 | 1 | 18 | 62 | 278 | 1146 | 5706 | 28707 | 154587 | 843476 |
| 3 | 18 | 38 | 583 | 5337 | 55815 | 617658 | |||
| 4 | 62 | 583 | 5327 | 257773 | |||||
| 5 | 278 | 5337 | 257773 | ||||||
| 6 | 1146 | 55815 | |||||||
| 7 | 5706 | 617658 | |||||||
| 8 | 28707 | ||||||||
| 9 | 154587 | ||||||||
| 10 | 843476 |
Вычисление S (5,5) уже кажется очень сложной задачей на основе имеющихся знаний.
Метод обмена
Метод перестановки для решения головоломок Survo был создан путем объединения идеи исходной решающей программы с наблюдением, что произведения предельных сумм грубо указывают позиции правильных чисел в окончательном решении.[10] Процедура начинается с заполнения исходной таблицы числами 1,2, ..., m · n в соответствии с размерами этих продуктов и вычисления сумм по строкам и столбцам в соответствии с этой начальной настройкой. В зависимости от того, насколько эти суммы отклоняются от истинных сумм, пытаются улучшить решение, меняя местами два числа за раз. При использовании метода перестановки характер решения головоломок Survo становится чем-то похожим на шахматные задачи. Этим методом вряд ли возможно проверить единственность решения.
Например, довольно сложная головоломка 4 × 4 (MD = 2050).
| 51 | ||||
| 36 | ||||
| 32 | ||||
| 17 | ||||
| 51 | 42 | 26 | 17 |
решается 5 перестановками. Начальная настройка
| Сумма | Ok | ошибка | |||||
| 16 | 15 | 10 | 8 | 49 | 51 | -2 | |
| 14 | 12 | 9 | 4 | 39 | 36 | 3 | |
| 13 | 11 | 6 | 3 | 33 | 32 | 1 | |
| 7 | 5 | 2 | 1 | 15 | 17 | -2 | |
| Сумма | 50 | 43 год | 27 | 16 | |||
| Ok | 51 | 42 | 26 | 17 | |||
| ошибка | -1 | 1 | 1 | -1 |
и решение находится перестановками (7,9) (10,12) (10,11) (15,16) (1,2). В Сурво системе, sucro / SP_SWAP заботится о бухгалтерии , необходимой в способе замены.
Быстрые игры
Решение сложной головоломки Survo может занять несколько часов. Решение головоломок Survo как быстрых игр предлагает другой вид задач.[4] Самая требовательная форма быстрой игры доступна в сети в виде Java-апплета.[11] В этой быстрой игре открытые головоломки 5 × 5 решаются путем выбора (или угадывания) чисел щелчком мыши. Неправильный выбор вызывает мелодичный музыкальный интервал. Его диапазон и направление указывают на качество и величину ошибки. Цель - набрать как можно больше очков. Оценка увеличивается в случае правильного выбора и уменьшается в случае неправильного выбора и времени, затраченного на поиск окончательного решения.
Версия 4x4 доступна для устройств iOS как «Hot Box».[12]
Смотрите также
использованная литература
- ^ Aitola, Kerttu (2006): "Сурво на täällä" ( "Сурво здесь"). Yliopisto 54 (12) : 44–45.
- ^ a b Мустонен, Сеппо (2007): "Survo Crossings". Архивировано 28 ноября 2008 г. в Wayback Machine . CSCnews 1/2007 : 30-32.
- ^ Вехкалахти Киммо (2007): «Некоторые замечания по поводу магических квадратов и Сурвых головоломок» . 16-й Международный семинар по матрицам и статистике, Виндзорский университет, Канада, 1–3 июня 2007 г.
- ^ a b Мустонен, Сеппо (2007): «О задачах с перекрестной суммой Survo» . В Я. Ниемеля, С. Пунтанен и Е.П. Лиски (ред.) Тезисы ежегодной конференции финских статистиков 2007 г., «Многомерные методы» , стр. 23–26. Кафедра математики, статистики и философии, Университет Тампере. ISBN 978-951-44-6957-2 .
- ^ "Tietojenkäsittelytieteen yhteisvalinta 22.5.2009, Tehtävä 3: Survo-ristikko" Архивировано 20 июля 2011 г. на Wayback Machine . («Национальный вступительный экзамен по информатике, 22 мая 2009 г., упражнение 3: Survo Puzzle»).
- ^ a b c d Мустонен, Сеппо (2006): "Survo-ristikot" (" Загадки Survo "). Сольму 3/2006 : 22–23.
- ^ a b Мустонен, Сеппо (2006-06-02): «О некоторых головоломках с перекрестной суммой» . Проверено 30 августа 2009.
- ^ Мустонен, Сеппо (2006-09-26): «Survo-ristikon vaikeuden arviointi» («Оценка степени сложности загадки Survo Puzzle»). Проверено 30 августа 2009.
- ^ Мустонен, Сеппо (2007-10-30): «Перечень однозначно решаемых открытых головоломок Survo» . Проверено 30 августа 2009.
- ^ Мустонен, Сеппо (2007-07-09): «О методе подкачки» . Проверено 30 августа 2009.
- ^ «Survo Puzzle (быстрая игра 5x5) в виде Java-апплета» . Проверено 30 августа 2009.
- ^ "Hot Box, реализация iOS 4x4" . Опубликовано в октябре 2008 г.
внешние ссылки
- Пазлы Survo : проблемы и решения
- Логические головоломки
