Loyd15 - je možné zložiť?

Loyd15 - je možné zložiť?
« kdy: 04. 09. 2015, 12:26:16 »
Zdravím všetkých.

Riešim problém rýchlej konktroly či je hra Loyd15 (https://en.wikipedia.org/wiki/15_puzzle) zložiteľná.
Algoritmus na zloženie implementovaný mám, ale rád by som pomocou neakých pár jednoduchých podmienok zistil či má zmysel ho púšťať, teda či je hra riešiteľná.

Dik za odpoveď.


Pali

Re:Loyd15 - je možné zložiť?
« Odpověď #1 kdy: 04. 09. 2015, 12:59:12 »
Riešiteľnosť overíš tak, že si zrátaš znamienko permutácie. Dokonca to máš popísané aj na tej wiki stránke čo si sem priložil.

Radovan.

Re:Loyd15 - je možné zložiť?
« Odpověď #2 kdy: 04. 09. 2015, 18:51:07 »
Jsou dvě stejně velké skupiny kombinací, jedna se dá složit v pořadí 1,2,...15,16 a druhá 16,1,...14,15. Jestli se prokoušeš QBasicem, samotný test najdeš pod labelem test. A jestli máš QBasic, můžeš si i zahrát ;-)

Kód: [Vybrat]
SCREEN 0
DIM p(16), t$(16)
RANDOMIZE TIMER
FOR a = 1 TO 16: READ t$(a): NEXT a
DATA " 1 "," 2 "," 3 "," 4 "," 5 "," 6 "," 7 "," 8 "," 9 ","1 0","1 1","1 2","1 3","1 4","1 5","   "

rozhazeni:
FOR a = 1 TO 16
cislo: p(a) = INT(RND * 16) + 1
IF a > 1 THEN
 FOR b = 1 TO a - 1
 IF p(a) = p(b) GOTO cislo
 NEXT b
END IF
NEXT a

test: c = 0: d = 16
FOR a = 1 TO 15
FOR b = a + 1 TO 16
IF p(a) > p(b) THEN c = c + 1
NEXT b
IF p(a) = 16 THEN
 d = a
 IF (INT((a - 1) / 4) + a MOD 2) MOD 2 = 0 THEN c = c + 1
END IF
NEXT a
IF (c MOD 2) GOTO rozhazeni
c = 0: PLAY "o2l8db"

pozadi:
COLOR 14, 1: CLS
PRINT
PRINT "     ▄▄▄▄▄          ▄             ▄█▀          ▄    ▄▄"
PRINT "     ██  ██  ▄▄▄▄▄ ██▄▄  ▄▄ ▄▄   ▄▄▄▄▄  ▄▄▄▄▄ ██▄▄  ██  ▄▄  ▄▄▄▄▄"
PRINT "   Lloydova ██▄▄█▀ ██  ██ ██    ██▀ ██ ██  ██ ██     ██    ██▄█▀  ██  ██"
PRINT "     ██     ▀█▄▀██ ▀█▄▄▄ ██  ██ ▀█▄▀██ ▀█▄▄▄▄ ▀█▄▄▄ ██ ▀█▄ ▀█▄▀██"
PRINT : COLOR 7
PRINT "    ╔═══════╦═══════╦═══════╦═══════╗     (C)2000 FARAON"
PRINT "    ║       ║       ║       ║       ║"
PRINT "    ║       ║       ║       ║       ║     Vzor:"
PRINT "    ║       ║       ║       ║       ║    ┌────┬────┬────┬────┐"
PRINT "    ╠═══════╬═══════╬═══════╬═══════╣    │  1 │  2 │  3 │  4 │"
PRINT "    ║       ║       ║       ║       ║    ├────┼────┼────┼────┤"
PRINT "    ║       ║       ║       ║       ║    │  5 │  6 │  7 │  8 │"
PRINT "    ║       ║       ║       ║       ║    ├────┼────┼────┼────┤"
PRINT "    ╠═══════╬═══════╬═══════╬═══════╣    │  9 │ 10 │ 11 │ 12 │"
PRINT "    ║       ║       ║       ║       ║    ├────┼────┼────┼────┤"
PRINT "    ║       ║       ║       ║       ║    │ 13 │ 14 │ 15 │    │"
PRINT "    ║       ║       ║       ║       ║    └────┴────┴────┴────┘"
PRINT "    ╠═══════╬═══════╬═══════╬═══════╣"
PRINT "    ║       ║       ║       ║       ║"
PRINT "    ║       ║       ║       ║       ║"
PRINT "    ║       ║       ║       ║       ║     F1 - Nápověda"
PRINT "    ╚═══════╩═══════╩═══════╩═══════╝"

