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ď.
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.
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 ;-)
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.
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