Patnáctka v C + ncurses

Patnáctka (známa též jako Loydova patnáctka podle jejího popularizátora Sama Loyda) je jednoduchý hlavolam, ve kterém musí hráč přesouváním kamenů uvnitř malé čtvercové krabičky tyto kameny seřadit.
Hlavolam sestává z krabičky, do které se vejde 4×4 čtvercových kamenů, místo jednoho kamene je však volné místo, které umožňuje kameny v krabičce posouvat. Na začátku jsou kameny zamíchány, cílem hry je seřadit je podle na nich napsaných čísel či jiného označení.

Původní nástin na zápočťák, než jsem měl lepší zadání.
Je tam základní nástin auto-solveru, žádná heuristika nebo tak. Nejdřív jednoduché pozice (první dva sloupce v prvních dvou řádcích), pak vyřešit přechod na nižší řádek a nakonec rošády v posledních dvou.
Pro kompilaci je potřeba mít ncurses a tohle by mělo fungovat: gcc -l ncurses curses.c

Stáhnout zdroj

 
#include <time.h>
#include <curses.h>
 
char k, l, zeroi, zeroj, lastzeroi, lastzeroj;
int i, j, input;
int doloop = 1;
int numbers[4][4];
static WINDOW *mainwnd;
static WINDOW *screen;
WINDOW *my_win;
 
/**
 * Inicializace obrazovky pro ncurses
*/
void screen_init()
{
	mainwnd = initscr();
	noecho();
	cbreak();
	nodelay(mainwnd, false); // getch() zastavi beh a ceka na vstup
	refresh();
	keypad(mainwnd, true); // Poslouchat vsechny klavesy
	wrefresh(mainwnd);
	screen = newwin(15, 75, 1, 1); // rozmery aktivniho okna
}
 
/**
 * Vykreslení stavu hry
*/
static void update_display()
{
	curs_set(0);
	mvwprintw(screen,1,1,"+---+---+---+---+");
	mvwprintw(screen,2,1,"|%3d|%3d|%3d|%3d|     Princip hry \"Patnact\" je presunout cisla", numbers[0][0], numbers[0][1], numbers[0][2], numbers[0][3]);
	mvwprintw(screen,3,1,"+---+---+---+---+     do spravneho poradi s prazdnym polem");
	mvwprintw(screen,4,1,"|%3d|%3d|%3d|%3d|     vpravo dole.", numbers[1][0], numbers[1][1], numbers[1][2], numbers[1][3]);
	mvwprintw(screen,5,1,"+---+---+---+---+     Hra se ovlada pomoci sipek klavesnice.");
	mvwprintw(screen,6,1,"|%3d|%3d|%3d|%3d|", numbers[2][0], numbers[2][1], numbers[2][2], numbers[2][3]);
	mvwprintw(screen,7,1,"+---+---+---+---+     (n) - Nova hra");
	mvwprintw(screen,8,1,"|%3d|%3d|%3d|%3d|     (h) - Napoveda", numbers[3][0], numbers[3][1], numbers[3][2], numbers[3][3]);
	mvwprintw(screen,9,1,"+---+---+---+---+     (z) - Zpet posledni krok");
	mvwprintw(screen,10,23,"(r) - Resitelna hra?");
	mvwprintw(screen,11,23,"(q) - Konec hry");
 
	// Nevykreslujeme nulu, ale mezeru
	mvwprintw(screen, (zeroi+1)*2, (zeroj+1)*4, " ");
 
	wrefresh(screen);
	refresh();
}
 
/**
 * Vyčístí okno
*/
void screen_end()
{
	endwin();
}
 
/**
 * Vygeneruje čistou (vyřešenou) herní desku
*/
void clean_board()
{
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 4; j++)
		{
			numbers[i][j] = j + 4*i + 1;
		}
	}
 
	numbers[3][3] = 0;
	zeroi = zeroj = lastzeroi = lastzeroj = 3;
 
	/* Priklad neresitelneho rozloeni
	numbers[3][2] = 14;
	numbers[3][1] = 15; */
}
 
