Numbers from 1 to 33 are written in 64 cells of the 8 x 8 square. Almost finished code, need to add it.

sergeyutkin221 (21)
Hello everyone, I have an assignment which is as follows:
"Write a program that will find a path in a numeric maze according to the specified rules.
Numbers from 1 to 33 are written in 64 cells of the 8 x 8 square. It is necessary, starting with the number 1 in the upper left corner, to draw a broken line that will not intersect itself and will consist of vertical and horizontal sections. The polyline must pass through exactly 33 numbers and end in the lower right corner at number 33. The polyline can only move horizontally or vertically, but not diagonally.
An example of the task execution is shown in the figure by the link: https://ibb.co/3mZHR3s"

I have a almost finished code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
#include <iostream>
using namespace std;
#include <iomanip>
#include <vector>
#include <ctime>
#include <algorithm>
int check(int n, vector<int> &a);
int move(int arr[10][10], vector<int> b, int current, int i, int j, int count);
void restart(int arr[10][10], vector<int> b);
int equal(vector<int> a, vector<int> b);

int equal(vector<int> a, vector<int> b)
{
    if (a == b)
    {
        return 1;
    }
    else
        return 0;
}
void restart(int arr[10][10], vector<int> b)
{
    b.clear();
    b.push_back(-1);
    b.push_back(0);
    int current = 1;
    int i = 1, j = 1;
    int count = 0;
    move(arr, b, current, i, j, count);
}

int move(int arr[10][10], vector<int> b, int current, int i, int j, int count)
{   
    
}

int checkfill(int n, vector<int> &a)
{
    auto it = find(a.begin(), a.end(), n);
    if (it != a.end())
    {
        return 0;
    }
    else
    {
        a.push_back(n);
        return 1;
    }
}

int main()
{
    vector<int> a{-1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33};
    vector<int> b{-1};
    int arr[10][10] = {{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
                       {-1, 1, 16, 5, 20, 25, 9, 21, 1, -1},
                       {-1, 18, 12, 27, 26, 11, 17, 12, 32, -1},
                       {-1, 32, 11, 15, 29, 8, 6, 27, 20, -1},
                       {-1, 17, 4, 13, 24, 30, 28, 31, 2, -1},
                       {-1, 25, 10, 2, 26, 4, 28, 22, 13, -1},
                       {-1, 5, 14, 30, 8, 15, 31, 19, 6, -1},
                       {-1, 23, 7, 24, 16, 29, 22, 18, 19, -1},
                       {-1, 3, 12, 9, 3, 7, 14, 23, 33, -1},
                       {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}};

    int k;

    for (int i = 0; i < 10; i++)
    {
        cout << endl;
        for (int j = 0; j < 10; j++)
        {
            cout << setw(3) << arr[i][j];
        }
    }
    cout << endl;
    restart(arr, b);
    
    return 0;
}

I am asking to help me with the move function, it must go from element [1][1] of the matrix to element [3][3]. Would be very grateful for your help.

Last edited on
lastchance (6980)
Try backtracking.
lastchance (6980)
You had an error in your grid which didn't help matters - one 12 should be a 10.

Anyway, here's a backtracking solution. In the output, numbers in brackets give the order of traversal. If you want to prettify it, change function display(). This is the only solution for this (corrected) grid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
#include <iostream>
#include <iomanip>
#include <utility>
using namespace std;

const int N = 8;
const int LENGTH = 33;
const int ISTART = 0, IEND = N - 1;
const int JSTART = 0, JEND = N - 1;

int A[N][N]{}, mv[N][N]{};
bool used[1+LENGTH]{};

int Grid[N][N] = 
{ {  1, 16,  5, 20, 25,  9, 21,  1 },
  { 18, 10, 27, 26, 11, 17, 12, 32 },
  { 32, 11, 15, 29,  8,  6, 27, 20 },
  { 17,  4, 13, 24, 30, 28, 31,  2 },
  { 25, 10,  2, 26,  4, 28, 22, 13 },
  {  5, 14, 30,  8, 15, 31, 19,  6 },
  { 23,  7, 24, 16, 29, 22, 18, 19 },
  {  3, 12,  9,  3,  7, 14, 23, 33 } };


//==========================================================

void display()
{
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ ) 
      {
         if ( A[i][j] ) cout << setw( 2 ) << A[i][j] << "(" << setw( 2 ) << mv[i][j] << ")  ";
         else           cout << "   --   ";
      }
      cout << '\n';
   }
}

//==========================================================

