Программирование на C и C++

Онлайн справочник программиста на C и C++

шахматная задача

Аватар пользователя merkul40
ср, 10/11/2017 - 19:37 -- merkul40

Доброго всем времени суток.
Меня заинтересовала следующая шахматная задача: попытаться обойти конем шахматную доску. Конь должен побывать в каждой клетке только один раз. Вот решение:

// MAIN FILE

#include<stdio.h>
#include<stdlib.h>

#define         COLS    8               // Размер массива
#define         ROWS    8               // Размер массива

//ВАРИАНТЫ ХОДА
//КОНЕМ
const int hor [ROWS] = {2, 1, -1, -2, -2, -1, 1, 2};
const int vert [COLS] = {-1, -2, -2, -1, 1, 2, 2, 1};

//ОБЪЯВЛЕНИЯ МАССИВА
// ШАХМАТНОЙ ДОСКИ
unsigned int board [ROWS][COLS] = {{0, 0, 0, 0, 0, 0, 0, 0},
                                                                  {0, 0, 0, 0, 0, 0, 0, 0},
                                                                  {0, 0, 0, 0, 0, 0, 0, 0},
                                                                  {0, 0, 0, 0, 0, 0, 0, 0},
                                                                  {0, 0, 0, 0, 0, 0, 0, 0},
                                                                  {0, 0, 0, 0, 0, 0, 0, 0},
                                                                  {0, 0, 0, 0, 0, 0, 0, 0},
                                                                  {0, 0, 0, 0, 0, 0, 0, 0}};

// СЧЕТЧИК ХОДОВ, ДОЛЖЕН БЫТЬ < 64
unsigned int stepNumber = 0;   

//КООРДИНАТЫ КОНЯ В МАССИВЕ
unsigned int currentPosition[2] = {0};

//ПРОТОТИПЫ ФУНКЦИЙ
unsigned int step(int, int);
int printing2 (unsigned int mass[ROWS][COLS], int, int);

int main()
{

                                                                   
        printf("Введите первичные координаты коня:\n");
        printf("Y = ");
        scanf("%d", &currentPosition[0]);
       
        //ЗАЩИТА ОТ НЕПРАВИЛЬНО ЗАДАННОЙ КООРДИНАТЫ
        if (currentPosition[0] < 0 || currentPosition[0] > 7)
        {
                printf("НЕПРАВИЛЬНО ЗАДАННАЯ КООРДИНАТА\n");
                return 0;
                }
        printf("X = ");
        scanf("%d", &currentPosition[1]);
       
        //ЗАЩИТА ОТ НЕПРАВИЛЬНО ЗАДАННОЙ КООРДИНАТЫ
        if (currentPosition[1] < 0 || currentPosition[1] > 7)
        {
                printf("НЕПРАВИЛЬНО ЗАДАННАЯ КООРДИНАТА\n");
                return 0;
                }
        do
        {
                stepNumber++;
                step(currentPosition[0], currentPosition[1]);
                //step(currentPosition[0], currentPosition[1]);
                }
        while (stepNumber < 64 || (currentPosition[0] != 25 && currentPosition[1] != 25));
       
        printing2(board, ROWS, COLS);// КОНТРОЛЬНЫЙ ПРИНТ
        }

