Skip to main content
Code Review

Return to Question

added 499 characters in body
Source Link
Jamal
  • 35.2k
  • 13
  • 134
  • 238

I was learning backtracking algorithms earlier today, and was excited and wrote this code for nQueensn-Queens problem. Being Being my first try at backtracking algorithms, I would appreciate if you guys could chip in some suggestions/flaws in my code.

Placing queen at Row- 0 , col-0
Placing queen at Row- 1 , col-2
Placing queen at Row- 2 , col-4
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-7
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-6
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-6
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-4
Placing queen at Row- 2 , col-5
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-6
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Removing queen at Row- 5 , col-3
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-1
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-5
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-1
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-6
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-5
Removing queen at Row- 2 , col-7
Removing queen at Row- 1 , col-2
Placing queen at Row- 1 , col-3
Placing queen at Row- 2 , col-1
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-7
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-4
Placing queen at Row- 3 , col-6
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-6
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-1
Placing queen at Row- 2 , col-5
Placing queen at Row- 3 , col-2
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-4
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-4
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Placing queen at Row- 5 , col-6
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-5
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-5
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-1
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-4
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-2
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-4
Removing queen at Row- 2 , col-7
Removing queen at Row- 1 , col-3
Placing queen at Row- 1 , col-4
Placing queen at Row- 2 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-3
Removing queen at Row- 6 , col-3
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-5
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-3
Removing queen at Row- 6 , col-3
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Placing queen at Row- 5 , col-3
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-1
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-1
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-6
Placing queen at Row- 5 , col-2
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-2
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-1
Placing queen at Row- 7 , col-3
Problem Solved!!
{true,false,false,false,false,false,false,false,}
{false,false,false,false,true,false,false,false,}
{false,false,false,false,false,false,false,true,}
{false,false,false,false,false,true,false,false,}
{false,false,true,false,false,false,false,false,}
{false,false,false,false,false,false,true,false,}
{false,true,false,false,false,false,false,false,}
{false,false,false,true,false,false,false,false,}
Completed in :9 milli sec
Took 981 backtrack calls for completion!
Placing queen at Row- 0 , col-0
Placing queen at Row- 1 , col-2
Placing queen at Row- 2 , col-4
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-7
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-6
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-6
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-4
Placing queen at Row- 2 , col-5
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-6
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Removing queen at Row- 5 , col-3
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-1
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-5
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-1
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-6
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-5
Removing queen at Row- 2 , col-7
Removing queen at Row- 1 , col-2
Placing queen at Row- 1 , col-3
Placing queen at Row- 2 , col-1
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-7
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-4
Placing queen at Row- 3 , col-6
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-6
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-1
Placing queen at Row- 2 , col-5
Placing queen at Row- 3 , col-2
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-4
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-4
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Placing queen at Row- 5 , col-6
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-5
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-5
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-1
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-4
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-2
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-4
Removing queen at Row- 2 , col-7
Removing queen at Row- 1 , col-3
Placing queen at Row- 1 , col-4
Placing queen at Row- 2 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-3
Removing queen at Row- 6 , col-3
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-5
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-3
Removing queen at Row- 6 , col-3
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Placing queen at Row- 5 , col-3
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-1
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-1
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-6
Placing queen at Row- 5 , col-2
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-2
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-1
Placing queen at Row- 7 , col-3
Problem Solved!!
{true,false,false,false,false,false,false,false,}
{false,false,false,false,true,false,false,false,}
{false,false,false,false,false,false,false,true,}
{false,false,false,false,false,true,false,false,}
{false,false,true,false,false,false,false,false,}
{false,false,false,false,false,false,true,false,}
{false,true,false,false,false,false,false,false,}
{false,false,false,true,false,false,false,false,}
Completed in :9 milli sec
Took 981 backtrack calls for completion!

I was learning backtracking algorithms earlier today, and was excited and wrote this code for nQueens problem. Being my first try at backtracking algorithms, I would appreciate if you guys could chip in some suggestions/flaws in my code.

