Submit | All submissions | Best solutions | Back to list |
ZSUD - Головоломки SuDoku |
В судоку играют на квадратном поле 9 на 9 клеток. Само поле поделено на районы (квадраты 3 на 3)
В начале игры известно некоторое число цифр в определенных клетках
Цель судоку заполнить все пустые клетки с помощью цифр 1-9 (по одной цифре на клетку), по следующим правилам:
1. Цифра может появиться только один раз в каждой строчке
Можно | |
Нельзя |
2. Цифра может появиться только один раз в каждом столбце
Можно | Нельзя |
3. Цифра может появиться только один раз в каждом районе
Можно | Нельзя |
Проще говоря, одна и та же цифра может появиться только один раз в каждой строчке, столбце и районе.
В отличии от журналов и газет, в цифровом виде головоломку обычно описывают в виде строки состоящей из 81 символа.
То есть все строчки головоломки записаны подряд одна за другой. Для записи используются символы ASCII '1' - '9' -
для обозначения цифр и '.' - для обозначения пустого места. Например головоломка на рисунке выше может быть записана
следующим образом:
7..25..98..6....1....61.3..9....1.......8.4.9..75.28.1.94..3.......4923.61.....4.
В данной задаче Вам прийдется автоматизировать процесс решения таких головоломок и чем эффективнее и быстрее будет работать Ваша программа, тем больше очков вы получите. Очки в данной задаче зависят, как от количества решенных головоломок, так и от скорости работы программы. Большинство головоломок имеет единственное решение, но не все. В тестах присутствует несколько головоломок с несколькими возможными решениями. В данном случае правильным будет любое решение не противоречащее первоначально заданной головоломке. Вы можете быть уверены в том, что все поданные на вход SuDoku являются корректными.
Входные данные
t – число тестов, затем следуют t тестов. [t <= 500]
Каждый тест состоит из одной строчки длиной 81 символ, описывающей одну из головоломок SuDoku.
Выходные данные
Для каждого теста необходимо вывести на отдельной строчке букву Y если вы хотите решать этот тест или же N в противном случае. Далее в том случае если вы ответили Y, необходимо вывести строчку длиной 81, соответствующую корректно решенной головоломке.
Начисление очков
Количество очков полученное за данную задачу вычисляется по формуле: score = 200*total_solved/(200+time), где total_solved - число правильно решенных головоломок, а time - время работы программы в секундах. Если счет выглядит как: xxx.xxxaaa, то aaa - это количество правильно решенных головоломок.
Пример
Входные данные: 3 ..41..3.8.1....62...82..4.....3.28.9....7....7.16.8...562..17.3.3.....4.1....5... 1.......4....1.38.27.9.4...91.7...........5..86.4.5.9..3......8..9....2.4.......7 7..25..98..6....1....61.3..9....1.......8.4.9..75.28.1.94..3.......4923.61.....4. Выходные данные: Y 294167358315489627678253491456312879983574216721698534562941783839726145147835962 Y 198563274654217389273984615915726843347198562862435791731642958589371426426859137 N Начисление очков: В данном случае total_solved = 2, положим также что программа работала 10 секунд. В этом случае количество очков полученных за программу будет равно 1.905002
Added by: | Roman Sol |
Date: | 2006-03-30 |
Time limit: | 0.100s |
Source limit: | 100000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |
Resource: | ZCon 2007 |