//ПРОГРАММИРОВАНИЕ ХОДА КОНЕМ
//ПРОВЕРКА ПОПАДАНИЯ В ПРЕДЕЛЫ ДОСКИ ПРОЙДЕНА
//(board [y + vert[0]][x + hor[0]] < 1) - это условие чтобы конь не ходил в клетки, где он уже был
unsigned int step(int y,int x)
{

//НОМЕР ВАРИАНТА ХОДА КОНЕМ
unsigned int moveNumber = 0;
       
                moveNumber = 0;//rand() % 7;
               
                switch (moveNumber)
                {
                        case 0:
                                if (((y + vert[0]) >= 0) && ((y + vert[0]) < 8) && ((x + hor[0]) >= 0) && ((x + hor[0]) < 8) && (board [y + vert[0]][x + hor[0]] < 1))
                                {                                      
                                        board [y + vert[0]][x + hor[0]] = stepNumber;
                                        currentPosition[0] = y + vert[0];
                                        currentPosition[1] = x + hor[0];
                                        return currentPosition;
                                        }                              
                        case 1:
                                if (((y + vert[1]) >= 0) && ((y + vert[1]) < 8) && ((x + hor[1]) >= 0) && ((x + hor[1]) < 8) && (board [y + vert[1]][x + hor[1]] < 1))
                                {
                                        board [y + vert[1]][x + hor[1]] = stepNumber;
                                        currentPosition[0] = y + vert[1];
                                        currentPosition[1] = x + hor[1];
                                        return currentPosition;
                                        }              
                        case 2:
                                if (((y + vert[2]) >= 0) && ((y + vert[2]) < 8) && ((x + hor[2]) >= 0) && ((x + hor[2]) < 8) && (board [y + vert[2]][x + hor[2]] < 1))
                                {                                      
                                        board [y + vert[2]][x + hor[2]] = stepNumber;
                                        currentPosition[0] = y + vert[2];
                                        currentPosition[1] = x + hor[2];
                                        return currentPosition;
                                        }      
                        case 3:
                                if (((y + vert[3]) >= 0) && ((y + vert[3]) < 8) && ((x + hor[3]) >= 0) && ((x + hor[3]) < 8) && (board [y + vert[3]][x + hor[3]] < 1))
                                {                                      
                                        board [y + vert[3]][x + hor[3]] = stepNumber;
                                        currentPosition[0] = y + vert[3];
                                        currentPosition[1] = x + hor[3];
                                        return currentPosition;
                                        }      
                        case 4:
                                if (((y + vert[4]) >= 0) && ((y + vert[4]) < 8) && ((x + hor[4]) >= 0) && ((x + hor[4]) < 8) && (board [y + vert[4]][x + hor[4]] < 1))
                                {                                      
                                        board [y + vert[4]][x + hor[4]] = stepNumber;
                                        currentPosition[0] = y + vert[4];
                                        currentPosition[1] = x + hor[4];
                                        return currentPosition;
                                        }      
                        case 5:
                                if (((y + vert[5]) >= 0) && ((y + vert[5]) < 8) && ((x + hor[5]) >= 0) && ((x + hor[5]) < 8) && (board [y + vert[5]][x + hor[5]] < 1))
                                {                                      
                                        board [y + vert[5]][x + hor[5]] = stepNumber;
                                        currentPosition[0] = y + vert[5];
                                        currentPosition[1] = x + hor[5];
                                        return currentPosition;
                                        }      
                        case 6:
                                if (((y + vert[6]) >= 0) && ((y + vert[6]) < 8) && ((x + hor[6]) >= 0) && ((x + hor[6]) < 8) && (board [y + vert[6]][x + hor[6]] < 1))
                                {                                      
                                        board [y + vert[6]][x + hor[6]] = stepNumber;
                                        currentPosition[0] = y + vert[6];
                                        currentPosition[1] = x + hor[6];
                                        return currentPosition;
                                        }      
                        case 7:
                                if (((y + vert[7]) >= 0) && ((y + vert[7]) < 8) && ((x + hor[7]) >= 0) && ((x + hor[7]) < 8) && (board [y + vert[7]][x + hor[7]] < 1))
                                {                                      
                                        board [y + vert[7]][x + hor[7]] = stepNumber;
                                        currentPosition[0] = y + vert[7];
                                        currentPosition[1] = x + hor[7];
                                        return currentPosition;
                                        }      
                        default:
                                currentPosition[0] = 25;
                                currentPosition[1] = 25;
                                return currentPosition;                        
                        }              
        }

// КОНТРОЛЬНЫЙ ПРИНТ
int printing2(unsigned int mass[ROWS][COLS], int  rowQuantity, int colQuantity)
{
        for (int i = 0; i < rowQuantity; i++)
        {
                for (int j = 0; j < colQuantity; j++)
                {
                        printf("%d\t", mass[i][j]);
                        }
                printf("\n");
                }
return 0;

<c>
Задача в итоге заходит в тупик (конь сам загоняет себя в окружение). Буду оптимизировать, посмотрим что получится.