Shuffle για slide puzzle

[rafinos]

Καλησπέρα, 

 

έχω ένα array στη javascript το οποίο έχει μέσα n*n τιμές και οι οποίες είναι οι τιμές των κουτιών ενός slide puzzle. 

Αν για παράδειγμα το n = 3 (3*3=9) τότε το array έχει μέσα τις τιμές 

var array = ["1","2',"3","4","5","6","7","8","transparent"];

Εγώ νόμιζα πως με ένα απλό shuffle του πίνακα όλα θα δουλεύουν ρολόι, αλλά τελικά κατάλαβα ότι δεν είναι τελείως σωστό αυτό γιατί πολλές φορές τα puzzles δεν έχουν λύση.

 

Έκανα το shuffle με την παρακάτω συνάρτηση

function shuffle(arr){
	var j, x, i;
	var new_array = arr.slice();
	for (i = new_array.length - 1; i; i--) {
		j = Math.floor(Math.random() * i);
		x = new_array[i - 1];
		new_array[i - 1] = new_array[j];
		new_array[j] = x;
	}
	
	return new_array;
}

To length είναι -1 για να έχω πάντα το transparent τελευταίο.

 

Υπάρχει κάποια λύση που να μου κάνει shuffle (τα κουτάκια) και να είναι σίγουρο πως υπάρχει λύση κάθε φορά;

[Kercyn]

Θα έλεγα να κάνεις x random κινήσεις (που επιτρέπονται προφανώς) μέχρι το παζλ σου να είναι μπερδεμένο. Αλλιώς, κάντο όπως το έχεις τώρα και μετά προσπάθησε να το λύσεις με κάποια συνάρτηση για να δεις αν λύνετε. Αν λύνετε, τότε είναι καλό, αλλιώς ξανά shuffle. Ο δεύτερος τρόπος μου φαίνεται απαίσιος βέβαια αλλά είπα να το βάλω

[rafinos]

Αυτό με τις κινήσεις σκέφτηκα και εγώ απλά μπερδεύομαι κάπως. 

 

Ίσως είναι τελείως λάθος ο τρόπος που το υλοποιώ. Αν θέλεις δες με ποιον τρόπο κινώ τα κουτιά εδώ (μην ανησυχείς παλιότερο θέμα του insomnia είναι). 

[rafinos]

Τελικά το έκανα με "x" μοναδικές-τυχαίες κινήσεις απλά δεν το κάνω με animation... κατά κάποιο τρόπο κουνάω τα κελιά μέσα στον πίνακα με τέτοιο τρόπο όπως κινούνται στο puzzle και φορτώνω το τελικό αποτέλεσμα στον πίνακα.

 

Αλήθεια πόσες από αυτές τις κινήσεις θα ήταν σωστό να κάνω. Ας πούμε το έβαλα να κάνει 1000 αλλά είναι υπερβολικό θαρρώ.

 

Για να σας δώσω ένα παράδειγμα. Σε ένα puzzle 3x3 ανταλλάσσω τη θέση του κελιού με το "κενό" με ένα από τα επιτρεπόμενα κελιά. Αν όμως για παράδειγμα η προηγούμενη κίνηση ήταν να κινηθεί το "κενό" κελί προς τα πάνω, η επόμενη δε γίνεται να είναι να πάει προς τα κάτω. 

[pigeon]

Οταν έχεις ελεύθερο χρόνο:

https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

[alou]

Οπότε στο ήδη υπάρχον shuffle, check τη φόρμουλα και recursion μέχρι να έχεις solvable array.

Εφόσον θες και το transparent πάντα τελευταίο, το condition είναι:  

ζυγό αριθμό inversion για μονό n ||  ζυγό αριθμό n && ζυγό αριθμό inversion.

Το μόνο δύσκολο είναι να βρεις το inversion, θα σε βοηθήσει αυτό 

http://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array-in-javascript

[rafinos]

Οπότε στο ήδη υπάρχον shuffle, check τη φόρμουλα και recursion μέχρι να έχεις solvable array.

Εφόσον θες και το transparent πάντα τελευταίο, το condition είναι:  

ζυγό αριθμό inversion για μονό n ||  ζυγό αριθμό n && ζυγό αριθμό inversion.

Το μόνο δύσκολο είναι να βρεις το inversion, θα σε βοηθήσει αυτό 

http://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array-in-javascript

Ευχαριστώ παιδιά για τις απαντήσεις, αλλά θα το αφήσω ως έχει χωρίς να είναι πάντα τελευταίο το transparent. Αν θέλετε μπορώ να σας δώσω και τον κώδικα του νέου shuffle.