I need to write a program that will find its way in the letter maze

[sergeyutkin221]

Greetings
I need to write a program that will find its way in the letter maze.

The letters of the Ukrainian alphabet are written in 64 cells of the 8 x 8 square.
It is necessary, starting with the letter A in the upper right corner, to draw a broken line that will not cross itself and will consist of vertical and horizontal sections.
The broken line must pass exactly through 33 letters of the Ukrainian alphabet and end in the lower left corner on the letter "Я". The broken line can move only horizontally or vertically, but not diagonally.
I need to design the program so that it can solve a puzzle with different inputs and a test case shown in the figure: https://ibb.co/XWCD9V8

I have a code, but it does not fit the conditions, this code is not for letters, but for numbers, and according to the condition, the polyline must go from the upper right corner to the lower left, the code is made so that the polyline goes from the upper left to the lower right:

#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::istream;
using std::ostream;
using std::vector;

struct Point {
Point(int r, int c): row(r), col(c) {}
int row, col;
};

class Board {
public:
int grid[8][8]; // The grid
unsigned long long flags {0}; // If a bit is set then the number is in the path
vector<Point> solution; // The solution in reverse order
void read(istream &is); // read a grid
bool solve(int row, int col); // solve the puzzle
void printSolution(ostream &os); // print the solution or "no solution."
void print(ostream &os);
};


bool Board::solve(int row, int col)
{
if (row < 0 || row >= 8 ||
col < 0 || col >= 8) {
return false; // out of bounds
}

int &cell {grid[row][col]}; // short hand

if (cell < 0) return false; // already on the path

if (flags & (1ULL << cell)) {
return false; // That value has been seen
}

// If you get here then you need to mark this position and move along.
flags |= 1ULL << cell;
cell = -cell; // Indicates a cell on the current path

if (row == 7 && col == 7) { // at bottom right corner
if ((flags | (1ULL << cell)) == 0x3fffffffeULL) { // got all values
solution.push_back(Point(row,col));
return true;
}

} else {
// try up, down, left and right
if (solve(row-1, col) ||
solve(row+1, col) ||
solve(row, col-1) ||
solve(row, col+1)) {
return true;
}
}

cell = -cell; // restore cell
flags &= ~(1ULL << cell); // and flags to previous value
return false;
}

void
Board::read(istream &is)
{
for (auto & row : grid) {
for (auto &cell : row) {
is >> cell;
}
}
solution.clear();
flags = 0;

}

void Board::print(ostream &os)
{
for (auto & row : grid) {
for (auto &cell : row) {
os.width(4);
os << cell << ' ';
}
os << '\n';
}

}

void Board::printSolution(ostream &os)
{
if (solution.size()) {
os << "Size is " << solution.size() << '\n';
for (unsigned i=0; i<solution.size(); ++i) {
Point &p {solution[solution.size()-i-1]};
os << grid[p.row][p.col] << '@' << p.row << ',' << p.col << ' ';
}
cout << '\n';
} else {
os << "No solution\n";
}
}

int main()
{
Board b;
b.read(cin);
b.solve(0,0);
b.print(cout);
}


I would be extremely grateful to you if you could help me with this problem.

[George P]

PLEASE learn to use code tags, they make reading and commenting on source code MUCH easier.

http://www.cplusplus.com/articles/jEywvCM9/
http://www.cplusplus.com/articles/z13hAqkS/

HINT: you can edit your post and add code tags.

Some formatting & indentation would not hurt either

You've posted enough times to know using code tags will be beneficial.

Well, you SHOULD know by now. Trying to read code without tags is a PITA.

[dhayden]

What a coincidence. I have that code too, probably because I wrote it :).
http://www.cplusplus.com/forum/general/278578/

The starting position is given in the first call to solve in main(). The ending position is encoded in this test in solve:
if (row == 7 && col == 7) { // at bottom right corner

The program relies on the values being less than 63 because of the use of the flags variable. You could use one of the other solutions in the linked thread, or modify my code. Change read() to convert letters to numbers and change print() to convert numbers back to letters.

[sergeyutkin221]

I have the input data/filling the grid:

Е Д А З Є Е Б А
К Б И З Ж Д Ґ Б
К П У И І А Г В
Ш О Л А Ї Й Н О
Ч Ц Х І К К Л Щ
Ш Щ Ф У В Н М И
З Ь Є Т П О Е Р
Я Ю Ж С Р Ь С П

How should i modify your code to find a path from upper right "A" to lower left "Я"?
Could u please help me?

[dhayden]

I don't want to tell you exactly how to change the program because I want you to learn how it works and how to make the change yourself. I suggest you first modify it to find the path from upper right to lower left using numbers. Then change the code to read the letters, convert to numeric values, solve the puzzle and covert back to letters when generating the output. I don't know much about multi-byte I/O so I can't help you there.