## Ali Baba and the Forty Thieves

For fans of all other kinds of logic puzzles

### Ali Baba and the Forty Thieves

Ali Baba is trapped in the enchanted courtyard where the top edge joins the edge at the bottom and the right side joins the left. The Exit gate is locked and forty oil jars hiding the thieves in this borderless courtyard limit Ali Baba's options.

Morgiana told him that to break the enchantment and unlock the gate, he has to step on each tile in the courtyard (Except those with the jars) only once and has to do that by leaping each time a distance of 2 tiles in any direction (including diagonally) finishing at the exit gate. Lucky for him his jump is high enough to clear any obstacle including any intervening oil jar or gate but if he lands on a jar or revisits a tile then he risks being trapped forever and alerting the thieves to his presence.

Morgiana helps Ali Baba by marking some of tiles with numbers to indicate at which stage in his escape they are. If Ali Baba is on the 1st tile and the gate is on the 81st and last tile, can you help Ali Baba on his perilous escape?

tarek

Posts: 3748
Joined: 05 January 2006

### Re: Ali Baba and the Forty Thieves

likely a problem understanding the jumps rule, but I don't see a possibility to jump from 79 to the exit gate in 2 steps
exit gate r6c1
79 in r8c8
champagne
2017 Supporter

Posts: 7178
Joined: 02 August 2007
Location: France Brittany

### Re: Ali Baba and the Forty Thieves

tarek mentioned the edges wrap around - top edge joins the edge at the bottom and the right side joins the left.
so (79)r10c10 - (80)r8c10 - (81)r6c1 in one likely exit route.
1to9only

Posts: 2265
Joined: 04 April 2018

### Re: Ali Baba and the Forty Thieves

As 1to9only kindly showed, the enchanted courtyard displays a top-down and right-left wrapping giving it the shape of torus (doughnut , halo).

(30)r1c1 - (31)r1c3 shows an orthogonal jump over an obstacle

