Problem with optimizations

[Olivier Scalbert <olivier.scalbert@algosyn.com>]

Hello,

I have write a little program that try to solve Rubik's cube, just to 
practice a little Ada.
The program is really stupid (brute force) but I have a strange problem.
When I compile it with:
gnatmake -O2 rubukmain, it works:

Depth:  1  Positions Counter:                    12
Depth:  2  Positions Counter:                   132
Depth:  3  Positions Counter:                  1440
Depth:  4  Positions Counter:                 15720
Depth:  5  Positions Counter:                171600
Depth:  6  Positions Counter:               1873200
Depth:  7  Positions Counter:              20448000
Depth:  8
Solved !
           1         12          8         10          2          6 
      3          3  Positions Counter:              18104705

When I compile it with:
gnatmake -O3 rubukmain, it does not work:

Depth:  1  Positions Counter:                     1
Then it stops.

When, inside the Recursive_Find_Solution, I replace Is_Solved by 
Is_Solved1, then it works in all cases.

I have try to understand what is happen with gdb and by having a look 
into the generated code, but without success.

I have the same behaviour with:
- Ubuntu 8.10 32 bits (GNATMAKE 4.3.2)
- Debian testing AMD 64bits (GNATMAKE 4.3.3)

The code can be found there:
http://scalbert.dyndns.org/adarubik/

This small project is a really a toy but I would like to understand the 
problem.

Thanks,

Olivier