Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 46 47 48 49 50 [51] 52 53 54 55   вперед  Ctrl
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В сообщении 21718542 было показано, что алгоритм МММ позволяет получить на доске 25х25 2500 модулярных решений.
Попробуем это представить в виде кода:
function main {					
	var N1 = 5;				
	var N2 = 5;				
	var R1 = new Array(N1+1);			
	var R2 = new Array(N2+1);			
	var R3 = new Array(N1+1);			
	var R4 = new Array(N2+1);			
	var N3 = N1*N2;				
	var MR = new Array(2500+1);		
	for (var i = 0; i < =2500 + 1; i++) { MR[i] = new Array(N3+1);}
						
	MODrech(N1, R1);		// решение на доске 5х5
	SDVlev(N1, R1, R3);			
						
	POVobr(N1, R1, R2);	// решение, обратное первому
	SDVlev(N1, R2, R4);			
						
	var q=0;			// счетчик решений
	var SIM=8;				
	BLOCsim(N1, R3,  N2, R3, q, SIM);	// 1-ый блок решений
	BLOCsim(N1, R4,  N2, R3, q, SIM);	// 2-ой блок решений
	SIM=2;					
	BLOCsim(N1, R3,  N2, R1, q, SIM);	// 3-ий блок решений
	BLOCsim(N1, R4,  N2, R1, q, SIM);	// 4-ый блок решений
	// должно получиться 2500 решений (q)	
}						
function SDVlev(N , R1, R2) {	
	// сдвиг вправо (левая вертикаль доски становится правой вертикалью
	for(var i = 1 ; i < N ; i++ ) {	
		R2[i] = R1[i + 1];	
	}			
	R2[N] = R1[1];		
}				
function SDVniz(N, R1, R2) {		
	//сдвиг вниз (верхняя горизонталь доски становится нижней горизонталью)
	for(var i = 1 ; i <= N ; i++ ) {	
		R2[i] = R1[i] + 1;	
		if (R2[i] > N) {	
			R2[i] = 1;	
		}		
	}			
}				
function SDVlevN(N, MR, q1, q) {	
	q = q +1;			
	for(var i = 1 ; i < N ; i++ ) {	
		МR [q][i] = МR [q1][i + 1];
	}			
	МR [q][N] = МR [q1][1];	
}				
				
