Наиболее известная задача о шахматных расстановках. Требуется расставить 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+, с/с++
|
|||||||