Алгоритми за решавање судокуа

С Википедије, слободне енциклопедије
A typical Sudoku puzzle, a 9x9 grid with several numbers missing
Типична Судоку слагалица

Судоку слагалица се састоји из 81 ћелије и оне се налазе у мрежи 9x9 која је подељена у 9 зона, где се у свакој зони налази по 9 ћелија. Свака ћелија може да садржи број од један до девет, сваки број се може наћи само једном у свакој зони. На самом почетку решавања слагалице неке од ћелија ће бити попуњене са бројевима. Циљ је да се и све остале ћелије попуне бројевима. Играчи могу да користе широк спектар стратегија за решавање Судокуа, и овај чланак прекрива низ метода за решавање.

Технике[уреди | уреди извор]

Бектрекинг[уреди | уреди извор]

Алгоритми бектрекинга који су прилагођени за решавање Судокуа испробавају сва могућа решења за дати Судоку. Ако додељена решења не представљају решење целокупног Судокуа алгоритам одбацује додељено решење и враћа се на првобитна решења, а онда покушава поново и због тога се зове бектрекинг.[1]

Испод је исписан генерални псеудокод бектрекинг алгоритма за стандардни Судоку пример (9x9).[2] 

 Initialize 2D array with 81 empty grids (nx = 9, ny = 9)
 Fill in some empty grid with the known values
 Make an original copy of the array
 Start from top left grid (nx = 0, ny = 0), check if grid is empty
 if (grid is empty) {
   assign the empty grid with values (i)
   if (no numbers exists in same rows & same columns same as (i) & 3x3 square (i) is currently in)
     fill in the number
   if (numbers exists in same rows & same columns same as (i) & 3x3 square (i) is currently in)
     discard (i) and repick other values (i++)
 }
 else {
   while (nx < 9) {
     Proceed to next row grid(nx++, ny)
     if (nx equals 9) {
       reset nx = 1
       proceed to next column grid(nx,ny++)
       if (ny equals 9) {
         print solution
       }
     }
   }
 }
Анимирани гиф показује како се Судоку решава помоћу бектрекинга. Црвени број је “фиксиран” број, док алгоритам непрестано покушава да пронађе решење да попуни празне ћелије Судокуа. Приметите како алгоритам одбацује сва претходна решења ако тренутно решење не испуњава услов.

Тачна одлука[уреди | уреди извор]

Судоку може бити описан као пример “проблема тачне одлуке”. Ово доводи и до елегантног описа проблема и ефикасног решења коришћењем бектрекинга. Док тачна одлука не гарантује брзо решавање зона, попуњавање Судокуа користећи алгоритам за тачну одлуку, као што је Играјуће везе, типично решава 9x9 Судоку за неколико секунди.

Исцрпна претрага (груба сила)[уреди | уреди извор]

Програмери су направили компјутерске програме који врше исцрпне претраге, тј. користе грубу силу. Иако је утврђено да постоји приближно 6.67 x 1021 финалних решења, користећи исцрпну претрагу компјутерски алгоритам може да буде практична метода решавања слагалица, уколико је код добро дизајниран.

Предности ове методе су:

  • Решење је загарантовано (док год је слагалица исправна)
  • Време решавања углавном није повезано са тежином слагалице

Мане ове методе су да је поприлчно спора кад се упореди са компјутерским методама решавања које су осмишљене према дедуктивним методама.

Алгоритам “грубе силе” долази до празних ћелија по неком реду, редом их попуњава бројевима који одговарају, или бектрекингом (уклањањем неодговарајућих избора) док не дође до краја. На пример, програм исцрпне претраге ће решити слагалицу уметањем цифре “1” у прву ћелију и проверавањем да ли је дозвољено да се она ту нађе. При проверавању да ли има преступа, сазнаје се да “1” није дозвољено, па се зато вредност повећава на ”2”. Ако се пронађе ћелија где ниједна од 9 цифара није дзвољена, алгоритам оставља ту ћелију празну и враћа се на претходну ћелију. Тада се вредност у тој ћелији повећава за 1. Алгоритам се понавља све док не нађе одговарајуће решење за сву 81 ћелију.[3][4]

Насумична претрага/метода оптимизације[уреди | уреди извор]

Судоку се може решити користећи насумичне методе претраге.[5][6] Пример овог приступа је да:

  1. Насумично одреди бројеве празним ћелијаама у мрежи
  2. Израчуна број грешака
  3. “Промеша” ове унете бројеве по мрежи док се број грешака не сведе на нулу