bool check( int num, int i, int j )
{
   int value = Grid[i][j];
   if ( i < 0 || i >= N || j < 0 || j >= N || A[i][j] || used[value] ) return false;
   if ( i == IEND && j == JEND && num < LENGTH ) return false;
   A[i][j] = value;
   mv[i][j] = num;
   used[value] = true;
   return true;
}

//==========================================================

bool solve( int num, int i0, int j0 )                      // Main backtracking routine
{
   const pair<int,int> jump[] = { {-1,0}, {1,0}, {0,-1}, {0,1} };

   if ( num > LENGTH  )                                    // *** COMPLETION
   {
      display();
      return true;
   }

   for ( int jp = 0; jp < 4; jp++ )                        // *** TRY SURROUNDING POINTS
   {
      int i = i0 + jump[jp].first ;
      int j = j0 + jump[jp].second;
      if ( check( num, i, j ) && solve( num + 1, i, j ) ) return true;   // Key recursion
   }

   A[i0][j0] = mv[i0][j0] = used[Grid[i0][j0]] = 0;        // *** OTHERWISE, TIDY UP
   return false;
}

//==========================================================

int main()
{
   // Start point
   int i = ISTART, j = JSTART, num = 1;
   int value = Grid[i][j];
   A[i][j] = value;
   mv[i][j] = num;
   used[value] = true;

   // Search
   solve( num + 1, i, j );
}


 1( 1)     --    5( 7)  20( 8)  25( 9)   9(10)  21(11)     --   
18( 2)  10( 5)  27( 6)     --      --   17(13)  12(12)     --   
32( 3)  11( 4)     --      --    8(15)   6(14)     --      --   
   --      --   13(18)  24(17)  30(16)     --      --      --   
   --      --    2(19)  26(20)   4(21)  28(22)  22(23)     --   
   --      --      --      --   15(26)  31(25)  19(24)     --   
   --      --      --   16(28)  29(27)     --      --      --   
   --      --      --    3(29)   7(30)  14(31)  23(32)  33(33)

Last edited on
dutch (2548)
I solved it like this. A little different, but same strategy, of course.
Originally I just printed out the solution directions: DDRURURRRRDLDLDLLDRRRRDLLDLDRRRR
Now it prints out a grid like lastchance's.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;

const int Size = 8, Goal = 33;

struct Position {
    int row = 0, col = 0;
    Position() = default;
    Position(int r, int c) : row(r), col(c) { }
    bool operator==(const Position& p) const { return row == p.row && col == p.col; }
    friend ostream& operator<<(ostream& out, const Position& p) {
        return out << '(' << p.col << ',' << p.row << ')';
    }
};

bool solve(int grid[][Size+2], vector<bool>& b, Position p, vector<Position>& path) {
    int val = grid[p.row][p.col];
    if (val == -1 || b[val]) return false;
    b[val] = true;
    if (val == Goal) {
        if (find(b.begin(), b.end(), false) == b.end()) {
            path.push_back(p);
            return true;
        }
    }
    else if (solve(grid, b, Position(p.row+1, p.col), path) ||
             solve(grid, b, Position(p.row-1, p.col), path) ||
             solve(grid, b, Position(p.row, p.col+1), path) ||
             solve(grid, b, Position(p.row, p.col-1), path)) {
        path.push_back(p);
        return true;
    }
    b[val] = false;
    return false;
}

void print_grid(const int grid[][Size+2], const vector<Position>& path) {
        for (int r = 1; r <= Size; ++r) {
            for (int c = 1; c <= Size; ++c) {
                cout << setw(2) << grid[r][c];
                // finding in vector adequate for small paths; otherwise a map should be used
                if (auto it = find(path.begin(), path.end(), Position(r, c)); it != path.end())
                    cout << '(' << setw(2) << path.size() - distance(path.begin(), it) << ") ";
                else
                    cout << "     ";
                    
            }
            cout << '\n';
        }
}

void print_path_dirs(const vector<Position>& path) {
    for (size_t i = path.size(); i-- > 1; )
        if (path[i].row != path[i-1].row)
            cout << (path[i].row < path[i-1].row ? 'D' : 'U');
        else
            cout << (path[i].col < path[i-1].col ? 'R' : 'L');
    cout << '\n';
}

