6 Replies - 388 Views - Last Post: 13 July 2013 - 06:09 PM Rate Topic: -----

#1 trigger202  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • 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  Icon User is offline

  • D.I.C Regular

Reputation: 90
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

#3 ConciselyVerbose  Icon User is offline

  • D.I.C Regular

Reputation: 90
  • View blog
  • 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

Was This Post Helpful? 1
  • +
  • -

#4 trigger202  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#5 ConciselyVerbose  Icon User is offline

  • D.I.C Regular

Reputation: 90
  • View blog
  • 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

Was This Post Helpful? 1
  • +
  • -

#6 trigger202  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#7 ConciselyVerbose  Icon User is offline

  • D.I.C Regular

Reputation: 90
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1