Algoritëm për zgjidhjen e lojës Sudoku

[soft-master]

A di ndonjeri ndonje algoritem per te zgjidhur nje sudoku? Dmth, kompjuterit ti jepet nje Variable ne formen Array, dhe pastaj kompjuteri ta zgjidhe kete. Po e theksoj edhe nje here qe dua thjesht ca info per ndonje algoritem te vlefshem, nuk ka rendesi gjuha e programimit. ju jam mirenjohes nese dikush me ndihmon pak...

[Borix]

Ekzistojne dy lloje algoritmesh: Algoritmet Evolucionare dhe ato deterministike. Per te paren, mund te merresh nese ke njohuri te avancuara. Per te dyten, duhet te dish nje fakt interesant, pastaj mund te besh algoritme sa te duash: http://www-imai.is.s.u-tokyo.ac.jp/~...sterThesis.pdf

[josif]

Ekzistojne dy lloje algoritmesh: Algoritmet Evolucionare dhe ato deterministike. Per te paren, mund te merresh nese ke njohuri te avancuara. Per te dyten, duhet te dish nje fakt interesant, pastaj mund te besh algoritme sa te duash: http://www-imai.is.s.u-tokyo.ac.jp/~...sterThesis.pdf

Duhet qe personi qe e kerkon te jete i qarte rreth kerkesave:

Nese kerkon nje zgjidhje cfaredo do te mjaftonte edhe nje algoritem brute-force.

Borix, sikur Soft-master te kishte njohuri nga algoritmat evolucionare, do te ishte i afte ta zgjidhte nje problem sudoku pa shume probleme, keshtu qe te jemi realiste kur japim keshilla.


Menyra me e thjeshte eshte te kerkosh nje zgjidhje te tipit "constraint satisfaction problem" te alternuar me backtracking, nje kategori elementare kerkimi ne Artificial Intelligence. Personalisht kam ndertuat para rreth nje viti e ca, nje program qe zgjidhte lojen sudoku duke perdorur kete teknike.

referenca: aima.cs.berkeley.edu/newchap05.pdf

[soft-master]

Kete MasterThesis e lexova por mesa kuptova une shpjegimi ne kete teze nuk ishte i perqendruar shume pas sudokut. Edhe brute-force do me kryente pune, por problemi eshte se rendimenti eshte i ulet. Koha per ta zgjidhur me brute-force esht e madhe. Ose me sakte, duhen disa minuta per ta zgjidhur. Gjithsesi, detyra qe kam un per te bere ne shkolle eshte per ta bere zgjidhjen ne assembly. Dhe meqe assembly punon shpejt, mbase edhe brute-force mund te kryente pune. Nese dini dicka te pershtatshme per kete, do e mireprisja.

[josif]

Kete MasterThesis e lexova por mesa kuptova une shpjegimi ne kete teze nuk ishte i perqendruar shume pas sudokut. Edhe brute-force do me kryente pune, por problemi eshte se rendimenti eshte i ulet. Koha per ta zgjidhur me brute-force esht e madhe. Ose me sakte, duhen disa minuta per ta zgjidhur. Gjithsesi, detyra qe kam un per te bere ne shkolle eshte per ta bere zgjidhjen ne assembly. Dhe meqe assembly punon shpejt, mbase edhe brute-force mund te kryente pune. Nese dini dicka te pershtatshme per kete, do e mireprisja.

http://www.techfinesse.com/game/sudoku_solver.php

[soft-master]

Faleminderit josif per linkun, por tek ky kodi ne C jane 1660 rreshta program. Dmth, do ishte shume e veshtire per ta kthyer kete lloj algoritmin ne assembly*. Une ne fakt, mendova nje zgjidhje me brack-tracking, dmth, nese gjate provave,qe ben programi per ta zgjidhur, ngec diku, atehere kthehet mbrapsht dhe provon nje vlere tjeter per kutine paraardhese. Dhe kjo nuk eshte shume e veshtire per tu hedhur ne kod assembly. Kjo zgjidhje eshte lloji i brute-force.
Do te doja te dija nese ka nje algoritem tjeter, disi me te pershtatshem per ta programuar ne Assembly...


*Pasi kete detyre per zgjidhjen e sukokut e kam ne lenden Assembly.

[Force-Intruder]

Mbase mundte doje ti hidhje nje sy kesaj...? ASM natyrisht :

http://coding.derkeiler.com/Archive/.../msg00077.html

[gimi_sky]

soft-master nese e ke programu me brute-force, provo qe secilen fushe qe e mbushe menjeher ta kontrollosh.. Algoritmi im (ne java) gjen zgjidhjen ne me pak se nje sekond.. Dhe perdor nje array dydimenzional - e ben kodin me te lexueshem..

agimi

[josif]

Faleminderit josif per linkun, por tek ky kodi ne C jane 1660 rreshta program. Dmth, do ishte shume e veshtire per ta kthyer kete lloj algoritmin ne assembly*. Une ne fakt, mendova nje zgjidhje me brack-tracking, dmth, nese gjate provave,qe ben programi per ta zgjidhur, ngec diku, atehere kthehet mbrapsht dhe provon nje vlere tjeter per kutine paraardhese. Dhe kjo nuk eshte shume e veshtire per tu hedhur ne kod assembly. Kjo zgjidhje eshte lloji i brute-force.
Do te doja te dija nese ka nje algoritem tjeter, disi me te pershtatshem per ta programuar ne Assembly...


*Pasi kete detyre per zgjidhjen e sukokut e kam ne lenden Assembly.

atehere gjenero dosjen objekt duke compiluar programin ne C. pastaj des-asembloje dhe shef kodin ne asembli. mund te perdoresh "objdump -d" ne sistemet unix.

[soft-master]

Ju faleminderit per ndihmen. Detyren kam filluar ta bej. Deri tani po ec mire. Jam duke perdorur backtracking. Po shoh njehere apo perfundon me sukses apo jo.