Методы решения судоку

[lex_t]

Было бы интересно увидеть алгоритм на каком-либо языке программирования, или псевдокоде. Научите компьютер решать судоку не перебором. С удовольствием почитал бы как это делается

[Dialog]

Перебором решать судоку даже компьютер устанет :) Поэтому такой вариант точно не вариант.

[backmeupplz]

Почему же, устанет? :) Вот, например, в прошлом семестре в универе было задание научить компьютер решать судоку методом бинарных деревьев с backtracking search (простите меня, не знаю, как это будет по-русски).

Dr.Racket

;;
;; Brute force Sudoku solver
;;
;; In Sudoku, the board is a 9x9 grid of SQUARES.
;; There are 9 ROWS and 9 COLUMNS, there are also 9
;; 3x3 BOXES.  Rows, columns and boxes are all UNITs.
;; So there are 27 units.
;;
;; The idea of the game is to fill each square with
;; a Natural[1, 9] such that no unit contains a duplicate
;; number.
;;


;; Data definitions:


;; Val is Natural[1, 9]

;; Board is (listof Val|false)   that is 81 elements long
;; interp.
;;  Visually a board is a 9x9 array of squares, where each square
;;  has a row and column number (r, c).  But we represent it as a
;;  single flat list, in which the rows are layed out one after
;;  another in a linear fashion. (See interp. of Pos below for how
;;  we convert back and forth between (r, c) and position in a board.)

;; Pos is Natural[0, 80]
;; interp.
;;  the position of a square on the board, for a given p, then
;;    - the row    is (quotient p 9)
;;    - the column is (remainder p 9)

(define (r-c->pos r c) (+ (* r 9) c))  ;helpful for writing tests


;; Unit is (listof Pos) of length 9
;; interp. 
;;  The position of every square in a unit. There are
;;  27 of these for the 9 rows, 9 columns and 9 boxes.


;; Constants:

(define ALL-VALS (list 1 2 3 4 5 6 7 8 9))

(define B false) ;B stands for blank


(define BD1 
  (list B B B B B B B B B
        B B B B B B B B B
        B B B B B B B B B
        B B B B B B B B B
        B B B B B B B B B
        B B B B B B B B B
        B B B B B B B B B
        B B B B B B B B B
        B B B B B B B B B))

(define BD2 
  (list 1 2 3 4 5 6 7 8 9 
        B B B B B B B B B 
        B B B B B B B B B 
        B B B B B B B B B 
        B B B B B B B B B
        B B B B B B B B B
        B B B B B B B B B
        B B B B B B B B B
        B B B B B B B B B))

(define BD3 
  (list 1 B B B B B B B B
        2 B B B B B B B B
        3 B B B B B B B B
        4 B B B B B B B B
        5 B B B B B B B B
        6 B B B B B B B B
        7 B B B B B B B B
        8 B B B B B B B B
        9 B B B B B B B B))

(define BD4                ;easy
  (list 2 7 4 B 9 1 B B 5
        1 B B 5 B B B 9 B
        6 B B B B 3 2 8 B
        B B 1 9 B B B B 8
        B B 5 1 B B 6 B B
        7 B B B 8 B B B 3
        4 B 2 B B B B B 9
        B B B B B B B 7 B
        8 B B 3 4 9 B B B))

(define BD4s               ;solution to 4
  (list 2 7 4 8 9 1 3 6 5
        1 3 8 5 2 6 4 9 7
        6 5 9 4 7 3 2 8 1
        3 2 1 9 6 4 7 5 8
        9 8 5 1 3 7 6 4 2
        7 4 6 2 8 5 9 1 3
        4 6 2 7 5 8 1 3 9
        5 9 3 6 1 2 8 7 4
        8 1 7 3 4 9 5 2 6))

(define BD5                ;hard
  (list 5 B B B B 4 B 7 B
        B 1 B B 5 B 6 B B
        B B 4 9 B B B B B
        B 9 B B B 7 5 B B
        1 8 B 2 B B B B B 
        B B B B B 6 B B B 
        B B 3 B B B B B 8
        B 6 B B 8 B B B 9
        B B 8 B 7 B B 3 1))

