Ali Baba and the Forty Thieves

For fans of all other kinds of logic puzzles

Re: Ali Baba and the Forty Thieves

Postby champagne » Thu May 28, 2020 2:12 pm

rjamil wrote:
My wild guesses are as follows:
(30)r1c1 - (31)r3c1 - (32)r3c3 - (33)r5c1 - (34)r7c1 - (35)r9c1 - (36)r11c3 - (37)r9c3
(37)r9c3 - (38)r11c1 - (39)r2c10 - (40)r2c8

R. Jamil

(39)r2c10
may be r11c10
champagne
2017 Supporter
 
Posts: 7141
Joined: 02 August 2007
Location: France Brittany

Re: Ali Baba and the Forty Thieves

Postby champagne » Thu May 28, 2020 2:58 pm

seems ok

Hidden Text: Show
Code: Select all
30   72   29   71   24   69   23   77   22   78   73
 X    X   13    X    X   46   10   40    8   63   50
31   74   32    X    X   76    X    X   21    X    X
 X    X   12   45   11   41    X    X    9   64    7
33   55    X   75    X   58   18   59   20    X    X
81    6    X   44    X   42    X   66    X   65    1
34   54    X   56    X   57   19   60   17    X    X
 X    X   27   43   26   67    X    X    2   80    5
35   53   37    X    X   61    X    X   16    X    X
 X    X   28    X    X   70   25   68    3   79    4
38   49   36   48   14   47   15   62   51   39   52
champagne
2017 Supporter
 
Posts: 7141
Joined: 02 August 2007
Location: France Brittany

Re: Ali Baba and the Forty Thieves

Postby 1to9only » Thu May 28, 2020 3:06 pm

I modified a Knights Tour program downloaded from the internet to help Ali Baba escape the Forty Thieves!

The program starts from the starting grid (enchanted courtyard in OP) and lists all possible jumps for each route, e.g. (1)r6c11-(4)r10c11, (4)r10c11-(8)r2c9, (8)r2c9-(17)r7c9, etc.

alibaba.zip
contains alibaba.c and alibaba.exe for windows
(3.89 KiB) Downloaded 7 times

2 routes are solved in the first run:
(4)r10c11 - (5)r8c11 - (6)r6c2 - (7)r4c11 - (8)r2c9
(79)r10c10 - (80)r8c10 - (81)r6c1

These jumps can then be entered into the grid: (5)r8c11, (6)r6c2, (7)r4c11 and (80)r8c10

On the 2nd run of the program this route is solved:
(1)r6c11 - (2)r8c9 - (3)r10c9 - (4)r10c11

2 more jumps can be entered into the grid: (2)r8c9 and (3)r10c9

After this, I've not spent much time on this problem of saving Ali Baba!!
But, I've been able to deduce the following:
(22)r1c9 - (23)r1c7 - (24)r1c5 -(25)r10c7 - (26)r8c5
(37)r9c3 - (38)r11c1 - (39)r2c10 - (40)r2c8

rjamil wrote:My wild guesses are as follows:
(30)r1c1 - (31)r3c1 - (32)r3c3 - (33)r5c1 - (34)r7c1 - (35)r9c1 - (36)r11c3 - (37)r9c3
(37)r9c3 - (38)r11c1 - (39)r2c10 - (40)r2c8

The '(37)r9c3 - (38)r11c1 - (39)r2c10 - (40)r2c8' route is correct.
I still have 3 possibles for the route '(31)r3c1 to (37)r9c3':
(31)r3c1 - (32)r5c1 - (33)r7c1 - (34)r9c1 - (35)r11c3 - (36)r11c5 - (37)r9c3
(31)r3c1 - (32)r1c3 - (33)r3c3 - (34)r5c1 - (35)r7c1 - (36)r9c1 - (37)r9c3
(31)r3c1 - (32)r3c3 - (33)r5c1 - (34)r7c1 - (35)r9c1 - (36)r11c3 - (37)r9c3
.
1to9only
 
Posts: 1708
Joined: 04 April 2018

Re: Ali Baba and the Forty Thieves

Postby champagne » Thu May 28, 2020 4:08 pm

="1to9only"
The '(37)r9c3 - (38)r11c1 - (39)r2c10 - (40)r2c8' route is correct.
.