int main() {
    int grid[Size+2][Size+2] = {
        {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
        {-1,  1, 16,  5, 20, 25,  9, 21,  1, -1},
        {-1, 18, 10, 27, 26, 11, 17, 12, 32, -1},
        {-1, 32, 11, 15, 29,  8,  6, 27, 20, -1},
        {-1, 17,  4, 13, 24, 30, 28, 31,  2, -1},
        {-1, 25, 10,  2, 26,  4, 28, 22, 13, -1},
        {-1,  5, 14, 30,  8, 15, 31, 19,  6, -1},
        {-1, 23,  7, 24, 16, 29, 22, 18, 19, -1},
        {-1,  3, 12,  9,  3,  7, 14, 23, 33, -1},
        {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
    };
    vector<bool> b(34);
    b[0] = true;
    vector<Position> path;

    if (solve(grid, b, Position(1, 1), path)) {
        print_grid(grid, path);
        cout << '\n';
        print_path_dirs(path);
    }
    else
        cout << "no solution\n";
}

 1( 1) 16      5( 7) 20( 8) 25( 9)  9(10) 21(11)  1     
18( 2) 10( 5) 27( 6) 26     11     17(13) 12(12) 32     
32( 3) 11( 4) 15     29      8(15)  6(14) 27     20     
17      4     13(18) 24(17) 30(16) 28     31      2     
25     10      2(19) 26(20)  4(21) 28(22) 22(23) 13     
 5     14     30      8     15(26) 31(25) 19(24)  6     
23      7     24     16(28) 29(27) 22     18     19     
 3     12      9      3(29)  7(30) 14(31) 23(32) 33(33) 

DDRURURRRRDLDLDLLDRRRRDLLDLDRRRR
dhayden (5798)
Here's another one. This reads the input from cin. To indicate that a cell is on the current path I negate its value. To indicate that a value has been seen, I use a bitmap. I'm used to this sort of bit twiddling but others might find std::bitset more intuitive. The output indicates the path by negative values.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
#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);
}

$ ./foo < input
  -1   16   -5  -20  -25   -9  -21    1
 -18  -10  -27   26   11  -17  -12   32
 -32  -11   15   29   -8   -6   27   20
  17    4  -13  -24  -30   28   31    2
  25   10   -2  -26   -4  -28  -22   13
   5   14   30    8  -15  -31  -19    6
  23    7   24  -16  -29   22   18   19
   3   12    9   -3   -7  -14  -23  -33

sergeyutkin221 (21)
Could you please help me to redo it so it would go from upper right corner, to lower left?
The arrangement of the numbers is also mirrored.


#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

const int Size = 8, Goal = 33;

struct Position {
int row = 0, col = 0;
Position() = default;
Position(int r, int c) : row(r), col(c) { }
bool operator==(const Position& p) const { return row == p.row && col == p.col; }
friend ostream& operator<<(ostream& out, const Position& p) {
return out << '(' << p.col << ',' << p.row << ')';
}
};

bool solve(int grid[][Size+2], vector<bool>& b, Position p, vector<Position>& path) {
int val = grid[p.row][p.col];
if (val == -1 || b[val]) return false;
b[val] = true;
if (val == Goal) {
if (find(b.begin(), b.end(), false) == b.end()) {
path.push_back(p);
return true;
}
}
else if (solve(grid, b, Position(p.row+1, p.col), path) ||
solve(grid, b, Position(p.row-1, p.col), path) ||
solve(grid, b, Position(p.row, p.col+1), path) ||
solve(grid, b, Position(p.row, p.col-1), path)) {
path.push_back(p);
return true;
}
b[val] = false;
return false;
}

void print_grid(const int grid[][Size+2], const vector<Position>& path) {
for (int r = 1; r <= Size; ++r) {
for (int c = 1; c <= Size; ++c) {
cout << setw(2) << grid[r][c];
// finding in vector adequate for small paths; otherwise a map should be used
if (auto it = find(path.begin(), path.end(), Position(r, c)); it != path.end())
cout << '(' << setw(2) << path.size() - distance(path.begin(), it) << ") ";
else
cout << " ";

}
cout << '\n';
}
}

void print_path_dirs(const vector<Position>& path) {
for (size_t i = path.size(); i-- > 1; )
if (path[i].row != path[i-1].row)
cout << (path[i].row < path[i-1].row ? 'D' : 'U');
else
cout << (path[i].col < path[i-1].col ? 'R' : 'L');
cout << '\n';
}

int main() {
int grid[Size+2][Size+2] = {
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, 1, 21, 9, 25, 20, 5, 16, 1, -1},
{-1, 32, 12, 17, 11, 26, 27, 10, 18, -1},
{-1, 20, 27, 6, 8, 29, 15, 11, 32, -1},
{-1, 2, 31, 28, 30, 24, 13, 4, 17, -1},
{-1, 13, 22, 28, 4, 26, 2, 10, 25, -1},
{-1, 6, 19, 31, 15, 8, 30, 14, 5, -1},
{-1, 19, 18, 22, 29, 16, 24, 7, 23, -1},
{-1, 33, 23, 14, 7, 3, 9, 12, 3, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
};
vector<bool> b(34);
b[0] = true;
vector<Position> path;

if (solve(grid, b, Position(1, 1), path)) {
print_grid(grid, path);
cout << '\n';
print_path_dirs(path);
}
else
cout << "no solution\n";
}
Last edited on
dhayden (5798)
It looks like you have already reversed the order of the items in the grid. Now you just need to tell the algorithm to start at the top right corner. You need to figure that your on your own. It's important that you understand how the code works.
sergeyutkin221 (21)
Could you please help me with this algorithm, I'm a student, I don't really understand how it works yet
seeplus (6592)
I don't really understand how it works yet


Then work through the one of the provided code solutions slowly and carefully, adding your own comments as desired until you do understand it. This might take quite a while until 'you get it' - but stick with it. The concepts of recursion and backtracking are important and you do need to understand. If there's a particular code you don't understand, then ask a specific question about that.
sergeyutkin221 (21)
In fact, I don't have very much time left, it would be faster if you helped me, I would be very grateful to you.
Albatross (4553)
Are you asking us to provide you a solution that you can just plagiarize without even making a basic effort to transform or perhaps even understand it?

-Albatross
dhayden (5798)
These algorithms work very much the same way that you'd solve it by hand. You'd start in the top left (in the original problem) and trace out a path. When you hit a number you've already visited, you try a different direction. If you can't go in any of the 4 directions then you backup one step and try again there.

Each move is done with a recursive call, so "backup up" is just returning from the recursive call, perhaps with some cleanup.

To make this work, you need some extra data besides the grid itself:
1. You have to record the path that you've traced so far. This is so you can avoid crossing over it.
2. You have to record the numbers (1-33) that you've seen so far so you know when you get to a square that contains a number you've already seen
3. You have to record the length of the path because a legal path must pass through exactly 33 squares.

I'll explain my solution. Regarding the extra data that must be stored:
1. I change the sign of the value in the grid to indicate that it's part of the path I'm on.
2. I store the values seen so far in an unsigned long long called "flags" where the n'th bit is set to indicate that n is on the path.
3. Rather than store the size directly, I check if the flags variable has all 33 bits set.

Let's go through the solve(). This gets called to try to add the cell at (row,col) to the path so far. it returns true if it found a legal path through this cell, and false otherwise. I works by seeing if the cell at row,col can be added to the path and then seeing if its neighbors can be added too.
bool Board::solve(int row, int col)

Before we do anything else, we check if row and col are legal values. Obviously there's no path through a row/col that isn't on the board:
1
2
3
4
 
    if (row < 0 || row >= 8 ||
	col < 0 || col >= 8) {
	return false;		// out of bounds
    }


Next I get a reference to the cell value. This is just for shorthand so I don't repeatedly have to type grid[row][col]:
int &cell {grid[row][col]}; // short hand

Remember, I change the sign of a grid value to indicate that it's on the path. That happens below. Here, we'll see if one of the higher-level recursive calls already negated this cell, meaning that it's already on the path
if (cell < 0) return false; // already on the path

Next we'll see if the value of the cell has already been seen by a higher level recursive call. Here << is the bit shift operator and 1ULL is an 1, as an unsigned long long. Se we shift 1 to the left by "cell" positions and see if that bit is already set in flags. If so then we've seen this value already.
    if (flags & (1ULL << cell)) {
	return false;		// That value has been seen
    }


Everything looks good so far. Let's set the flag bit and negate the cell value to indicate that this cell is on the path. If we find that it won't work, we'll switch these back before returning
1
2
3
 
    // 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


Now we'll check if we've found a solution. That happens if we're at the lower right corner and the value of flags has bits 1-33 set (0x3fffffffeULL). If so, then we'll push the current row/col onto a "solutions" vector and return true.
1
2
3
4
5
 
    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;
	}


If we aren't at the end then recursively call solve for the squares that are up, down, left and right of this one. If any of those returns true then return true from here too.
1
2
3
4
5
6
7
8
9
 
    } 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;
	}
    }


Dang. The recursive calls must have all returned false, meaning there is no solution in the current path. Restore the sign of the cell, clear the bit in flags and return false.
1
2
3
 
    cell = -cell;		// restore cell
    flags &= ~(1ULL << cell);	// and flags to previous value
    return false;

}

Hope this helps.
Topic archived. No new replies allowed.