Day 5 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:
https://www.geeksforgeeks.org/problems/the-knights-tour-problem/1

The Knight's tour problem

Difficulty: Medium Accuracy: 69.08%

You are given a n × n chessboard with a Knight starting at the top-left corner (0, 0). Your task is to determine a valid Knight's Tour, where the Knight visits every square exactly once, following the standard movement rules of a chess Knight.
You have to return the order in which each cell is visited. If a solution exists, print the sequence of numbers representing the order of visited squares. If no solution is possible, return -1.
Note: You can return any valid ordering, if it is correct the driver code will print true else it will print false.
Examples:
Input: n = 5
Output: true
Explanation: A possible Knight's Tour in a 5x5 chessboard is given below where Each number represents the step at which the Knight visits that cell, starting from (0, 0) as step 0.
[[0, 11, 2, 17, 20],
[3, 16, 19, 12, 7],
[10, 1, 6, 21, 18],
[15, 4, 23, 8, 13],
[24, 9, 14, 5, 22]]
Input: n = 4
Output: true
Explanation: For n = 4, it is not possible for a valid Knight's Tour so you have to return -1.
Constraints:
1 ≤ n ≤ 6

Solution:
class Solution:
def knightTour(self, n):
MOVES = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]
end_step = n * n - 1
board = [[-1] * n for _ in range(n)]

    def dfs(x=0, y=0, step=0):
        board[x][y] = step
        if step == end_step:
            return True
        next_step = step + 1
        for dx, dy in MOVES:
            x1, y1 = x + dx, y + dy
            if 0 <= x1 < n and 0 <= y1 < n and board[x1][y1] == -1:
                if dfs(x1, y1, next_step):
                    return True
        board[x][y] = -1
        return False

    if dfs():
        return board
    else:
        return [[-1]]