n-queens problem in Μatlab{Please Help!}

[rania12]

Γεια σας!εχω μια εργασια στην Μαtlab που αφορά το πρόβλημα των ν-βασσιλισσών στο σκάκι,που ειναι ευρέως γνωστό ως το n-queens problem.Στο πρόβλημα αυτό πρέπει ο χρήστης δίνοντας όποια τιμή θέλει στο n, ώστε να δημιουργείτε μια σκακιέρα ανάλογων διαστάσεων,π.χ. 8*8 ή 23*23 το πρόγραμμα να του τοποθετεί τις βασσίλισες έτσι ώστε η κάθε βασσίλισσα να μην απειλεί την άλλη,δηλαδή να μην βρίσκονται 2 βασσίλισσες στην ίδια κάθετο,στήλη ή διαγώνιο.Μέσα στο πρόγραμμα αυτό πρεπει να εμφανίζεται και η καταλλήλων διαστάσεων σκακιέρα κάθε φορά με την χρήση γραφικών.Αν καποιος εχει κανει την εργασία σε Μαtlab ,αν μπορεί να μου την στείλει. Ή αν καποιος ξερει να χειρίζεται την Μαtlab και μπορεί να μου στείλει κάποια ιδέα του για την λύση θα με βοηθούσε πολύ!Ευχαριστώ εκ των προτέρων!

[eirinikp]

http://www.csd.uoc.gr/~hy215/GetStartWithMATLAB.pdf

 

Twra esu 8es tin askisi lumeni... Ti na sou pw... An sti dwsei kapoios lumeni, otan se e3etasei o ka8igitis ti 8a tou peis oti ekanes?

 

3ekina kalutera kai rwta opou kollas...

[rania12]

euxaristw gia ton odigo tou Matlab pou mou esteiles!Tha to diabasw kai tha ksekinisw tin ergasia.Den zitaw tin ergasia etoimi apo kapoion pou den tin exei.Aplws an kapoios tin exei idi etoiomi kai einai prothumos na mou tin steilei tha katsw na tin diabasw kai fusika na kanw tis aparaitites allages.Apla epeidi afenos eimai arxaria stin Matlab ki afeterou epeidi den exw brei akomi ton algorithmo pou prepei na xrisimopoiisw sto problima zitaw boithia. Kai pali thanks ki oson afora to programma tha akolouthisw tin sumbouli sou!

[Directx]

Για matlab δεν ξέρω, όμως πριν αρκετό καιρό είχα υλοποιήσει τον παρακάτω αλγόριθμο της Wikipedia σε C++ & VCL , τα βήματα είναι πολύ λογικά και εύκολα στον προγραμματισμό τους για κάθε γλώσσα οπότε ρίξε μια ματιά εδώ http://en.wikipedia.org/wiki/N-queens (βλέπε Constructing a solution).

[eirinikp]

Gia na skefteis pws 8a luseis to problima sou, prospa8ise na to spaseis se mikrotera problimatakia. (Diairei kai basileue!)

Ylopoiise arxika to programma gia mia mono diastasi (opoia sou aresei!)

Asxolisou 3exwrista me oles tis pi8anes periptwseis stis opoies mia basilissa apeilei tin alli.

Meta asxolisou 3exwrista me to pws kaneis grafika se mia skakiera. (Egw protimw na asxoloumai sto telos me grafika)

Kai sto telos prospa8ise na to kaneis na allazei tis diastaseis analogws me to ti zitaei o xristis.

Proxwra bima bima kai sigoura 8a ta katafereis!

 

( O sundesmos tou Directx apo oti blepw sigoura 8a sou fanei polutimos...)

[rania12]

Euxaristw polu!tha ksekinisw sumfwna me tis odigies pou mou dwsate ki opou antimetwpisw problima tha sas rwtisw.Aurio logika tha exete nea mou.euxaristw polu gia to endiaferon!

[FarCry]

O algorithmos einai aplos. I pio apli lisi einia me backtracking. Fisika gia megala N iparxei problima giati to plithos ton sindiasmon ginetai terastio

 

