Подскажите алгоритм

Вариант, использующий часть кода tvv для повышения читабельности:

<?php

$matrix=array();

for($x=0;$x<15;++$x) {

	$matrix=array();

	for($y=0;$y<15;++$y)

		$matrix=rand(-1,1);

}


$result=-1;


function check_line($x,$y,$d1,$d2) {

	global $matrix,$result;

	$z=$matrix;

	if($z==-1)

		return false;

	for($i=0;$i<5;++$i)

		if($matrix!=$z)

			return false;

	$result=$z;

	return true;

}


function check_matrix() {

	for($x=0;$x<15;++$x) {

		for($y=0;$y<15;++$y) {

			if($y>=4) {

				if(check_line($x,$y,0,-1)) return;

				if($x>=4)

					if(check_line($x,$y,-1,-1)) return;

				if($x<=11) {

					if(check_line($x,$y,1,0)) return;

					if(check_line($x,$y,1,-1)) return;

				}

			}

			elseif($x<=11) {

				if(check_line($x,$y,1,0)) return;

				if(check_line($x,$y,1,-1)) return;

			}

		}

	}

}


check_matrix();

echo $result;

?>

То же самое на JS:

var matrix=new Array();

for(var x=0;x<15;++x) {

	matrix=new Array();

	for(y=0;y<15;++y)

		matrix=Math.floor(Math.random()*3)-1;

}


var result=-1;


function check_line(x,y,d1,d2) {

	var z=matrix;

	if(z==-1)

		return false;

	for(var i=0;i<5;++i)

		if(matrix!=z)

			return false;

	result=z;

	return true;

}


function check_matrix() {

	for(var x=0;x<15;++x) {

		for(var y=0;y<15;++y) {

			if(y>=4) {

				if(check_line(x,y,0,-1)) return;

				if(x>=4)

					if(check_line(x,y,-1,-1)) return;

				if(x<=11) {

					if(check_line(x,y,1,0)) return;

					if(check_line(x,y,1,-1)) return;

				}

			}

			elseif(x<=11) {

				if(check_line(x,y,1,0)) return;

				if(check_line(x,y,1,-1)) return;

			}

		}

	}

}


check_matrix();

alert(result);

Привет Вам, народ.
Читаю я эту тему, и что-то мне кажется Вы зациклились в одном направлении: по-точечная проверка на наличие линии.
Хочу предложить Вам вариант, который первым приходит на ум. Сразу оговорюсь, что с ПХП я не другу и особенностей выделения памяти и быстродействия на переходах в условиях я не знаю, но всё-же:
заводим ещё 4-ре матрицы (байтовые) такой же размерности. зануляем их. а потом в цикле по ячейкам основной матрицы проходимся с проверкой следующих условий:
1) если в клетке пусто, то во все 4-ре матрицы в такуюже ячейку вбиваем нули. иначе вбиваем во все 4-ре матрицы 1-цу и:
2) проверка всех соседних с текущей, уже пройденных клеток на наличие такого же символа как в этой ячейке, и если в одной из них есть такой же, то в соответствующую ячейку соответствующей матрицы вносим 1+значение в этой матрице на месте второй клетки(ранее пройденной).
итд.
проходя, заодно запоминаем ячейку с максимальным числом в одной из матриц. если это число 5 или более, то выигрыш есть
надеюсь доступно объяснил

DoctorShtein, нифига не понятно.

Набрал чутка кодов на С++:
не компилил, не запускал, но по ходу должно работать

byte matr;

byte v;

byte h;

byte d1;

byte d2;


//zero all memory;

int max_x_pos=-1;

int max_y_pos=-1;

bool canbreak=false;


for (int i=0;((i<15)&&(!canbreak));++i)//columns

{

	for (int j=0;j<15;++j)//rows

	{

		if (matr==0)//empty

		{

			v=h=d1=d2=0;

			continue;

		}		

		v=h=d1=d2=1;		

		if ((j>0) && (matr==matr))//check v		

			v+=v;

		if ((i>0) && (matr==matr))//check h		

			h+=h;

		if ((j>0) && (i>0) && (matr==matr))//check d1		

			d1+=d1;

		if ((j<14) && (i>0) && (matr==matr))//check d2		

			d2+=d2;


		if (max(v, max(h, max(d1,d2))) > 4)

		{

			max_x_pos=i;

			max_y_pos=j;

			canbreak=true;

			break;

		}

	}

}

Google : гомоку исходный код
всего то )

А вообще-то есть смысл проверять только поле 9х9 возле последнего хода . Да и то только по горизонтали , вертикали и диагонади от точки хода . Во к примеру :

5- точка последнего хода 1- проверять клетку , 0 не проверять

100010001

010010010

001010100

000111000

111151111

000111000

0010101001

010010010

100010001

Всего то )
UPD . Как то не очень квадратно вышло ...

Только что появилась идея более оптимального алгоритма. Дальнейшее развитие того, что предложил lisio:

var N = 15;

var M = 5;

var matrix = ...; // array a


var result = -1;


checkMatrix();

alert(result);


function f(i, j, di, dj) {

    for (var b = 1, x = -1; i >= 0 && i < N && j < N; i += di, j += dj) {

        var t = matrix;


        if (t == -1 || t != x) {

            x = t; b = 1;

        } else {

            if (++b == M) { result = t; return true; }

        }

    }


    return false;

}


function checkMatrix() {

    for (var k = 0; k < N; ++k)

        if (f(k, 0, 0, 1)                                // right

         || f(0, k, 1, 0)                                // down

         || k <= N - M && (

            f(k, 0, 1, 1) || f(0, k, 1, 1)               // right-down

         || f(k + M - 1, 0, -1, 1) || f(N - 1, k, -1, 1) // right-up

        )) break;

}

Результат проверил у себя локально.

Спасибо всем огромное за идеи и реализации.