(define BD5s               ;solution to 5
  (list 5 3 9 1 6 4 8 7 2
        8 1 2 7 5 3 6 9 4
        6 7 4 9 2 8 3 1 5
        2 9 6 4 1 7 5 8 3
        1 8 7 2 3 5 9 4 6
        3 4 5 8 9 6 1 2 7
        9 2 3 5 4 1 7 6 8
        7 6 1 3 8 2 4 5 9
        4 5 8 6 7 9 2 3 1))

(define BD6                ;hardest ever? (Dr Arto Inkala)
  (list B B 5 3 B B B B B 
        8 B B B B B B 2 B
        B 7 B B 1 B 5 B B 
        4 B B B B 5 3 B B
        B 1 B B 7 B B B 6
        B B 3 2 B B B 8 B
        B 6 B 5 B B B B 9
        B B 4 B B B B 3 B
        B B B B B 9 7 B B))

(define BD7                 ; no solution 
  (list 1 2 3 4 5 6 7 8 B 
        B B B B B B B B 2 
        B B B B B B B B 3 
        B B B B B B B B 4 
        B B B B B B B B 5
        B B B B B B B B 6
        B B B B B B B B 7
        B B B B B B B B 8
        B B B B B B B B 9))




;; Positions of all the rows, columns and boxes:

(define ROWS
  (list (list  0  1  2  3  4  5  6  7  8)
        (list  9 10 11 12 13 14 15 16 17)
        (list 18 19 20 21 22 23 24 25 26)
        (list 27 28 29 30 31 32 33 34 35)
        (list 36 37 38 39 40 41 42 43 44)
        (list 45 46 47 48 49 50 51 52 53)
        (list 54 55 56 57 58 59 60 61 62)
        (list 63 64 65 66 67 68 69 70 71)
        (list 72 73 74 75 76 77 78 79 80)))

(define COLS
  (list (list 0  9 18 27 36 45 54 63 72)
        (list 1 10 19 28 37 46 55 64 73)
        (list 2 11 20 29 38 47 56 65 74)
        (list 3 12 21 30 39 48 57 66 75)
        (list 4 13 22 31 40 49 58 67 76)
        (list 5 14 23 32 41 50 59 68 77)
        (list 6 15 24 33 42 51 60 69 78)
        (list 7 16 25 34 43 52 61 70 79)
        (list 8 17 26 35 44 53 62 71 80)))

(define BOXES
  (list (list  0  1  2  9 10 11 18 19 20)
        (list  3  4  5 12 13 14 21 22 23)
        (list  6  7  8 15 16 17 24 25 26)
        (list 27 28 29 36 37 38 45 46 47)
        (list 30 31 32 39 40 41 48 49 50)
        (list 33 34 35 42 43 44 51 52 53)
        (list 54 55 56 63 64 65 72 73 74)
        (list 57 58 59 66 67 68 75 76 77)
        (list 60 61 62 69 70 71 78 79 80)))

(define UNITS (append ROWS COLS BOXES))




;; Functions:


;; Board -> Board or false
;; produce solution for bd; or false if bd is unsolvable
;; Assumption: bd is valid
(check-expect (solve BD4) BD4s)
(check-expect (solve BD5) BD5s)
(check-expect (solve BD7) false)

; 
; Backtracking search through arbitrary-arity search tree.
; 
; Generative recursion.
; 
; Termination argument:
;  trivial case:  checked board has no blanks
;  reduction step: fill first blank with all possible valid values
;  argument: the reduction step fills the blanks board by one, so
;            eventually the board will be full. 
;            
;            


(define (solve bd)
  (local [(define (solve/one bd)
            (if (solved? bd)
                bd 
                (solve/list (next-boards bd))))
          
          (define (solve/list lobd)
            (cond [(empty? lobd) false]
                  [else
                   (local [(define try (solve/one (first lobd)))]
                     (if (not (false? try))
                         try
                         (solve/list (rest lobd))))]))
          
          (define (next-boards bd)
            (local [(define blank (find-blank bd))] ;position of blank
              (filter valid-board?                  ;valid next boards
                      (map (λ (v) (bsubst bd blank v))
                           ALL-VALS))))]
    
    (solve/one bd)))