if my solution is correct and if the solution unique, it is (39)r11c10
champagne
2017 Supporter
 
Posts: 7141
Joined: 02 August 2007
Location: France Brittany

Ali Baba and the Forty Thieves (solution)

Postby tarek » Fri May 29, 2020 1:23 pm

Well done Champagne,

Your answer is the same as the Unique solution that I have

Ali Baba and the Forty Thieves Solution: Show
Image

Here is the toroidal view of the enchanted garden

Image


It is a variant of the Knight tour (as Hidato or Numbrix are) so techniques already in place to solve them should work with this one too. http://forum.enjoysudoku.com/hidato-t6404.html

Alibaba is actually a fairy chess piece that moves 2 squares in any direction, so this puzzle took advantage of the chess tour aspect and the Ali Baba story. http://forum.enjoysudoku.com/fairy-chess-piece-tour-puzzles-including-numbrix-hidato-t30443-60.html#p275608

I prepared 2 puzzles from which I decided to post the above but I can post the other as V2 puzzle tomorrow if anybody is interested to have another go.

tarek
User avatar
tarek
 
Posts: 3646
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves (solution)

Postby champagne » Fri May 29, 2020 2:01 pm

tarek wrote:
I prepared 2 puzzles from which I decided to post the above but I can post the other as V2 puzzle tomorrow if anybody is interested to have another go.

tarek


If you post it, I'll make a try to see if I learned anything from the first one. I assume that it would be again a 11x11 square.
BTW, this was done without any program, just an excel table to have a clean view of the work in progress
champagne
2017 Supporter
 
Posts: 7141
Joined: 02 August 2007
Location: France Brittany

Re: Ali Baba and the Forty Thieves

Postby tarek » Fri May 29, 2020 3:52 pm

Both puzzles should be human solvable. I didn’t say they were easy so any help even from a computer will still be appreciated by Ali Baba who is desperate to escape :D

I’ll post the puzzle tomorrow with code for copy/paste too.

Tarek
User avatar
tarek
 
Posts: 3646
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves

Postby 1to9only » Fri May 29, 2020 4:27 pm

1to9only wrote:After this, I've not spent much time on this problem of saving Ali Baba!!
But, I've been able to deduce the following:

(37)r9c3 - (38)r11c1 - (39)r2c10 - (40)r2c8

the program i posted is working correctly. it just my deducing is not so good. champagne has posted the correct solution.
1to9only
 
Posts: 1708
Joined: 04 April 2018

Re: Ali Baba and the Forty Thieves V2

Postby tarek » Sat May 30, 2020 7:38 am

Ali Baba and the Forty Thieves V2

Image

Code: Select all
... ... 044 ... ... ... ... 012 ... ... ...
XXX XXX ... XXX XXX ... ... ... ... ... ...
041 ... ... XXX XXX ... XXX XXX ... XXX XXX
XXX XXX ... ... ... ... XXX XXX ... ... 067
... ... XXX 028 XXX ... 058 ... ... XXX XXX
081 ... XXX 001 XXX 016 XXX ... XXX ... ...
... ... XXX ... XXX ... 057 033 ... XXX XXX
XXX XXX ... ... 049 ... XXX XXX ... ... ...
... ... ... XXX XXX ... XXX XXX ... XXX XXX
XXX XXX ... XXX XXX 010 ... ... 006 ... ...
... 062 073 ... ... 022 ... ... ... ... ...
User avatar
tarek
 
Posts: 3646
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves

Postby 1to9only » Sat May 30, 2020 10:30 am

Single jump: (57)r7c7 - (58)r5c7
Plug the new puzzle into alibaba.c, and the 1st route is solved:
Hidden Text: Show
(58)r5c7 - (59)r7c9 - (60)r9c9 - (61)r11c11 - (62)r11c2
1to9only
 
Posts: 1708
Joined: 04 April 2018

Re: Ali Baba and the Forty Thieves

Postby rjamil » Sat May 30, 2020 12:16 pm

Lets start wild guessing!!!

