Sudoku
Thursday, June 9th, 2005
Недавно в кулере пробежала ссылка на sudoku - японскую головоломку с числами, которая получила гигансткое распространение в UK, потому что Daily Telegraph начала помещать выпуски головоломок в разделе ежедневных кроссвордов.
Правило одно и очень просто: поле из 9Х9 клеток должно быть заполнено числами от 1 до 9 так, чтобы в каждой горизонтали, в каждой вертикали и в каждом блоке 3х3 (поле делится на 9 блоков) присутствовали числа от 1 до 9. Начальное игровое поле задается с определенным набором чисел, после чего, используя логические рассуждения, игрок заполняет числами головоломку. Простые поля решаются без логических ответвлений. Над сложными полями можно провести очень много времени.
Естественно, мне сразу захотелось загрузить решением головоломок компьютер, тем более, что решение может быть очень элегантным, если не задаваться простым перебором чисел. После некоторого размышления я придумал алгоритм, который (как я позже выяснил), называется алгоритмом наименьших кандидатов. Несколько часов возни на С++, и программка начала щелкать головоломки, как орехи. Легкие головоломки на 1Ghz Pentium решались за три - десять секунд (большую точность можно получить, если прикручивать библиотеку с точными таймерами, а мне лень). Но тяжелые головоломки занимали неприлично много времени.
Подумав еще немного, я добавил к алгоритму возможность глядеть на шаг вперед, и время для легких головоломок сократилось до долей секунды, а для тяжелых - 50-70 секунд. У меня есть еще пара идей, как ускорить алгоритм, так что скоро выйдут следующие версии программки.
Код текущей версии и несколько готовых полей можно взять вот здесь. Используется только стандартный С++, так что должно компилиться без всяких проблем на любой ОС.
————
Latest edition of cooler had a link to Sudoku - a japanese puzzle with numbers that gained huge popularity in the UK. Daily Telegraph started printing it in the crowssword section, and Sudoku took off.
There's only one and simple rule: in a field of 9×9 cells, each horizontal and vertical line, as well as a block of 3×3 (field is dividied into 9 of those), all numbers from 1 to 9 must be present. Initial field is set with a certain number of cells filled, and after that using logic and backtracking, players can fill out the rest of the cells. Some of the fields are easy. Some are deceptively easy, and some are diabolically hard.
Naturally, I thought about giving the computer a task of cracking these puzzles. Setting aside plain brute force, an algorithm could be a very elegant piece of code. I sat down and after a while came up with what turned out to be (as I later found out), the least candidates algorithm. A couple of hours of C++ coding, and my program started cracking puzzles like nuts. It took about 3 - 10 seconds on a 1Ghz Athlon to crack an easy puzzle (I was too lazy to install a library with precise timers). However, tough puzzles took forever.
So, I sat down again, and added a 1-step lookahead to existing least candidates. Now, the time for an easy puzzle is under 1 second, and the heardest puzzles take 50-75 seconds. I still have a bunch of ideas on how to optimize the algorithm and speed up the running time, so stay tuned for the next versions of sudoku solver.
You can get the current source code and some sample fields here. I used only standard C++, so it should compile on any platform.