function SDVnizN(N, MR, q1, q) {	
	q = q +1;			
	for(var i = 1 ; i <= N ; i++ ) {	
		МR[q][i] = МR[q1][i] + 1;
		 if (МR [q][i] > N) {	
			МR [q][i] = 1;
		}		
	}			
}				
function SIMMET(N, MR, q1, q, SIM) {		
	q = q +1;				
	for (var i = 1 ; i <= N ; i++ ) МR [q][ N + 1 - i] = МR [q1][i]; 
	если SIM < 3 то return;		
	q = q +1;				
	for (var i = 1 ; i <= N ; i++ ) МR [q][ МR [q1][i] ] = N +1 – i;    
	q = q +1;				
	for (var i = 1 ; i <= N ; i++ ) МR [q][ МR [q1][i] ] = i;   
	если SIM < 5 то return;		
	q = q +1;				
	for (var i = 1 ; i <= N ; i++ ) МR [q][ N +1 – i] = N +1 – МR [q1][i]; 
	q = q +1;				
	for (var i = 1 ; i <= N ; i++ ) МR [q][ i] = МR [q1][ N + 1 - МR [q1][i] ]; 
	q = q +1;				
	for (var i = 1 ; i <= N ; i++ ) МR [q][ N + 1 -  МR [q1][i] ] = i;    
	q = q +1;				
	for (var i = 1 ; i <= N ; i++ ) МR [q][ N + 1 -  МR [q1][i] ] = N + 1 - i;   
	return;				
}					
function BLOCsim(N1, R1,  N2, R2, q, SIM) {	
	var N3 = N1*N2;			
	var R5 = new Array(N3+1);		
	var q2;				
	MMM1(N1, R1, N2, R2, R5);		
	q=q+1;				
	for (var i = 1 ; i <= N3 ; i++ ) МR [q][ i ] = R5[i]; 
	var q1=q;			
	for (var i = 2 ; i <= N3 ; i++ ) SDVlevN(N , MR, q1, q); 
	for (var i = 1 ; i <= N3 ; i++ ) {	
		q2=q1+(i-1);		
		for (var j = 1 ; j <= N2 ; j++ ) {
			if (  j> 1)  {	
				SDVnizN(N3 , MR, q2, q);
				q2=q;	
			}		
			SIMMET(N3, MR, q2, q, SIM);
		}			
	}				
}		
Часть процедур берется из сообщения 21732504
14 ноя 18, 08:05    [21733746]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В сообщении 21733746 в коде необходимо поменять следующие процедуры:
function BLOCsim(N1, R1,  N2, R2, q, SIM) {						
	var N3 = N1*N2;					
	var R5 = new Array(N3+1);					
	var q2;					
	MMM1(N1, R1, N2, R2, R5);					
	q=q+1;					
	for (var i = 1 ; i <= N3 ; i++ ) МR [q][ i ] = R5[i]; 					
	var q1=q;					
	q2=q;					
	for (var i = 2 ; i <= N3 ; i++ ) SDVlevN(N3 , MR, q2, q); 					
	for (var i = 1 ; i <= N3 ; i++ ) {					
		q2=q1+(i-1);				
		for (var j = 1 ; j <= N2 ; j++ ) {				
			if (  j > 1)  {			
				SDVnizN(N3 , MR, q2, q);		
			}			
			SIMMET(N3, MR, q2, q, SIM);			
		}				
	}					
}						
function SDVlevN(N, MR, q1, q) {					
	q = q +1;				
	for(var i = 1 ; i < N ; i++ ) {				
		МR [q][i] = МR [q1][i + 1];			
	}				
	МR [q][N] = МR [q1][1];				
	q1=q;				
}					
function SDVnizN(N, MR, q1, q) {					
	q = q +1;				
	for(var i = 1 ; i <= N ; i++ ) {				
		МR[q][i] = МR[q1][i] + 1;			
		 if (МR [q][i] > N) {			
			МR [q][i] = 1;		
		}			
	}				
	q1=q;				
}				
15 ноя 18, 07:48    [21734774]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Следующим шагом будет построение кода для всех решений, получаемых с помощью алгоритма МММ в обычном варианте:
function main {									
	var N1 = 5;								
	var N2 = 5;								
	var R1 = new Array(N1+1);							
	var R2 = new Array(N2+1);							
	var N3 = N1*N2;								
	var MR5 = new Array(10+1);					// массив решений на доске 5х5
	for (var i = 0; i < =10 + 1; i++) { MR5[i] = new Array(N1+1);}			
	var MR25 = new Array(2500+1);				// массив решений на доске 25х25
	for (var i = 0; i < =2500 + 1; i++) { MR25[i] = new Array(N3+1);}			
										
	var q=1;							// счетчик решений на доске 5х5
	MODrech(N1, R1);						// решение на доске 5х5
	for (var i = 1 ; i <= N1 ; i++ ) МR5 [q][ i ] = R1[i]; 					
	var q1=1;								
	for (var i = 2 ; i <= N1 ; i++ ) SDVlevN(N1, MR5, q1, q); 				
										
	q=q+1;									
	POVobr(N1, R1, R2);					// решение, обратное первому
	for (var i = 1 ; i <= N1 ; i++ ) МR5 [q][ i ] = R2[i]; 					
	var q1=q;								
	for (var i = 2 ; i <= N1 ; i++ ) SDVlevN(N1, MR5, q1, q); 				
										
	var Q1=q;								
	var SIM=0;								
	q=0;							// счетчик решений на доске 25х25
	VCLUCHodna(N1, MR5, Q1,  N2, MR5, Q1, MR25, q, SIM);				
										
	// должно получиться 100 решений (q) на доске 25х25				
}										

function VCLUCHodna(N1, MR1, Q1,  N2, MR2, Q2, MR3, q, SIM) {	
	var R1 = new Array(N1+1);				
	var R2 = new Array(N2+1);				
	var N3 = N1*N2;					
	var R5 = new Array(N3+1);				
	for (var q1 = 1 ; q1 <= Q1 ; q1++ ) {			
		for (var i = 1 ; i <= N1 ; i++ )  R1[i]= МR1 [q1][ i ];  
		for (var q2 = 1 ; q2 <= Q2 ; q2++ ) {		
			for (var i = 1 ; i <= N2 ; i++ )  R2[i]= МR2 [q2][ i ];  
			MMM1(N1, R1, N2, R2, R5);		
			q=q+1;				
			for (var i = 1 ; i <= N3 ; i++ ) МR3 [q][ i ] = R5[i]; 
		}					
	}						
}		
16 ноя 18, 07:19    [21735911]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В сообщении 21727327 было показано применение двух включенных матриц.
Попробуем это представить в виде кода.

Рассмотрим пока одну пару включенных матриц.
В сообщении 21735911 в function main вместо function VCLUCHodna применим function VCLUCHdve следующим образом:

VCLUCHdve(N1, MR5, Q1,  N2, MR25, q, SIM);	
					
