The N-Queen Problem
Backtracking
As of lately I’ve been studying algorithms a lot and ran into the N-Queen problem in leetcode. The problem consists of placing N queens on an NxN board in such a way that none of the queens are in the way of the others. It was a fascinating problem to solve and I decided to share my approach with my fervent followers.
My approach to this problem was to use a technique called backtracking, since I have to start placing queens on the board one by one, checking that none are on the way of one another, and try different combinations until a solution is found or all combinations are tried. If you don't know what backtracking is I recommend reading my previous post about backtracking https://garycordero1690.medium.com/backtracking-f2ef1a5b3e90.
This solution abstract the board as a NxN matrix using javascript arrays. Before jumping into the code to implement our algorithm we have to be able to identify two things:
- Identify if the place on the board where we are currently placing the queen is a valid move, meaning that it is not in the way of the other queens that have been already placed.
- Identify when N number of queens are on the board in order to identify when a solution has been found.
Identifying if it is a valid move
To identify a valid move we have to understand how a queen moves on the board. The queen can move horizontally, vertically and diagonally across the board. Imagine we are placing a queen in our board on the 2nd Row and 2nd column we would have something like this.
It is easy to check vertically or horizontally since rows and columns have an specific number, but checking diagonally is different. Cells in the board have an intricate relationship when adding and substracting the values of their row and column indices, as shown below.
When we add the indices of the cells, you can see that cell in the same diagonal from top right to bottom left have the same value. Some thing similar happens when you substract them, cells in the same diagonal from top left to bottom right will have the same value. Using this we can create a function to validate our moves.
Identifying when a solution has been found
In this step we only have to make sure that we have N number of queens on the board. We can do this by iterating over the board and counting them.
In order to create the NxN board I created a helper function in charge of that.
Solving N-Queen Problem
The result after running nQueen(4).
