The New Sudoku Players' Forum

[rjamil]

Hi creint,

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

R. Jamil

[creint]

73 is given so not interchangeable.

[rjamil]

My mistake. I forget about givens vs solved difference.

R. Jamil

[m_b_metcalf]

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.

[StrmCkr]

my solution to the first one

ali1.PNG (10.54 KiB) Viewed 1167 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 1167 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 (10.35 KiB) Viewed 1174 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

[tarek]

All my own work.

Great and well done.

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?

[StrmCkr]

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.

[tarek]

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

[StrmCkr]

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}

[tarek]

Ali Baba and the Forty Thieves V2 Solution: Show

[tarek]

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 ... ... 015
081 ... ... ... ... ... ... ... ... ... 001
039 ... ... 034 ... ... ... 036 ... ... 013
... ... 071 ... ... 078 ... ... 002 ... ...
... ... ... ... ... ... ... ... ... ... ...
... ... ... 058 070 ... 047 075 ... ... ...
... ... ... ... ... ... ... ... ... ... ...

[m_b_metcalf]

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!

[tarek]

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

[StrmCkr]

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

[m_b_metcalf]

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.