/**
 * Je vyřešená hra?
*/
int is_solved()
{
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 4; j++)
		{
			if (numbers[i][j] != j + 4*i + 1 && !(i == 3 && j == 3))
			{
				return 0; // Nějaké číslo nesedí - není vyřešeno
			}
		}
	}
 
	// Už zbyla jen možnost, že je hra vyřešena
	return 1;
}
 
/**
 * Zjistí, jestli je úloha řešitelná
 *
 * @return int 0 pokud není, 1 pokud řešitelná je
*/
int is_solvable()
{
	int parity = 0; // parita permutace
 
	// Loop je osklivy, ale potrebuju projit vsechny policka
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 4; j++)
		{
			for (k = 0; k <= i; k++)
			{
				for (l = 0; l < 4; l++)
				{
					if ((i != k || l < j) && numbers[i][j] != 0 && numbers[k][l] > numbers[i][j])
					{
						parity++;
					}
				}
			}
		}
	}
 
	// Pokud je radek s nulou sudy, pridame jedna
	if (zeroi % 2 == 0)
	{
		parity++;
	}
 
	// Hra je resitelna pri sude parite ( 0 ... licha; 1 ... suda )
	return (parity + 1) % 2;
}
 
/**
 Přesune bílé místo nahoru
*/
void move_up()
{
	if (zeroi > 0)
	{
		numbers[zeroi][zeroj] = numbers[zeroi - 1][zeroj];
		numbers[zeroi - 1][zeroj] = 0;
		lastzeroi = zeroi;
		zeroi -= 1;
	}
}
 
/**
 Přesune bílé místo doprava
*/
void move_right()
{
	if (zeroj < 3)
	{
		numbers[zeroi][zeroj] = numbers[zeroi][zeroj + 1];
		numbers[zeroi][zeroj + 1] = 0;
		lastzeroj = zeroj;
		zeroj += 1;
	}
}
 
/**
 Přesune bílé místo dolu
*/
void move_down()
{
	if (zeroi < 3)
	{
		numbers[zeroi][zeroj] = numbers[zeroi + 1][zeroj];
		numbers[zeroi + 1][zeroj] = 0;
		lastzeroi = zeroi;
		zeroi += 1;
	}
}
 
/**
 Přesune bílé místo doleva
*/
void move_left()
{
	if (zeroj > 0)
	{
		numbers[zeroi][zeroj] = numbers[zeroi][zeroj - 1];
		numbers[zeroi][zeroj - 1] = 0;
		lastzeroj = zeroj;
		zeroj -= 1;
	}
}
 
void generate_puzzle()
{
	clean_board();
 
	const int NUM_STEPS = 300; // Počet tahů, kterým "rozbijeme" úvodní scénář
	srand((unsigned int)time(NULL));
	for (i = 0; i < NUM_STEPS; i++)
	{	
		j = rand() % 4;
		switch(j)
		{
			case 0: move_up(); break;
			case 1: move_down(); break;
			case 2: move_left(); break;
			case 3: move_right(); break;
		}
	}
}
 
/**
* Vrátí cílovou polohu čísla pro správné řešení (řádek)
* @param int number
* @return char Číslo řádky
*/
char get_target_pos_row(int number)
{
	return (number - 1) / 4;
}
 
/**
* Vrátí cílovou polohu čísla pro správné řešení (sloupec)
*
* @param int number
* @return char Číslo sloupce
*/
char get_target_pos_col(int number)
{
	return (number - 1) % 4;
}
 
void wait_after_move()
{
	update_display();
	sleep(1);
}
 