zobrazeni:
FOR a = 0 TO 3: FOR b = 1 TO 4
LOCATE a * 4 + 9, b * 8 + 7
PRINT t$(p(a * 4 + b))
NEXT b, a
IF c = 0 THEN c = TIMER

poradi:
FOR a = 1 TO 16
IF NOT p(a) = a GOTO hra
NEXT a
c = INT(TIMER - c)
mx:
LOCATE 20, 50
PRINT "Dosažený čas:"; c; "sekund";
c = c MOD 100
a = c MOD 10
IF c < 11 OR c > 14 THEN
 IF a = 1 THEN PRINT "a";
 IF a > 1 AND a < 5 THEN PRINT "y";
END IF
PRINT "."
LOCATE 22, 50
PRINT "Chceš hrát znovu? (A/N)";

fanfara:
PLAY "p8l4cl8egl4o3cp4"
DATA o2l8bal4bp8l8bagfl4ef
DATA

konec: a$ = INKEY$: IF a$ = "" GOTO konec
a$ = LCASE$(a$)
IF a$ = "a" GOTO rozhazeni
IF a$ = "n" THEN GOTO ven
PLAY "l16c"
GOTO konec

hra: a$ = INKEY$: IF a$ = "" GOTO hra
a$ = RIGHT$(a$, 1)
IF a$ = CHR$(27) GOTO esc
IF a$ = ";" GOTO help
IF a$ = "K" AND NOT d MOD 4 = 1 THEN
 p(d) = p(d - 1): d = d - 1
ELSE
 IF a$ = "M" AND d MOD 4 THEN
  p(d) = p(d + 1): d = d + 1
 ELSE
  IF a$ = "H" AND d > 4 THEN
   p(d) = p(d - 4): d = d - 4
  ELSE
   IF a$ = "P" AND d < 13 THEN
    p(d) = p(d + 4): d = d + 4
   ELSE
    PLAY "l16c"
    GOTO hra
   END IF
  END IF
 END IF
END IF
p(d) = 16
PLAY "l64n32"
GOTO zobrazeni

esc:
LOCATE 22, 50
PRINT "Chceš ukončit program? (A/N)"
PLAY "l8n65"
an: a$ = INKEY$: IF a$ = "" GOTO an
a$ = LCASE$(a$)
IF a$ = "a" THEN GOTO ven
IF a$ = "n" THEN
 LOCATE 22, 50
 GOTO pozadi
END IF
PLAY "l16c"
GOTO an

help:
LOCATE 7: PRINT SPACE$(1330)
LOCATE 8, 29: PRINT "Nápověda - návod ke hře:"
LOCATE 9, 28: PRINT STRING$(26, 205)
LOCATE 11, 16: PRINT "Seřaď čísla ve velkém rámečku podle vzoru v malém."
LOCATE 13, 22: PRINT "Posunuj prázdné políčko pomocí šipek."
LOCATE 15, 18: PRINT "Po seřazení čísel program zobrazí dosažený čas"
LOCATE 17, 23: PRINT "a zeptá se, jestli chceš hrát znovu."
LOCATE 19, 9: PRINT "Klávesou Escape můžeš hru ukončit, program si vyžádá potvrzení."
LOCATE 22, 32: PRINT "Stiskni klávesu..."
LOCATE 23, 31: PRINT STRING$(20, 196)
WHILE INKEY$ = "": WEND
GOTO pozadi

ven: COLOR 7, 0: CLS : SYSTEM
REM 14.1

Už si přesně nepamatuji jak to fungovalo, ale mělo by stačit sečíst xory čísla s paritou pole, která je rozmístěná jako na šachovnici. Buď ti na konci vyjde sudá nebo lichá, což určuje do které z těch dvou skupin patříš. Pokud jí chceš změnit, stačí prohodit dvě libovolná stranou sousedící čísla.

Re:Loyd15 - je možné zložiť?
« Odpověď #3 kdy: 08. 09. 2015, 12:39:18 »
Dakujem Radovanovi
Nakoniec som vygeneroval najcistejsie riesenie s minimalnou narocnostou v cistom C takto:

// check if is possible solve it
bool isPossibleSolve(byte loyd[][])
{
  byte sum;
  byte test_array[16];

  for(int y=0; y<4; y++)
    for(int x=0; x<4; x++)
    {
      test_array[y*4+x] = loyd[ x][y];
      // add row of empty
      if( loyd[ x][y] == 0 )
          sum = (3-y);
    }

  // count smaller that I
  for(int i=0; i<16; i++)
  {
    for(int n=i+1; n<16; n++)
      if((test_array[n] < test_array)
      && (test_array[n] != 0 ))
         sum++;
  }

  // is even - then it is no possible
  return (sum % 2)? false: true;
}
// -----------------------------------------------------------------------------

PS: Zdrojaky Loyd15 pre Arduino s TFT displayom som dal sem https://github.com/Trsek/loyd15