Placing queen at Row- 0 , col-0
Placing queen at Row- 1 , col-2
Placing queen at Row- 2 , col-4
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-7
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-6
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-6
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-4
Placing queen at Row- 2 , col-5
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-6
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Removing queen at Row- 5 , col-3
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-1
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-5
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-1
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-6
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-5
Removing queen at Row- 2 , col-7
Removing queen at Row- 1 , col-2
Placing queen at Row- 1 , col-3
Placing queen at Row- 2 , col-1
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-7
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-4
Placing queen at Row- 3 , col-6
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-6
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-1
Placing queen at Row- 2 , col-5
Placing queen at Row- 3 , col-2
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-4
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-4
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Placing queen at Row- 5 , col-6
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-5
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-5
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-1
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-4
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-2
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-4
Removing queen at Row- 2 , col-7
Removing queen at Row- 1 , col-3
Placing queen at Row- 1 , col-4
Placing queen at Row- 2 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-3
Removing queen at Row- 6 , col-3
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-5
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-3
Removing queen at Row- 6 , col-3
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Placing queen at Row- 5 , col-3
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-1
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-1
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-6
Placing queen at Row- 5 , col-2
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-2
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-1
Placing queen at Row- 7 , col-3
Problem Solved!!
{true,false,false,false,false,false,false,false,}
{false,false,false,false,true,false,false,false,}
{false,false,false,false,false,false,false,true,}
{false,false,false,false,false,true,false,false,}
{false,false,true,false,false,false,false,false,}
{false,false,false,false,false,false,true,false,}
{false,true,false,false,false,false,false,false,}
{false,false,false,true,false,false,false,false,}
Completed in :9 milli sec
Took 981 backtrack calls for completion!

I was learning backtracking algorithms earlier today, and was excited and wrote this code for n-Queens problem. Being my first try at backtracking algorithms, I would appreciate if you guys could chip in some suggestions/flaws in my code.

