Knight's Tour

[anishagg17]

https://github.com/mrsac7/CSES-Solutions/blob/master/src/1689%20-%20Knight's%20Tour.cpp

Hello @mrsac7 can you please explain to me why do we need to sort the points,

CSES-Solutions/src/1689 - Knight's Tour.cpp

Line 70 in becd3cc

sort(all(v));

Also why we are checking for !grid[x1][y1] in

CSES-Solutions/src/1689 - Knight's Tour.cpp

Line 55 in becd3cc

if (x2>=1 && x2<=8 && y2>=1 && y2<=8 && !grid[x1][y1]) s++;

[mrsac7]

Hello @mrsac7 can you please explain to me why do we need to sort the points,

Hello @anishagg17! Sure. I'm using Warnsdorf ’s rule. According to Antti Laaksonen - Competitive Programmer's Handbook:

Warnsdorf’s rule is a simple and effective heuristic for finding a knight’s tour. Using the rule, it is possible to efficiently construct a tour even on a large board. The idea is to always move the knight so that it ends up in a square where the number of possible moves is as small as possible.

deg function calculates the number of moves possible from a cell. Here, I'm storing the number of moves possible from a cell (x1, y1) in the vector vc<tiii> v.

CSES-Solutions/src/1689 - Knight's Tour.cpp

Lines 66 to 67 in becd3cc

	int d = deg(x1,y1);
	v.pb({d,x1,y1});

And then I'm sorting the cells according to the number of possible moves so that I can move my knight to the cell from which the least number of moves are possible (Warnsdorf's rule).

CSES-Solutions/src/1689 - Knight's Tour.cpp

Line 70 in becd3cc

sort(all(v));

The grid contains 0 on empty cells and a positive number on the occupied cells. I'm checking !grid[x1][y1] to ensure that the cell is empty. This is required because we can only move the knight on empty cells in every subsequent move.

[anishagg17]

I'm checking !grid[x1][y1] to ensure that the cell is empty

but the cell should be grid[x2][y2], I think

[mrsac7]

but the cell should be grid[x2][y2], I think

Suppose my knight is currently at the cell (x, y). From here, I will explore all the empty cells (x1, y1) which can be reached from (x, y) in a single move. So I need to check the empty condition for the cell (x1, y1).

Cells (x2, y2) are different. They come into play when I calculate the degree of each cell (x1, y1). Because to calculate the degree, I need to count the number of empty cells (x2, y2) which can be reached from (x1, y1). This calculation takes place in the deg function.

[anishagg17]

CSES-Solutions/src/1689 - Knight's Tour.cpp

Lines 51 to 58 in becd3cc

	int deg(int x1, int y1){
	int s = 0;
	rep(i1,0,8){
	int x2 = x1+fx[i1], y2 = y1+fy[i1];
	if (x2>=1 && x2<=8 && y2>=1 && y2<=8 && !grid[x1][y1]) s++;
	}
	return s;
	}

empty neighbors to (x1,y1) are (x2,y2) , so why are you checking if (x1,y1) is empty on line 55?

I just mean to say

         if (x2>=1 && x2<=8 && y2>=1 && y2<=8 && !grid[**x1**][**y1**]) s++; 

Should this be changed to

         if (x2>=1 && x2<=8 && y2>=1 && y2<=8 && !grid[**x2**][**y2**]) s++; 

[mrsac7]

Should this be changed to

         if (x2>=1 && x2<=8 && y2>=1 && y2<=8 && !grid[**x2**][**y2**]) s++; 

I realized the mistake. Yes, it should be changed.