## Ali Baba and the Forty Thieves

For fans of all other kinds of logic puzzles

### Re: Ali Baba and the Forty Thieves

Hi creint,

If your answer is correct, I see 73 and 74 interchangeable. Maybe, there are more.

R. Jamil
rjamil

Posts: 605
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: Ali Baba and the Forty Thieves

73 is given so not interchangeable.
creint

Posts: 231
Joined: 20 January 2018

### Re: Ali Baba and the Forty Thieves

My mistake. I forget about givens vs solved difference.

R. Jamil
rjamil

Posts: 605
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: Ali Baba and the Forty Thieves

I realised that my approach of using recursion between successive numbered tiles doesn't crack the problem. So I changed the procedure jump to act over all unsolved tiles, changing the code to :
Hidden Text: Show
Code: Select all
`recursive subroutine jump(row, col)       integer :: row, col, row_save, col_save    integer :: dirn         depth = depth + 1    row_save = row; col_save = col    do dirn = 1, 8  ! eight possible jump directions        row = row_save; col = col_save        select case(dirn)            case(1)                row = clip(row + 2); if(blocked(row, col)) cycle            case(2)                row = clip(row - 2); if(blocked(row, col)) cycle            case(3)                col = clip(col + 2); if(blocked(row, col)) cycle            case(4)                col = clip(col - 2); if(blocked(row, col)) cycle            case(5)                row = clip(row + 2)                col = clip(col + 2); if(blocked(row, col)) cycle            case(6)                row = clip(row + 2)                col = clip(col - 2); if(blocked(row, col)) cycle            case(7)                row = clip(row - 2)                col = clip(col + 2); if(blocked(row, col)) cycle            case(8)                row = clip(row - 2)                col = clip(col - 2); if(blocked(row, col)) cycle        end select                  tiles(row, col) =  depth          if(depth == path(3, step + 1)) then            if(row == path(1, step + 1) .and. col == path(2, step + 1)) then                if(step == top) then                   success = .true.                     exit                else                    step = step + 1                end if            else                                 tiles(row, col) = 0                cycle            end if            end if            call jump(row, col)                                           <<< The recursion here        if(success) return         tiles(row, col) = 0                                       if(depth == path(3, step)) step = step - 1      end do    depth = depth - 1        row = row_save; col = col_save    end subroutine jump`

which happily gave the result:
Code: Select all
` step  16 T 43  8 44  9 46 11 54 12 53 42  7  *  * 72  *  * 20 69 21 66 77 63 41 27 45  *  * 31  *  * 55  *  *  *  * 71 19 70 18  *  * 68 78 67 40 26  * 28  * 30 58 32 56  *  * 81  3  *  1  * 16  * 17  * 79  4 39 25  * 29  * 34 57 33 59  *  *  *  * 48  2 49 15  *  * 51 80  5 38 24 75  *  * 35  *  * 60  *  *  *  * 47  *  * 10 50 14  6 13 52 76 62 73 23 74 22 65 36 64 37 61 Solved in  0.5781250 s.`

All my own work.

Regards,

Mike

P.S. Afterthought: The first puzzle solves in a tiny fraction of a second so is much easier than the second. Don't know why.

m_b_metcalf
2017 Supporter

Posts: 11484
Joined: 15 May 2006
Location: Berlin

### Re: Ali Baba and the Forty Thieves

my solution to the first one
ali1.PNG (10.54 KiB) Viewed 115 times

Code: Select all
`30 . . . 24 . . . . . . x x . x x . . 40 8 . . 31 . . x x . x x . x x x x . . . . x x . . . . . x . x 58 18 . . x x 81 . x 44 x . x . x . 1 . . x . x . . . 17 x x x x . . . . x x . . . . . 37 x x . x x . x x x x . x x 70 . . . 79 4 . . . . . . . 62 . . 52`

my solution to the 2nd one
ali2.PNG (10.73 KiB) Viewed 115 times

Code: Select all
`. . 44 . . . . 12 . . . x x . x x . . . . . . 41 . . x x . x x . x x x x . . . . x x . . 67 . . x 28 x . 58 . . x x 81 . x 1 x 16 x . x . . . . x . x . 57 33 . x x x x . . 49 . x x . . . . . . x x . x x . x x x x . x x 10 . . 6 . . . 62 73 . . 22 . . . . .`

x represents the Jars and displayed numbers is the step sequence for the square to be landed on.