(10)r10c6 - (11)r1c6 - (12)r1c8 or
(10)r10c6 -(11)r10c8 - (12)r1c8 (added)
(41)r3c1 - (42)r5c1 - (43)r3c3 - (44)r1c3 or
(41)r3c1 - (42)r3c3 - (43)r1c5 - (44)r1c3 or
(41)r4c1 - (42)r1c1 - (43)r10c3 - (44)r1c3
(58)r5c7 - (59)r7c9 - (60)r9c9 - (61)r11c11 - (62)r11c2

R. Jamil
Last edited by rjamil on Sat May 30, 2020 2:20 pm, edited 1 time in total.
rjamil
 
Posts: 560
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Ali Baba and the Forty Thieves

Postby m_b_metcalf » Sat May 30, 2020 1:18 pm

I thought it would be nice to try to solve this problem using recursion. I wrote a complete new program whose kernel is a procedure to jump from one numbered tile to the next in the correct number of jumps. The jumps are controlled by a function that handles wraparound. They're shown here:
Hidden Text: Show
Code: Select all
    recursive subroutine jump(row, col)   
    integer :: row, col, row_save, col_save
    integer :: dirn
!
!  jump recursively in all directions until arrive at target in correct number of jumps
    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) = path(3, step) + depth
        if(depth == stretch) then
            if(row == path(1, step + 1) .and. col == path(2, step + 1)) then
                success = .true.
                exit
            else   
                tiles(row, col) = 0
                cycle
            end if   
        end if   
        call jump(row, col)           <<----------------- recursion is here
        if(success) exit
        tiles(row, col) = 0
    end do
   
    depth = depth - 1
    row = row_save; col = col_save
    end subroutine jump
   
    integer function clip(coord)
    integer coord
    !
    !    wraparound where necessary
    clip = coord
    if(coord > 11) then
        clip = clip  - 11
    else if(coord < 1) then
        clip = clip + 11
    end if
    end function clip

The funtion blocked (not shown) prevents Ali from landing on an incorrect numbered tile or, worse, on a thief. It also contains some information that Ali has cleverly stored in his head before setting off: looking ahead, he has calculated his future likely paths and noted which tiles he is very likely to have to land on. He then cunningly avoids those tiles in earlier moves.

Unfortunately, that crystal-ball gazing still requires some more refinement, as he only arrives at the exit
Code: Select all
 step  16 T
 30 72 29 71 24 69 23 77 22 78 73
  *  * 13  *  * 46 10 40  8 63 50
 31 74 32  *  * 76  *  * 21  *  *
  *  * 12 45 11 41  *  *  9 64  7
 33 55  * 75  * 58 18 59 20  *  *
 81  6  * 44  * 42  * 66  * 65  1
 34 54  * 56  * 57 19 60 17  *  *
  *  * 27 43 26 67  *  *  2 80  5
 35 53 37  *  * 61  *  * 16  *  *
  *  * 28  *  * 70 25 68  3 79  4
 38 49 36 48 14 47 15 62 51 39 52
with a bit of further prompting (explicitly hand coded). Still, I thought it worth mentioning the approach for any comments.

Regards,

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10883
Joined: 15 May 2006
Location: Berlin

Re: Ali Baba and the Forty Thieves

Postby tarek » Sat May 30, 2020 7:37 pm

m_b_metcalf wrote:….as he only arrives at the exit with a bit of further prompting (explicitly hand coded). Still, I thought it worth mentioning the approach for any comments.
Great … Ali Baba is saved!
User avatar
tarek
 
Posts: 3646
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves V2

Postby m_b_metcalf » Sun May 31, 2020 9:50 am

tarek wrote:Ali Baba and the Forty Thieves V2

