Разгадайте головоломку
Пазл Survo — это разновидность логической головоломки, представленная (в апреле 2006 года) и изученная Сеппо Мустоненом . [1] Название головоломки связано с системой Мустонена Survo , которая представляет собой общую среду для статистических вычислений и смежных областей. [2]
В головоломке Survo задача состоит в том, чтобы заполнить таблицу размера m × n целыми числами 1, 2, ..., m · n так, чтобы каждое из этих чисел встречалось только один раз, а суммы их строк и столбцов были равны целым числам, заданным в таблице. нижнюю и правую часть таблицы. Часто некоторые целые числа легко приводятся в таблице, чтобы гарантировать уникальность решения и/или для облегчая задачу. [2]
В какой-то степени головоломки Survo напоминают Судоку и Какуро головоломки . Однако числа, используемые в решении, не ограничиваются 1, 2, ..., 9, а размер сетки головоломки обычно очень мал. Решение головоломок Survo также связано с составлением магических квадратов . [3]
Степень сложности решения головоломок Survo сильно варьируется. Легкие головоломки, предназначенные для школьников, представляют собой чистые упражнения на сложение и вычитание, тогда как более сложные головоломки требуют еще и хороших логических рассуждений. Самые сложные головоломки Survo невозможно решить без компьютеров. [4]
Некоторые свойства системы Survo, такие как редакционные вычисления и операция COMB, например создание ограниченных целочисленных разделов , поддерживают решение головоломок Survo.
Пазлы Survo регулярно публикуются в Финляндии издательством Ilta-Sanomat и научным журналом Хельсинкского университета с сентября 2006 года. Решение головоломок Survo было одной из трех основных тем национального вступительного экзамена. финских университетов по информатике (2009 г.). [5]
Пример
[ редактировать ]Вот простая головоломка Survo с 3 рядами и 4 столбцами:
| А | Б | С | Д | ||
| 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 такие.
Столбец А не является благоприятным, поскольку сумму 19 пропущенных чисел можно представить по правилам несколькими способами (например, 19 = 7 + 12 = 12 + 7 = 9 + 10 = 10 + 9). В столбце Б указана сумма недостающих числа - это 10, имеющие только один раздел 10 = 1 + 9, поскольку другие альтернативы 10 = 2 + 8 = 3 + 7 = 4 + 6 не принимаются, поскольку числа уже присутствуют в стол. Число 9 нельзя поставить в строку 2, так как тогда сумма этой строки превысит значение 18. Поэтому единственный выход — начать решение с
| А | Б | С | Д | ||
| 1 | 6 | 30 | |||
| 2 | 8 | 1 | 18 | ||
| 3 | 9 | 3 | 30 | ||
| 27 | 16 | 10 | 25 |
Теперь в столбце А есть только одна альтернатива 27 – 8 = 19 = 7 + 12 = 12 + 7. Число 7 не может находиться в строке 1, поскольку сумма пропущенных чисел в этой строке будет 30 - 7 - 6 = 17, и это не допускает разрешенного разделения. Таким образом, мы имеем
| А | Б | С | Д | ||
| 1 | 12 | 6 | 30 | ||
| 2 | 8 | 1 | 18 | ||
| 3 | 7 | 9 | 3 | 30 | |
| 27 | 16 | 10 | 25 |
подразумевая, что последнее число в последней строке будет 30 - 7 - 9 -3 = 11:
| А | Б | С | Д | ||
| 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 дюймов эта позиция слишком велика для суммы столбца.
| А | Б | С | Д | ||
| 1 | 12 | 6 | 2 | 10 | 30 |
| 2 | 8 | 1 | 18 | ||
| 3 | 7 | 9 | 3 | 11 | 30 |
| 27 | 16 | 10 | 25 |
Решение тогда легко завершается как
| А | Б | С | Д | ||
| 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 проще, чем у Sudoku . Сетка всегда прямоугольная или квадратная и, как правило, меньше, чем в Судоку и Какуро . [6]
Стратегии решения варьируются в зависимости от сложности. головоломки. [6] В своей простейшей форме, как в следующем случае 2 × 3 (степень сложности 0)
| 3 | 9 | ||
| 6 | 12 | ||
| 9 | 7 | 5 |
Пазлы Survo – это подходящие упражнения на сложение и вычитание. [6]
Открытая головоломка Survo 3×4 (сложность 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 раз, начиная с рандомизированная таблица. Распределение числа мутаций близко к геометрическому.
Эти числовые значения часто преобразуются в 5-звездочную шкалу следующим образом: [8]
доктор медицинских наук
| 0 - 30 | * |
| 31 - 150 | ** |
| 151 - 600 | *** |
| 601 - 1500 | **** |
| 1500 - | ***** |
Степень сложности, указанная в виде значения MD, довольно неточная. и это может даже ввести в заблуждение, когда решение будет найдено путем умных умозаключений или творческих догадок. Эта мера работает лучше, когда требуется, чтобы решатель также доказывает, что решение единственно.
Открыть пазлы 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 перестановками. Первоначальная настройка
| Сумма | ХОРОШО | ошибка | |||||
| 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 | |||
| ХОРОШО | 51 | 42 | 26 | 17 | |||
| ошибка | -1 | 1 | 1 | -1 |
и решение находится перестановками (7,9) (10,12) (10,11) (15,16) (1,2). В системе Survo ведением бухгалтерского учета занимается sucro /SP_SWAP. необходим в методе замены.
Быстрые игры
[ редактировать ]Решение сложной головоломки Survo может занять несколько часов. Решение головоломок Survo в виде быстрых игр ставит перед нами еще одну задачу. [4] В сети доступна самая требовательная форма быстрой игры. как Java-апплет. [11] В этой быстрой игре открытые головоломки 5×5 решаются путем выбора (или угадывания) цифры щелчками мыши. Неправильный выбор вызывает мелодичный музыкальный интервал. Его диапазон и направление указывают на качество и величину ошибки. Цель – набрать как можно больше очков. Оценка увеличивается при правильном выборе и уменьшается при неправильном. ко времени, затраченному на поиск окончательного решения.
Версия 4x4 доступна для устройств iOS как «Hot Box». [12]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Айтола, Кертту (2006): «Сурво здесь». Университет 54 (12) : 44–45.
- ^ Перейти обратно: а б Мустонен, Сеппо (2007): «Survo Crossings» . Архивировано 28 ноября 2008 г. в Wayback Machine . CSCnews 1/2007 : 30–32.
- ^ Вехкалахти, Киммо (2007): «Некоторые комментарии о магических квадратах и головоломках Survo» . 16-й международный семинар по матрицам и статистике, Виндзорский университет, Канада, 1–3 июня 2007 г.
- ^ Перейти обратно: а б Мустонен, Сеппо (2007): «О головоломках с перекрестной суммой Survo» . В Й. Ниемеля, С. Пунтанене и Э. П. Лиски (ред.) Тезисы докладов Ежегодной конференции финских статистиков 2007 г., «Многомерные методы» , стр. 23–26. Кафедра математики, статистики и философии Университета Тампере. ISBN 978-951-44-6957-2 .
- ^ «Совместный выбор в области информатики 22 мая 2009 г., Задача 3: Сетка Survo». Архивировано 20 июля 2011 г. в Wayback Machine . («Национальный вступительный экзамен по информатике, 22 мая 2009 г., Упражнение 3: Survo Puzzle»).
- ^ Перейти обратно: а б с д Мустонен, Сеппо (2006): «Сурво-ристикот» («Загадки Сурво»). Узел 3/2006 : 22–23.
- ^ Перейти обратно: а б Мустонен, Сеппо (2 июня 2006 г.): «О некоторых головоломках с перекрестной суммой» . Проверено 30 августа 2009 г.
- ^ Мустонен, Сеппо (26 сентября 2006 г.): «Оценка степени сложности головоломки Survo». Проверено 30 августа 2009 г.
- ^ Мустонен, Сеппо (30 октября 2007 г.): «Перечень однозначно решаемых открытых головоломок Survo» . Проверено 30 августа 2009 г.
- ^ Мустонен, Сеппо (09.07.2007): «О методе подкачки» . Проверено 30 августа 2009 г.
- ^ «Survo Puzzle (быстрая игра 5x5) в виде Java-апплета» . Проверено 30 августа 2009 г.
- ^ «Hot Box, реализация iOS 4x4» . Опубликовано в октябре 2008 года.
Внешние ссылки
[ редактировать ]- Пазлы Survo : проблемы и решения