not a crazy fast code but works quick enough.
escape: Show
Code: Select all
`{all my own code in free pascal some borrowed from my sudoku solver} //written in Freepascal Turbopascal program Escape;uses crt,windows,SysUtils, StrUtils;//,Dialogs;{\$IFDEF UNIX}{\$IFDEF UseCThreads}  cthreads,  {\$ENDIF}{\$ENDIF}typecell = 0..120;numberset = set of cell;grids = array of integer;track = array of integer;jump = array of array of integer;limit = array of numberset;varG : grids;T:track;n,x:integer;ch:char;J:jump;lim:limit;used:numberset;Variation:boolean;Grid          : String ; {imported grid string}procedure writexy(x,y:integer; s:string);begin  gotoxy(x,y);  write(s);end;procedure initiate;Varn,b:integer;beginif variation = true then B:=1 else b:=0; setlength(g,0);setlength(t,0);setlength(g,(11*11));setlength(t,81+b);used:=[];for N:= 0 to (80+b) do T[n]:=-1;for n:= 0 to 120 do begin G[n]:=-1; end; end;procedure Arrange;varxn,n:integer;dig:string;dig3,dig2: integer;beginN:=0;  for xn:= 1 to 121 do   begin          if (extractword(xn, grid,[' ']) = 'X') or (extractword(xn, grid,[' ']) = 'x')            then               G[xn-1]:=1          else                if    (extractword(xn, grid,[' ']) <> '.')                       then                                   T[strtoINt(extractword(xn,grid,[' ']))-1]:=xn-1;             end; if variation = true then    t[81]:=t[0];   end;procedure import;varmyfile:text;ior:integer;filename:string;verifygrid:integer;Begininitiate;      repeat      writexy(2,28,'                                       ');      writexy(2,28, 'file path ');       readln(filename);           if (filename = ('')) or (filename = ('exit'))            then exit           else        writexy(2,29,'                                       ');        writexy(2,28,'                                       ');        assign(myfile,filename);        ior:= 0;        {\$I-}        reset(myfile);        {\$I+}        IOR:=ioresult;      if Ior <> 0      then      writexy(2,29,'file not found')      else       begin        textcolor(yellow );        writexy(2,14,'Import');        delay(300);        writexy(2,14,'       ');        textcolor(lightgray);       end;      until IoR = 0;      read(myfile,grid);      close(myfile);end;procedure limiter;varxn,r,c,g,xn2,b:integer;beginif variation = true then b:=1 else b:=0;  setlength(lim,0);setlength(lim,82+b);used:=[];for xn:=80+B downto 0 do begin   if (T[xn] <> -1)    then     begin                 include(used,t[xn]);         lim[xn]:=[T[xn]]; if xn > 0 then   begin      if t[xn] <> -1 then      for n in [0..7] do        include(lim[xn-1],j[T[xn],n]);       for xn2:= xn-1 downto 1 do        if T[xn2] <> -1 then break         else          if lim[xn2] <> [] then           begin          for g in lim[xn2] do           for n in [0..7] do             include(lim[xn2-1],j[g,n]);            end;   end;         end;  end;end;procedure runpath;typehold = array of integer;base = array of integer;digit = array of integer;act2 = array of numberset;varxn,w,p,p2,n,n2,b:integer;a2:act2;h:hold;step: base;z:digit;beginlimiter;  for xn:= 120 downto 0 do   {startin cell} if t[0] = xn  then begin  w:=0;    {step count}  setlength(h,(w+1));  {set the array size to w}  h[w]:=7;        {keeps track of what jump is being used for step W }  setlength(step,(w+1));   {set the array size to w}  step[w]:=xn;  { keeps track of what cells are used at each step W }   setlength(a2,w+1);   a2[w]:=[xn];   repeat    for p:= h[w] downto 0 do    {iteration of jumps}      if  not (j[step[w],p] in a2[w])     and (G[J[step[w],p]] = -1)      and ((T[w+1] = -1) or (T[w+1] = J[step[w],p]))       and  ((J[step[w],p] in (lim[w+1])) or (lim[w+1] = []))      and  (not( j[step[w],p] in used ) or (T[w+1] = J[step[w],p]))       then         begin          h[w]:=h[w]-1;    { advance the peer count for step w}          inc(w);        {increase the step count}         setlength(h,(w+1));          setlength(step,(w+1));     {increse the array size  to w}          step[w]:=j[step[w-1],p];   {set the step cell active for the newly created step w}          h[w]:=7;  {set the jump count for the new step w as 7}        setlength(a2,w+1);          a2[w]:=a2[w-1] + [j[step[w-1],p]];          break;        end       else         h[w]:=h[w]-1;  {if the above is false  advance the jump number}if (w =80) and (h[w] <> -1) then  for N in [0..120] do    begin    if g[n]= -1 then       begin           if n in a2[w]        then         begin                for x in [0..80] do            if step[x]=n              then              begin               if x <10 then write(' ');                  write(x,' ');                     end;           end          else write('__ ');    end    else    write(' x ');     if N in [10,21,32,43,54,65,76,87,98,109]       then writeln;     end;       if ((h[w] < 0 )  and (w > 0 ))  {the following resets the step to the previous state}     then      begin       w:=(w-1);       setlength(z,(w+1));       setlength(h,(w+1));       setlength(step,(w+1));       setlength(a2,w+1);      end;    until (w = 0) and (h[w] = -1) end;end;procedure Jumpset;Varxn,r,c,s,e,l,k:integer; begin setlength(j,0,0); setlength(J,121,8); for r:= 0 to 10 do  for C:= 0 to 10 do begin      xn:= R*11 + C;    if (R = 0) or (R = 1)         then s:= (R - 2) + 11          else S:=R-2;    if (R = 10) or (R = 9 )       then e:= (R+2) - 11         else E:=R+2;      J[xn,0]:= S*11+C; {up}      J[xn,4]:=E*11+C; {down}   if (C = 10) or (C = 9)          then L:=(C+2 - 11)        else L:= C+2;    if (C = 0) or (C = 1)          then K:=(C-2 + 11)        else K:= C-2;       J[xn,2]:=R*11 + L; {right}      J[xn,6]:=R*11 + k; {left}      J[xn,1]:=S*11+L;  { up diagonal right}      J[xn,3]:=E*11+L;  {down diagonal right}      J[xn,5]:=e*11+K;  {down diagonal left}      J[xn,7]:=s*11+K;  {up diagonal left} end; end;beginclrscr;initiate;jumpset;limiter;repeatgotoxy(1,1);  for N in [0..120] do    begin    if g[n]= -1 then       begin        if n in used        then         begin          for x in [0..80] do            if T[x]=n              then              begin               if x <10 then write(' ');                  write(x,' ');            end;           end       else write('__ ');    end    else    write(' X ');     if N in [10,21,32,43,54,65,76,87,98,109]       then writeln;     end;gotoxy(1,14); write(variation,' ');gotoxy(1,15);Write('Commands: "I": import, "S": solve:, "V": variation ');ch:=readkey;write(ch);gotoxy(1,17);  if( ch=#105 ) then begin import; arrange; limiter; end;  if ch=#115 then runpath;  if ch=#118 then if variation=true  then variation:=false else  variation:=true; until (ch=#27);end.`