; ASIDE: For the really curious, lookup what the function curry does, and then
; replace the definition of solve/one above with the following. You'll need to
; put (require racket/function) at the top of the file for it to work. Its kind
; of neat.
; 
;           (define (solve/one bd)
;             (if (solved? bd)
;                 bd                   
;                 (solve/list 
;                  (filter check-board?
;                          (map (curry bsubst bd (find-blank bd)) ALL-VALS)))))
; 


;; Board -> Boolean
;; produce true if board has no blank squares
(check-expect (solved? BD1) false)
(check-expect (solved? (list 1 1)) true) ;white box test

(define (solved? bd) (andmap number? bd))


;; Board -> Pos
;; Produce the position of a blank square in bd
;; ASSUMPTION: the board contains at least 1 blank square
(check-expect (find-blank BD1) (r-c->pos 0 0))
(check-expect (find-blank BD2) (r-c->pos 1 0))
(check-expect (find-blank BD3) (r-c->pos 0 1))
(check-expect (find-blank BD4) (r-c->pos 0 3))
(check-expect (find-blank BD5) (r-c->pos 0 1))

(define (find-blank lovf)
  (cond [(empty? lovf) (error "Board should have contained at least one blank.")]
        [else
         (if (false? (first lovf))
             0
             (add1 (find-blank (rest lovf))))]))


;; Board -> Boolean
;; produce true if no unit on bd contains duplicate values; false otherwise
(check-expect (valid-board? BD1) true)
(check-expect (valid-board? BD2) true)
(check-expect (valid-board? BD3) true)
(check-expect (valid-board? BD4) true)
(check-expect (valid-board? BD5) true)
(check-expect (valid-board? (cons 2 (rest BD2))) false)
(check-expect (valid-board? (cons 2 (rest BD3))) false)
(check-expect (valid-board? (append (list 2 6) (rest (rest BD4)))) false)

(define (valid-board? bd)
  (local [(define (check-units lou)
            (andmap check-unit lou))     
          (define (check-unit u)
            (no-duplicates? (map (λ (p) (bref bd p)) u)))
          (define (no-duplicates? vals)
            (cond [(empty? vals) true]
                  [else
                   (if (and (number? (first vals))
                            (member (first vals) (rest vals)))
                       false
                       (no-duplicates? (rest vals)))]))]
    (check-units UNITS)))


;; Board Pos -> Val or false
;; Produce value at given position on board.
(check-expect (bref BD2 (r-c->pos 0 5)) 6)
(check-expect (bref BD3 (r-c->pos 7 0)) 8)

; 
; Function on 2 complex data: Board and Position (Position is Natural[0, 80]).
; We can assume that p is <= (length bd).
; 
;               empty     (cons Val-or-False Board)
;  0             XXX         (first bd)
;  
;  (add1 p)      XXX         <natural recursion>


(define (bref bd p)
  #;
  (cond [(zero? p) (first bd)]
        [else
         (bref (rest bd) (sub1 p))])

  (list-ref bd p))                    ;Dr Racket's version is faster!


;; Board Pos Val -> Board
;; produce new board with val at given position
(check-expect (bsubst BD1 (r-c->pos 0 0) 1)
              (cons 1 (rest BD1)))

; 
; Function on 2 complex data, Board and Position (which is Natural[0, 80]).
; We can assume that p is <= (length bd).
; 
;               empty     (cons Val-or-False Board)
;  0             XXX         (cons nv (rest bd))
;  
;  (add1 p)      XXX         (cons (first bd) <natural recursion>)


(define (bsubst bd p nv)
  (cond [(zero? p) (cons nv (rest bd))]
        [else
         (cons (first bd)
               (bsubst (rest bd) (sub1 p) nv))]))

[Brand]

«backtracking» — перебор с возвратом.

[MikeMirzayanov]

Неправда. Перебор очень шустро отрабатывает. На соревнованиях по программированию такое бывало давали: например.
А вот статистика по решениям (смотрите на время исполнения).

[KvanTTT]

Если использовать эвристики, то не устанет.

Судоку — это же не Го или Точки, даже не шахматы.

[VenomBlood]

Судоку — это же не Го или Точки, даже не шахматы.

Обобщенная судоку — NP полная.

[KvanTTT]

