Задача о 8 ферзях

screen

Наиболее известная задача о шахматных расстановках. Требуется расставить 8 ферзей на шахматной доске таким образом, чтобы они не били друг друга.

В программе используется алгоритм перебора с возвратами. Просматривается шахматная доска от нулевой до седьмой вертикали. При
переходе к очередной вертикали имеется 8 вариантов размещения ферзя: от нулевой до седьмой горизонтали. Для каждой горизонтали, в свою очередь, производится проверка, не находится ли поле под боем, пока не будет найдено правильное положение ферзя на этой вертикали, иначе происходит возврат.

void main()
{
#include <stdlib.h>
#include <gtk/gtk.h>
#include <gdk/gdkkeysyms.h>
#include <../cairo/cairo.h>
 
/*Размеры окна */
 
#define WIDTH  720
#define HEIGHT 700
 
/*Количество ферзей*/
#define N 8
 
// ->> Обьявление функций
gboolean   Draw   ( GtkWidget*, GdkEventExpose*, gpointer  );
gboolean KeyPress ( GtkWidget*,  GdkEventKey*,   gpointer  );
 
char      check      (  int* , int  );
void   print_field   (  int* , int  );
void      build      (  int* , int  );
// <<-
 
 
// ->> Указатели для хранения виджета(окна) и 2 изображений (доски и ферзя)
  GtkWidget         *window       =   NULL;
cairo_surface_t     *background   =   NULL;
cairo_surface_t     *queen        =   NULL;
// <<-
 
// ->> Максимальное количество вариантов и текущий просматриваемый вариант расстановки
int MaxNumber = 0;
int CurrentVariant = 0;
// <<-
 
// ->> Двумерный массив хранения координат по X для каждого из 92 случаев для 8 ферзей и строка вывода собщения
int AllPos[93][8];
char MessageString[100 + 1];
// <<-
 
// ->> Просмотр шахматной доски и проверка, не находится ли поле под боем
char check ( int *A, int n )
{
    int i,j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {
            if ( ( A[i] == A[j] ) && ( i != j ) && ( A[i] != 0 ) )
                return 0;
            if ( ( ( A[i] + i ) == ( A[j] + j ) ) && ( i != j ) && ( A[i] != 0 ) && ( A[j] != 0 ) )
                return 0;
            if ( ( ( A[i] - i ) == ( A[j] - j ) ) && ( i != j ) && ( A[i] != 0 ) && ( A[j] != 0 ) )
                return 0;
    }
    return 1;
}
 
void print_field ( int *A, int n )
{
    int i,j;
    for (i = 0; i < n; i++)
    {
        for( j = 0; j < n; j++)
            printf("--");
        printf("-\n");
        for (j = 1; j < A[i]; j++)
            printf("| ");
        printf("|F");
        //Записываем расположениt ферзя по X координате
 
        AllPos[MaxNumber][i] = A[i];
 
        for (j = A[i]; j < n; j++)
            printf("| ");
        printf("|\n");
    }
    for(j = 0; j < n; j++)
        printf("--");
    printf("-\n\n");
    //Увеличиваем кол-во вариантов
    MaxNumber++;
}
 
 
void build ( int *A, int n )
{
    int *B;
    int i,k;
    for( k = 0; ( A[k] != 0 ) && ( k < n ); k++ );
    if( k >= n )
    {
        print_field ( A, n );
        return;
    }
    B = (int *) malloc( n * sizeof(int) );
    for ( i = 0; i < k; i++ )
        B[i] = A[i];
    for ( i = k; i < n; i++ )
        B[i] = 0;
 
    for ( i = 1; i <= n; i++ )
    {
        B[k] = i;
        if ( check ( B, n ) )
            build ( B, n );
    }
    free( B );
}
 
 
int main ( int argc, char *argv[] )
{
    gtk_init (&argc, &argv);                        //Инициализируем GTK+
 
    window = gtk_window_new (GTK_WINDOW_TOPLEVEL);  //Создаём окно поверх остальных созданных
    gtk_window_set_title (GTK_WINDOW (window), "Queen Algorithm");                  //Устанавливаем заголовок окна
 
    background   =   cairo_image_surface_create_from_png (   "image/bg.png"   );    //Открываем изображение доски
      queen      =   cairo_image_surface_create_from_png (  "image/queen.png" );    //Открываем изображение ферзя
 
    gtk_widget_set_size_request (  window,    WIDTH,   HEIGHT  );                   //Устанавливаем размеры окна
    gtk_window_set_resizable    ( GTK_WINDOW ( window ), FALSE );                   //Запрещаем возможность растяжения окна
 
    gtk_window_set_position ( GTK_WINDOW ( window ), GTK_WIN_POS_CENTER );          //Устанавливаем окно по-середине экрана
    gtk_widget_realize ( window );
 
    /*
        ->> Создаём 3 события: 1 - проверяет закрыто ли окно, в случае закрытия вызывает функцию остановки главного цикла GTK
            2 - События прорисовки экрана, требуется для прорисовки изображения
            3 - Событие, отслеживающее нажатие клавиши
    */
    g_signal_connect ( window,    "destroy",      gtk_main_quit,   NULL );
    g_signal_connect ( window,  "expose-event",        Draw,       NULL );
    g_signal_connect ( window, "key_press_event",    KeyPress,     NULL );
    // <<-
 
    gtk_widget_show_all ( window );                             //Отображаем наше окно
 
    //построение
    int A[N];
    int i;
    for ( i = 0; i < N; i++)
        A[i] = 0;
 
    build(A, N);
    char str[] = "Resheniy: %i ";
    printf(str, MaxNumber);
    // <<-
 
    gtk_main ();                                            //Запускаем главный, бесконечный цикл GTK
 
    /* ->>
        После срабатывания события закрытия окна, выключается главный цикл, после чего мы уничтожаем
        в оперативной памяти изображения, которые были открыты ранее (Доска и ферзь)
    */
    cairo_surface_destroy ( background );
    cairo_surface_destroy (    queen   );
    // <<-
    return 0;
}
 
 
// ->> Функция вызывается после срабатывания события нажатия клавиши
// ->> Параметры: 1 - виджет, в котором сработало событие - т.е. наше окно
// ->> 2 - Параметры самого события
// ->> 3 - Данные, передаваемые в функцию, но здесь они в принципе не нужны, т.к. мы ничего не передаём
gboolean KeyPress ( GtkWidget *wid, GdkEventKey *event, gpointer data )
{
    //Проверка, какая клавиша была нажата..
    switch( event->keyval )
    {
        //Если клавиша в право или D - показать след. вариант расстновки
        case GDK_Right:
        case GDK_d:
 
            printf("Right is pressed\n");
            //Проверка, что если мы дошли до конца списка возможных вариантов расстановки - то начать заного
            if( ++CurrentVariant >= MaxNumber )
                CurrentVariant = 0;
            //Стереть текущее расположение изображение в окне
            gtk_widget_queue_clear(wid);
 
            break;
        //Если влево или A - предыдущий
        case GDK_Left:
        case GDK_a:
 
            printf("Left is pressed\n");
            //Тут аналогично
            if( --CurrentVariant < 0 )
                CurrentVariant = MaxNumber - 1;
            //Стереть текущее расположение изображение в окне
            gtk_widget_queue_clear(wid);
 
            break;
    }
 
    return TRUE;
}
 
//Функция вызывается при прорисовке изображений внутри окна, параметры те же, что и в предыдущей функции
gboolean Draw ( GtkWidget *wid, GdkEventExpose *event, gpointer data )
{
    cairo_t *cr ;
    //Создаём область для рисования в окне
    cr = gdk_cairo_create ( wid->window );
    //Рисуем изображение шахматной доски в координатах (0.0)
    cairo_set_source_surface ( cr, background,  0,  0 );
    //Рисуем...
    cairo_paint ( cr );
    //Циклом прогоняем все 8 ферзей, и каждый рисуем в соответствии с координатами умноженными на масштаб, т.к. область рисования у нас не единичная
    int i;
    for(i = 0; i < N; i++) {
        cairo_set_source_surface ( cr, queen, 90 * AllPos[CurrentVariant][i] - 90 + 3, i * 90 + 4 );
        cairo_paint ( cr );
    }
    //Формируем строку вывода вариантов
    sprintf(MessageString, "Current Variant: %d, Max: %d", CurrentVariant + 1, MaxNumber);
    //Устанавливаем цвет текста, его размер, и месторасположение
    cairo_set_source_rgb(cr, 1.0, 0.8, 0.2);
    cairo_set_font_size(cr, 20);
    cairo_move_to(cr, 10, HEIGHT - 10);
    //Выводим текст
    cairo_show_text(cr, MessageString);
    //Удаляем область рисования
    cairo_destroy ( cr );
 
 
    return TRUE;
}
 
 
}

Ключевые слова: 
8 ферзей, шахматные расстановки, gtk+, с/с++
ВложениеРазмер
Chess.rar1.17 Мб