Пользователь
0,0
рейтинг
22 марта 2013 в 07:28

Разработка → Методы решения судоку tutorial

1. Основы


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


1.1 «Последний герой»



Рассмотрим седьмой квадрат. Всего четыре свободных клетки, значит что-то можно быстро заполнить.
"8" на D3 блокирует заполнение H3 и J3; точно также "8" на G5 закрывает G1 и G2
С чистой совестью ставим "8" на H1

1.2 «Последний герой» в строке



После просмотра квадратов на очевидные решения, переходим к столбцам и строкам.
Рассмотрим "4" на поле. Понятно, что она будет где-то в строке A.
У нас есть "4" на G3, что зыкрывает A3, есть "4" на F7, убирающая A7. И ещё одна "4" во втором квадрате запрещает её повтор на A4 и A6.
«Последний герой» для нашей "4" это A2

1.3 «Выбора нет»


Иногда есть несколько причин для конкретного расположения. "4" в J8 будет отличным примером.
Синие стрелки показывают, что это последнее возможное число в квадрате. Красные и синие стрелки дают нам последнее число в столбце 8. Зеленые стрелки дают последнее возможное число в строке J.
Как видим, выбора у нас нет, кроме как поставить эту "4" на место.

1.4 «А кто, как не я?»


Заполнение чисел проще проводить вышеописанными методами. Однако проверка числа, как последнего возможного значения, тоже даёт результаты. Метод стоит применять, когда кажется, что все числа есть, но чего-то не хватает.
"5" в B1 ставится исходя из того, что все числа от "1" до "9", кроме "5" есть в строке, столбце и квадрате (отмечено зеленым).

На жаргоне это "Голая одиночка". Если заполнять поле возможными значениями (кандидатами), то в ячейке такое число будет единственным возможным. Развивая эту методику, можно искать "Скрытые одиночки" — числа, уникальные для конкретной строки, столбца или квадрата.

2. «Голая миля»



2.1 «Голые» пары

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

В этом примере несколько «голых пар».
Красным в строке А выделены ячейки А2 и А3, обе содержащие "1" и "6". Я пока не знаю, как именно они расположены здесь, но я спокойно могу убрать все другие "1" и "6" из строки A (отмечено желтым). Также А2 и А3 принадлежат общему квадрату, поэтому убираем "1" из C1.


2.2 «Threesome»

«Голые тройки» — усложненный вариант «голых пар».
Любая группа из трех ячеек в одном блоке содержащая в общем три кандидата является «голой тройкой». Когда такая группа нашлась, эти три кандидата могут быть убраны из других ячеек блока.

Комбинации кандидатов для «голой тройки» могуть быть такими:

[abc] [abc] [abc] // три числа в трех ячейках.
[abc] [abc] [ab] // любые комбинации.
[abc] [ab] [ab] // любые комбинации.
[ab] [aс] [bc]

В этом примере все довольно очевидно. В пятом квадрате ячейки E4, E5, E6 содержат [5,8,9], [5,8], [5,9] соответственно. Получается, что в общем у этих трех ячеек есть [5,8,9], и только эти числа там могут быть. Это позволяет нам убрать их из других кандидатов блока. Этот трюк даёт нам решение "3" для ячейки E7.

2.3 «Великолепная четверка»

"«Голая» четверка" весьма редкое явление, особенно в полной форме, и все же дает результаты при обнаружении. Логика решения такая же как и у «голых троек».


В указанном примере в первом квадрате ячейки A1, B1, B2 и C1 в общем содержат [1,5,6,8], поэтому эти числа займут только эти ячейки и никакие другие. Убираем подсвеченных желтым кандидатов.

3. «Все тайное становится явным»



3.1 Скрытые пары

Отличным способом раскрыть поле будет поиск скрытых пар. Этот метод позволяет убрать лишних кандидатов из ячейки и дать развитие более интересным стратегиям.

В этой головоломке мы видим, что 6 и 7 есть в первом и втором квадратах. Кроме этого 6 и 7 есть в столбце 7. Комбинируя эти условия, мы можем утверждать, что в ячейках A8 и A9 будут только эти значения и все другие кандидаты мы убираем.