Решење слагалице ће тада бити пронађено. Приступи мешању бројева укључују симулационо прекаљивање, генетички алгоритам и табу претраживање. Насумично засновани оптимизовани алгоритми знају да буду веома брзи, иако можда нису брзи као неке логички засноване технике. За разлику од других, оптимизациони алгоритми не захтевају да проблеми буду обавезно логички решиви, тако им давајући потенцијал да реше шири распон проблемских случајева. Алгоритми дизајнирани за графичко бојење исто знају да раде веома добро са Судоку слагалицама.[7]

Такође је могуће да Судоку прикажемо као проблем целобројнох линеарног програмирања. Изгледа да су такви приступи ближи брзом проналажењу решења и онда могу да користе рачвање пред крај. Симплекс алгоритам делује као да може да поднесе веома добро ситуације без решења или са вишеструким решењима.

Ограничено програмирање[уреди | уреди извор]

Судоку је ограничен проблем. Судоку као ограничен проблем[8] описује многе разумне алгоритме приступачне у форми ограничења који се могу применити на моделу и решити проблем. Неки модератори ограничења обухватају пример како подесити и решити Судоку проблеме.[9][10] Програм ограничења подешавањем и решавањем ће код већине случајева имати мање од 100 редова кода. Ако код користи јак разуман алгоритам, укључивање претраге је потребно само за најтеже слагалице.

Време рачунања[уреди | уреди извор]

Компјутерски алгоритми извршавају све више циклуса када претражују Судоку са 20 или мање трагова. Заиста, слагалице са 17 трагова је изузетно тешко решити. Када се ограничење симетрије примени, очекивано време претраге ће се драматично повећати још више.[11]

Празне Судоку мреже[уреди | уреди извор]

Иако Судоку мреже које долазе са неким од ћелија које су унапред попуњене, решавање може бити веома изазовно, празне Судоку ћелије се заправо могу веома брзо решити. Можда је најлакши начин да се то спроведе је да се произведе коренско решење, које се може достићи коришћењем следећег једноставног полиномијалног временског алгоритма.

За стандардну n2 x n2 (9 x 9) мрежу, овај алгоритам (еквивалентна имплементација у Јави и Хаскелу) је следећи: 

final int n = 3;
final int[][] field = new int[n*n][n*n];
for (int i = 0; i < n*n; i++)
	for (int j = 0; j < n*n; j++)
		field[i][j] = (i*n + i/n + j) % (n*n) + 1;

sol :: [[Int]]
sol = [ [ witness (build i j) | j <- [0..heightGame] ]
                              | i <- [0..heightGame] ]
  where
    build i j     = (i * heightRegion) + (i `div` heightRegion) + j
    witness       = (`mod` heightGame) . (+ 1)
    heightRegion  = 3
    heightGame    = heightRegion^2

Наведени поступак даје следећи 9x9 Судоку: 

+-----------------------+
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 8 9 | 1 2 3 |
| 7 8 9 | 1 2 3 | 4 5 6 |
|-------+-------+-------|
| 2 3 4 | 5 6 7 | 8 9 1 |
| 5 6 7 | 8 9 1 | 2 3 4 |
| 8 9 1 | 2 3 4 | 5 6 7 |
|-------+-------+-------|
| 3 4 5 | 6 7 8 | 9 1 2 |
| 6 7 8 | 9 1 2 | 3 4 5 |
| 9 1 2 | 3 4 5 | 6 7 8 |
+-----------------------+

Референце[уреди | уреди извор]

  1. ^ Zelenski, Julie. Lecture 11 | Programming Abstractions (Stanford). Stanford Computer Science Department. 
  2. ^ „YasSS - Yet Another (Simple”. Архивирано из оригинала 30. 06. 2014. г. Приступљено 19. 05. 2016.  Текст „Stupid) Sudoku Solver - Moritz Lenz ” игнорисан (помоћ)
  3. ^ „Geeks For Geeks Back Tracking Sudoku Algorithm”. Архивирано из оригинала 28. 08. 2016. г. Приступљено 19. 05. 2016. 
  4. ^ Solving Every Sudoku Puzzle
  5. ^ Lewis, R (2007) Metaheuristics Can Solve Sudoku Puzzles Journal of Heuristics, vol. 13 (4). стр. 387-401.
  6. ^ Perez, Meir and Marwala, Tshilidzi (2008) Stochastic Optimization Approaches for Solving Sudoku arXiv:0805.0697.
  7. ^ Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015.
  8. ^ „"Судоку као ограничен проблем"” (PDF). Архивирано из оригинала (PDF) 07. 10. 2009. г. Приступљено 19. 05. 2016. 
  9. ^ "JaCoP"
  10. ^ "Sudokusolver"
  11. ^ "17 Clue Sudoku with Diagonal Symmetry"

Спољашње везе[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Алгоритми_за_решавање_судокуа&oldid=26807445”