Generowanie gry piętnastki - co jest źle?

0

Generuję dynamicznie grę piętnastkę w JavaScript wg zasady:

#Utwórz tablicę od do 15 i potasuj ją losowo.
#Policz parzystość permutacji.
#Zamień pierwsze 2 elementy tablicy, gdy:

  • puste jest zielone pole i permutacja jest nieparzysta
  • puste jest białe pole i permutacja jest parzysta

Wszystko działa, tylko czasami trafia się układ nierozwiązywalny. Co jest źle?

//Shuffle riddle
var i, inv=0, blank=0, tab=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

//Funkcja działa OK, ale zamieszczę ją poniżej
shuffle(tab);

//Check permutation parity
for(i=1; i<16; i++)
{
	if(tab[i] < tab[i-1]) inv++;
	if(tab[i] === 15) blank = i;
}

//Check if game is solvable and fix it
if(blank%2 && !(inv%2) || !(blank%2) && inv%2)
{
	var tmp = tab[1];
	tab[1] = tab[0];
	tab[0] = tmp;
}
function shuffle(a)
{
	for(var i=0,tmp,n,max=a.length-1; i<max; i++)
	{
		n = rand(i+1, max);
		tmp = a[i];
		a[i] = a[n];
		a[n] = tmp;
	}
}
0

Jest nie dobrze kiedy trzeba zrobić wymianę zaś puste pole jest w indeksie 0 lub 1.

0

Już widzę problem. Nie można policzyć koloru blank%2, bo idą tak: Z B Z B B Z B Z Z B Z B B Z B Z.

user image

Ktoś ma pomysł na optymalny wzór? Da się szybciej niż (blank+parseInt(blank/4)) % 2?

0

((blank&3)+(blank>>2))&1 http://ideone.com/0QzvLx
lub:
((blank>>2)^blank)&1 http://ideone.com/CnWojT

0

Kod źle obliczał parzystość permutacji. Mam nadzieję, że teraz będzie dobrze:

var i,j,odd=0,blank=15,tab=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
shuffle(tab);

//Check permutation parity
for(i=0; i<15; i++)
{
	for(j=i+1; j<16; j++)
	{
		if(tab[i] > tab[j]) odd = 1-odd;
	}
	if(tab[i] === 15)
	{
		blank = i
	}
}

//Blank color
var white = parseInt(blank*1.25) % 2;

//Check if game is solvable
if(white ^ odd)
{
	var tmp = tab[0];
	tab[0] = tab[1];
	tab[1] = tmp;
}

Na czacie matematycznym dostałem taki przykład:

parity_preserving_shuffle(array) {
  # Use a Knuth shuffle to give equal chances to each permutation.
  
  odd = false
  for (i=array.length - 1; i >= 0; i--) {
    j = rand(i)
    if (i != j) {
      odd = !odd
      temp = array[i]
      array[i] = array[j]
      array[j] = temp
    }
  }
  
  # This shouldn't have a bias in which even permutations it creates.
  if (odd) {
    random_swap(array)
  }
}

random_swap(array) {
  # There are array.length*(array.length - 1)/2 different swaps.
  # We want to give one equal chance to each of them.
  
  array_length = array.length
  swap_index = rand(array_length*(array_length - 1)/2)
  
  x = floor((sqrt(8*swap_index + 1) + 1)/2)
  y = array_length - x
  
  i = y - 1
  j = y + swap_index - x*(x - 1)/2
  
  temp = array[i]
  array[i] = array[j]
  array[j] = temp
}

Wykorzystuje tasowanie Fisher–Yates. Jest bardziej optymalne, bo mamy tylko 1 pętlę. Czy zawsze po 1 zamianie permutacja jest nieparzysta, po 2 parzysta, po 3 nieparzysta itd? W przypadku mojego kodu parzystość permutacji można policzyć ze wzoru. Zawsze wychodzi nieparzysta. Funkcja shuffle() podana w pierwszym poście. Kod wynikowy:

var i,blank=15,tab=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
shuffle(tab);

//Find blank - niestety spacja < 15
for(i=0; i<15; i++)
{
	if(tab[i] === 15)
	{
		blank = i;
		break
	}
}

//Blank color
var white = parseInt(blank*1.25) % 2;

//Check if game is solvable
if(!white)
{
	var tmp = tab[0];
	tab[0] = tab[1];
	tab[1] = tmp;
}

//Rearrange board
for(i=0, tab[blank]=''; i<16; i++)
{
	rows[parseInt(i/4)].cells[i%4].innerHTML = tab[i].toString(16).toUpperCase();
}
0

Wcześniej grę dało się przejść. Odpalam dzisiaj - układ nierozwiązywalny. Co jest źle?

var rows = $('orderbox').rows;
var i;
var blank = 15; //pozycja pustego pola - początkowo 15
var tab = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]; //tablica
shuffle(tab); //tasowanie tablicy

//Znajdź puste pole - liczba 15 oznacza puste pole
for(i=0; i<15; i++)
{
	if(tab[i] === 15)
	{
		blank = i;
		break
	}
}

//F is blank
tab[blank] = '';

//Kolor pustego pola
//Nie pamiętam, skąd wziął się ten wzór
//Może coś źle przekształciłem i jest przyczyną problemu
var white = parseInt(blank*1.25) % 2;

//Jeśli gra jest nierozwiązywalna, 
//Wcześniej zauważyłem, że nie ma potrzeby badać parzystości
//Permutacja zawsze jest nieparzysta?
if(!white)
{
	var tmp = tab[0];
	tab[0] = tab[1];
	tab[1] = tmp;
}

//Poprzestawiaj liczby w tabeli
for(i=0; i<16; i++)
{
	rows[parseInt(i/4)].cells[i%4].innerHTML = tab[i].toString(16).toUpperCase();
}

//A oto funkcja shuffle()
function shuffle(a)
{
	for(var i=0,tmp,n,max=a.length-1; i<max; i++)
	{
		n = rand(i+1, max);
		tmp = a[i];
		a[i] = a[n];
		a[n] = tmp;
	}
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1