რვა ლაზიერის ამოცანა

ერთ–ერთი ამონახსნი

რვა ლაზიერის ამოცანა გულისხმობს 8x8 განზომილების მქონე საჭადრაკო დაფაზე რვა ლაზიერის განთავსებას ისე, რომ ისინი ერთმანეთს არ ემუქრებოდნენ ჭადრაკის წესების გათვალისწინებით. ლაზიერის ფერს ამ შემთხვევაში მნიშვნელობა არ აქვს. უფრო ზუსტად ამოცანა გულისხმობს რომ, ლაზიერები დაფაზე ისე უნდა იყოს განლაგებული, რომ არც ერთ ჰორიზონტალზე, ვერტიკალზე და დიაგონალზე არ უნდა იმყოფებოდეს ერთზე მეტი ლაზიერი. რვა ლაზიერის ამოცანა წარმოადგენს NxN განზომილების მქონე დაფაზე N ლაზიერის განთავსების ამოცანის ერთ–ერთ ქვეამოცანას.

ისტორია

პირველად ამოცანა დასმული იქნა 1848 წელს, მოჭადრაკე მაქს ბეზელის მიერ და მრავალი წლის განმავლობაში მრავალი მათემატიკოსი, მათ შორის კარლ ფრიდრიხ გაუსი, თავს იმტვრევდა მის ამოხსნაზე. XX საუკუნის მიწურულს ეს ამოცანა ძლიერ პოპულარული გახდა ინფორმაციულ ერაში, პროგრამირების მაღალი დონის ენების განვითარების დროს.

ამონახსნი

ამ ამოცანას სულ გააჩნია 92 ამონახსნი, რომელთაგან 12 წარმოადგენს უნიკალურ ამონახსნს (დანარჩენი ამონახსნები მიიღება ამ 12 ამონახსნის სარკული ინვერსიით ან ჭადრაკის დაფის საათის ისრის საწინააღმდეფო/საპირისპირო მიმართულებით 90, 180 ან 270 გრადუსით მოტრიალებით).

რვა ლაზიერის ამოცანა ინფორმატიკაში

ეს ამოცანა წარმოადგენს არატრივიალურ სავარჯიშოს ალგორითმიკაში და ხშირ შემთხვევაში, ის თვალსაჩინო მაგალითად იხმარება რეკურსიული ფუნქციების აღწერის დროს. კომბინატორიკის ინსტრუმენტების გამოყენებით შეიძლება განისაზღვროს ვარიანტების სრული რაოდენობა, თუ კი ყველა ვარიანტის განმხილველ გრძელ და ცუდ გზას ავირჩევთ. საჭიროა განთავსდეს 64 უჯრაზე 8 ლაზიერი, ვარიანტების საერთო რაოდენობა განისაზღვრება ფორმულით: 64! / 56! = 178462987637760. რეკურსიის გამოყენებით კი ვარიანტების რაოდენობა მცირდება 8⁸ = 2²⁴ = 16 777 216–მდე.

პროგრამის მაგალითი C++ –ზე

პროგრამა ამონახსნის სახით ბეჭდავს 92 ამონახნს. შესაძლებელია #define N 8–ში 8–ის შეცვლა. ამ შემთხვევაში პროგრამის ამონახსნი ის ნებისმიერი N იქნება რომელსაც მიუთითებთ 8–ის ნაცვლად.

#include <iostream>
#include <iomanip>
#include <conio.h>

#define N 8
using namespace std;

void Gaanule();
void Dabechde();
void Lazieri(int=0);

int dafa[N][N] = {0};
int hor[N] = {0};
int ver[N] = {0};
int diag_down[N*2-1] = {0}; // i-j+7
int diag_up[N*2-1] = {0}; // i+j

int ramdenia = 0;

int main()
{
	Gaanule();
	Lazieri();

	return 0;
}

void Dabechde()
{
	for(int i=0; i<N; i++)
	{
		for(int k=0; k<N; k++)
		{
			cout << setw(3) << dafa[i][k];
		}

		cout << endl;
	}

	cout << ramdenia << endl;
	cout << endl << endl;
}

void Gaanule()
{
	for(int i=0; i<N; i++)
	{
		for(int k=0; k<N; k++)
		{
			dafa[i][k] = 0;
		}
	}
}

void Lazieri(int i)
{
	for (int j=0; j<N; j++)
	{
		if ( !hor[i] && !ver[j] && !diag_down[i-j+N-1] && !diag_up[i+j] && !dafa[i][j] )
		{
			dafa[i][j] = 1;
			hor[i] = 1;
			ver[j] = 1;
			diag_up[i+j] = 1;
			diag_down[i-j+N-1] = 1;

			if ( i < N-1)
			{
				Lazieri(i+1);
			}
			else
			{
				ramdenia++;
				Dabechde();
			}
			
			if ( i < N)
			{
				dafa[i][j] = 0;
				hor[i] = 0;
				ver[j] = 0;
				diag_up[i+j] = 0;
				diag_down[i-j+N-1] = 0;
			}
		}
	}
}

პროგრამის მაგალითი Java–ზე

class EightQueen
{
	public static void main(String args[])
	{
		Queen q = new Queen(8);
		q.Run(0);
	}
}

class Queen
{
	private int N;
	private int dafa[][];
	private int hor[];
	private int ver[];
	private int diagDown[];
	private int diagUp[];
	public int Ramdenia;
	
	Queen(int Number)
	{
		N = Number;	
		Initialize();
	}
	
	Queen()
	{
		N = 8;
		Initialize();		
	}
	
	private void Initialize()
	{
		Ramdenia = 0;
		dafa = new int[N][N];
		
		hor = new int[N];
		ver = new int[N];
		
		for(int i=0; i<N; i++)
		{
			hor[i] = 0;
			ver[i] = 0;
		}
		
		diagDown = new int[2*N-1];
		diagUp = new int[2*N-1];
		
		for (int i=0; i<2*N-1; i++)
		{
			diagDown[i] = 0;
			diagUp[i] = 0;
		}	
		
		MakeZero();	
	}
	
	public void MakeZero()
	{
		for(int i=0; i<N; i++)
		{
			for(int j=0; j<N; j++)
			{
				dafa[i][j] = 0;
			}
		}	
		
		Ramdenia = 0;	
	}
	
	public void Print()
	{
		for(int i=0; i<N; i++)
		{
			for(int j=0; j<N; j++)
			{
				System.out.print(dafa[i][j] + " ");
			}
			
			System.out.println();
		}
		
		System.out.println(Ramdenia);
		System.out.println();		
	}
	
	public void Run(int i)
	{
		for (int j=0; j<N; j++)
		{
			if ( hor[i] == 0 && ver[j] ==0 && diagDown[i-j+N-1] == 0 
				&& diagUp[i+j] ==0 && dafa[i][j] ==0 )
			{
				dafa[i][j] = 1;
				hor[i] = 1;
				ver[j] = 1;
				diagUp[i+j] = 1;
				diagDown[i-j+N-1] = 1;

				if ( i < N-1)
				{
					Run(i+1);
				}
				else
				{
					Ramdenia++;
					Print();
				}
			
				if ( i < N)
				{
					dafa[i][j] = 0;
					hor[i] = 0;
					ver[j] = 0;
					diagUp[i+j] = 0;
					diagDown[i-j+N-1] = 0;
				}
			}
		}
	}
}

რესურსები ინტერნეტში

• MathWorld article
• Solutions to the 8-Queens Problem
• Walter Kosters's N-Queens Page დაარქივებული 2006-10-14 საიტზე Wayback Machine.
• Durango Bill's N-Queens Page
• On-line Guide to Constraint Programming