Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
м Renamed template
.
Ред 1:
[[File:Sudoku-by-L2G-20050714.svg|thumb|250px|alt=A typical Sudoku puzzle, a 9x9 grid with several numbers missing|Типична Судоку слагалица]]
{{Neprovereni seminarski}}
{{лош српски}}
{{МАТФКА2016}}
[[Судоку]] слагалица се састоји из 81 ћелије и оне се налазе у мрежи 9x9 која је подељена у 9 зона, где се у свакој зони налази по 9 ћелија. Свака ћелија може да садржи број од један до девет, сваки број се може наћи само једном у свакој зони. На самом почетку решавања слагалице неке од ћелија ће бити попуњене са бројевима, циљ је да се и све остале ћелије попуне бројевима. Играчи могу да користе широк спектар стратегија за решавање Судокуа, и овај чланак прекрива низ метода за решавање.▼
 
▲[[Судоку]] слагалица се састоји из 81 ћелије и оне се налазе у мрежи 9x9 која је подељена у 9 зона, где се у свакој зони налази по 9 ћелија. Свака ћелија може да садржи број од један до девет, сваки број се може наћи само једном у свакој зони. На самом почетку решавања слагалице неке од ћелија ће бити попуњене са бројевима,. циљЦиљ је да се и све остале ћелије попуне бројевима. Играчи могу да користе широк спектар стратегија за решавање Судокуа, и овај чланак прекрива низ метода за решавање.
== Технике ==▼
 
▲== Технике ==
=== Бектрекинг ===
БектрекингАлгоритми алгоритми[[бектрекинг]]а који су прилагођени за решавање Судокуа, они испробавају сва могућа решења за дати Судоку. Ако додељена решења не представљају решење целокупног Судокуа алгоритам одбацује додељено решење и враћа се на првобитна решења, а онда покушава поново и због тога се зове бектрекинг.<ref>{{cite AV media | people=Zelenski, Julie | title=Lecture 11 &#124; Programming Abstractions (Stanford) | publisher=Stanford Computer Science Department | url = https://www.youtube.com/watch?v=p-gpaIGRCQI}}</ref>
 
Испод је исписан генерални псеудокод бектрекинг алгоритма за стандардни Судоку пример (9x9).<ref>[http://moritz.faui2k3.org/en/yasss YasSS - Yet Another (Simple|Stupid) Sudoku Solver - Moritz Lenz]</ref>
<ref>[http://moritz.faui2k3.org/en/yasss YasSS - Yet Another (Simple|Stupid) Sudoku Solver - Moritz Lenz<!-- Botovski generisani naziv -->]</ref>
 
Initialize 2D array with 81 empty grids (nx = 9, ny = 9)
Линија 36 ⟶ 33:
}
 
[[Датотека:Sudoku solved by bactracking.gif|thumb|250px|Анимирани гиф показје како се Судоку решава помоћу бектрекинга[[бектрекинг]]а. Црвени број је “фиксиран” број, док алгоритам непрестано покушава да пронађе решење да попуни празне ћелије Судокуа. Приметите како алгоритам одбацује сва претходна решења ако тренутно решење не испуњава услов.▼
 
]]
▲Анимирани гиф показје како се Судоку решава помоћу бектрекинга. Црвени број је “фиксиран” број, док алгоритам непрестано покушава да пронађе решење да попуни празне ћелије Судокуа. Приметите како алгоритам одбацује сва претходна решења ако тренутно решење не испуњава услов.
 
[[Датотека:Sudoku solved by bactracking.gif|The animated gifs shows how the Sudoku is solved using backtracking. The red number is the "fixed" number meanwhile the algorithm consistently tries to find a solution to fulfil the Sudoku grids using backtrack algorithm]]
 
=== Тачна одлука ===
Судоку може бити описан као пример за “проблем“проблема тачне одлуке”. Ово доводи и до елегантног описа проблема и ефикасног решења коришћењем бектрекинга. Док тачна одлука не гарантује брзо решавање зона, попуњавање Судокуа користећи алгоритам за тачну одлуку, као што је [[Играјуће везе]], типично решава 9x9 Судоку са минималним мерењем времена одза неколико секунди.
 
=== Исцрпна претрага (груба сила) ===
Неки програмери су направили компјутерске програме који ће решавативрше [[Iscrpna pretraga|исцрпну претрагу]], тј. Грубукористе грубу силу. Иако је утврђено да постоји приближно 6.67 x 1021 преосталих ћелија користећи исцрпну претрагу компјутерски алгоритам може да буде практична метода у решавању слагалица, акоуколико је код добро дизајниран.
 
Предности ове методе су:
Линија 51 ⟶ 46:
* Време решавања углавном није повезано са тежином слагалице
 
Мане ове методе су да је поприлчно спора кад се упореди са компјутерским методама решавања које су осмишљене према [[дедуктив|дедуктивним методама]].
 
Алгоритам “грубе силе” долази до празних ћелија по неком реду, редом их попуњава бројевима који одговарају, или бектрекингом (уклањањем неодговарајућих избора) док не дође до краја. На пример, програм исцрпне претраге ће решити слагалицу уметањем цифре “1” у прву ћелију и проверавањем да ли је дозвољено да се она ту нађе. При проверавању да ли има преступа, сазнаје се да “1” није дозвољено, па се зато вредност повећава на ”2”. Ако се пронађе ћелија где ниједна од 9 цифара није дзвољена, алгоритам оставља ту ћелију празну и враћа се на претходну ћелију. Тада се вредност у тој ћелији повећава за 1. Алгоритам се понавља све док не нађе одговарајуће решење за сву 81 ћелију.<ref>[http://www.geeksforgeeks.org/backtracking-set-7-suduku/ Geeks For Geeks Back Tracking Sudoku Algorithm]</ref><ref>[http://www.norvig.com/sudoku.html]</ref>
Линија 66 ⟶ 61:
 
=== Ограничено програмирање ===
Судоку је ограничен проблем. Судоку као ограничен проблем<ref>[http://4c.ucc.ie/~hsimonis/sudoku.pdf "Судоку као ограничен проблем"]</ref> описује многе разумне алгоритме приступачне у форми ограничења који се могу применити на моделу и решити проблем. Неки модератори ограничења обухватају пример како подесити и решити Судоку проблеме.<ref>[http://jacop.osolpro.com "JaCoP"]</ref><ref>[https://github.com/Rhollor/SudoKuSolver "Sudokusolver"]</ref> Програм ограничења подешавањем и решавањем ће код већине случајева имати мање од 100 редова кода. Ако код користи јак разуман алгоритам, укључивање претраге је потребно само за најтеже слагалице.
 
== Време рачунања ==
Преузето из „https://sr.wikipedia.org/wiki/Алгоритми_за_решавање_судокуа”