(79)r10c10 has 4 of the potential 8 jumps removed out of the equation (3 through blockage by the oil jars and r1c1 already marked as (30). From the 4 possible jumps only one will lead to the exit tile at r6c1 and that is the path 1to9only mentioned (79)r10c10-(80)r8c10-(81)r6c1`

tarek

Posts: 3748
Joined: 05 January 2006

### Re: Ali Baba and the Forty Thieves

I need a daytour from
r6c11-r8c9-r10c7-r8c5-r8c3-r6c1
to cover all 81 cells. That is at least go twice around the edges.

Hajime

Posts: 280
Joined: 20 April 2018
Location: Netherlands

### Re: Ali Baba and the Forty Thieves

Hajime wrote:I need a daytour from r6c11-r8c9-r10c7-r8c5-r8c3-r6c1 to cover all 81 cells. That is at least go twice around the edges.
Probably more but once the concept is visualized you will not worry too much about the edges. This was tested to be human solvable and should have one single solution.

There are several strategies to help Alibaba escape the enchanted courtyard which I'll supply if there is no progress as time goes by.

tarek

tarek

Posts: 3748
Joined: 05 January 2006

### Re: Ali Baba and the Forty Thieves

Hi Tarek,

Nice puzzle.

If I convert your visual puzzle in to numeric values then it looks like as follows:
Code: Select all
`030000000000024000000000000000000-99-99000-12-99000000040008000000031000000-99-99000-99-99000-99-99-99-99000000000000-99-99000000000000000-99000-99-58018000000-10-99081000-99044-99000-99000-99000-01000000-99000-99000000000-17+12-99-99+10000000000000-99-99000000000000000-37-99-99000-99+23000-99-99-99-99000+10-99070000000000-79004000000000000000000000062000000052`

Whereas:
1) each three digits represent a cell;
2) 000 in a cell means empty cell;
3) -99 in a cell means a thief in a cell;
4) +/-02 to +/-98 in a cell means to jump forward/backward towards aero head cell;
5) -1 means starting cell position; and
5) 81 means finishing cell position.

If a brute-force backtrack solver be written, then it will create another single dimension array of 81 elements that will represent move wise cell position as follows:
Code: Select all
` 65, -1, -1,109, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, 74, 50, -1, -1, -1, -1, -1,  4, -1, -1, -1, -1, -1,  0, 22, -1, -1, -1, -1, -1, 90, -1, -1, 18, -1, -1, -1, 58, -1, -1, -1, -1, -1, -1, -1,120, -1, -1, -1, -1, -1, 49, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,104, -1, -1, -1, -1, -1, -1, -1, -1,108, -1, 55`

Whereas:
1) first number represent starting zeroth move cell;
2) last number represent finishing end move cell; and
3) -1 represent to be searched cell position for specific move number.

a pseudocode should be, check from starting move cell position to each 8 positions for next move as follows:
1) Top-Right by subtracting 10 from cell position;
2) Right by adding 2 to cell position;
3) Bottom-Right by adding 12 to cell position;
4) Bottom by adding 11 to cell position;
5) Bottom-Left by adding 10 to cell position;
6) Left by subtracting 1 from cell position;
7) Top-Left by subtracting 12 from cell position; and
8) Top by subtracting 11 from cell position.
Note:
a) if cell position exceed from [INT (cell / 9) + 10] value then subtract 11; and
b) if cell position still exceed 120 value then further subtract 120.
2) after subtracting above value:
a) if cell position decreased from [INT (cell / 9)] value then add 11;
b) if cell position still decreased from 0 value then further add 120.

1to9only wrote:so (79)r10c10 - (80)r8c10 - (81)r6c1 in one likely exit route.

Similarly, some more possible move cell positions are as follows:
Move / Cell: 1 / 87, 2 / 85, 3 / 107, 59 / 71, 60 / 93, 61 / 115.

R. Jamil
rjamil

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

### Re: Ali Baba and the Forty Thieves

I have not been helping Ali Baba escape the enchanted courtyard, but might try every now and then!

Here's my enchanted courtyard (C-coding, -1=thief in oil jar, 0=empty cell, 1=start, n=route, 81=exit):
Code: Select all
`int grid[11]11] = {   { 30,  0,  0,  0, 24,  0,  0,  0,  0,  0,  0 },   { -1, -1,  0, -1, -1,  0,  0, 40,  8,  0,  0 },   { 31,  0,  0, -1, -1,  0, -1, -1,  0, -1, -1 },   { -1, -1,  0,  0,  0,  0, -1, -1,  0,  0,  0 },   {  0,  0, -1,  0, -1, 58, 18,  0,  0, -1, -1 },   { 81,  0, -1, 44, -1,  0, -1,  0, -1,  0,  1 },   {  0,  0, -1,  0, -1,  0,  0,  0, 17, -1, -1 },   { -1, -1,  0,  0,  0,  0, -1, -1,  0,  0,  0 },   {  0,  0, 37, -1, -1,  0, -1, -1,  0, -1, -1 },   { -1, -1,  0, -1, -1, 70,  0,  0,  0, 79,  4 },   {  0,  0,  0,  0,  0,  0,  0, 62,  0,  0, 52 }};`

Ali Baba's escape route (Sudoku RC notation):
Code: Select all
`start:  (1)r6c11route:  (4)r10c11route:  (8)r2c9route: (17)r7c9route: (18)r5c7route: (24)r1c5route: (30)r1c1route: (31)r3c1route: (37)r9c3route: (40)r2c8route: (44)r6c4route: (52)r11c11route: (58)r5c6route: (62)r11c8route: (70)r10c6route: (79)r10c10exit:  (81)r6c1`

My helping Ali Baba would be to map all possible escape subroutes, e.g: (1)r6c11-(4)r10c11, (4)r10c11-(8)r2c9, (8)r2c9-(17)r7c9, etc. and then resolving route conflicts.
Will take me some time so save Ali Baba from the Forty Thieves.
1to9only

Posts: 2265
Joined: 04 April 2018

### Re: Ali Baba and the Forty Thieves

Hi 1to9only,

Notice some minor corrections from your pseudocode, like starting Ali Baba cell position is 1 (instead of 0).

However, some oil jar jumping aeros are out of alignment. I think, no jump should be possible from empty cell. Need Tarek's confirmation regarding jumping aero from/to cell positions (either 0 to 120 or r1c1 to r11c11 cell notation form).

R. Jamil
rjamil

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

### Re: Ali Baba and the Forty Thieves

So for Alibaba to break the enchantment he has to always jump two tiles in any direction even if there is no obstacle in his path. The tile that he lands on is marked by a number. Alibaba at the start is on tile number 1 he needs to jump 80 jumps to complete his journey around the courtyard

tarek

tarek

Posts: 3748
Joined: 05 January 2006

### Re: Ali Baba and the Forty Thieves

rjamil wrote:Notice some minor corrections from your pseudocode, like starting Ali Baba cell position is 1 (instead of 0).

This is my preferred notation, it would be how I code this in C.
1to9only wrote:so (79)r10c10 - (80)r8c10 - (81)r6c1 in one likely exit route.

This is the only exit route.

There is only one route for: (4)r10c11 - (8)r2c9
After this, there is only one route for: (1)r6c11 - (4)r10c11
.
1to9only

Posts: 2265
Joined: 04 April 2018

### Re: Ali Baba and the Forty Thieves

Hi 1to9only,

We are now very close to each other.

I have one more route (manually) confirmed, i.e., (58)r5c6 - (59)r7c6 - (60)r9c6 - (61)r11c6 - (62)r11c8.

R. Jamil
rjamil

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

### Re: Ali Baba and the Forty Thieves

rjamil wrote:I have one more route (manually) confirmed, i.e., (58)r5c6 - (59)r7c6 - (60)r9c6 - (61)r11c6 - (62)r11c8.

I can see other option available for that route, however, I can confirm that I can only see one route possible to link 4-5-6-7-8 as all other routes are blocked:

Code: Select all
`4r10c11-5r8c11-6r6c2-7r4c11-8r2c9`

tarek

Posts: 3748
Joined: 05 January 2006

### Re: Ali Baba and the Forty Thieves

due to the constraint in r6c10, I see only one path from 40 to 44

EDIT 2 paths but one locked to go from 44 to 52

r4c6 41
r6c6 42
r8c6 43
r4c4 45
r2c6 46
r11c6 47
r11c4 48
r11c2 49
r2c11 50
r11c9 51

EDIT r8c4 43

still 24 cells to fill but I must have a long break
champagne
2017 Supporter

Posts: 7178
Joined: 02 August 2007
Location: France Brittany

### Re: Ali Baba and the Forty Thieves

Hi 1to9only and Tarek,

tarek wrote:
rjamil wrote:I have one more route (manually) confirmed, i.e., (58)r5c6 - (59)r7c6 - (60)r9c6 - (61)r11c6 - (62)r11c8.

I can see other option available for that route, however, I can confirm that I can only see one route possible to link 4-5-6-7-8 as all other routes are blocked:

Code: Select all
`4r10c11-5r8c11-6r6c2-7r4c11-8r2c9`

Ok. Thanks.

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
rjamil

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

Next