update 2: added an import feature for puzzle 121 grid string "x" or "X" for Jars. "." for unmarked cells.
changed "j" to "x" for easier readability
also made it so the solution is slightly more readable by changing to step in the corresponding cells on a grid updated screen shots.
updated 3: removed useless array section, amalgamated others to do the work of it.
update4: fixed a transcription error that was preventing "0" start position from displaying on imported grids, and an error exit clause in run procedure.

{spoiler alert for 3rd puzzle view at own risk}
Hidden Text: Show
Capture3.PNG (10.35 KiB) Viewed 122 times

Code: Select all
`X X . X X . X X . X X X . . 30 6 X 5 53 . . X X . . . . . . . . . X . x 22 . . 54 . . 8 X . 67 X . 62 X X X 64 . X 15 81 . . . . . . . . . 1 39 X . 34 X X X 36 . X 13 . X 71 . . 78 . . 2 X . X . . . . . . . . . X x . . 58 70 X 47 75 . . X X X . X X . X X . X X`
Last edited by StrmCkr on Sun Jun 07, 2020 5:31 am, edited 12 times in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1205
Joined: 05 September 2006

### Re: Ali Baba and the Forty Thieves

m_b_metcalf wrote:All my own work.

Great and well done.

StrmCkr wrote:J represents the Jars and displayed numbers is the step sequence for the square to be landed on.

solution is read underneath the grid
left to right top down and it is zero based for square sequence

I must confess that I couldn't read your solution you provided! I thought for a second that the numbers underneath are the (holes) solution but there is a 112. are these RC coordinates?

tarek

Posts: 3748
Joined: 05 January 2006

### Re: Ali Baba and the Forty Thieves

Yes the cell cordinals.
(0..80) (start to end) listing cell (r, c)

Its a xy wing chain technically. My code cycles through all of them.

Logic solution for speed up. Probably would be going from end to start
And marking all the cells for the bridging steps to narrow down the construct.
Then its j cells connected by n jumps