Да, но если сравнивать Судоку и Го на полях одинакового размера, то мне кажется Судоку гораздо легче решить.

[OlegTar]

Я делал программу для решения судоку перебором с возвратами, решала быстро.

[LionSoft]

Насчёт перебора: Есть такая игра «Быки и Коровы» (в институте мы любили играть в неё на парах).
Не знаю как у кого, но когда мы играли в эту игру на листике, то метод решения был в общих чертах такой: сразу назывались два числа (скажем 1234 и 5678) и дальше все последующие варианты были кандидатами на ответ с учётом предыдущей информации (т.е. банальный перебор).
За 6 ходов угадывали почти всегда. В 30% случаев угадывали за 5 ходов. 4 хода — это если сильно везло.
В какой-то момент пришла идея, что алгоритм можно оптимизировать таким образом: предположим (упрощённо) есть три варианта правильного ответа причём если мы не угадываем — то дополнительной информации не появляется, т.е. всё-равно остаётся два варианта после первого фэйла. (Другими словами, можно равновероятно закончить игру за 1, 2 или 3 хода). Однако на первом ходе можно спросить заведомо неправильный вариант, ответ на который даст точную информацию, какой из трёх вариантов верный. Т.е. игра будет закончена за два хода в любом случае. Мне показалось, что используюя такой алгоритм мы должны выигрывать чаще, особенно учитывая, что так можно играть с самого начала (со второго хода), а не только в конце.
Короче, т.к. самому считать такое было лень — пришлось быстренько наваять программку на Паскале :)
Результат разочаровал — программа угадывала примерно так же как и мы на листике, за 5 — 6 ходов. Тогда я сделал, чтобы программа угадывала числа простым перебором. Результат был ещё более ошеломляющим: 4 — 5 ходов!!!
Не знаю, в чём был подвох, то ли в не совсем верной реализации моего убер-алгоритма (скорее-всего), то ли действительно лобовой метод настолько эффективен для данной задачи (всё-таки всего ходов на одну игру мало — особо не сэкономишь), однако результатом этих исследований стало то, что я разлюбил играть в эту игру (.

[xmoonlight]

Быки и коровы — типа этой?
Сам периодически играю.

[valergrad]

Читал статью с полным решением этой игры. В общем, если память меня не подводит, то в худшем случае 6 ходов — это минимум. Написать программу, которая будет всегда отгадывать за 6 ходов действительно, не очень сложно, а вот доказать, что нельзя придумать алгоритм, который всегда будет отгадывать за 5 ходов — оказалось весьма сложной задачей.

[Quilin]

Еще интересный вариант задачи — приближенный к реальным условиям. В детстве частенько игра затягивалась на девять-десять ходов из-за того, что кто-то случайно «лгал» оппоненту, оценивая предложенный им вариант. Было бы круто написать программу, угадывающую число, получая данные с потерями =)

[mrHobbY]

Всем спасибо за отзывы. Пишу продолжение. И еще попробую реализовать псевдокод.

[Devider]

Вот тут я попытался в меру сил это реализовать на руби.

[Ambyte]

По началу я тоже решал судоку путем просмотра сначала квадратов, а потом строк, как описано в первых пунктах, затем я стал применять метод последовательной проверки для каждого числа, т.е. беру единицу и смотрю куда ее можно поставить, затем двойку, и так до 9, затем возвращаюсь к единице и заново, получается зацикленный поиск по числам, для меня этот способ более удобен.

[Bytexpert]

Я бы немного уточнил, я ищу варианты подстановки единицы, если найден единственный вариант — ставлю, а если их более одного — перехожу к следующему числу, проблема возникает, когда нет чисел с единственным вариантом, тут уже я сдаюсь и ставлю наугад.

[olshevskiy87]

Я тоже так делаю, но бывает, что все варианты исчерпаны и приходится фантазировать :) или ставить наугад.
Хотелось бы почитать про продвинутые методы и попробовать применить на практике, а то эти циклы от 1 до 9 уже малость поднадоели.

[Tairesh]

Всего-то за одну секунду!

[Xenkok]

Да что вы переживаете, этот пост оставил сам Чак Норрис))

[zBit]

