15 puzzle written in C+asm as an university course project (early 2014).

15puzzle.c

/*
15Puzzle.c - 15 Puzzle Windowsi konsoolis
2014 Indrek Ardel
*/

#include <stdio.h>
#include <conio.h>
#include <Windows.h>
#include <time.h>
#include <string.h>

// Kasti joonistamise märgid (Windows)
#define  BOX_SLR      "\304"  /* ─ */
#define  BOX_SUD      "\263"  /* │ */
#define  BOX_SUL      "\331"  /* ┘ */
#define  BOX_SUR      "\300"  /* └ */
#define  BOX_SDL      "\277"  /* ┐ */
#define  BOX_SDR      "\332"  /* ┌ */
#define  BOX_SULR     "\301"  /* ┴ */
#define  BOX_SDLR     "\302"  /* ┬ */
#define  BOX_SUDL     "\264"  /* ┤ */
#define  BOX_SUDR     "\303"  /* ├ */
#define  BOX_SUDLR    "\305"  /* ┼ */

// Konsooli teksti värvid
// Raam
#define FRAME 7
// Paaritud arvud
#define NUM_ODD 3
// Paarisarvud
#define NUM_EVEN 7

// Täpitähed (väikesed)
#define AUML "\204"
#define OUML "\224"
#define OTILDE "\344"
#define UUML "\201"

// Klahvide _getch väärtused
enum KEYS {
	UP = 72,
	DOWN = 80,
	LEFT = 75,
	RIGHT = 77,
	ESC = 27
};

// Pide konsooliakna sisu manipuleerimiseks
HANDLE hConsole;

// Muudab kirjutatava teksti värvi
void setColor(int color)
{
	SetConsoleTextAttribute(hConsole, color);
}

// Liigutab tekstikursorit konsooliaknas
void setPos(int x, int y)
{
	COORD c;
	c.X = x;
	c.Y = y;
	SetConsoleCursorPosition(hConsole, c);
}

// Mänguväljaku ning tema lahendatud versiooni massiiv. Viimast on tarvis, et neid oleks võimalik kiiresti võrrelda.
static int area[16], solved[16];

// Kontrollib, kas 'area' ja 'solved' on omavahel võrdsed.
int isSolved()
{
	return memcmp(area, solved, sizeof(area)) == 0;
}

/* Kontrollib, kas mäng on lahendatav.
   Lisainfot:
   http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
   http://www.brian-borowski.com/Software/Puzzle/
*/
int isSolvable(int* state)
{
	/* Disassembly näitab, et Proloog ja EBX, ESI, EDI pushimine tehakse juba meie eest ära - ei näe mõtet seda 2x teha. */
	__asm
	{
		xor		esi, esi // inversions = 0
		mov		edx, dword ptr [state] // edx = state

		xor		ecx, ecx // i = 0
	loop_a:
		mov		eax, dword ptr [edx + type int * ecx] // eax = state[i]
		cmp		eax, 0 // state[i] == 0
		je		zero
		// state[i] != 0
		mov		ebx, ecx // j = i 
		push	ecx // ecx hakkab ajutiselt hoidma state[j]
	loop_b:
		inc		ebx // j++
		cmp		ebx, 16 // ebx < 16?
		jge		loop_b_end
		mov		ecx, dword ptr [edx + type int * ebx] // ecx = state[j]
		cmp		ecx, 0 // state[j] != 0
		je		loop_b
		cmp		ecx, eax // state[j] < state[i]
		jge		loop_b
		inc		esi // inversions++
		jmp		loop_b
	loop_b_end:
		pop		ecx // taastame ecx = i
		jmp		endzero
	zero: // eax == 0
		// eax-i võib ära risustada, sest see väärtustatakse järgmine tsükli samm uuesti
		push	edx
		push	ecx

		// inversions += (1 + i / 4);
		xor		edx, edx // edx = 0, jagamise jaoks
		mov		eax, ecx // eax = ecx = i
		mov		ecx, 4 // ecx = 4
		idiv	ecx // eax /= ecx (4)
		inc		eax // eax++
		add		esi, eax // inversions += eax

		// taastame ecx, edx, eax algsed väärtused
		pop		ecx
		pop		edx
	endzero: // endif (state[i] == 0)
		inc		ecx // i++
		cmp		ecx, 16 // i < 16?
		jl		loop_a

		// Tsüklist väljas
		and		esi, 1 // inversions %= 2 
		xor		esi, 1 // inversions = !inversions
		mov		eax, esi // return inversions
	}

	/* C kood:
	int inversions = 0;
	for (int i = 0; i < 16; i++)
		if (state[i] == 0)
			inversions += 1 + (i / 4);
		else
			for (int j = i + 1; j < 16; j++)
				if (state[j] != 0 && state[j] < state[i])
					inversions++;

	return inversions % 2 == 0;*/
}

