Эй, это в пятницу днем, пусть будет решать головоломку/алгоритм проблемы.
Одна из моих любимых игр Nintendo DS - Picross DS. Игра довольно проста, она включает в себя решение головоломок, называемых Nonograms. Вы можете попробовать простой онлайн-скрипт Picross: TylerK Picross.
Nonograms - это сетка с последовательностями чисел, определенными для каждой строки и столбца сетки. Числа определяют блоки "заполненных" квадратов для этой строки/столбца, но незаполненные области по обе стороны от блоков не определены. Например, если у вас есть строка, которая выглядит так:
http://steam-punk.net/images/picross1.jpg
Возможные решения для этой строки будут включать:
http://steam-punk.net/images/picross2.jpg http://steam-punk.net/images/picross3.jpg
и др.
"4 5" просто сообщает вам, что где-то в строке есть 4 последовательных блока, за которыми следуют 5 последовательных блоков, заполненных. Это будут только заполненные блоки, а объем пространства до/после них не определены.
Головоломка завершается, когда все строки и столбцы соответствуют их определениям без каких-либо противоречий.
Чрезвычайно простая игра в концепции, но для решения некоторых из них может потребоваться довольно много времени. Пазлы Picross DS постепенно увеличиваются в размере до 25х20 сеток, что обычно занимает около получаса, чтобы решить.
Однако мне всегда приходит в голову, что было бы довольно легкой игрой написать программу для решения. Я никогда не обходился, но, возможно, некоторые люди здесь будут наслаждаться этой проблемой. Если будет опубликовано достойное количество решений, я сравню их по большой головоломке друг против друга, подобно тому, как странице Nonogram Wikipedia о методах атаки головоломки, если вы хотите ссылаться на нее.
Здесь легко разобрать определение головоломки №1 от TylerK Picross, поэтому у вас есть что-то, что можно кормить программой. Строка 1 - это размеры головоломки (возможно, не нужны), строка 2 - это определения строк, строка 3 - определения столбцов. Это только первое, что приходило в голову, поэтому, если кто-то может подумать о более удобном исходном формате, не стесняйтесь комментировать или редактировать этот пост, чтобы включить его.
15 15
15,4 5,2 4,1 3,2,2,2 4 3,2 6 2,2 1 6 2,2 1 1 4 2,1 1,1 3 2 1,2 2 1 2 1,3 3 2 1,9
4 4,3 1 2 3,2 1 2 2,2 1 1,1 4 2,1 3,1 8,1 3 1 1,1 4 2 1,1 4,2 4 3,3 3 3,4 1,10 3,10