Добавил алгоритм обхода конём

2 files changed, 115 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..7e36cc1
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,9 @@
+CXX=g++
+CXXFLAGS=-Wall -Wpedantic -ggdb -std=c++17
+SOURCES := $(wildcard *.cpp)
+EXECS := $(patsubst %.cpp,%.out,$(SOURCES))
+
+all: $(EXECS)
+
+%.out: %.cpp
+	$(CXX) $(CXXFLAGS) $< -o $@
diff --git a/knights-tour.cpp b/knights-tour.cpp
new file mode 100644
index 0000000..3f1e674
--- /dev/null
+++ b/knights-tour.cpp
@@ -0,0 +1,106 @@
+#include <iostream>
+#include <vector>
+#include <iomanip>
+
+typedef std::vector<std::vector<int>> field_t;
+struct point_t { int row, col; };
+
+int n;
+int row, col;
+field_t field;
+
+std::vector<point_t>
+neighbors(int row, int col)
+{
+    std::vector<point_t> v;
+    std::vector<point_t> possible = {
+        { row - 2, col - 1 },
+        { row - 1, col - 2 },
+        { row + 1, col - 2 },
+        { row + 2, col - 1 },
+        { row - 2, col + 1 },
+        { row - 1, col + 2 },
+        { row + 1, col + 2 },
+        { row + 2, col + 1 },
+    };
+
+    for (point_t p : possible)
+    {
+        if (p.row >= 0 && p.row < n &&
+            p.col >= 0 && p.col < n)
+        {
+            v.push_back(p);
+        }
+    }
+
+    return v;
+}
+
+bool
+tour(int row, int col, int step, field_t field, field_t &result)
+{
+    for (point_t p : neighbors(row, col))
+    {
+        if (field[p.row][p.col] != 0) continue;
+        field[p.row][p.col] = step;
+
+        if (step == n * n)
+        {
+            result = field;
+            return true;
+        }
+        if (tour(p.row, p.col, step + 1, field, result))
+        {
+            return true;
+        }
+        field[p.row][p.col] = 0;
+    }
+    return false;
+}
+
+int
+main()
+{
+    std::cout << "Размер поля (n): ";
+    std::cin >> n;
+
+    std::cout << "Положение коня (ряд, колонка): ";
+    std::cin >> row >> col;
+    row--;
+    col--;
+
+    field = std::vector(n, std::vector<int>(n));
+    field[row][col] = 1;
+
+    field_t result(n, std::vector<int>(n));
+    bool found = tour(row, col, 2, field, result);
+
+    int width = 0;
+    {
+        int q = n * n;
+        while (q > 0)
+        {
+            width++;
+            q /= 10;
+        }
+    }
+
+    if (found)
+    {
+        std::cout << "Обход конём найден:" << std::endl;
+        for (int i = 0; i < n; ++i)
+        {
+            for (int j = 0; j < n; ++j)
+            {
+                std::cout << std::setw(width + 1) << result[i][j];
+                if (j < n - 1) std::cout << ' ';
+            }
+            if (i < n - 1) std::cout << '\n';
+        }
+        std::cout << std::endl;
+    }
+    else
+    {
+        std::cout << "Обход конём не найден" << std::endl;
+    }
+}