15 posts
• Page **2** of **2** • 1, **2**

#NextSpot does calculate the next safe column to put the queen at. As of right now, I'm still supplying that calculated position as a binary pattern for #queenPut. I'm still scratching my head on the recursion part.

- bobgillies
**Posts:**60**Joined:**24 Jan 2017 06:26

bobgillies wrote:

- Code: Select all
`// global variables`

tvar: board

tvar: laneMask

tvar: currentLane

tvar: queenCount

tvar: queenRank

//*************************************************************************************************

Object Class new: Queens

( numQueens, mutable lane )

Queens method: initialize( numQueens -- )

numQueens := numQueens

//* lanes for downleft diagonal, downright diagonal, and vertical threats. *//

ArrayBuffer newWith( 3 , 0 ) := lane

numQueens 2* to laneMask

numQueens to queenCount

0 to queenRank

1 to currentLane

;

Queens method: at \ i -- x //* I don't know why this works! *//

@lane at

;

Queens method: put \ i x -- //* this too! *//

@lane put

;

// queenPut method - mark the position in the vertical lane bit where

// the queen is placed for that row. Usage: 0b0010 Queens queenPut

Queens method: queenPut ( n -- )

// n = bitpattern. 0b0010 queen in the 3rd column of a 4x4 board.

1 @lane at n bitOr 1 swap @lane put

2 @lane at n bitOr 2 swap @lane put

3 @lane at n bitOr 3 swap @lane put

queenRank 1+ to queenRank

1 @lane at 2* laneMask 2* 1- bitAnd 1 swap @lane put

2 @lane at 2/ 2 swap @lane put

;

Queens method: nextSpot \

queenCount queenRank == if "\nAll the queens solved" . return then

1 @lane at 2 @lane at 3 @lane at bitOr bitOr laneMask

while ( dup ) //* while the bitmask has not shifted down to zero. *//

[ 2dup bitAnd

ifZero: [ 2/ //*IF it's safe, place Queen in this spot. *//

"\nQueen is to be put next at col" . currentLane . break

]

else: [ 2/ ] //* ELSE the lanes of attack are detected. *//

//* THEN increment the current spot. *//

currentLane 1+ to currentLane

]

2drop 1 to currentLane

;

//********************************************test*******************************************

// This code pattern works for a solved 4x4 board.

// next version needs needs for nextSpot to supply the

// next safe spot as a parameter for queenPut or terminate.

: firstTry

4 Queens new to board

0b1000 board queenPut

board nextSpot

0b0010 board queenPut

board nextSpot

;

: secondTry

4 Queens new to board

0b0100 board queenPut

board nextSpot

0b0001 board queenPut

board nextSpot

0b1000 board queenPut

board nextSpot

0b0010 board queenPut

board nextSpot

;

firstTry

secondTry

P.S. Method's put and at were never called by a function in my program. Please disregard/delete them.

- bobgillies
**Posts:**60**Joined:**24 Jan 2017 06:26

bobgillies wrote:Hi Franck, here's a neat side effect I wasn't expecting. It would seem that the THEN clause gets pushed onto the return stack each time SELF is called.

: barfly (self )

self 8 > ifTrue: [ "\n\nI've had me a beer ev'time ah been here!" .

"\n\nAnd ahwul have me another! " . return ]

else: [ "chug " . self 1+ barfly ]

"\nAnd another!" .

;

true barfly

Hi,

Sorry, I don't understand the side effect you are talking about.

For me, this works like a recursion should work.

What do you except for this recursion to do ?

return does not stop the computation : it comes back to the caller of the function.

Be carefull also, "self" is not called, self just push the parameter "self" on the stack.

Btw, you should not call your parameters "self" because a function does not have receiver. For readability, I suggest you to use another name (n for instance).

Also, here, the way "return" is used, the "else" clause is not necessary. The #barfly you wrote is the same as this one :

- Code: Select all
`: barfly ( n )`

n 8 > ifTrue: [

"\n\nI've had me a beer ev'time ah been here!" .

"\n\nAnd ahwul have me another! " .

return

]

"chug " .

n 1+ barfly

"\nAnd another!" .

;

Is it what you wanted ?

Franck

- Franck
**Posts:**140**Joined:**29 Oct 2014 19:01

After some study on what I thought was a neat side effect I should make a confession. Only after reading up on recursion did I realized that I have an almost total lack of understanding regarding recursion.

I think my code an example of what's called Tail Recursion. Am I right?

