THINK FIRST·CODE LATER

← All labs

N-Queens by backtracking

Problem

Place n queens on an n × n board so that no two attack each other (same row, column or diagonal).

Write NQueens. Place one queen per row with a recursive method place(row): try every column, keep it only if it is safe with respect to the rows above, recurse to the next row, and backtrack when no column works. Read n and print the number of solutions, how many queens were placed during the whole search (count one each time a queen is put on a safe square), and the first solution found (columns tried from left to right).

For the input

6

the program prints

Solutions for n = 6: 4
Queens placed during the search: 152
First solution:
.Q....
...Q..
.....Q
Q.....
..Q...
....Q.

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d1-3-data-1.txt

6
What your program must print for d1-3-data-1.txt
Solutions for n = 6: 4
Queens placed during the search: 152
First solution:
.Q....
...Q..
.....Q
Q.....
..Q...
....Q.

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d1-3-data-1.txt

Windows PowerShell does not understand <:

Get-Content d1-3-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.