The first step to a solution is to verify that at least one path can be found between each consecutive pair of numbered tiles. This is the case. Here is an example for each step:
Hidden Text: Show
Code: Select all
 step  1 T
  .  .  .  .  .  .  .  .  .  .  .
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  3  .  2  *  *  .  .  .
  .  .  *  .  *  .  .  .  .  *  *
  .  4  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  5
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  *  *  .  .  .  6  .  .
  .  .  .  .  .  .  .  .  .  .  .
 step  2 T
  .  .  .  .  .  .  .  .  .  .  .
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  *  .  .  .  .  *  *
  .  8  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  9  .  .  *  *  .  .  7
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  *  * 10  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .
 step  3 T
  .  .  .  .  .  .  . 12  .  .  .
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  *  .  .  .  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  *  *  .  . 11  .  .  .
  .  .  .  .  .  .  .  .  .  .  .
 step  4 T
  .  .  .  .  .  .  .  .  .  .  .
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  *  .  .  .  .  *  *
  .  .  *  1  * 16  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  .  . 15  *  *  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  *  *  .  . 14  . 13  .
  .  .  .  .  .  .  .  .  .  .  .
 step  5 T
  .  .  .  .  .  .  .  .  .  .  .
  *  *  .  *  * 18  .  .  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  . 17  .  .  *  *  .  .  .
  .  .  *  .  *  .  .  .  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  .  *  * 20  *  *  .  *  *
  *  *  .  *  *  .  .  .  .  .  .
  .  .  . 19  . 22  . 21  .  .  .
 step  6 T
  .  .  .  .  .  .  .  .  .  .  .
  *  *  .  *  *  .  . 23  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  * 28  *  .  .  .  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  * 27  *  .  .  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  .  *  * 26  *  *  .  *  *
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  .  .  .  . 25  . 24  .
 step  7 T
  .  .  . 30  .  .  .  .  .  .  .
  *  *  .  *  *  .  .  .  .  .  .
  . 29  .  *  * 31  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  *  .  . 32  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  . 33  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .
 step  8 T
  .  .  . 37  . 38  .  .  . 40  .
  *  *  .  *  *  .  .  .  .  .  .
 41  .  .  *  * 36  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  * 34  . 35  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  *  *  .  . 39  .  .  .
  .  .  .  .  .  .  .  .  .  .  .
 step  9 T
 43  . 44  .  .  .  .  .  . 42  .
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  *  .  .  .  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .
 step  10 T
 45  .  .  . 47  .  .  .  .  .  .
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  *  .  .  .  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  . 49  .  *  *  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  * 46  *  *  . 48  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .
 step  11 T
 51  .  .  . 53  . 54  .  .  .  .
  *  *  .  *  *  .  .  .  .  .  .
  .  . 52  *  *  .  *  * 55  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  *  .  .  . 56  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  . 57  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  * 50  *  *  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .
 step  12 T
  .  .  .  .  .  .  .  .  .  .  .
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  *  . 58  .  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .
 step  13 T
  .  .  .  .  .  .  .  .  .  .  .
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  *  .  .  .  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  . 59  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  .  *  *  .  *  * 60  *  *
  *  *  .  *  *  .  .  .  .  .  .
  . 62  .  .  .  .  .  .  .  . 61
 step  14 T
  .  .  .  .  .  .  .  .  .  .  .
  *  *  .  *  *  . 65  .  .  . 63
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  .  .  *  * 66  . 67
  .  .  *  .  *  .  .  .  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  .  .  .  .  . 64  .  .
 step  15 T
  .  .  .  .  .  .  .  .  .  .  .
  *  *  .  *  *  .  .  . 68  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  .  *  .  *  .  .  .  .  *  *
  .  .  *  1  *  .  *  .  *  .  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
  .  . 71  *  *  .  *  *  .  *  *
  *  *  .  *  *  .  .  .  .  .  .
 72  . 73  . 70  . 69  .  .  .  .
 step  16 T
  .  .  .  .  .  .  .  .  .  .  .
  *  *  .  *  *  .  . 76  .  .  .
  .  .  .  *  *  .  *  *  .  *  *
  *  *  .  .  . 77  *  *  . 79  .
  .  .  *  .  *  .  .  .  .  *  *
 81  .  *  1  *  .  * 78  * 80  .
  .  .  *  .  *  .  .  .  .  *  *
  *  *  .  .  .  .  *  *  .  .  .
 74  .  .  *  *  .  *  *  .  *  *
  *  *  .  *  *  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  . 75  .
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10883
Joined: 15 May 2006
Location: Berlin

Re: Ali Baba and the Forty Thieves

Postby creint » Sun May 31, 2020 11:14 am

Using Z3 Ali Baba can find his way very easy.
Within 3.3 seconds single solution found:
Hidden Text: Show
Code: Select all
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
creint
 
Posts: 171
Joined: 20 January 2018

PreviousNext

Return to Other logic puzzles