/**
* Přesune čísla, která jdou jednoduchým posunutím na jejich správná místa (1,2,5,6)
*
* @param char row Současný řádek prvku
* @param char col Současný sloupec prvku
* @param char target_row Cílový řádek prvku
* @param char target_col Cílový sloupec prvku
*/
void move_simple_to_target_pos(char row, char col, char target_row, char target_col)
{
	if (col < zeroj)
	{
		for (i = 0; i < zeroj - col; i++)
		{
			move_left();
			wait_after_move();
		}
	}
 
	if (col > zeroj)
	{
		for (i = 0; i < col - zeroj; i++)
		{
			move_right();
			wait_after_move();
		}
	}
 
	// Je prázdné políčko a políčko k přesunutí na stejném řádku?
	if (zeroi != row)
	{	
		char movement = row - zeroi;
		if (movement < 0)
		{
			for (i = 0; i < -1 * movement; i++)
			{
				move_up();
				wait_after_move();
			}
		}
		else
		{
			for (i = 0; i < movement; i++)
			{
				move_down();
				wait_after_move();
			}
		}	
	}
 
}
 
int find_row(char number)
{
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 4; j++)
		{	
			// Našli jsme ho, dáme ho tedy na správné místo
			if (numbers[i][j] == number)
			{
				return i;
			}
		}
	}
}
 
int find_col(char number)
{
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 4; j++)
		{	
			// Našli jsme ho, dáme ho tedy na správné místo
			if (numbers[i][j] == number)
			{
				return j;
			}
		}
	}
}
 
/**
* Automat pro řešení hádanky
*/
void solve_puzzle()
{
	if (is_solved())
	{
		return;
	}
 
	char target_row, target_col;
 
	nodelay(mainwnd, true);
 
	// Postupne vyresit kazde policko
	for (k = 1; k < 16; k++)
	{
		i = find_row(k);
		j = find_col(k);
		target_row = get_target_pos_row(k);
		target_col = get_target_pos_col(k);
 
		printf("%d: %d/%d %d/%d", k, i, j, target_row, target_col);
		if (i == target_row && j == target_row)
		{
			continue;
		}
 
		// Jednoduché přímočaré případy, je potřeba jen dostrkat číslo na jeho místo
		if (k == 1 || k == 2 || k == 5 || k == 6)
		{
			mvwprintw(screen, 14, 1, "Presouvam %d", k);
			move_simple_to_target_pos(i, j, target_row, target_col);
		}
 
	}
 
	//mvwprintw(screen, 12, 1, "Hra byla uspesne vyresena");
 
	nodelay(mainwnd, false);
}
 
int main()
{
 
	// Vygeneruje čistou hru, aktivuje obrazovku a vykreslí první situaci
	clean_board();
	screen_init();
	update_display();
 
 
	// Čeká na vstup dokud uživatel neukončí program (q)
	while (doloop)
	{
		// Reset zpravy (napr. resitelnost)
		mvwprintw(screen, 11, 1, "%40s", "");
 
		input = getch();
		switch (input)
		{
			case 113: // (q) konec programu
			case 81:
				doloop = 0;
			break;
 
			case KEY_UP:
				move_up();
			break;
 
			case KEY_RIGHT:
				move_right();
			break;
 
			case KEY_DOWN:
				move_down();
			break;
 
 
			case KEY_LEFT:
				move_left();
			break;
 
			case 122: // (z) - zpet jeden krok
			case 90:
				numbers[zeroi][zeroj] = numbers[lastzeroi][lastzeroj];
				numbers[lastzeroi][lastzeroj] = 0;
				zeroj = lastzeroj;
				zeroi = lastzeroi;
			break;
 
			case 78: // (n) - nova hra
			case 110:
				generate_puzzle();
			break;
 
			case 83: // (s) - vyresit puzzle
			case 115:
				solve_puzzle();
			break;
 
			case 82: // (r) - ma hra reseni?
			case 114:
				if (is_solvable())
				{
					mvwprintw(screen, 11, 1, "Hra je resitelna");
				}
				else
				{
					mvwprintw(screen, 11, 1, "Hra nema reseni");
				}
				if (is_solved())
				{
					mvwprintw(screen, 12, 1, "Hra je vyresena");
				}
				else
				{
					mvwprintw(screen, 12, 1, "Hra neni vyresena");
				}
 
			break;
		}
 
		update_display();
	}
 
	screen_end();
}

Kategorie

Odkazy

Patnáctka v C + ncurses

Máte k článku co říct?