(for example 55 could only be reached from 8 jumps.(subtract jar cells and previous used)
(using that we can restrict the possibilities for step 79 etc.
My code doesnt do that atm.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1205
Joined: 05 September 2006

### Re: Ali Baba and the Forty Thieves

Ah ... Now I see it. Well done

Well do to everyone for Attempting solving these puzzles. They should be human solvable but it is good that you found programming a nice challenge too.

tarek

tarek

Posts: 3748
Joined: 05 January 2006

### Re: Ali Baba and the Forty Thieves

Ah ... Now I see it. Well done
thanks

updated my code above added in reduction steps to line up the next link.
program wasn't skipping cells that where predefined landing sites for x step.

also added a code that highlights the (x - 1) step for all x step saving all the Jump slots of x {as those lead to x} from the x-1 step.
then ran a subset code that highlights all those peer cells by jumps for the subset cells. {x-2... > the next predefined step}

{the 2nd grid for example}
step 80 = 55
then step 79 = 8 jumps from spot 55
step 78 = 8 jumps of each of the 8 jumps in 79.
repeat until it hits {step 72} as 72 is a landing site

{note that u can remove the jar cells, and cells that must be designated landing spot if it isn't that spot}

now only if i could ever solve how to do a proper recursive program instead of the messy
Frozen array method i found with a for do loop that cant loop to the next number as the digit is stuck as part of an array call.

Ps. {number corresponds to your grid on page 1}
if i am correct 79 in the first puzzle is an extra clue. {i can remove it and still have 1 solution}
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1205
Joined: 05 September 2006

### Ali Baba and the Forty Thieves V2 Solution

Ali Baba and the Forty Thieves V2 Solution: Show

tarek

Posts: 3748
Joined: 05 January 2006

### Ali Baba and the Forty Thieves V3

Ali Baba and the Forty Thieves V3

This one has the clues symmetrical and is easier to solve to see if you can manage without computer assistance

Code: Select all
`... ... ... ... ... ... ... ... ... ... ...... ... ... 030 006 ... 005 053 ... ... ...... ... ... ... ... ... ... ... ... ... ...... ... 022 ... ... 054 ... ... 008 ... ...067 ... ... 062 ... ... ... 064 ... ... 015081 ... ... ... ... ... ... ... ... ... 001039 ... ... 034 ... ... ... 036 ... ... 013... ... 071 ... ... 078 ... ... 002 ... ...... ... ... ... ... ... ... ... ... ... ...... ... ... 058 070 ... 047 075 ... ... ...... ... ... ... ... ... ... ... ... ... ...`

tarek

Posts: 3748
Joined: 05 January 2006

### Re: Ali Baba and the Forty Thieves V3

tarek wrote:Ali Baba and the Forty Thieves V3

This one has the clues symmetrical and is easier to solve to see if you can manage without computer assistance

But the text file is missing the jars!

m_b_metcalf
2017 Supporter

Posts: 11484
Joined: 15 May 2006
Location: Berlin

### Re: Ali Baba and the Forty Thieves V3

m_b_metcalf wrote:
tarek wrote:Ali Baba and the Forty Thieves V3

This one has the clues symmetrical and is easier to solve to see if you can manage without computer assistance

But the text file is missing the jars!

Code: Select all
`X   X   .   X   X   .   X   X   .   X   XX   .   .   30  6   X   5   53  .   .   XX   .   .   .   .   .   .   .   .   .   X.   X   22  .   .   54  .   .   8   X   .67  X   .   62  X   X   X   64  .   X   1581  .   .   .   .   .   .   .   .   .   139  X   .   34  X   X   X   36  .   X   13.   X   71  .   .   78  .   .   2   X   .X   .   .   .   .   .   .   .   .   .   XX   .   .   58  70  X   47  75  .   .   XX   X   .   X   X   .   X   X   .   X   X`

tarek

Posts: 3748
Joined: 05 January 2006

### Re: Ali Baba and the Forty Thieves

Updated my code in previous post

Code: Select all
`X X . X X . X X . X X X . . 30 6 X 5 53 . . X X . . . . . . . . . X . x 22 . . 54 . . 8 X . 67 X . 62 X X X 64 . X 15 81 . . . . . . . . . 1 39 X . 34 X X X 36 . X 13 . X 71 . . 78 . . 2 X . X . . . . . . . . . X x . . 58 70 X 47 75 . . X X X . X X . X X . X X`
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1205
Joined: 05 September 2006

### Re: Ali Baba and the Forty Thieves

Very easy:
Hidden Text: Show
Code: Select all
` step  23 T  *  * 69  *  * 59  *  * 45  *  *  * 29 21 30  6  *  5 53 10 51  *  * 61 68 60 42 63 43 65 44 66  * 50  * 22 28  4 54  7 52  8  *  9 67  * 41 62  *  *  * 64 14  * 15 81 27 49 55 23 77  3 79 25 80  1 39  * 40 34  *  *  * 36 16  * 13 73  * 71 56 48 78 24 76  2  * 26  * 33 19 32 18 35 17 37 12 38  *  * 57 72 58 70  * 47 75 46 74  *  *  * 20  *  * 31  *  * 11  *  * Solved in  4.6E-02 s.`

m_b_metcalf
2017 Supporter

Posts: 11484
Joined: 15 May 2006
Location: Berlin

PreviousNext