Placing queen at Row- 0 , col-0
Placing queen at Row- 1 , col-2
Placing queen at Row- 2 , col-4
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-7
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-6
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-6
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-4
Placing queen at Row- 2 , col-5
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-6
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-3
Removing queen at Row- 5 , col-3
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-1
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-5
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-1
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-6
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-3
Removing queen at Row- 3 , col-5
Removing queen at Row- 2 , col-7
Removing queen at Row- 1 , col-2
Placing queen at Row- 1 , col-3
Placing queen at Row- 2 , col-1
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-7
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-4
Placing queen at Row- 3 , col-6
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-6
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-1
Placing queen at Row- 2 , col-5
Placing queen at Row- 3 , col-2
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-1
Placing queen at Row- 5 , col-4
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-4
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-4
Removing queen at Row- 5 , col-4
Placing queen at Row- 5 , col-6
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-5
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-5
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-1
Placing queen at Row- 6 , col-4
Removing queen at Row- 6 , col-4
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-7
Placing queen at Row- 5 , col-1
Removing queen at Row- 5 , col-1
Removing queen at Row- 4 , col-7
Removing queen at Row- 3 , col-4
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-2
Removing queen at Row- 3 , col-2
Placing queen at Row- 3 , col-4
Placing queen at Row- 4 , col-1
Removing queen at Row- 4 , col-1
Placing queen at Row- 4 , col-2
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-4
Removing queen at Row- 2 , col-7
Removing queen at Row- 1 , col-3
Placing queen at Row- 1 , col-4
Placing queen at Row- 2 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-3
Removing queen at Row- 6 , col-3
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Removing queen at Row- 3 , col-5
Placing queen at Row- 3 , col-7
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-3
Removing queen at Row- 6 , col-3
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-2
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Placing queen at Row- 5 , col-3
Removing queen at Row- 5 , col-3
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-7
Removing queen at Row- 2 , col-1
Placing queen at Row- 2 , col-6
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-5
Placing queen at Row- 5 , col-2
Removing queen at Row- 5 , col-2
Placing queen at Row- 5 , col-7
Removing queen at Row- 5 , col-7
Removing queen at Row- 4 , col-5
Removing queen at Row- 3 , col-1
Removing queen at Row- 2 , col-6
Placing queen at Row- 2 , col-7
Placing queen at Row- 3 , col-1
Placing queen at Row- 4 , col-3
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-2
Removing queen at Row- 6 , col-2
Removing queen at Row- 5 , col-6
Removing queen at Row- 4 , col-3
Placing queen at Row- 4 , col-6
Placing queen at Row- 5 , col-2
Placing queen at Row- 6 , col-5
Removing queen at Row- 6 , col-5
Removing queen at Row- 5 , col-2
Removing queen at Row- 4 , col-6
Removing queen at Row- 3 , col-1
Placing queen at Row- 3 , col-5
Placing queen at Row- 4 , col-2
Placing queen at Row- 5 , col-6
Placing queen at Row- 6 , col-1
Placing queen at Row- 7 , col-3
Problem Solved!!
{true,false,false,false,false,false,false,false,}
{false,false,false,false,true,false,false,false,}
{false,false,false,false,false,false,false,true,}
{false,false,false,false,false,true,false,false,}
{false,false,true,false,false,false,false,false,}
{false,false,false,false,false,false,true,false,}
{false,true,false,false,false,false,false,false,}
{false,false,false,true,false,false,false,false,}
Completed in :9 milli sec
Took 981 backtrack calls for completion!
deleted 1 character in body
Source Link
package com.komal.backtracking;
import java.util.concurrent.TimeUnit;
public class Nqueens {
 static boolean[][] chessBoard;
 static int size;
 static int boundary;
 public void initChessBoard() {
 chessBoard = new boolean[size][size];
 boundary = size - 1;
 }
 static int noOfBacktrackCalls;
 public static void main(String[] args) {
 size = 32;8;
 Nqueens nQueens = new Nqueens();
 nQueens.initChessBoard();
 long startTime = System.nanoTime();
 if (!nQueens.backTrackRoutine(0, 0)) {
 System.out.println("Cannot be solved!!");
 }
 for (boolean[] i : chessBoard) {
 System.out.print("\n{");
 for (boolean i1 : i) {
 System.out.print(i1 + ",");
 }
 System.out.print("}");
 }
 long timeTaken = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime);
 System.out.println("\nCompleted in :" + timeTaken + " milli sec");
 System.out.println("\nTook " + noOfBacktrackCalls + " backtrack calls for completion!");
 }
 public boolean backTrackRoutine(int row, int col) {
 noOfBacktrackCalls++;
 boolean flag = true;
 if (col == size || row == size) {
 return false;
 }
 if (canPlace(row, col)) {
 System.out.println("Placing queen at Row- " + row + " , col-" + col);
 chessBoard[row][col] = true;
 if (row == boundary) {
 System.out.println("Problem Solved!!");
 return true;
 } else if (!backTrackRoutine(row + 1, 0)) {
 System.out.println("Removing queen at Row- " + row + " , col-" + col);
 chessBoard[row][col] = false;
 flag = backTrackRoutine(row, col + 1);
 }
 return flag;
 } else {
 return backTrackRoutine(row, col + 1);
 }
 }
 public boolean canPlace(int row, int col) {
 return !rowAndColhasAQueen(row, col) && !diagonalHasAQueen(row, col);
 }
 public boolean rowAndColhasAQueen(int row, int col) {
 for (int i = 0; i < size; i++) {
 if (chessBoard[row][i]) {
 return true;
 }
 }
 for (int i = 0; i < size; i++) {
 if (chessBoard[i][col]) {
 return true;
 }
 }
 return false;
 }
 public boolean diagonalHasAQueen(int row, int col) {
 int flag = 0;
 while (row != 0) {
 flag++;
 row--;
 if (col + flag < size)
 if (chessBoard[row][col + flag]) {
 return true;
 }
 if (col - flag > -1)
 if (chessBoard[row][col - flag]) {
 return true;
 }
 }
 return false;
 }
}
package com.komal.backtracking;
import java.util.concurrent.TimeUnit;
public class Nqueens {
 static boolean[][] chessBoard;
 static int size;
 static int boundary;
 public void initChessBoard() {
 chessBoard = new boolean[size][size];
 boundary = size - 1;
 }
 static int noOfBacktrackCalls;
 public static void main(String[] args) {
 size = 32;
 Nqueens nQueens = new Nqueens();
 nQueens.initChessBoard();
 long startTime = System.nanoTime();
 if (!nQueens.backTrackRoutine(0, 0)) {
 System.out.println("Cannot be solved!!");
 }
 for (boolean[] i : chessBoard) {
 System.out.print("\n{");
 for (boolean i1 : i) {
 System.out.print(i1 + ",");
 }
 System.out.print("}");
 }
 long timeTaken = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime);
 System.out.println("\nCompleted in :" + timeTaken + " milli sec");
 System.out.println("\nTook " + noOfBacktrackCalls + " backtrack calls for completion!");
 }
 public boolean backTrackRoutine(int row, int col) {
 noOfBacktrackCalls++;
 boolean flag = true;
 if (col == size || row == size) {
 return false;
 }
 if (canPlace(row, col)) {
 System.out.println("Placing queen at Row- " + row + " , col-" + col);
 chessBoard[row][col] = true;
 if (row == boundary) {
 System.out.println("Problem Solved!!");
 return true;
 } else if (!backTrackRoutine(row + 1, 0)) {
 System.out.println("Removing queen at Row- " + row + " , col-" + col);
 chessBoard[row][col] = false;
 flag = backTrackRoutine(row, col + 1);
 }
 return flag;
 } else {
 return backTrackRoutine(row, col + 1);
 }
 }
 public boolean canPlace(int row, int col) {
 return !rowAndColhasAQueen(row, col) && !diagonalHasAQueen(row, col);
 }
 public boolean rowAndColhasAQueen(int row, int col) {
 for (int i = 0; i < size; i++) {
 if (chessBoard[row][i]) {
 return true;
 }
 }
 for (int i = 0; i < size; i++) {
 if (chessBoard[i][col]) {
 return true;
 }
 }
 return false;
 }
 public boolean diagonalHasAQueen(int row, int col) {
 int flag = 0;
 while (row != 0) {
 flag++;
 row--;
 if (col + flag < size)
 if (chessBoard[row][col + flag]) {
 return true;
 }
 if (col - flag > -1)
 if (chessBoard[row][col - flag]) {
 return true;
 }
 }
 return false;
 }
}
package com.komal.backtracking;
import java.util.concurrent.TimeUnit;
public class Nqueens {
 static boolean[][] chessBoard;
 static int size;
 static int boundary;
 public void initChessBoard() {
 chessBoard = new boolean[size][size];
 boundary = size - 1;
 }
 static int noOfBacktrackCalls;
 public static void main(String[] args) {
 size = 8;
 Nqueens nQueens = new Nqueens();
 nQueens.initChessBoard();
 long startTime = System.nanoTime();
 if (!nQueens.backTrackRoutine(0, 0)) {
 System.out.println("Cannot be solved!!");
 }
 for (boolean[] i : chessBoard) {
 System.out.print("\n{");
 for (boolean i1 : i) {
 System.out.print(i1 + ",");
 }
 System.out.print("}");
 }
 long timeTaken = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime);
 System.out.println("\nCompleted in :" + timeTaken + " milli sec");
 System.out.println("\nTook " + noOfBacktrackCalls + " backtrack calls for completion!");
 }
 public boolean backTrackRoutine(int row, int col) {
 noOfBacktrackCalls++;
 boolean flag = true;
 if (col == size || row == size) {
 return false;
 }
 if (canPlace(row, col)) {
 System.out.println("Placing queen at Row- " + row + " , col-" + col);
 chessBoard[row][col] = true;
 if (row == boundary) {
 System.out.println("Problem Solved!!");
 return true;
 } else if (!backTrackRoutine(row + 1, 0)) {
 System.out.println("Removing queen at Row- " + row + " , col-" + col);
 chessBoard[row][col] = false;
 flag = backTrackRoutine(row, col + 1);
 }
 return flag;
 } else {
 return backTrackRoutine(row, col + 1);
 }
 }
 public boolean canPlace(int row, int col) {
 return !rowAndColhasAQueen(row, col) && !diagonalHasAQueen(row, col);
 }
 public boolean rowAndColhasAQueen(int row, int col) {
 for (int i = 0; i < size; i++) {
 if (chessBoard[row][i]) {
 return true;
 }
 }
 for (int i = 0; i < size; i++) {
 if (chessBoard[i][col]) {
 return true;
 }
 }
 return false;
 }
 public boolean diagonalHasAQueen(int row, int col) {
 int flag = 0;
 while (row != 0) {
 flag++;
 row--;
 if (col + flag < size)
 if (chessBoard[row][col + flag]) {
 return true;
 }
 if (col - flag > -1)
 if (chessBoard[row][col - flag]) {
 return true;
 }
 }
 return false;
 }
}
deleted 33 characters in body; edited title
Source Link
200_success
  • 145.5k
  • 22
  • 190
  • 479