Более интересный и сложный пример скрытых пар. Синим выделена пара [2,4] в D3 и E3, убирающая 3, 5, 6, 7 из этих ячеек. Красным выделены две скрытые пары, состоящие из [3,7]. C одной стороны, они уникальны для для двух ячеек в 7 столбце, с другой стороны — для строки E. Выделеные желтым кандидаты убираются.

3.1 Скрытые тройки

Мы можем развить скрытые пары до скрытых троек или даже скрытых четверок. Скрытая тройка состоит из трех пар чисел, расположенных в одном блоке. Такие как [a,b,c], [a,b,c] и[a,b,c]. Однако, как и в случае с «голыми тройками», в каждой из трех ячеек не обязательно должно быть по три числа. Сработают всего три числа в трех ячейках. Например [ab], [aс], [bc]. Скрытые тройки будут замаскированы другими кандидатами в ячейках, поэтому сначала надо убедиться, что тройка применима к конкретному блоку.


В этом сложном примере есть две скрытые тройки. Первая, отмеченная красным, в столбце А. Ячейка А4 содержит [2,5,6], A7 — [2,6] и ячейка A9 -[2,5]. Эти три ячейки единственные, где могут быть 2 ,5 или 6, поэтому только они там и будут. Следовательно убираем лишних кандидатов.

Вторая, в столбце 9. [4,7,8] уникальны для ячеек B9, C9 и F9. Используя ту же логику, убираем кандидатов.

3.1 Скрытые четверки


Прекрасный пример скрытых четверок. [1,4,6,9] в пятом квадрате могут быть только в четырех ячейках D4, D6, F4, F6. Следуя нашей логике, убираем всеъ других кандидатов (отмеченых желтым).

4. «Нерезиновая»



Если любое из чисел появляется дважды или трижды в одном блоке (строке, столбце, квадрате), тогда мы можем убрать это число из сопряженного блока. Есть четыре вида сопряжения:
  1. Пара или Тройка в квадрате — если они расположены в одной строке, то можно убрать все другие такие же значения из соответствующей строки.
  2. Пара или Тройка в квадрате — если они расположены в одном столбце, то можно убрать все другие такие же значения из соответствующего столбца.
  3. Пара или Тройка в строке — если они расположены в одном квадрате, то можно убрать все другие такие же значения из соответствующего квадрата.
  4. Пара или Тройка в столбце — если они расположены в одном квадрате, то можно убрать все другие такие же значения из соответствующего квадрата.

4.1 Указавыющие пары, тройки



В качестве примера покажу эту головоломку. В третьем квадрате "3" находится только в B7 и B9. Следуя утверждению №1, мы убираем кандидатов из B1, B2, B3. Аналогично, "2" из восьмого квадрата убирает возможное значение из G2.


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

4.2 Сокращаем несокращаемое


Эта стратегия включает в себя аккуратный анализ и сравнение строк и столбцов с содержимым квадратов (правила №3, №4).
Рассмотрим строку А. "2" возможны только в А4 и А5. Следуя правилу №3, убираем "2" их B5, C4, C5.


Продолжим решать головоломку. Имеем единственное расположение "4" в пределах одного квадрата в 8 столбце. Согласно правилу №4, убираем лишних кандитатов и, в добавок, получаем решение "2" для C7.

Послесловие

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


