Tag: Queens

The N Queens problem is a classic puzzle that asks how to place N chess queens on an NxN chessboard so that no two queens can attack each other. This means that no two queens can share the same row, column, or diagonal.

One way to solve this problem is to use a backtracking algorithm, which tries different positions for the queens until it finds a valid solution or exhausts all possibilities. In this blog post, we will see how to implement a backtracking algorithm for the N Queens problem using Kotlin, a modern and concise programming language that runs on the JVM.

Kotlin Basics

Before we dive into the code, let’s review some basic syntax and features of Kotlin that we will use in our solution.

• Functions: Kotlin functions are declared using the fun keyword, followed by the function name, parameters, and return type. For example:

fun sum(a: Int, b: Int): Int { return a + b }

• Parameters: Function parameters are defined using Pascal notation – name: type. Parameters are separated using commas, and each parameter must be explicitly typed. For example:

fun powerOf(number: Int, exponent: Int): Int { /*...*/ }

• Default arguments: Function parameters can have default values, which are used when you skip the corresponding argument. This reduces the number of overloads. For example:

fun read(b: ByteArray, off: Int = 0, len: Int = b.size) { /*...*/ }

• Named arguments: You can name one or more of a function’s arguments when calling it. This can be helpful when a function has many arguments and it’s difficult to associate a value with an argument, especially if it’s a boolean or null value. When you use named arguments in a function call, you can freely change the order that they are listed in. For example:

fun foo(bar: Int = 0, baz: Int = 1, qux: () -> Unit) { /*...*/ } foo(1) { println("hello") } // Uses the default value baz = 1 foo(qux = { println("hello") }) // Uses both default values bar = 0 and baz = 1 foo { println("hello") } // Uses both default values bar = 0 and baz = 1

• Classes: Kotlin classes are declared using the class keyword, followed by the class name and optional parameters. For example:

class Person(val firstName: String, val lastName: String, var age: Int)

• Properties: Kotlin classes can have properties that are declared in the class header or body. Properties can be either val (read-only) or var (mutable). For example:

class Rectangle(var height: Double, var length: Double) { var perimeter = (height + length) * 2 }

• Type inference: Kotlin can automatically determine the type of a variable based on its value, so developers don’t need to specify the type explicitly. For example:

var x = 5 // `Int` type is inferred x += 1 val y = "Hello" // `String` type is inferred y += " world!"

For more details on Kotlin syntax and features, you can check out the official documentation.

Backtracking Algorithm

Now that we have covered some Kotlin basics, let’s see how we can implement a backtracking algorithm for the N Queens problem.

The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack to the previous column and try a different row. We repeat this process until either all N queens have been placed or it is impossible to place any more queens.

To implement this algorithm in Kotlin, we will need:

• A function to check if a given position is safe for placing a queen.
• A function to print the solution as a matrix of ‘Q’ and ‘.’ characters.
• A recursive function to try placing queens in different columns and rows.

Let’s start with the first function:

// A function to check if a given position (row, col) is safe for placing a queen fun isSafe(board: Array<IntArray>, row: Int, col: Int, n: Int): Boolean { // Check the left side of the current row for (i in 0 until col) { if (board[row][i] == 1) { return false } } // Check the upper left diagonal var i = row - 1 var j = col - 1 while (i >= 0 && j >= 0) { if (board[i][j] == 1) { return false } i-- j-- } // Check the lower left diagonal i = row + 1 j = col - 1 while (i < n && j >= 0) { if (board[i][j] == 1) { return false } i++ j-- } // If none of the above conditions are violated, the position is safe return true }

This function takes four parameters:

• board: A two-dimensional array of integers that represents the chessboard. Each element can be either 0 (empty) or 1 (queen).
• row: The row index of the current position.
• col: The column index of the current position.
• n: The size of the chessboard and the number of queens.

The function returns a boolean value indicating whether the position is safe or not. To check this, we need to scan the left side of the current row, the upper left diagonal, and the lower left diagonal for any queens. If we find any queen in these directions, we return false. Otherwise, we return true.

