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

თავისუფალი ქართულენოვანი ენციკლოპედია ვიკიპედიიდან
გადასვლა: ნავიგაცია, ძიება
Chess zhor 26.png
Chess zver 26.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.png
Chess zhor 26.png
ერთ–ერთი ამონახსნი

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

ისტორია[რედაქტირება]

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

ამონახსნი[რედაქტირება]

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

რვა ლაზიერის ამოცანა ინფორმატიკაში[რედაქტირება]

ეს ამოცანა წარმოადგენს არატრივიალურ სავარჯიშოს ალგორითმიკაში და ხშირ შემთხვევაში, ის თვალსაჩინო მაგალითად იხმარება რეკურსიული ფუნქციების აღწერის დროს. კომბინატორიკის ინსტრუმენტების გამოყენებით შეიძლება განისაზღვროს ვარიანტების სრული რაოდენობა, თუ კი ყველა ვარიანტის განმხილველ გრძელ და ცუდ გზას ავირჩევთ. საჭიროა განთავსდეს 64 უჯრაზე 8 ლაზიერი, ვარიანტების საერთო რაოდენობა განისაზღვრება ფორმულით: 64! / 56! = 178462987637760. რეკურსიის გამოყენებით კი ვარიანტების რაოდენობა მცირდება 88 = 224 = 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;
                                }
                        }
                }
        }
}

რესურსები ინტერნეტში[რედაქტირება]