Me apla logia topotheteis ti proti basillisa kai proxoras. Dokimazeis oles tis epomenes liseis mexri na breis ekei pou den exei dieneksi. Otan xtipisei kapou pas piso mexri to simeio pou itan xoris ploblima kai koitas allo sindiasmo. Des to os dentra me kombous kai fila. Mia DFS ilopoiisi pou panta briskei lisi kai telos

 

http://www.cosc.canterbury.ac.nz/mukundan/dsal/NQP.html

 

Edo tha deis patontas to animated button pos psaxnei o DFS. Auto pou kanei einai mia eksantlitiki anazitisi se olo to dentro giauto an to N einai megalo tote tha exeis problima kai prepei na breis pio efficient methodous.

 

The amount of time required to find all solutions for any order N is roughly proportional to N Factorial. It took over 11 days to get the results for N = 20. If we increase N to 21, it would take about 4 months for the program to run. For higher orders of N, the problem has to be broken into parts with each part delegated to a separate computer. Thus, dozens and more likely, hundreds of computers are needed to solve problems with N in the low 20's. With present computing power, it is unlikely that the total number of solutions will be found when N equals 30 or higher.

 

Giauto prosekse ti N tha baleis

 

PS: proteino na exeis dinato PC gia ta calculations

[Directx]

Σε μια παλιά λύση backtrack ενός ανάλογου προβλήματος (τοποθέτηση αριθμών σε πίνακα ΝχΝ με βάση συγκεκριμένους κανόνες απόκλισης) είχα διαπιστώσει πως η χρήση Quick-Sort στις δομές του backtrack (ώστε να τοποθετηθούν πρώτες οι θέσεις που είχαν μια πιθανότητα επίλυσης του προβλήματος σε σχέση με άλλες) αύξησε ως το 40x40 πολύ ικανοποιητικά την ταχύτητα της λύσης αλλά ως εκεί καθώς για πίνακες 41x41 κτλ.. χρειαζότανε κάτι "άλλο" από QSort..

[FarCry]

Gia to problima ton bassilison an deis kai sto net to megisto pou exoun brei einai gia to N=23

 

[rania12]

Geia sas!Prwta apo ola euxaristw gia tis sumboules sas!tis elaba upopsin mou.Ksekinisa na grafw to programma ki antimetwpizw to eksis problima:

sigkerimena grafw ston Matlab Debugger thelontas na mou bgalei sto kenriko parathuro tin entoli na dwsw timi gia to n lambanontas upopsin tou to programma tous parakatw periorismous gia to x{while x<=0 | x=2 | x=3}.To programmataki einai to akoloutho.Mipws mporei kapoios na mou pei pou einai to lathos kai pws prepei na to grapsw gia na leitourgei?Epipleon pws mporw na grapsw ton periorismo oti to n prepei na einai mono akeraios{auto epeidi den tognwrizw den to exw sumperilabei sto parakatw programma}.To programma einai to eksis:

R=input('give value n');

while x<=0 | x=2 | x=3

R=input('give value n');

disp('n')

end

 

thanks!

[eirinikp]

R=input('give value n');

while x<=0 | x==2 | x==3

R=input('give value n\n');

disp('n')

end

 

Kalutera twra?

 

Gia na apofeugeis na grafeis genika ti sun8iki x=2 enw 8es na grafeis x==2, prospa8ise na suni8iseis na to grafeis 2==x, opote an kamia fora 3exasteis kai grapseis 2=x 8a sou xtupisei la8os o compiler!

[eirinikp]

Oso gia ton int pou 8eleis na dilwseis, apo oti eida sto matlab egrafe to parakatw:

 

"MATLAB does not require any type declarations or dimension statements. When MATLAB encounters a new variable name, it automatically creates the variable and allocates the appropriate amount of storage"

 

Opote pws na elegxeis an mia timi einai akeraia?

Gia des uparxei kamia sunartisi pou na sou epistrefei to akeraio meros enos ari8mou? An nai tote o ari8mos x einai akeraios an i diafora tou apo to akeraio tou meros einai 0.

An de breis kamia tetoia sunartisi sto Matlab pes gia na doume ti allo mporoume na kanoume

[FarCry]

eukolo einai. pairneis to mod 2 kai elegxeis an einai 0,1. allios einai real