PP @mrHobbY
карма
14,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (62)

  • +3
    Было бы интересно увидеть алгоритм на каком-либо языке программирования, или псевдокоде. Научите компьютер решать судоку не перебором. С удовольствием почитал бы как это делается
    • –7
      Перебором решать судоку даже компьютер устанет :) Поэтому такой вариант точно не вариант.
      • +4
        Почему же, устанет? :) Вот, например, в прошлом семестре в универе было задание научить компьютер решать судоку методом бинарных деревьев с 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))]))
        
        
        
        • +7
          «backtracking» — перебор с возвратом.
      • 0
        Неправда. Перебор очень шустро отрабатывает. На соревнованиях по программированию такое бывало давали: например.
        А вот статистика по решениям (смотрите на время исполнения).
      • 0
        Если использовать эвристики, то не устанет.

        Судоку — это же не Го или Точки, даже не шахматы.
        • +1
          Судоку — это же не Го или Точки, даже не шахматы.
          Обобщенная судоку — NP полная.
          • 0
            Да, но если сравнивать Судоку и Го на полях одинакового размера, то мне кажется Судоку гораздо легче решить.
      • +1
        Я делал программу для решения судоку перебором с возвратами, решала быстро.
    • +2
      Насчёт перебора: Есть такая игра «Быки и Коровы» (в институте мы любили играть в неё на парах).
      Не знаю как у кого, но когда мы играли в эту игру на листике, то метод решения был в общих чертах такой: сразу назывались два числа (скажем 1234 и 5678) и дальше все последующие варианты были кандидатами на ответ с учётом предыдущей информации (т.е. банальный перебор).
      За 6 ходов угадывали почти всегда. В 30% случаев угадывали за 5 ходов. 4 хода — это если сильно везло.
      В какой-то момент пришла идея, что алгоритм можно оптимизировать таким образом: предположим (упрощённо) есть три варианта правильного ответа причём если мы не угадываем — то дополнительной информации не появляется, т.е. всё-равно остаётся два варианта после первого фэйла. (Другими словами, можно равновероятно закончить игру за 1, 2 или 3 хода). Однако на первом ходе можно спросить заведомо неправильный вариант, ответ на который даст точную информацию, какой из трёх вариантов верный. Т.е. игра будет закончена за два хода в любом случае. Мне показалось, что используюя такой алгоритм мы должны выигрывать чаще, особенно учитывая, что так можно играть с самого начала (со второго хода), а не только в конце.
      Короче, т.к. самому считать такое было лень — пришлось быстренько наваять программку на Паскале :)
      Результат разочаровал — программа угадывала примерно так же как и мы на листике, за 5 — 6 ходов. Тогда я сделал, чтобы программа угадывала числа простым перебором. Результат был ещё более ошеломляющим: 4 — 5 ходов!!!
      Не знаю, в чём был подвох, то ли в не совсем верной реализации моего убер-алгоритма (скорее-всего), то ли действительно лобовой метод настолько эффективен для данной задачи (всё-таки всего ходов на одну игру мало — особо не сэкономишь), однако результатом этих исследований стало то, что я разлюбил играть в эту игру (.
      • 0
        Быки и коровы — типа этой?
        Сам периодически играю.
      • 0
        Читал статью с полным решением этой игры. В общем, если память меня не подводит, то в худшем случае 6 ходов — это минимум. Написать программу, которая будет всегда отгадывать за 6 ходов действительно, не очень сложно, а вот доказать, что нельзя придумать алгоритм, который всегда будет отгадывать за 5 ходов — оказалось весьма сложной задачей.
      • 0
        Еще интересный вариант задачи — приближенный к реальным условиям. В детстве частенько игра затягивалась на девять-десять ходов из-за того, что кто-то случайно «лгал» оппоненту, оценивая предложенный им вариант. Было бы круто написать программу, угадывающую число, получая данные с потерями =)
    • 0
      Всем спасибо за отзывы. Пишу продолжение. И еще попробую реализовать псевдокод.
    • 0
      Вот тут я попытался в меру сил это реализовать на руби.
  • +7
    По началу я тоже решал судоку путем просмотра сначала квадратов, а потом строк, как описано в первых пунктах, затем я стал применять метод последовательной проверки для каждого числа, т.е. беру единицу и смотрю куда ее можно поставить, затем двойку, и так до 9, затем возвращаюсь к единице и заново, получается зацикленный поиск по числам, для меня этот способ более удобен.
    • –3
      Я бы немного уточнил, я ищу варианты подстановки единицы, если найден единственный вариант — ставлю, а если их более одного — перехожу к следующему числу, проблема возникает, когда нет чисел с единственным вариантом, тут уже я сдаюсь и ставлю наугад.
    • +1
      Я тоже так делаю, но бывает, что все варианты исчерпаны и приходится фантазировать :) или ставить наугад.
      Хотелось бы почитать про продвинутые методы и попробовать применить на практике, а то эти циклы от 1 до 9 уже малость поднадоели.
  • НЛО прилетело и опубликовало эту надпись здесь
    • +8
      Всего-то за одну секунду!
      • +1
        Да что вы переживаете, этот пост оставил сам Чак Норрис))
        • +2
          Он не может быть Чаком Норрисом, т.к. Чак не решает судоку, потому, что судоку само решает себя, когда появляется Чак.
    • +2
      Вы решаете быстрее меня. Я решаю за 5 секунд при наличии быстрого интернета. Фотографирую своим андроидофоном судоку через Goggles и через несколько секунд он выдаёт мне решённый кроссворд.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Я бы сильно удивился, если бы ваша программа решала судоку больше секунды.
  • +2
    Кто бы рассказал алгоритмы _генерации_ карт судоку…
    • +2
      Простейший вариант.
      Сначала пишем программу, которая умеет решать любую конфигурацию, и выдаёт варианты «нет решений/одно решение/много решений».
      Начинаем с пустого поля. У него, очевидно, много решений.
      Цикл{
      Выбираем случайную незанятую клетку. Перетасовываем цифры от 1 до 9, и пытаемся подставить их в эту клетку. Если у полученной карты решений нет — переходим к следующей цифре. Решение есть (одно или много) — отлично, пишем цифру в эту клетку.
      Если есть требование симметричности — проделываем то же с симметричной клеткой.
      Проверяем, сколько решений. Если одно — выходим из цикла.
      }
      Карта готова.

      А вот кто бы рассказал алгоритмы генерации японских кроссвордов (пригодных для ручного составления)…
      • 0
        Вы имеете в виду картинку?
        И конечно с проверкой на решаемость
        • 0
          Да, битовую маску по регулярным выражениям. С проверкой на единственность решения.
    • +1
      поддерживаю это гораздо интереснее тема. Особенно логика генерации сложных уровней.
      Те алгоритмы которые я видел и щупал либо создают слабые поля, либо слишком долго это делают.
      • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        FYI: Минимальное количество подсказок для возможного единственного решения — 17. Причем количество решаемых уникальных задач с 17 подсказками (т.е исключая симметричные) равно 49.151. По ссылке можно их все скачать.
    • 0
      Есть же сгенерированные карты. И написано чем сгенерированные. Например Gnome Sudoku.
      У неё есть такая штука:
      GNOME Sudoku automatically generates new puzzles in the background when you are getting low.

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

        А по статье — мне кажется, что простое итерактивное «вычеркивание» будет самым быстрым.
        Но это только кажется — не проверял. Может — есть какие-то silver bullets, типа описанных в статье — но алгоритмизированных.
        • 0
          А какая нужна скорость генерации?
          • 0
            Максимальная
            • 0
              В таком случае: берёте любое решение перебором с возвратом (с отсечением тупиков, т.е. на каждом шаге определяя всё, что можно, с помощью приведённых в этой статье приёмов — достаточно первых двух пунктов), но клетку и порядок перебора цифр в ней определяете случайно. Решаете «пустое поле». Как только найдено какое-нибудь решение — проходите по стеку перебора, и берёте только клетки и цифры в них, которые отмечены в стеке. Очевидно, они дадут задание с однозначным решением. Сложность будет соответствовать приёмам, использованным для отсечения.
              • 0
                Моя программа строит одно задание за 1.5 секунды, но я писал её около 7 лет назад и не старался оптимизировать.
    • –1
      Мой вариант такой: простым перебором последовательно заполняем ячейки случайными цифрами от 1 до 9. На каждом шаге проверяем нету ли повторений в строках, столбцах, квадратах. Если есть повторение, откатываемся на шаг назад. И так до победного. В итоге за небольшое время (несколько секунд в худшем случае) получается полная карта судоку. Потом опять таки рандомом, очищаем N ячеек.
      • 0
        Несколько секунд на генерацию полной карты — это фантастически много.
        • +1
          Не генерацию одного уровня во время запуска приложения 1-2 секунды это не много. А потом ничто не мешает в фоне посчитать еще несколько
          • 0
            На генерацию _уровня_ (т.е. незаполненной карты) — немного.
            Но на генерацию заполненной — много.
            Прочитайте внимательно камент.
            • 0
              если я правильно понимаю по любому нужно сначала создать заполненное поле.
              В конечном счете алгоритм проверяющий единственность решения должен будет решить судоку столько раз сколько будет вызван, соответственно полное решение он выдаст только раз, остальные случаи на более ранних этапах покажут что вариантов решения больше 1
              • 0
                Да, но у человека только создание заполненного — несколько секунд. Сотльвер же — ясен день — работает на порядок дольше.
                Что-то мне подсказывает, что а) несколько секунд на создание полной карты — слишком много и б) это хороший повод для начала фаллометрии библиотек генераторов/сольверов :-)
                • 0
                  да повод просто шикарный.
                  Ту либо которую я трогал хард уровень создавала от 10 секунд до бесконечности( на 40 секунде принудительно сбрасывал).
                  • 0
                    Дайте тоже потрогать. Для старта.
                    А я бы генерировал не поточечно, а попачечно — блоками 3x3.
                    Вполне можно обнаружить, что некоторые блоки несовместимы между собой (т.е. не могут стоять в тех же строках/столбцах) — и отбрасывать их сразу.
                    • 0
                      Код класса генератора брал из одного проекта от сюда codeproject
                      Вот только из какого точно не помню ссылки уже не осталось
  • 0
    То же сначала реализовывал «человеческие» способы решения судоку, но для программы быстрее и проще всего оказался способ с начальным заполнением всех клеток чисел 1-9 и последующим их «вычёркиванием».
    • +1
      Человеческие алгоритмы полезны для автоматической генерации судоку заданного уровня сложности.
      • 0
        Для генерации их использовать сложно. Вот для оценки сложности сгенерированного — в самый раз.
        • 0
          Ну почему? Можно начинать с случайного решённого судоку, случайно удалять по одной цифре и оценивать сложность сгенерированного. Если она недостаточна, удалять ещё. Если перепрыгнули нужную сложность или пришли к судоку с множеством решений, то вернуться на шаг назад. Нормальный алгоритм, мне кажется.
  • +5
    Ничего не понял))
  • +1
    Спасибо за статью! Приятно было узнать, что я использую достаточно стандартные алгоритмы для решения судоку.
    Ждём продолжения:)
  • 0
    Вот они, методики которых мне не хватало для решения. Пошел качать судоку.
  • +1
    Интересно, часть этих методов (1-3) я «изобрел» сам, пока решал одну книжечку судоку. В результате пришел к выводу, что более сложных методов не нужно, поскольку и так всё решается почти без перебора. Но, поскольку автор называет перечисленные методы базовыми и грозится показать более продвинутые, наверно бывают намного более сложные примеры судоку, чем попадавшиеся мне. Где можно посмотреть реально сложные примеры?

    PS. И кто придумал такую систему нумерации клеток? Это специально, чтобы развязать холивары между остроконечниками и тупоконечниками? Шахматисты негодуют.
    • 0
      Сложные примеры в моем комментарии выше.
      • 0
        Ага, спасибо. Хотя не факт, что самые сложные находятся среди минимальных.
        • 0
          Верно. Вот Вам «самое сложное судоку». Автор Arto Inkala. 20 подсказок.
          image
  • 0
    Сам учился по этому руководству. Там же можно потренироваться. Описанных правил достаточно для решения лишь простеньких головоломок. Дальше начинается какое-то сложное кунг-фу — я так и не осилил их понять, тем более применять.
    • 0
      Автор вроде брал картинки с sudokuwiki? И не упомянул?!

      Сам тоже учился на sudokuwiki, и несколько методов вполне легко применяю.
      • 0
        Больше на перевод похоже.
  • +1
    Писал решение на SQL (Firebird). Решает любой

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.