# help with backtracking nQueens

Page 1 of 1

## 6 Replies - 1013 Views - Last Post: 13 July 2013 - 06:09 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=324776&amp;s=5a9c42fc883ae6bf1423176195b47dbc&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 trigger202

• New D.I.C Head

Reputation: -1
• Posts: 32
• Joined: 13-March 11

# help with backtracking nQueens

Posted 13 July 2013 - 02:16 PM

hi guys i think i have implemented the NQueens problem.
but i am still confused with the unwinding of the recursive backtracking so can someone explain to me what my code is doing

1. this is not an assignment or project but rather something i am doing during the holidays
and if you think its assignment or project please don't respond.

what i don't understand
my code prints out different solutions close to 90 times, i didn't check if all were different.
but i want it stop after it has found 1 solution to the problem if any.
so can anyone tell me why its printing so many times
since i have the base case if n==size:return board

if you require more explanation me know.
thought i mention that i understand the general concepts of recursion and backtracking to some degree

here is my code

i left out one functions/method call is_Safe(board,x,y) because it looks messy and bad implementation, anyway it returns true or false if the x,y is a safe place to place a queen in according to the board

```board=[[0]*8]*8

def solve(board,x,size):

if x==size:
print" found solution"
return board
else:
for i in range(8):#boar is 8*8
if is_Safe(board,x,i):
board[x][i]="Q"
solve(board,x+1,size)
board[x][i]=0

solve(board,0,8)#place 8 queens on board

```

Is This A Good Question/Topic? 0

## Replies To: help with backtracking nQueens

### #2 ConciselyVerbose

• D.I.C Regular

Reputation: 91
• Posts: 315
• Joined: 05-July 13

## Re: help with backtracking nQueens

Posted 13 July 2013 - 02:47 PM

It appears it will search for every possible solution. So if you look at this as your stack:

```solve(board,0,8)
solve(board,1,8)
solve(board,2,8)
...
solve(board,7,8)
solve(board, 8,8)
```

When the last call returns, the call before it will keep searching, and every other level below that.

What you need to do is not continue through your for loop once you have reached an acceptable answer.

### #3 ConciselyVerbose

• D.I.C Regular

Reputation: 91
• Posts: 315
• Joined: 05-July 13

## Re: help with backtracking nQueens

Posted 13 July 2013 - 02:47 PM

Edit: double post

This post has been edited by ConciselyVerbose: 13 July 2013 - 02:49 PM

### #4 trigger202

• New D.I.C Head

Reputation: -1
• Posts: 32
• Joined: 13-March 11

## Re: help with backtracking nQueens

Posted 13 July 2013 - 05:19 PM

well trying playing with it but still i could not stop it from search all solutions
this is what i tried so if any one could elaborate bit more
```board=[[0]*8]*8

def solve(board,x,size):

if x==size:
print" found solution"
return board
else:

for i in range(8):#boar is 8*8
if x==size:
return
if is_Safe(board,x,i):
board[x][i]="Q"
solve(board,x+1,size)
board[x][i]=0
solve(board,0,8)#place 8 queens on board

```

This post has been edited by trigger202: 13 July 2013 - 05:20 PM

### #5 ConciselyVerbose

• D.I.C Regular

Reputation: 91
• Posts: 315
• Joined: 05-July 13

## Re: help with backtracking nQueens

Posted 13 July 2013 - 05:30 PM

You have your the last level return a board, right? You don't have that do anything. What I would do, in place of your if statement, looks more like this.

```for i in range(8):#boar is 8*8
if is_Safe(board,x,i):
board[x][i]="Q"
returned = solve(board,x+1,size)
if returned:
return returned
```

If it goes through the whole if statement for loop (edit: oops) without an acceptable solution, the default return is None. When you check the "returned" variable will be interpreted as true if it is a value, and false if nothing was returned, therefore, it will only return to the calling function if you have found a solution.

This post has been edited by ConciselyVerbose: 13 July 2013 - 06:11 PM

### #6 trigger202

• New D.I.C Head

Reputation: -1
• Posts: 32
• Joined: 13-March 11

## Re: help with backtracking nQueens

Posted 13 July 2013 - 06:02 PM

bro thank you man, this really was pissing me off
but it worked, that was neat little trick you added i had know idea you could do that

### #7 ConciselyVerbose

• D.I.C Regular

Reputation: 91
• Posts: 315
• Joined: 05-July 13

## Re: help with backtracking nQueens

Posted 13 July 2013 - 06:09 PM

With another language you could return null and do basically the same thing, but python is real nice because you can do that so easily. Do you understand why that works? I might have glossed over it a bit but if you have a question I can elaborate a little.

Also, keep in mind this should give the same solution every time for the same number of queens.

This post has been edited by ConciselyVerbose: 13 July 2013 - 07:19 PM