Доброго всем времени суток.
Меня заинтересовала следующая шахматная задача: попытаться обойти конем шахматную доску. Конь должен побывать в каждой клетке только один раз. Вот решение:
#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", ¤tPosition[0]);
//ЗАЩИТА ОТ НЕПРАВИЛЬНО ЗАДАННОЙ КООРДИНАТЫ
if (currentPosition[0] < 0 || currentPosition[0] > 7)
{
printf("НЕПРАВИЛЬНО ЗАДАННАЯ КООРДИНАТА\n");
return 0;
}
printf("X = ");
scanf("%d", ¤tPosition[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>
Задача в итоге заходит в тупик (конь сам загоняет себя в окружение). Буду оптимизировать, посмотрим что получится.
Комментарии
продолжение шахматной задачи
В данном варианте добавлена функция поиска оптимального хода с учетом матрицы доступности (матрица, которая содержит информацию о доступности каждой клетки на доске)
#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 optimal (int, int);
//MAIN
int main()
{
printf("Введите первичные координаты коня:\n");
printf("Y = ");
scanf("%d", ¤tPosition[0]);
//ЗАЩИТА ОТ НЕПРАВИЛЬНО ЗАДАННОЙ КООРДИНАТЫ
if (currentPosition[0] < 0 || currentPosition[0] > 7)
{
printf("НЕПРАВИЛЬНО ЗАДАННАЯ КООРДИНАТА\n");
return 0;
}
printf("X = ");
scanf("%d", ¤tPosition[1]);
//ЗАЩИТА ОТ НЕПРАВИЛЬНО ЗАДАННОЙ КООРДИНАТЫ
if (currentPosition[1] < 0 || currentPosition[1] > 7)
{
printf("НЕПРАВИЛЬНО ЗАДАННАЯ КООРДИНАТА\n");
return 0;
}
printf("\n");
int counter = 0;
while (stepNumber <= 63 || (currentPosition[0] < 25 || currentPosition[1] < 25))
{
stepNumber++;
step(currentPosition[0], currentPosition[1]);
//printing2(board, ROWS, COLS);// КОНТРОЛЬНЫЙ ПРИНТ
counter++;
}
printing2(board, ROWS, COLS);// КОНТРОЛЬНЫЙ ПРИНТ
printf("\nКоличество ходов %d\n", counter);
return 0;
}
//ПРОГРАММИРОВАНИЕ ХОДА КОНЕМ
unsigned int step(int y,int x)
{
//НОМЕР ВАРИАНТА ХОДА КОНЕМ
unsigned int moveNumber = 0;
moveNumber = optimal(currentPosition[0], currentPosition[1]);
switch (moveNumber)
{
case 0:
{
board [y + vert[0]][x + hor[0]] = stepNumber;
currentPosition[0] = y + vert[0];
currentPosition[1] = x + hor[0];
return *currentPosition;
}
case 1:
{
board [y + vert[1]][x + hor[1]] = stepNumber;
currentPosition[0] = y + vert[1];
currentPosition[1] = x + hor[1];
return *currentPosition;
}
case 2:
{
board [y + vert[2]][x + hor[2]] = stepNumber;
currentPosition[0] = y + vert[2];
currentPosition[1] = x + hor[2];
return *currentPosition;
}
case 3:
{
board [y + vert[3]][x + hor[3]] = stepNumber;
currentPosition[0] = y + vert[3];
currentPosition[1] = x + hor[3];
return *currentPosition;
}
case 4:
{
board [y + vert[4]][x + hor[4]] = stepNumber;
currentPosition[0] = y + vert[4];
currentPosition[1] = x + hor[4];
return *currentPosition;
}
case 5:
{
board [y + vert[5]][x + hor[5]] = stepNumber;
currentPosition[0] = y + vert[5];
currentPosition[1] = x + hor[5];
return *currentPosition;
}
case 6:
{
board [y + vert[6]][x + hor[6]] = stepNumber;
currentPosition[0] = y + vert[6];
currentPosition[1] = x + hor[6];
return *currentPosition;
}
case 7:
{
board [y + vert[7]][x + hor[7]] = stepNumber;
currentPosition[0] = y + vert[7];
currentPosition[1] = x + hor[7];
return *currentPosition;
}
case 10:
{
currentPosition[0] = 25;
currentPosition[1] = 25;
return *currentPosition;
}
}
}
//ФУНКЦИЯ ОТСЕВА НЕВОЗМОЖНЫХ ХОДОВ И НАХОЖДЕНИЯ ОПТИМАЛЬНЫХ ХОДОВ
int optimal (int y, int x)
{
//МАТРИЦА ДОСТУПНОСТИ
const int matrix [ROWS][COLS] = {{2, 3, 4, 4, 4, 4, 3, 2},
{3, 4, 6, 6, 6, 6, 4, 3},
{4, 6, 8, 8, 8, 8, 6, 4},
{4, 6, 8, 8, 8, 8, 6, 4},
{4, 6, 8, 8, 8, 8, 6, 4},
{4, 6, 8, 8, 8, 8, 6, 4},
{3, 4, 6, 6, 6, 6, 4, 3},
{2, 3, 4, 4, 4, 4, 3, 2}};
int regection [8] = {0};//МАССИВ ВЫБРАКОКВИ НЕВОЗМОЖНЫХ ХОДОВ 1 - ХОД ВОЗМОЖЕН 0 - ХОД НЕВОЗМОЖЕН char - ДЛЯ ЭКОНОМИИ ПАМЯТИ (если прокатит);
int min = 8, minStep = 0;
x = currentPosition[1];
y = currentPosition[0];
int flagPossibility = 0;//ФЛАГ ВОЗМОЖНОСТИ ХОДА
for (int i = 0; i < 8; i++)
{
//ЭТИМ ИФОМ ПРОВЕРЯЕТСЯ ВОЗМОЖЕН ЛИ ДАННЫЙ ХОД ИЗ ДАННОЙ ПОЗИЦИИ
//(board [y + vert[0]][x + hor[0]] < 1) - это условие чтобы конь не ходил в клетки, где он уже был
if (((y + vert[i]) >= 0) && ((y + vert[i]) < 8) && ((x + hor[i]) >= 0) && ((x + hor[i]) < 8) && (board [y + vert[i]][x + hor[i]] < 1))
{
regection [i] = 1;
flagPossibility = 1;
}
else
{
regection [i] = 0;
}
}
if (flagPossibility < 1) //БЛОК ПРОВЕРКИ ВОЗМОЖНОСТИ ПОХОДИТЬ КУДА-ЛИБО ВООБЩЕ
{
return 10;//ЕСЛИ НЕТ - ПЕРЕДАЕМ В ФУНКЦИЮ step ЗНАЧЕНИЕ 10 ДЛЯ ЗАВЕРШЕНИЯ РАБОТЫ ПРОГРАММЫ
}
//ЭТИМ БЛОКОМ ОПЕРАЦИЙ ВЫЯСНЯЕМ НАИБОЛЕЕ ПРИЕМЛЕМЫЙ ВАРИАНТ ХОДА ИЗ ДАННОЙ ПОЗИЦИИ
//Я ДОЛЖЕН ЗАПОМНИТЬ ВАРИАНТ ХОДА С НАИМЕНЬШИМ ЗНАЧЕНИЕМ В МАТРИЦЕ ВОЗМОЖНОСТИ
for (int counter1 = 0; counter1 < 8; counter1++)
{
if (regection [counter1] > 0 )
{
if (matrix[y + vert [counter1]][x + hor[counter1]] <= min)
{
min = matrix[y + vert [counter1]][x + hor[counter1]];
minStep = counter1;
}
}
}
return minStep;
}
// КОНТРОЛЬНЫЙ ПРИНТ
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");
}
printf("\n");
return 0;
}
продолжение шахматной задачи с генератором псевдослучайных чисел
В принципе все тоже самое, но вместо поиска оптимального хода применяем псевдослучайное значение хода
#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 optimal (int, int);
//MAIN
int main()
{
printf("Введите первичные координаты коня:\n");
printf("Y = ");
scanf("%d", ¤tPosition[0]);
//ЗАЩИТА ОТ НЕПРАВИЛЬНО ЗАДАННОЙ КООРДИНАТЫ
if (currentPosition[0] < 0 || currentPosition[0] > 7)
{
printf("НЕПРАВИЛЬНО ЗАДАННАЯ КООРДИНАТА\n");
return 0;
}
printf("X = ");
scanf("%d", ¤tPosition[1]);
//ЗАЩИТА ОТ НЕПРАВИЛЬНО ЗАДАННОЙ КООРДИНАТЫ
if (currentPosition[1] < 0 || currentPosition[1] > 7)
{
printf("НЕПРАВИЛЬНО ЗАДАННАЯ КООРДИНАТА\n");
return 0;
}
printf("\n");
int counter = 0;
while (stepNumber <= 63 || (currentPosition[0] < 25 || currentPosition[1] < 25))
{
stepNumber++;
step(currentPosition[0], currentPosition[1]);
//printing2(board, ROWS, COLS);// КОНТРОЛЬНЫЙ ПРИНТ
counter++;
}
printing2(board, ROWS, COLS);// КОНТРОЛЬНЫЙ ПРИНТ
printf("\nКоличество ходов %d\n", counter);
return 0;
}
//ПРОГРАММИРОВАНИЕ ХОДА КОНЕМ
unsigned int step(int y,int x)
{
//НОМЕР ВАРИАНТА ХОДА КОНЕМ
unsigned int moveNumber = 0;
moveNumber = optimal(currentPosition[0], currentPosition[1]);
switch (moveNumber)
{
case 0:
{
board [y + vert[0]][x + hor[0]] = stepNumber;
currentPosition[0] = y + vert[0];
currentPosition[1] = x + hor[0];
return *currentPosition;
}
case 1:
{
board [y + vert[1]][x + hor[1]] = stepNumber;
currentPosition[0] = y + vert[1];
currentPosition[1] = x + hor[1];
return *currentPosition;
}
case 2:
{
board [y + vert[2]][x + hor[2]] = stepNumber;
currentPosition[0] = y + vert[2];
currentPosition[1] = x + hor[2];
return *currentPosition;
}
case 3:
{
board [y + vert[3]][x + hor[3]] = stepNumber;
currentPosition[0] = y + vert[3];
currentPosition[1] = x + hor[3];
return *currentPosition;
}
case 4:
{
board [y + vert[4]][x + hor[4]] = stepNumber;
currentPosition[0] = y + vert[4];
currentPosition[1] = x + hor[4];
return *currentPosition;
}
case 5:
{
board [y + vert[5]][x + hor[5]] = stepNumber;
currentPosition[0] = y + vert[5];
currentPosition[1] = x + hor[5];
return *currentPosition;
}
case 6:
{
board [y + vert[6]][x + hor[6]] = stepNumber;
currentPosition[0] = y + vert[6];
currentPosition[1] = x + hor[6];
return *currentPosition;
}
case 7:
{
board [y + vert[7]][x + hor[7]] = stepNumber;
currentPosition[0] = y + vert[7];
currentPosition[1] = x + hor[7];
return *currentPosition;
}
case 10:
{
currentPosition[0] = 25;
currentPosition[1] = 25;
return *currentPosition;
}
}
}
//ФУНКЦИЯ ОТСЕВА НЕВОЗМОЖНЫХ ХОДОВ И НАХОЖДЕНИЯ ОПТИМАЛЬНЫХ ХОДОВ
int optimal (int y, int x)
{
/*
//МАТРИЦА ДОСТУПНОСТИ
const int matrix [ROWS][COLS] = {{2, 3, 4, 4, 4, 4, 3, 2},
{3, 4, 6, 6, 6, 6, 4, 3},
{4, 6, 8, 8, 8, 8, 6, 4},
{4, 6, 8, 8, 8, 8, 6, 4},
{4, 6, 8, 8, 8, 8, 6, 4},
{4, 6, 8, 8, 8, 8, 6, 4},
{3, 4, 6, 6, 6, 6, 4, 3},
{2, 3, 4, 4, 4, 4, 3, 2}};*/
int regection [8] = {0};//МАССИВ ВЫБРАКОКВИ НЕВОЗМОЖНЫХ ХОДОВ 1 - ХОД ВОЗМОЖЕН 0 - ХОД НЕВОЗМОЖЕН char - ДЛЯ ЭКОНОМИИ ПАМЯТИ (если прокатит);
int min = 8, minStep = 0, counter1 = 0;
x = currentPosition[1];
y = currentPosition[0];
int flagPossibility = 0;//ФЛАГ ВОЗМОЖНОСТИ ХОДА
for (int i = 0; i < 8; i++)
{
//ЭТИМ ИФОМ ПРОВЕРЯЕТСЯ ВОЗМОЖЕН ЛИ ДАННЫЙ ХОД ИЗ ДАННОЙ ПОЗИЦИИ
//(board [y + vert[0]][x + hor[0]] < 1) - это условие чтобы конь не ходил в клетки, где он уже был
if (((y + vert[i]) >= 0) && ((y + vert[i]) < 8) && ((x + hor[i]) >= 0) && ((x + hor[i]) < 8) && (board [y + vert[i]][x + hor[i]] < 1))
{
regection [i] = 1;
flagPossibility = 1;
}
else
{
regection [i] = 0;
}
}
if (flagPossibility < 1) //БЛОК ПРОВЕРКИ ВОЗМОЖНОСТИ ПОХОДИТЬ КУДА-ЛИБО ВООБЩЕ
{
return 10;//ЕСЛИ НЕТ - ПЕРЕДАЕМ В ФУНКЦИЮ step ЗНАЧЕНИЕ 10 ДЛЯ ЗАВЕРШЕНИЯ РАБОТЫ ПРОГРАММЫ
}
// ЭТИМ БЛОКОМ ОПЕРАЦИЙ ГЕНЕРИРУЕМ ПСЕВДОСЛУЧАЙНЫЙ ХОД
label1:
counter1 = rand() % 7;
if (regection[counter1] > 0)
{
minStep = counter1;
return minStep;
}
else
{
goto label1;
}
}
// КОНТРОЛЬНЫЙ ПРИНТ
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");
}
printf("\n");
return 0;
}