Он не может быть Чаком Норрисом, т.к. Чак не решает судоку, потому, что судоку само решает себя, когда появляется Чак.

[zBit]

Вы решаете быстрее меня. Я решаю за 5 секунд при наличии быстрого интернета. Фотографирую своим андроидофоном судоку через Goggles и через несколько секунд он выдаёт мне решённый кроссворд.

[zBit]

Я бы сильно удивился, если бы ваша программа решала судоку больше секунды.

[TIEugene]

Кто бы рассказал алгоритмы _генерации_ карт судоку…

[Mrrl]

Простейший вариант.
Сначала пишем программу, которая умеет решать любую конфигурацию, и выдаёт варианты «нет решений/одно решение/много решений».
Начинаем с пустого поля. У него, очевидно, много решений.
Цикл{
Выбираем случайную незанятую клетку. Перетасовываем цифры от 1 до 9, и пытаемся подставить их в эту клетку. Если у полученной карты решений нет — переходим к следующей цифре. Решение есть (одно или много) — отлично, пишем цифру в эту клетку.
Если есть требование симметричности — проделываем то же с симметричной клеткой.
Проверяем, сколько решений. Если одно — выходим из цикла.
}
Карта готова.

А вот кто бы рассказал алгоритмы генерации японских кроссвордов (пригодных для ручного составления)…

[wrewolf]

Вы имеете в виду картинку?
И конечно с проверкой на решаемость

[Mrrl]

Да, битовую маску по регулярным выражениям. С проверкой на единственность решения.

[wrewolf]

поддерживаю это гораздо интереснее тема. Особенно логика генерации сложных уровней.
Те алгоритмы которые я видел и щупал либо создают слабые поля, либо слишком долго это делают.

[mrHobbY]

FYI: Минимальное количество подсказок для возможного единственного решения — 17. Причем количество решаемых уникальных задач с 17 подсказками (т.е исключая симметричные) равно 49.151. По ссылке можно их все скачать.

[elgato]

Есть же сгенерированные карты. И написано чем сгенерированные. Например Gnome Sudoku.
У неё есть такая штука:
GNOME Sudoku automatically generates new puzzles in the background when you are getting low.

Реально разные уровни сложности получаются, и главное количество неограниченное.

[TIEugene]

1. За ссылку — спс. Но я ж спрашивал алгоритмы генерации, а не карты. Решение «в лоб» (вычеркиванием цифр по одной и попыткой решения) получится крайне времяемко.
2. «неограниченное количество» — сильно сказано :-)

А по статье — мне кажется, что простое итерактивное «вычеркивание» будет самым быстрым.
Но это только кажется — не проверял. Может — есть какие-то silver bullets, типа описанных в статье — но алгоритмизированных.

[Mrrl]

А какая нужна скорость генерации?

[TIEugene]

Максимальная

[Mrrl]

В таком случае: берёте любое решение перебором с возвратом (с отсечением тупиков, т.е. на каждом шаге определяя всё, что можно, с помощью приведённых в этой статье приёмов — достаточно первых двух пунктов), но клетку и порядок перебора цифр в ней определяете случайно. Решаете «пустое поле». Как только найдено какое-нибудь решение — проходите по стеку перебора, и берёте только клетки и цифры в них, которые отмечены в стеке. Очевидно, они дадут задание с однозначным решением. Сложность будет соответствовать приёмам, использованным для отсечения.

[Mrrl]

Моя программа строит одно задание за 1.5 секунды, но я писал её около 7 лет назад и не старался оптимизировать.

[ZurgInq]

Мой вариант такой: простым перебором последовательно заполняем ячейки случайными цифрами от 1 до 9. На каждом шаге проверяем нету ли повторений в строках, столбцах, квадратах. Если есть повторение, откатываемся на шаг назад. И так до победного. В итоге за небольшое время (несколько секунд в худшем случае) получается полная карта судоку. Потом опять таки рандомом, очищаем N ячеек.

[TIEugene]

Несколько секунд на генерацию полной карты — это фантастически много.

[wrewolf]

Не генерацию одного уровня во время запуска приложения 1-2 секунды это не много. А потом ничто не мешает в фоне посчитать еще несколько

[TIEugene]