// Vahetab x ja y väärtused omavahel ära
void swap(int *x, int *y) {
	__asm {
		mov		eax, x // eax = x asukoht
		mov		ebx, y // ebx = y asukoht
		mov		ecx, [eax] // ecx = x väärtus
		mov		edx, [ebx] // edx = y väärtus
		mov		[eax], edx // x asukohta, y väärtus
		mov		[ebx], ecx // y asukohta, x väärtus
	}
}

// Massiivi elementide ärasegamine
// http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
void shuffle(int* arr, int sz)
{
	__asm
	{
		mov		ecx, [sz] // ecx = i = sz (üldjuhul 16)
	mloop:
		dec		ecx // i--
		cmp		ecx, 0 // i > 0 ?
		jle		endloop

		// Põhjus selle järgi selgub hiljem
		push	ecx // Push A
		push	ecx // Push B
		push	ecx // Push C

		// j = rand() % (i + 1); => m = rand(); k = i; k++; j = m % k;
		call	rand // eax = m = rand()
		pop		ecx  // Pop C (call-ist taastumine); k = i
		inc		ecx // (i+1) ehk k++

		xor		edx, edx // jagamise jaoks edx = 0
		idiv	ecx // eax / ecx = m / k	[edx = j = m % k]
		pop		ecx // Pop B (ecx = i); äkki on decrement parem siin?

		/* swap(&array[i], &array[j]); */
		mov		eax, dword ptr [arr] // eax-is on arr asukoht
		imul	ebx, edx, type int // j väärtuse asukoha ja array alguse asukoha vahe
		add		eax, ebx // eax = arr[j] asukoht
		push	eax // Pushime swap jaoks teise argumendi

		mov		eax, dword ptr [arr] // eax-is on uuesti arr asukoht
		imul	ebx, ecx, type int // i väärtuse kaugus array asukoha algusest
		add		eax, ebx // eax = arr[i] asukoht
		push	eax // swap-i esimene argument

		call	swap // Teeme swapi

		pop		eax // Võtame argumendid ära
		pop		eax
		pop		ecx // Pop A (ecx = i, sest call risustas ära)

		jmp		mloop // Ja nüüd uuesti
	endloop:
	}
	/*
	Funktsioon C-s.
	int j;
	for (int i = sz - 1; i > 0; i--)
	{
		j = rand() % (i+1);
		swap(&array[i], &array[j]);
	}
	*/
}

// Valib vastavalt arvu väärtusele värvi ning trükib selle arvu ekraanile
void drawNumber(int n)
{
	if (n % 2 == 0)
		setColor(NUM_EVEN);
	else
		setColor(NUM_ODD);

	if (n == 0)
		printf("  ");
	else
		printf("%2d", n);

	setColor(FRAME);
}

// Viib kursori ruudu 'pos' asukohta ning kirjutab sinna 'area[pos]' väärtuse
void drawSquare(int pos)
{
	int x = 31 + (pos % 4) * 5;
	int y = 9 + (pos / 4) * 2;
	setPos(x, y);
	drawNumber(area[pos]);
}

// Vahetab kahe ruudu väärtused ning värskendab seisu ekraanil
void swapSquares(int* area, int a, int b)
{
	swap(&area[a], &area[b]);
	drawSquare(a);
	drawSquare(b);
}

/*
Joonistatakse selline kast:
╔════╦════╦════╦════╗
║  1 ║  2 ║  3 ║  4 ║
╠════╬════╬════╬════╣
║  5 ║  6 ║  7 ║  8 ║
╠════╬════╬════╬════╣
║  9 ║ 10 ║ 11 ║ 12 ║
╠════╬════╬════╬════╣
║ 13 ║ 14 ║ 15 ║ 16 ║
╚════╩════╩════╩════╝

Arvude 1-16 asemel on massiivi 'area' väärtused
Pole just kõige loetavam (vabandan selle pärast), aga koodi kuju on enam-vähem sama, mis ruudustik muidu oleks.
*/
void drawGame(int* area)
{
	setColor(FRAME);
	setPos(29, 8);
	printf(BOX_SDR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SDL);
	setPos(29, 9);
	printf(BOX_SUD " "); drawNumber(area[0]); printf(" " BOX_SUD " "); drawNumber(area[1]); printf(" " BOX_SUD " "); drawNumber(area[2]); printf(" " BOX_SUD " "); drawNumber(area[3]); printf(" " BOX_SUD);
	setPos(29, 10);
	printf(BOX_SUDR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDL);
	setPos(29, 11);
	printf(BOX_SUD " "); drawNumber(area[4]); printf(" " BOX_SUD " "); drawNumber(area[5]); printf(" " BOX_SUD " "); drawNumber(area[6]); printf(" " BOX_SUD " "); drawNumber(area[7]); printf(" " BOX_SUD);
	setPos(29, 12);
	printf(BOX_SUDR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDL);
	setPos(29, 13);
	printf(BOX_SUD " "); drawNumber(area[8]); printf(" " BOX_SUD " "); drawNumber(area[9]); printf(" " BOX_SUD " "); drawNumber(area[10]); printf(" " BOX_SUD " "); drawNumber(area[11]); printf(" " BOX_SUD);
	setPos(29, 14);
	printf(BOX_SUDR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDLR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUDL);
	setPos(29, 15);
	printf(BOX_SUD " "); drawNumber(area[12]); printf(" " BOX_SUD " "); drawNumber(area[13]); printf(" " BOX_SUD " "); drawNumber(area[14]); printf(" " BOX_SUD " "); drawNumber(area[15]); printf(" " BOX_SUD);
	setPos(29, 16);
	printf(BOX_SUR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SULR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SULR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SULR BOX_SLR BOX_SLR BOX_SLR BOX_SLR BOX_SUL);
	printf("\n");
}

