Ali Baba and the Forty Thieves

For fans of all other kinds of logic puzzles

Re: Ali Baba and the Forty Thieves

Postby rjamil » Sun May 31, 2020 7:13 pm

Hi creint,

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

R. Jamil
rjamil
 
Posts: 594
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Ali Baba and the Forty Thieves

Postby creint » Sun May 31, 2020 9:08 pm

73 is given so not interchangeable.
creint
 
Posts: 201
Joined: 20 January 2018

Re: Ali Baba and the Forty Thieves

Postby rjamil » Mon Jun 01, 2020 12:01 am

My mistake. I forget about givens vs solved difference.

R. Jamil
rjamil
 
Posts: 594
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Ali Baba and the Forty Thieves

Postby m_b_metcalf » Mon Jun 01, 2020 9:17 am

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.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 11134
Joined: 15 May 2006
Location: Berlin

Re: Ali Baba and the Forty Thieves

Postby StrmCkr » Tue Jun 02, 2020 12:01 pm

my solution to the first one
ali1.PNG
ali1.PNG (10.54 KiB) Viewed 60 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
ali2.PNG (10.73 KiB) Viewed 60 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}
type

cell = 0..120;
numberset = set of cell;
grids = array of integer;
track = array of integer;
jump = array of array of integer;
limit = array of numberset;
var
G : 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;
Var
n,b:integer;
begin
if 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;
var
xn,n:integer;
dig:string;
dig3,dig2: integer;
begin
N:=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;
var
myfile:text;
ior:integer;
filename:string;
verifygrid:integer;
Begin

initiate;


      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;
var
xn,r,c,g,xn2,b:integer;
begin
if 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;

type
hold = array of integer;
base = array of integer;
digit = array of integer;
act2 = array of numberset;

var
xn,w,p,p2,n,n2,b:integer;

a2:act2;
h:hold;

step: base;
z:digit;

begin

limiter;
 
 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;
Var
xn,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;

begin
clrscr;

initiate;

jumpset;
limiter;

repeat

gotoxy(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.



updates: vastly improved
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
Capture3.PNG (10.35 KiB) Viewed 67 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.
User avatar
StrmCkr
 
Posts: 1163
Joined: 05 September 2006

Re: Ali Baba and the Forty Thieves

Postby tarek » Tue Jun 02, 2020 7:07 pm

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?
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves

Postby StrmCkr » Tue Jun 02, 2020 7:20 pm

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.
User avatar
StrmCkr
 
Posts: 1163
Joined: 05 September 2006

Re: Ali Baba and the Forty Thieves

Postby tarek » Wed Jun 03, 2020 12:25 am

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
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves

Postby StrmCkr » Wed Jun 03, 2020 6:40 am

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.
User avatar
StrmCkr
 
Posts: 1163
Joined: 05 September 2006

Ali Baba and the Forty Thieves V2 Solution

Postby tarek » Wed Jun 03, 2020 1:26 pm

Ali Baba and the Forty Thieves V2 Solution: Show
Image
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Ali Baba and the Forty Thieves V3

Postby tarek » Wed Jun 03, 2020 1:31 pm

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 :D

Image

Code: Select all
... ... ... ... ... ... ... ... ... ... ...
... ... ... 030 006 ... 005 053 ... ... ...
... ... ... ... ... ... ... ... ... ... ...
... ... 022 ... ... 054 ... ... 008 ... ...
067 ... ... 062 ... ... ... 064 ... ... 015
081 ... ... ... ... ... ... ... ... ... 001
039 ... ... 034 ... ... ... 036 ... ... 013
... ... 071 ... ... 078 ... ... 002 ... ...
... ... ... ... ... ... ... ... ... ... ...
... ... ... 058 070 ... 047 075 ... ... ...
... ... ... ... ... ... ... ... ... ... ...
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves V3

Postby m_b_metcalf » Wed Jun 03, 2020 5:11 pm

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!
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 11134
Joined: 15 May 2006
Location: Berlin

Re: Ali Baba and the Forty Thieves V3

Postby tarek » Wed Jun 03, 2020 6:24 pm

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   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
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves

Postby StrmCkr » Thu Jun 04, 2020 5:35 am

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.
User avatar
StrmCkr
 
Posts: 1163
Joined: 05 September 2006

Re: Ali Baba and the Forty Thieves

Postby m_b_metcalf » Thu Jun 04, 2020 7:56 am

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.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 11134
Joined: 15 May 2006
Location: Berlin

PreviousNext

Return to Other logic puzzles