Next, let’s write the function to print the solution:

// A function to print the solution as a matrix of 'Q' and '.' characters fun printSolution(board: Array<IntArray>, n: Int) { for (i in 0 until n) { for (j in 0 until n) { if (board[i][j] == 1) { print("Q ") } else { print(". ") } } println() } }

This function takes two parameters:

• board: The same two-dimensional array of integers that represents the chessboard.
• n: The size of the chessboard and the number of queens.

The function prints each element of the board as either ‘Q’ or ‘.’ depending on whether it is a queen or not. It also adds a space after each character and a line break after each row.

Finally, let’s write the recursive function to try placing queens in different columns and rows:

// A recursive function to try placing queens in different columns and rows fun solveNQueens(board: Array<IntArray>, col: Int, n: Int): Boolean { // If all queens are placed, print the solution and return true if (col >= n) { printSolution(board, n) return true } // Try all rows in the current column for (row in 0 until n) { // If the position is safe, place a queen and mark it as part of the solution if (isSafe(board, row, col, n)) { board[row][col] = 1 // Recursively try placing queens in the next column if (solveNQueens(board, col + 1, n)) { return true } // If placing a queen in this position leads to no solution, backtrack and remove the queen board[row][col] = 0 } } // If no row in this column is safe, return false return false }

This function takes three parameters:

• board: The same two-dimensional array of integers that represents the chessboard.
• col: The current column index where we are trying to place a queen.
• n: The size of the chessboard and the number of queens.

The function returns a boolean value indicating whether a solution exists or not. To find a solution, we follow these steps:

• If all queens are placed (i.e., col >= n), we print the solution and return true.
• Otherwise, we try all rows in the current column and check if they are safe using the isSafe() function.
• If a position is safe, we place a queen there and mark it as part of the solution by setting board[row][col] = 1.
• Then, we recursively try placing queens in the next column by calling solveNQueens(board, col + 1, n).
• If this leads to a solution, we return true.

• Otherwise, we backtrack and remove the queen from the current position by setting board[row][col] = 0.
• We repeat this process for all rows in the current column.
• If none of the rows in this column are safe, we return false.

Testing the Code

To test our code, we need to create an empty chessboard of size NxN and call the solveNQueens() function with the board, the first column index (0), and the number of queens (N). For example, to solve the 4 Queens problem, we can write:

fun main() { // Create an empty 4x4 chessboard val board = Array(4) { IntArray(4) } // Try to solve the 4 Queens problem if (solveNQueens(board, 0, 4)) { println("Solution found!") } else { println("No solution exists!") } }

If we run this code, we will get the following output:. Q . . . . . Q Q . . . . . Q . Solution found!

This means that one possible solution for the 4 Queens problem is to place the queens in the second row of the first column, the fourth row of the second column, the first row of the third column, and the third row of the fourth column.

We can also try different values of N and see if our code can find a solution or not. For example, if we change N to 3, we will get:No solution exists!

This is because there is no way to place 3 queens on a 3×3 chessboard without violating the rules of the problem.

Conclusion

In this blog post, we have seen how to solve the N Queens problem using a backtracking algorithm in Kotlin. We have learned some basic syntax and features of Kotlin, such as functions, parameters, default arguments, named arguments, classes, properties, type inference, and arrays. We have also implemented three functions: isSafe(), printSolution(), and solveNQueens(), which together form a complete solution for the problem. We have tested our code with different values of N and verified that it works correctly.

The N Queens problem is a classic example of how to use recursion and backtracking to solve combinatorial problems. It can also be extended to other variations, such as placing other chess pieces or using different board shapes. Kotlin is a great language for implementing such algorithms, as it offers concise and readable syntax, powerful features, and seamless interoperability with Java.

I hope you enjoyed this blog post and learned something new. If you have any questions or feedback, please feel free to leave a comment below. Thank you for reading!