int main(int argc, char* argv[])
{
	// Juhuslike arvude seemendamine
	srand((unsigned int)time(NULL));

	// Konsooli pide väärtustamine
	hConsole = GetStdHandle(STD_OUTPUT_HANDLE);

	// Peidetakse mängija eest ära tekstikursor
	CONSOLE_CURSOR_INFO curInf;
	curInf.bVisible = 0;
	curInf.dwSize = 1;
	SetConsoleCursorInfo(hConsole, &curInf);

	// Konsooliakna suuruse fikseerimine ja puhtakstegemine
	system("mode 80, 25 & cls");

	// Tutvustav tekst
	printf("15-puzzle\n");
	printf("2014 Indrek Ardel\n\n");
	printf("Genereeriti juhuslik (aga lahendatav) m" AUML "nguseis. Sinu " UUML "lesandeks on nooleklahvidega t" UUML "hja ruutu liigutades k" OTILDE "ik ruudud j" AUML "rjestada. T" UUML "hi ruut j" AUML AUML "b viimaseks.\n");
	printf("M" AUML "ng annab m" AUML "rku, kui k" OTILDE "ik on lahendatud ning seej" AUML "rel l" OTILDE "petab t" OUML OUML ".");

	// Mängu lõppseisu moodustamine (1, 2, 3, ..., 14, 15, 0)
	for (int i = 0; i < 16; i++)
		solved[i] = area[i] = (i+1) % 16;

	do
	{
		// Ruutude ärasegamine
		shuffle(area, 16);

		// Juhusliku segamise puhul võib tekkida olukord, kus mäng ei ole lahenduv.
		// Kui püüda mittelahenduvat mängu lahendada, siis tekib seis, kus ruudud 14 ja 15 on omavahel ära vahetatud.
		if (!isSolvable(area))
		{
			// Kahe (mittetühja) ruudu vahetamisel saab muuta mängu seda, kas mäng on lahenduv.
			if (area[14] != 0 && area[15] != 0)
				swap(&area[14], &area[15]);
			else
				swap(&area[12], &area[13]);
		}
	} while (isSolved()); // Võib juhtuda, et antakse ette koheselt lahendatud mäng, seda me ei taha.

	// Tühja ruudu hetkene asend, see tuleb massiivist üles leida.
	int curPos;
	for (int i = 0; i < 16; i++)
	{
		if (area[i] == 0)
		{
			curPos = i;
			break;
		}
	}

	// Mänguvälja ekraanile joonistamine
	drawGame(area);

	// Mängu tsükkel. Kestab kuni mäng on lahendatud.
	do
	{
		int key = _getch(); // Klahvivajutuste jälgimine
		switch (key)
		{
			case UP:
				if (curPos > 3) // Üles saab liikuda ainult siis, kui me ei ole esimesel real.
				{
					swapSquares(area, curPos, curPos - 4);
					curPos -= 4;
				}
				break;
			case DOWN:
				if (curPos < 12) // Alla saab liikuda ainult siis, kui me ei ole viimasel real.
				{
					swapSquares(area, curPos, curPos + 4);
					curPos += 4;
				}
				break;
			case LEFT:
				if (curPos % 4 != 0) // Vasakule saab liikuda siis, kui me ei ole esimeses veerus
				{
					swapSquares(area, curPos, curPos - 1);
					curPos--;
				}
				break;
			case RIGHT:
				if ((curPos + 1) % 4 != 0) // Paremale saab liikuda siis, kui me ei ole viimases veerus
				{
					swapSquares(area, curPos, curPos + 1);
					curPos++;
				}
				break;
			case ESC:
				setPos(0, 23);
				printf("Vajutati ESC");
				goto exit;
		}

		// Kui mäng saab lahendatud, siis väljutakse tsüklist.
	} while (!isSolved());
	setPos(0, 23);
	printf("Lahendatud!");

// Mängust väljumine. Et aken koheselt ei sulguks, palume veel enterit vajutada.
exit:
	printf("\nVajuta enterit v" AUML "ljumiseks.");
	getchar();
	return 0;
}