Knight's Tour about cses-solutions HOT 5 CLOSED

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++; 

from cses-solutions.

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.

from cses-solutions.

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.

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).

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.

from cses-solutions.

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

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

from cses-solutions.

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.

from cses-solutions.