На генерацию _уровня_ (т.е. незаполненной карты) — немного.
Но на генерацию заполненной — много.
Прочитайте внимательно камент.

[wrewolf]

если я правильно понимаю по любому нужно сначала создать заполненное поле.
В конечном счете алгоритм проверяющий единственность решения должен будет решить судоку столько раз сколько будет вызван, соответственно полное решение он выдаст только раз, остальные случаи на более ранних этапах покажут что вариантов решения больше 1

[TIEugene]

Да, но у человека только создание заполненного — несколько секунд. Сотльвер же — ясен день — работает на порядок дольше.
Что-то мне подсказывает, что а) несколько секунд на создание полной карты — слишком много и б) это хороший повод для начала фаллометрии библиотек генераторов/сольверов :-)

[wrewolf]

да повод просто шикарный.
Ту либо которую я трогал хард уровень создавала от 10 секунд до бесконечности( на 40 секунде принудительно сбрасывал).

[TIEugene]

Дайте тоже потрогать. Для старта.
А я бы генерировал не поточечно, а попачечно — блоками 3x3.
Вполне можно обнаружить, что некоторые блоки несовместимы между собой (т.е. не могут стоять в тех же строках/столбцах) — и отбрасывать их сразу.

[wrewolf]

Код класса генератора брал из одного проекта от сюда codeproject
Вот только из какого точно не помню ссылки уже не осталось

[danSamara]

То же сначала реализовывал «человеческие» способы решения судоку, но для программы быстрее и проще всего оказался способ с начальным заполнением всех клеток чисел 1-9 и последующим их «вычёркиванием».

[tagir_valeev]

Человеческие алгоритмы полезны для автоматической генерации судоку заданного уровня сложности.

[Mrrl]

Для генерации их использовать сложно. Вот для оценки сложности сгенерированного — в самый раз.

[tagir_valeev]

Ну почему? Можно начинать с случайного решённого судоку, случайно удалять по одной цифре и оценивать сложность сгенерированного. Если она недостаточна, удалять ещё. Если перепрыгнули нужную сложность или пришли к судоку с множеством решений, то вернуться на шаг назад. Нормальный алгоритм, мне кажется.

[Sinucs]

Ничего не понял))

[dbelka]

Спасибо за статью! Приятно было узнать, что я использую достаточно стандартные алгоритмы для решения судоку.
Ждём продолжения:)

[EvilSoul]

Вот они, методики которых мне не хватало для решения. Пошел качать судоку.

[janatem]

Интересно, часть этих методов (1-3) я «изобрел» сам, пока решал одну книжечку судоку. В результате пришел к выводу, что более сложных методов не нужно, поскольку и так всё решается почти без перебора. Но, поскольку автор называет перечисленные методы базовыми и грозится показать более продвинутые, наверно бывают намного более сложные примеры судоку, чем попадавшиеся мне. Где можно посмотреть реально сложные примеры?

PS. И кто придумал такую систему нумерации клеток? Это специально, чтобы развязать холивары между остроконечниками и тупоконечниками? Шахматисты негодуют.

[mrHobbY]

Сложные примеры в моем комментарии выше.

[janatem]

Ага, спасибо. Хотя не факт, что самые сложные находятся среди минимальных.

[mrHobbY]

Верно. Вот Вам «самое сложное судоку». Автор Arto Inkala. 20 подсказок.

[vlivyur]

Сам учился по этому руководству. Там же можно потренироваться. Описанных правил достаточно для решения лишь простеньких головоломок. Дальше начинается какое-то сложное кунг-фу — я так и не осилил их понять, тем более применять.

[EndUser]

Автор вроде брал картинки с sudokuwiki? И не упомянул?!

Сам тоже учился на sudokuwiki, и несколько методов вполне легко применяю.

[vlivyur]

Больше на перевод похоже.

[shavluk]

Писал решение на SQL (Firebird). Решает любой

[Fodin]

Существует замечательная программа Sudoku Explainer. Написана на Java давным-давно. Генерирует судоку, решает, дает подсказки и объяснения (графические и пошаговые) любых используемых методов решения. Лет 10 назад я переводил ее на русский язык и чуть-чуть дописывал под себя, чтоб мне было удобно решать судоку.