Thuật toán của game Lines98 (P.1)

Bảng trò chơi 9×9 được mô tả bằng mảng 2 chiều: int a[9][9]. Trong đó, a[i][j] = c (0 <= c <= 7) là màu của viên bi tại cột i, hàng j. Quy ước c = 0 tức là không có viên bi nào ở vị trí đó.

Đánh số các ô từ 0 đến 80 theo thứ tự từ trên xuống dưới, từ trái qua phải.

Phần 1: Tạo ngẫu nhiên bảng trò chơi.

Đầu tiên ta có 81 ô trống, cần tìm 1 vị trí ngẫu nhiên nào đó (từ 0 đến 80) để đặt viên bi đầu tiên. Thế thì cứ lấy random(81) cho ra số k, chuyển đổi k sang chỉ số cột i, hàng j tương ứng rồi gán cho ô ở vị trí này 1 màu bi ngẫu nhiên: a[i][j] = (random(7) + 1).

Tiếp theo, còn lại 80 ô trống, lại lấy k = random(80). Tuy nhiên, để chuyển đổi k sang chỉ số hàng cột thì lưu ý làm thế này: duyệt tuần tự từ trên xuống dưới, từ trái qua phải, gặp ô trống thì đếm, ô đã có bi thì không đếm, và cho đến khi đếm đủ k thì dừng lại. Vị trí dừng lại chính là vị trí hàng i cột j cần tìm. Rồi, lại gán: a[i][j] = (random(7) + 1).

Cứ thế, cứ thế 5 lần thì thôi. Vì số lượng viên bi ban đầu là 5.

Code C:

#define BOARD_COL		9
#define BOARD_ROW		9
#define INIT_BALL_NUM	5
#define NEXT_BALL_NUM	3
#define MAX_COLOR		7

int myrandom(int n)
{
	return rand() % n;
}

void makeRandMatrix(int** a)
{
	int i, j, remain, count, count2, stop;
	srand(time(NULL));

	for (i = 0; i < BOARD_COL; i++)
	{
		for (j = 0; j < BOARD_ROW; j++)
		{
			a[i][j] = 0;
		}
	}

	count = BOARD_COL * BOARD_ROW;
	count2 = count - INIT_BALL_NUM;
	do
	{
		remain = myrandom(count--) + 1;
		stop = 0;
		for (i = 0; i < BOARD_COL; i++)
		{
			if (stop) break;
			for (j = 0; j < BOARD_ROW; j++)
			{
				if (a[i][j] == 0)
				{
					remain--;
					if (remain == 0)
					{
						a[i][j] = myrandom(MAX_COLOR) + 1;
 						stop = 1;
 						break;
					}
				}
			}
		}
	} while (count > count2);

	addNextColor(a);
}

Hàm addNextColor(int** a) sẽ thêm vào ma trận a 3 vị trí ngẫu nhiên đặt các viên bi sắp được hiện lên. Quy ước: màu của các viên bi đó sẽ là số âm, ví dụ a[i][j] = -2 tức là nó có màu 2 nhưng vì nó chưa hiện lên, chỉ là sắp hiện lên thôi, nên phải đảo dấu.

Code C:

void addNextColor(int** a)
{
	int count, tmp, i, j, remain, stop;
	count = countEmpty(a);

	srand(time(NULL));

	for (tmp = 0; tmp < NEXT_BALL_NUM; tmp++)
	{
		remain = myrandom(count--) + 1;
		stop = 0;
		for (i = 0; i < BOARD_COL; i++)
		{
			if (stop) break;
			for (j = 0; j < BOARD_ROW; j++)
			{
				if (a[i][j] == 0)
				{
					remain--;
					if (remain == 0)
					{
						a[i][j] = - (myrandom(MAX_COLOR) + 1);
						stop = 1;
						break;
					}
				}
			}
		}
	}
}

Bổ sung hàm countEmpty(int** a)

int countEmpty(int** a)
{
	int i, j, count;
	count = 0;
	for (i = 0; i < BOARD_COL; i++)
		for (j = 0; j < BOARD_ROW; j++)
			if (a[i][j] <= 0)
				count++;
	return count;
}

Còn nữa…

• Phần 1
• Phần 2
• Phần 3