Anyway they say that recursive algorithms can be easier to conceptualize. I'm still more comfortable with iteration, and although the text I have on the 8 Queens Problem mentions it can be solved using iteration, the 8 Queens algorithm was provided in pseudo-code using recursion. So recursion it'll be.

In my intent on trying to understand recursion for the 8 Queens Problem, I did so in a silly sort of way in what would constitute a "true barfly" for laughs only.

As always, I learn more every time I log in here.

Cordially,

Bob

I think my code an example of what's called Tail Recursion. Am I right?

Anyway they say that recursive algorithms can be easier to conceptualize. I'm still more comfortable with iteration, and although the text I have on the 8 Queens Problem mentions it can be solved using iteration, the 8 Queens algorithm was provided in pseudo-code using recursion. So recursion it'll be.

In my intent on trying to understand recursion for the 8 Queens Problem, I did so in a silly sort of way in what would constitute a "true barfly" for laughs only.

As always, I learn more every time I log in here.

Cordially,

Bob

- bobgillies
**Posts:**60**Joined:**24 Jan 2017 06:26

There is a recursion each time a word call itself into its defintion.

Some algorithms are smaller / cleaner with a recursion.

But the counterpart is that you need more space for the return stack as it will grow for each call (with at least the return address but also the word locals) until the condition that stops the recursion is reached.

For instance, to calculate the factorial of a number ( 1 * 2 * 3 ... * n ), you can write (without recursion) :

Or you can use a recursion, as you can write :

fact(0) = 1

fact(n) = fact(n-1) * n ( ie 1*2*3*... *n = n * 1*2*3*...*n-1 = n * fact(n-1) )

So :

When you call fact(5)

1) n = 5 so it pushes 5 on the stack, substrat 1 and call fact again.

2) n = 4 so it pushes 4 on the stack, substrat 1 and call fact again.

3) n = 3 so it pushes 3 on the stack, substrat 1 and call fact again.

4) n = 2 so it pushes 2 on the stack, substrat 1 and call fact again.

5) n = 1 so it pushes 1 on the stack, substrat 1 and call fact again.

6) n = 0 so it just pushes 1 on the stack and returns.

7) fact(1) pushes 1 (from RS) on the stack and call * ==> 1

8) fact(2) pushes 2 (from RS) on the stack and call * ==> 2

9) fact(3) pushes 3 (from RS) on the stack and call * ==> 6

10) fact(4) pushes 4 (from RS) on the stack and call * ==> 24

11) fact(5) pushes 5 (from RS) on the stack and call * ==> 120.

So you end with 120 on the stack ( ie fact(5) )

Franck

Some algorithms are smaller / cleaner with a recursion.

But the counterpart is that you need more space for the return stack as it will grow for each call (with at least the return address but also the word locals) until the condition that stops the recursion is reached.

For instance, to calculate the factorial of a number ( 1 * 2 * 3 ... * n ), you can write (without recursion) :

- Code: Select all
`: fact \ n -- n!`

| i |

1 swap loop: i [ i * ]

;

Or you can use a recursion, as you can write :

fact(0) = 1

fact(n) = fact(n-1) * n ( ie 1*2*3*... *n = n * 1*2*3*...*n-1 = n * fact(n-1) )

So :

- Code: Select all
`: fact ( n )`

n ifZero: [ 1 ] else: [ n 1- fact n * ]

;

When you call fact(5)

1) n = 5 so it pushes 5 on the stack, substrat 1 and call fact again.

2) n = 4 so it pushes 4 on the stack, substrat 1 and call fact again.

3) n = 3 so it pushes 3 on the stack, substrat 1 and call fact again.

4) n = 2 so it pushes 2 on the stack, substrat 1 and call fact again.

5) n = 1 so it pushes 1 on the stack, substrat 1 and call fact again.

6) n = 0 so it just pushes 1 on the stack and returns.

7) fact(1) pushes 1 (from RS) on the stack and call * ==> 1

8) fact(2) pushes 2 (from RS) on the stack and call * ==> 2

9) fact(3) pushes 3 (from RS) on the stack and call * ==> 6

10) fact(4) pushes 4 (from RS) on the stack and call * ==> 24

11) fact(5) pushes 5 (from RS) on the stack and call * ==> 120.

So you end with 120 on the stack ( ie fact(5) )

Franck

- Franck
**Posts:**140**Joined:**29 Oct 2014 19:01

15 posts
• Page **2** of **2** • 1, **2**

Users browsing this forum: No registered users and 1 guest