// должно получиться 310 решений (q) на доске 25х25
А также необходимо добавить следующие процедуры:
function VCLUCHdve(N1, MR1, Q1,  N2, MR3, q, SIM) {	
	var R1 = new Array(N1+1);			
	var R2 = new Array(N2+1);			
	var R3 = new Array(N2+1);			
	var N3 = N1*N2;				
	var RR = new Array(N3+1);			
						
	var P = new Array(N1+2);			
	for(var i = 1; i <= N1; i++) P[i]=0;		
						
	MODrech(N2, R2);				
	POV90(N2, R2, R3);			
						
	for (var q1 = 1 ; q1 <= Q1 ; q1++ ) {		
		for (var i = 1 ; i <= N1 ; i++ )  R1[i]= МR1 [q1][ i ];  
		while(SOCHET3(N1, P)) {		
			if (P[i] == 0 {		
				MMM1(N1, R1, N2, R2, R5);
			} else {			
				MMM1(N1, R1, N2, R3, R5);
			}			
			q=q+1;			
			for (var i = 1 ; i <= N3 ; i++ ) МR3 [q][ i ] = R5[i]; 
		}				
		q=q-1;				
	}					
}						
function POV90(N, R1, R2) {	
	// 90 градусов	
	for (var i = 1 ; i <= N ; i++ ) R2[ R1[i] ] = N + 1 – i;    
}			
function SOCHET3(K, P)  {	
	var i1;		
	for(i1 = 1; i1 <=K; i1++) {
		P[i1]=P[i1]+1;
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;	
	}		
	return i1 <= K;	
}		
17 ноя 18, 16:08    [21737043]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1492
Немного визуализации модулярок на штатной точечной диаграмме, без макросов.
Эксэл, в 2003 красивее не смог.

Фрагмент статистики парных распределений.

Можно задавать вопросы.

К сообщению приложен файл. Размер - 26Kb
18 ноя 18, 13:26    [21737386]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1492
Фрагмент статистики парных распределений.
В принципе там д.б. симметрия.

К сообщению приложен файл. Размер - 16Kb
18 ноя 18, 13:27    [21737388]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1492
Ошибся, не парных (как-нить потом).
Это когда в разложениях на циклы имеется хотя бы 1 5- или 6-цикл.
18 ноя 18, 13:30    [21737389]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Теперь можно попытаться найти все пары включенных матриц на примере доски 25х25.
Для этого в коде из сообщения 21737043 заменим function VCLUCHdve на следующую процедуру:
function VCLUCHdve(N1, MR1, Q1,  N2, MR3, q, SIM) {	
	var R2 = new Array(N2+1);				
	var R3 = new Array(N2+1);				
	var R4 = new Array(N2+1);				
	var R5 = new Array(N2+1);				
	MODrech(N2, R2);						
	POV90(N2, R2, R3);					
	VCLUCHdve1(N1, MR1, Q1, N2, R2, R3, MR3, q, SIM);
	POVobr(N2, R2, R4);					
	POV270(N2, R4, R5);					
	if (N2 > 5) VCLUCHdve1(N1, MR1, Q1, N2,  R4, R5, MR3, q, SIM);
	var К1 = reminder(N2+1, 4);				
	var K2;							
	if (K1 != 0)  {							
		К1 = (N2-1)/ 4;					
		K2=(N2-1)/2;					
	} else {							
		К1 = (N2+1)/ 4;					
		K2=(N2-1)/2+1;					
	}								
	DVEvcl(N1, MR1, Q1, N2, R2 , R3, MR3, q, K1, K2, SIM);
	DVEvcl(N1, MR1, Q1, N2, R4 , R5, MR3, q, K1, K2, SIM);
}		
Далее необходимо дополнить данную процедуру другими процедурами:
function DVEvcl(N1, MR1, Q1, N2, R1 , R2, MR3, q, K1, K2, SIM) {	
	var R3 = new Array(N1+1);					
	var R4 = new Array(N1+1);					
	var R5 = new Array(N1+1);					
	var R6 = new Array(N1+1);					
										
	SDVIG2(N2, R1, R3, K1);						
	SDVIG2(N2, R1, R4, N2-K1);					
										
	SDVIG2(N2, R2, R5, K2);						
	SDVIG2(N2, R2, R6, N2-K2);					
										
	VCLUCHdve1(N1, MR1, Q1, N2,  R3, R5, MR3, q, SIM);	
	VCLUCHdve1(N1, MR1, Q1, N2,  R4, R6, MR3, q, SIM);	
}										
function VCLUCHdve1(N1, MR1, Q1, N2, R2, R3, MR3, q, SIM) {	
	var R1 = new Array(N1+1);					
	var R5 = new Array(N2+1);					
	var P = new Array(N1+2);						
	for(var i = 1; i <= N1; i++) P[i]=0;					
	var N3 = N1*N2;							
	for (var q1 = 1 ; q1 <= Q1 ; q1++ ) {				
		for (var i = 1 ; i <= N1 ; i++ )  R1[i]= МR1 [q1][ i ];  	
		while(SOCHET3(N1, P)) {					
			if (P[i] == 0 {						
				MMM1(N1,R1,N2,R2,R5);		
			} else {						
				MMM1(N1,R1,N2,R3,R5);		
			}							
			q=q+1;						
			for (var i = 1 ; i <= N3 ; i++ ) МR3 [q][ i ] = R5[i]; 
		}								
		q=q-1;							
	}									
}										
function POV270(N, R1, R2) {		
	// 270 градусов			
	for (var i = 1 ; i <= N ; i++ ) R2[ N + 1 -  R1[i] ] = i;    
}						
function SDVIG2(N2 , R1 , R2, SDV) {	
	for (var i = 1 ; i <= N2 ; i++ ) R2[ i ] = R1[i]; 
	for (var sd = 1 ; sd <= SDV ; sd++ ) { 
		var a = R2[1 ];		
		for(var i = 1 ; i <= N ; i++ ) {
			R2[i] =R2[i+1];	
		}				
		R2[N] = a;			
	}					
}		
Всего должно получиться на доске 25х25 (310 х 5 ) = 1550 решений
18 ноя 18, 20:28    [21737547]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Если основная матрица является матрицей модулярного решения, то при использовании алгоритма МММ с применением двух включенных матриц получаем модулярные решения.
Следовательно, из этих решений можно получить другие решения с помощью «сдвигов» решений.

Если в алгоритме МММ имеем {N, M}, то количество новых решений за счет сдвигов будет МхМ-1.
Для получения всех «сдвигов» необходимо в коде 21737547 для алгоритма МММ с двумя включенными матрицами ввести в процедуру VCLUCHdve1 переменную sumP и процедуру BLOCdvе, а также заменить SOCHET3 на SOCHET4:
function VCLUCHdve1(N1, MR1, Q1, N2, R2, R3, MR3, q, SIM) {										
	var R1 = new Array(N1+1);									
	var R5 = new Array(N2+1);									
	var P = new Array(N1+2);									
	for(var i = 1; i <= N1; i++) P[i]=0;									
	var sumP=0;									
	var N3 = N1*N2;									
	for (var q1 = 1 ; q1 <= Q1 ; q1++ ) {									
		for (var i = 1 ; i <= N1 ; i++ )  R1[i]= МR1 [q1][ i ];  								
		while(SOCHET4(N1, P, sumP)) {								
			if (sumP < N1) {							
				if (P[i] == 0 {						
					MMM1(N1, R1, N2, R2, R5);					
				} else {						
					MMM1(N1, R1, N2, R3, R5);					
				}						
				q=q+1;						
				for (var i = 1 ; i <= N3 ; i++ ) МR3 [q][ i ] = R5[i]; 						
				BLOCdve(N3, MR3, N2, q);						
			}							
		}								
	}									
}										
function BLOCdve(N3, MR,  N2, q) {						
	var q2;					
	var q1=q;					
	for (var i = 2 ; i <= N2 ; i++ ) SDVlevN(N3 , MR, q1, q); 					
	for (var i = 1 ; i <= N2 ; i++ ) {					
		q2=q1+(i-1);				
		for (var j = 1 ; j <= N2 ; j++ ) {				
			if (  j >  1)  {			
				SDVnizN(N3 , MR, q2, q);		
			}			
		}				
	}					
}						
function SOCHET4(K, P,sumP)  {					
	var i1;				
	for(i1 = 1; i1 <=K; i1++) {				
		P[i1]=P[i1]+1;			
		sumP=sumP+1;			
		if (P[i1] != 2) break; 			
		P[i1] = 0;			
		sumP=sumP-2;			
	}				
	return i1 <= K;				
}					
Тогда должно получиться на доске 25х25 (300 х 5 х25) = 37500 решений.
19 ноя 18, 19:15    [21738457]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Проведенные исследования показали, что нельзя найти двух включенных матриц для модулярных решений, имеющих вторую степень симметрии.

Поэтому в function VCLUCHdve необходимо поменять операцию:
VCLUCHdve1(N1, MR1, Q1, N2, R2, R3, MR3, q, SIM);
на операцию:
if (N2 > 5) VCLUCHdve1(N1, MR1, Q1, N2, R2, R3, MR3, q, SIM);
В результате общее количество получаемых решений на доске 25х25 с применением алгоритма МММ с двумя включенными матрицами уменьшится до 30000 решений.
20 ноя 18, 19:55    [21739491]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Все построения алгоритма МММ с двумя включенными матрицами основано на одном шаге – 2.
Вместе с тем, в сообщении 16 21154133 говорится о наличии нескольких шагов при построении МФР1 и МФР2.

Поэтому применение различных шагов на больших досках при определении включенных матриц позволит на этих досках увеличить количество определяемых модулярных решений.

Кроме того, можно определить две включенные матрицы среди сложных решений, которые получаются на доске 25х25 с применением алгоритма МММ.
Тогда применение алгоритма МММ с двумя включенными матрицами возможно на доске 125х125 для случая {5, 25}.

Данные исследования можно продолжить и на досках с большим размером, причем две включенные матрицы можно будет определять на сколь угодно больших досках.
21 ноя 18, 13:48    [21740029]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Забыл важную деталь – определение массивов для решений на доске 25х25.
Последний раз его размер составлял
var MR25 = new Array(2500+1);
for (var i = 0; i < =2500 + 1; i++) { MR25[i] = new Array(N3+1);}
Поскольку последние коды обеспечивают получение количество решений намного большее, чем 2500, то и в кодах надо поменять размер массива MR25 на то количество решений, которое будет на этой доске.
В частности, в последнем коде будет:
var MR25 = new Array(30000+1);
for (var i = 0; i < =30000 + 1; i++) { MR25[i] = new Array(N3+1);}
Можно с запасом.
21 ноя 18, 14:30    [21740110]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В сообщении 21730301 говорится о применении алгоритма МММ с перемещением ферзей.
Если рассматривать случай {5, 5} на доске 25х25, то согласно 21730301 можно будет определить 1 000 000 модулярных решений, а если ещё добавить «сдвиги» этих решений, то получается 25 000 000 модулярных решений.

Попробуем составить код для определения этих решений алгоритма МММ с перемещением ферзей на доске 25х25 или {5, 5}.
function main {									
	var N1 = 5;								
	var N2 = 5;								
	var N3 = N1*N2;								
	var MR5 = new Array(10+1);					// массив решений на доске 5х5
	for (var i = 0; i < =10 + 1; i++) { MR5[i] = new Array(N1+1);}				
										
	var MR25 = new Array(25000000+1);				// массив решений на доске 25х25
	for (var i = 0; i < =25000000 + 1; i++) { MR25[i] = new Array(N3+1);}			
										
	var Q1=10;						// счетчик решений на доске 5х5
	var q=0;									
	MR5x5(N1, Q1, MR5, q);							
										
	var SIM=0;								
	q=0;							// счетчик решений на доске 25х25
	PEREMfer(N1, MR5, Q1,  N2, MR5, Q1, MR25, q, SIM);				
										
	// должно получиться (10x10x10x10x10)x10x5x5 решений (q) на доске 25х25		
	//	25000000	решений							
}										
function PEREMfer(N1, MR1, Q1,  N2, MR2, Q2, MR3, q, SIM) {	
	var R2 = new Array(N2+1);				
	var R5 = new Array(N3+1);				
	var P = new Array(N1+2);				
	for(var i = 1; i <= N1; i++) P[i]=1;			
	var R1;						
	var a;						
	var N3 = N1*N2;					
							
	for (var q2 = 1 ; q2 <= Q2 ; q2++ ) {			
		for (var i = 1 ; i <= N2 ; i++ )  R2[i]= МR2 [q2][ i ];  
		while(SOCHETM(N1, P, Q1)) {		
			for (var j = 1 ; j<= N2 ; j++ )  {  	
				var ij;			
				a=P[j];			
				for (var i = 1; i <= N1; i++) {	
					ij = N2 * (i - 1) + j;	
					R1=МR1 [a][ i ];  	
					R5[ ij] = N2 * (R1 - 1) + R2[ j ];
				}			
			}				
			q=q+1;				
			for (var i = 1 ; i <= N3 ; i++ ) МR3 [q][ i ] = R5[i]; 
			BLOCdve(N3, MR3, N2, q);		
		}					
	}						
}							
function SOCHETM(K, P, M)  {			
	for(var i1 = 1; i1 <=K; i1++) {			
		P[i1]=P[i1]+1;			
		if (P[i1] != (M + 1)) break; 	// Выход из цикла если P[i1] != M+1
		P[i1] = 1;				
	}					
	return i1 <= K;				
}						
function MR5x5(N1, Q1, MR, q)  {			
	var R1 = new Array(N1+1);			
	var R2 = new Array(N2+1);			
	q=q+1;					
	MODrech(N1, R1);				
	for (var i = 1 ; i <= N1 ; i++ ) МR [q][ i ] = R1[i]; 	
	var q1=q;				
	for (var i = 2 ; i <= N1 ; i++ ) SDVlevN(N1, MR, q1, q); 
						
	POVobr(N1, R1, R2);			
	q=q+1;					
	for (var i = 1 ; i <= N1 ; i++ ) МR [q][ i ] = R2[i]; 	
	var q1=q;				
	for (var i = 2 ; i <= N1 ; i++ ) SDVlevN(N1, MR, q1, q); 
}
function SOCHETM взята из сообщения 21738688.
function MR5x5 специально сделана в виде формулы (все решения на доске 5х5 уже известны), чтобы эту функцию применить для любых досок (с расширением).
22 ноя 18, 13:20    [21741238]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Теперь в виде одного кода можно собрать два кода алгоритма МММ: с двумя включенными матрицами и с перемещением ферзей.
Всего на доске 25х25 должно получиться 25 030 000 модулярных решений.

Поскольку в алгоритме МММ с двумя включенными матрицами в каждой из этих матриц один ферзь совпадает по расположению, то можно будет перемещать этого ферзя так же, как и в варианте перемещения ферзей.

Следовательно, в итоге получаем на доске 25х25 с применением алгоритма МММ с двумя включенными матрицами и с перемещением ферзей
25 150 000 модулярных решений.

Процедуры, описанные в 21738457(с учетом 21739491 и 21740110) и в 21741238, с учетом небольшой доработки, можно будет применить на любой доске с целью определения решений. При этом есть ограничения для таких досок:
- размер доски больше 19;
- размер доски имеет два множителя, больших 3;
- величина одного из множителей равна 6хК+1 или 6хК+5, К>=0.
23 ноя 18, 13:37    [21742815]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В сообщении 21742815говорится об ограничениях на размер досок, для которых определяются решения с помощью алгоритма МММ.

Однако можно расширить перечень досок.
На топике не один раз упоминалось о возможности перехода при поиске решений с решения большей доски (NxN) на решение меньшей доски ((N-1)x(N-1)).

Данная возможность заключается в поиске среди определяемых решений на доске NхN таких решений, у которых ферзь расположен в клетках:
(1, 1), (1, N), (N, N), (N, 1).

Если у решения в одной из этих клеток находится ферзь, то достаточно «отбросить» от этого решения значение такого ферзя, и получаем решение на доске ((N-1)x(N-1)).

Проведенные исследования на небольших досках показали, что соотношение определяемых решений на доске (NxN) и решений на доске ((N-1)x(N-1)) после «отбрасывания» значений ферзей будет около N : 1.
24 ноя 18, 05:13    [21743508]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Теперь, имея несколько кодов, которые охватывают большую часть определяемых с помощью найденных алгоритмов МЭА решений, можно приступить к рассмотрению расширения задачи N ферзей.

Здесь целесообразно рассмотреть обратную задачу: имея на доске NxN часть решения (несколько ферзей М, где М<N) найти всё решение, а также ещё несколько решений. 21406243.
В сообщении 21634888 предполагается поиск расширения с помощью сравнения значений известных решений со значениями установленных ферзей (прикладной вариант задачи N ферзей).

Но обратная задача может предполагать и обратное построение известных алгоритмов.
В сообщении 2721158788 рассматривался вопрос об определении решений с помощью «четверок» ферзей за счет их «поворотов».
Об этих «поворотах» было сказано в 21156317.

Теперь, имея код процедуры по определению «четверки» ферзей для установленного ферзя 21750905, можно построить код по определению решения для нескольких установленных ферзей.
Пусть на доске 13х13 установлены ферзи: (6, 2) и (11, 3).
Имеем код:
function main {							
	var N=13;						
							
	// определяем массив ФМР1						
	var R = new Array(N+1);						
	// определяем массив ФМР3						
	var R1 = new Array(N+1);						
	// определяем массив установленных ферзей						
	var FR = new Array(N+1);						
							
							
	// определяем ФМР1						
	var shag=5;						
	MODrech(N, R, shag);						
							
	// определяем установленные ферзи						
	for(var i = 1; i < =N; i++) { FR[i]=0;}						
	FR[6]=2;						
	FR[11]=3;						
							
	// формируем основу нового решения						
	for(var i = 1; i < =N; i++) { R1[i]=R[i];}						
	for(var i = 1; i < =N; i++) { 						
		if (FR[i] > 0) {					
			Fx=i;				
			Fy=FR[i];				
			// поворот "четверки" ферзей .				
			POVORchet(N, R, R1, Fx, Fy); 				
		}					
	}						
	// получаем новое решение R1						
}	
И получаем решение:
11 8 1 7 4 2 9 2 10 5 3 6 13
1 дек 18, 08:58    [21750906]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Метод применения обратной задачи к алгоритму построения «четверок» ферзей, описанный в предыдущем сообщении, имеет следующие ограничения:
- метод можно применить на досках, размер которых 6хК+1 или 6хК+5, К>0, а также на досках 6хК или 6хК+4 после добавления ферзя;
- количество «четверок» ферзей в одном решении не может быть более N1 (N1=(N-1)/4) (иначе эти «четверки» будут иметь общие ферзи, и при «повороте» одной «четверки» ферзей перемещаются отдельные ферзи из другой «четверки» ферзей);
- устанавливаемые ферзи должны отвечать требованию наличия решения (не бить друг друга);
- устанавливаемые ферзи должны отвечать требованию модулярности (особый вид построения диагоналей).
Даже при соблюдении второго ограничения может возникнуть ситуация, когда не будет независимых «четверок» ферзей.
Например, на доске 13х13 в предыдущем примере получилось 2 «четверки» ферзей, а третью найти не удаётся, хотя выполняется второе ограничение.

Данный метод может быть удобен на очень больших досках, когда М мало по сравнению с N1. То есть, в этом случае с большой долей вероятности получаются независимые «четверки» ферзей для определяемого решения.
1 дек 18, 15:32    [21751029]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
На самом деле на доске 13х13 для ФМР1 можно найти блок модулярных решений в количестве 13х13х2 решений.
И для каждого их этих решений из блока решений можно искать решение обратной задачи для М установленных ферзей.
Попробуем написать код для такой обратной задачи.
В начале выбираем размер доски – N, шаг для ФМР1 - shag, массив установленных ферзей – FR, далее обращаемся к блоку поиска решений – BLOCobr.
function main {														
	var N=13;													
	var shag=5;													
	// обозначаем массив решений													
	var MR13 = new Array(1000+1);													
	for (var i = 0; i < =1000 + 1; i++) { MR13[i] = new Array(N+1);}													
														
	// обозначаем массив установленных ферзей													
	var FR = new Array(N+1);													
	// определяем установленные ферзи													
	for(var i = 1; i < =N; i++) { FR[i]=0;}													
	FR[6]=2;													
	FR[11]=3;													
														
	// определяем блок решений													
	var q=0;													
	BLOCobr(N, FR, MR, shag, q);													
	// печать решений в количестве q													
}	

В блоке поиска решений BLOCobr определяются два ФМР1 (прямое и обратное), и для каждого ФМР1 обращаемся к процедуре поиска ФМР3 - RECHfmr3.
function BLOCobr(N, FR, MR, shag, q) {									
	// определяем массив ФМР1								
	var FMR1 = new Array(N+1);								
									
	// определяем 1-ый ФМР1								
	MODrech(N, FMR1, shag);								
									
	RECHfmr3(N, FMR1, FR, MR, q);								
									
	// определяем 2-ой ФМР1								
	shag= -shag;								
	MODrech(N, FMR1, shag);								
									
	RECHfmr3(N, FMR1, FR, MR, q);								
}				
3 дек 18, 19:21    [21752376]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В процедуре поиска ФМР3 - RECHfmr3 идет поиск решений из блока ФМР1 и обращение к процедуре POISKfmr3 для определения «четверок» ферзей с целью изменения решения из блока ФМР1.
Если решение ФМР3 найдено, то оно записывается в массив решений MR.
function RECHfmr3(N, FMR1, FR, MR, q) {												
	var R1 = new Array(N+1);											
	var R2 = new Array(N+1);											
												
	// определяем массив ФМР3											
	var FMR3 = new Array(N+1);											
												
	// сдвиги по х и по y											
	for(var niz = 1; niz < =N; niz++) { 											
		if(niz == 1) {										
			for(var i = 1; i < =N; i++) { R1[i]=FMR1[i];}									
		} else {										
			SDVniz1(N, R1);									
		}										
		for(var pra = 1; pra < =N; pra++) { 										
			if(pra == 1) {									
				for(var i = 1; i < =N; i++) { R2[i]=R1[i];}								
			} else {									
				SDVlev1(N, R2);								
			}									
			// запись найденного решения									
			if (POISKfmr3(N, R2, FR, FMR3) == 0) {									
				q=q+1;								
				for(var i = 1; i < =N; i++) { MR[q][i]=FMR3[i];}								
			}									
		}										
	}											
}												
function SDVlev1(N , R1) {									
	// сдвиг вправо (левая вертикаль доски становится правой вертикалью								
	var a=R1[1];								
	for(var i = 1 ; i < N ; i++ ) {								
		R1[i] = R1[i + 1];							
	}								
	R1[N] = a;								
}									
function SDVniz1(N, R1) {									
	//сдвиг вниз (верхняя горизонталь доски становится нижней горизонталью)								
	for(var i = 1 ; i <= N ; i++ ) {								
		R1[i] = R1[i] + 1;							
		if (R1[i] > N) {							
			R1[i] = 1;						
		}							
	}								
}									
3 дек 18, 19:26    [21752378]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
В процедуре POISKfmr3 определяются «четверки» ферзей для установленных ферзей, и если эти «четверки» не зависимы друг от друга (нет пересечений), то получаем решение ФМР3.
function POISKfmr3(N, R2, FR, FMR3) {												
	var ax, ay, bx, by, cx, cy, dx, dy;											
												
	// формируем массив ФМР3											
	for(var i = 1; i < =N; i++) { FMR3[i]=R2[i];}											
	// формируем контролный массив 											
	for(var i = 1; i < =N; i++) { AR[i]=0;}											
	// ищем "четверки" для каждого установленного ферзя											
	for(var i = 1; i < =N; i++) { 											
		if (FR[i] > 0 & R2[i] != FR[i]) {										
			ax=i;									
			ay=R2[i];									
			var i1=1;									
			while (R2[i1] != FR[i]) {									
				i1=i1+1;								
			}									
			bx=i1;									
			by=R2[i1];									
			// определяем "четверку" ферзей									
			KVADRAT(N, ax, ay, bx, by, cx, cy, dx, dy);									
			// проверяем совпадение ферзей из разных четверок									
			if (AR[ax]==0 & AR[bx]==0 & AR[cx]==0 & AR[dx]==0) {									
				AR[ax] = AR[bx] = AR[cx] = AR[dx] = 1;								
				// уточняем ФМР3								
				FMR3[ax]= ay;								
				FMR3[bx]= by;								
				FMR3[cx]= cy;								
				FMR3[dx]= dy;								
			} else {									
				// для одного из установленных ферзей не нашлось "четверки"								
				return 1;								
			}									
		}										
	}											
	return 0;											
}												
3 дек 18, 19:29    [21752382]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Таким образом, для любой доски, где существует ФМР1, можно построить обратную задачу для установленных ферзей, отвечающих требованиям 21742815 и 21743508, с целью быстрого получения большого количества решений задачи расширения.
3 дек 18, 19:31    [21752383]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
Таким образом, для любой доски, где существует ФМР1, можно построить обратную задачу для установленных ферзей, отвечающих требованиям 21742815 и 21743508, с целью быстрого получения большого количества решений задачи расширения.


быстро - это полиномиально?

большое - это какое?
1 - это большое количество?
a 10^10 - большое?
a 10^10^10?
a N^10?
a 10^N?

P.S. И еще хотелось бы, наконец, увидеть условия прямой задачи: что дано, что надо найти.
А потом и обратной.
4 дек 18, 00:27    [21752487]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
Таким образом, для любой доски, где существует ФМР1, можно построить обратную задачу для установленных ферзей, отвечающих требованиям 21742815 и 21743508, с целью быстрого получения большого количества решений задачи расширения.
быстро - это полиномиально?
большое - это какое?
1 - это большое количество?
a 10^10 - большое?
a 10^10^10?
a N^10?
a 10^N?
Допустим, у нас доска NxN и установлено М ферзей, М < (N-1)/4.
При этом М ферзей являются частью модулярного решения.

Тогда модулярное решение на доске можно найти за:
- N нахождений ферзей для решения вида ФМР1;
- М определений «четверок» ферзей для каждого установленного ферзя в ФМР1;
- М перестановок вертикалей в этих «четверках» для ФМР1 (формирование ФМР3);
- запись ФМР3 в базу решений.

Это для одного возможного решения. За счет использования блока модулярных решений для ФМР1 (сдвиги решения) можно найти ещё (NxNx2-1) возможных решений.

А теперь считайте, сколько это времени занимает при расчете на ЭВМ.
Причем, при увеличении размера доски и количества установленных ферзей время поиска увеличивается только пропорционально этим увеличениям.

Такое решение обратной задачи возможно на досках 6хК+1 и 6хК+5 и на досках 6хК и 6хК+4 (в этом случае доска увеличивается на 1 и в один из углов доски ставится дополнительный ферзь).
4 дек 18, 07:04    [21752540]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
Таким образом, для любой доски, где существует ФМР1, можно построить обратную задачу для установленных ферзей, отвечающих требованиям 21742815 и 21743508, с целью быстрого получения большого количества решений задачи расширения.
большое - это какое?
Я ничего не сказал про большое.

Допустим найдено решение для М ферзей, причем имеется существенная разница между М и (N-1)/4 (установленных ферзей не очень много).
При этом при формировании ФМР3 были проведены М1 изменений значений ферзей ФМР1, где М1 =Мх4.
Тогда появляется возможность искать «четверки» ферзей для N1 ферзей, где N1 = (N – M1).21749869

Далее будут сочетания для новых «четверок», и для каждого сочетания будет новое решение. Количество «четверок» для поиска сочетаний может быть больше (N – N1-1)/4.

Но для этого уже будет написан следующий код.
4 дек 18, 07:30    [21752549]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
P.S. И еще хотелось бы, наконец, увидеть условия прямой задачи: что дано, что надо найти.
А потом и обратной.
В сообщении 21156317 говорится о том, что на определенных досках существуют решения (ФМР1), в которых определяются «четверки» ферзей, имеющие свои горизонтали, вертикали и диагонали. Ферзи в каждой из этих «четверок» могут «перемещаться» в этих рамках. Они не будут бить остальные ферзи.
Перемещение только одно: одновременная перестановка вертикалей для противоположных ферзей квадрата («четверки»).

Прямая задача – найти все сочетания всех возможных «четверок» (которые не "бьют" друг друга) и за счет перестановки вертикалей у "четверок" для очередного сочетания получать решение ФМР3.

Обратная задача – для установленных ферзей найти те «четверки», которые после перестановки вертикалей, совместились с установленными ферзями. И уже за счет перестановки вертикалей в найденных «четверках» определяется всё ФМР3. Для "четверок", которые не попали в полученный ФМР3, можно решать прямую задачу по поиску сочетаний, что позволит получить дополнительные решения.
4 дек 18, 07:52    [21752559]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 46 47 48 49 50 [51] 52 53 54 55   вперед  Ctrl
Все форумы / Программирование Ответить