Доброго времени суток, доброе хабрасообщество. Недавно я увлекся головоломками какуро (для тех, кто не слышал о них). Те из вас, кто уже проводил вечера с ними — знают, что иногда нужно перебрать много вариантов расстановки цифр, и что иногда это бывает утомительно/сложно не пропустить ничего/нереально для человеческого мозга.
Для облегчения этого дела я сваял небольшую программку, которая за нас переберет все варианты согласно заданным параметрам. Собственно, в этом посте я просто делюсь своею софтинкой, не рассказывая долгой теории и не описывая короткого процесса разработки
Скачать проект (VS 2012) можно здесь.
Алгоритмом перебора является, собственно, перебор всех вариантов с последующей проверкой. Как-то оптимизировать его, в принципе, можно, но на быстродействии сильно это не скажется.
Продемонстрирую пример работы (далее цифра в квадратных скобках соответствует цифре на скриншоте):
Нам необходимо посмотреть, какие же комбинации возможны в текущей ситуации: имеем число 39 [1], разнесенное на 7 ячеек [2]. Пусть в результате прошлых изысканий мы нашли, что в первой ячейке могут быть только 2, 3 или 4, во второй — любая от 1 до 9, и т.д. Эти данные мы заносим в [3].
Нажимая «ОК» [8], мы находим все возможные комбинации с учетом перестановок [5], без оного [6], а также все возможные цифры для каждой ячейки [4]. Как видно из примера, в нашей полной неопределенностей ситуации вырисовались 2 точные цифры, а также сократилось количество вариантов для других ячеек.
Скажу сразу, что к помощи этой программки следует прибегать только в самых сложных случаях, иначе процесс решения становится неинтересным. За сим откланяюсь, до свидания.
PS: Если кто-то сможет сделать распознавание/оцифровку какуро с фотоснимка для дальнейшего полного решения компьютером — то я с радостью возьмусь за то самое полное решение (результатом будет нечто похожее на решение судоку).
Для облегчения этого дела я сваял небольшую программку, которая за нас переберет все варианты согласно заданным параметрам. Собственно, в этом посте я просто делюсь своею софтинкой, не рассказывая долгой теории и не описывая короткого процесса разработки
Скачать проект (VS 2012) можно здесь.
Алгоритмом перебора является, собственно, перебор всех вариантов с последующей проверкой. Как-то оптимизировать его, в принципе, можно, но на быстродействии сильно это не скажется.
Продемонстрирую пример работы (далее цифра в квадратных скобках соответствует цифре на скриншоте):
Нам необходимо посмотреть, какие же комбинации возможны в текущей ситуации: имеем число 39 [1], разнесенное на 7 ячеек [2]. Пусть в результате прошлых изысканий мы нашли, что в первой ячейке могут быть только 2, 3 или 4, во второй — любая от 1 до 9, и т.д. Эти данные мы заносим в [3].
Нажимая «ОК» [8], мы находим все возможные комбинации с учетом перестановок [5], без оного [6], а также все возможные цифры для каждой ячейки [4]. Как видно из примера, в нашей полной неопределенностей ситуации вырисовались 2 точные цифры, а также сократилось количество вариантов для других ячеек.
Скажу сразу, что к помощи этой программки следует прибегать только в самых сложных случаях, иначе процесс решения становится неинтересным. За сим откланяюсь, до свидания.
PS: Если кто-то сможет сделать распознавание/оцифровку какуро с фотоснимка для дальнейшего полного решения компьютером — то я с радостью возьмусь за то самое полное решение (результатом будет нечто похожее на решение судоку).