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!
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;
}
}
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.