Is this n-Queens backtracking code efficient? (in terms of memory/performance/unnecessary checks)

I was learning backtracking algorithms earlier today, and was excited and wrote this code for nQueens problem. Being my first try at backtracking algorithms, I would appreciate if you guys could chip in some suggestions/flaws in my code. Also, I had a really tough time getting this to work - I struggled mainly in trying to debug so many recursive calls and often got lost in analyzing which ones were waiting for "return value" from the other deeper function calls. - any help on how to get started/thinking about recursion while writing code would be very helpful. Thanks.

Here'sAlso, I had a really tough time getting this to work - I struggled mainly in trying to debug so many recursive calls and often got lost in analyzing which ones were waiting for "return value" from the other deeper function calls. — any help on how to get started/thinking about recursion while writing code, would be very helpful.

Is this n-Queens backtracking code efficient? (in terms of memory/performance/unnecessary checks)

I was learning backtracking algorithms earlier today, and was excited and wrote this code for nQueens problem. Being my first try at backtracking algorithms, I would appreciate if you guys could chip in some suggestions/flaws in my code. Also, I had a really tough time getting this to work - I struggled mainly in trying to debug so many recursive calls and often got lost in analyzing which ones were waiting for "return value" from the other deeper function calls. - any help on how to get started/thinking about recursion while writing code would be very helpful. Thanks.

Here's the code,

n-Queens backtracking code

I was learning backtracking algorithms earlier today, and was excited and wrote this code for nQueens problem. Being my first try at backtracking algorithms, I would appreciate if you guys could chip in some suggestions/flaws in my code.

Also, I had a really tough time getting this to work - I struggled mainly in trying to debug so many recursive calls and often got lost in analyzing which ones were waiting for "return value" from the other deeper function calls. — any help on how to get started/thinking about recursion while writing code would be very helpful.

Source Link
Loading
lang-java

AltStyle によって変換されたページ (->オリジナル) /