Ali Baba and the Forty Thieves

For fans of all other kinds of logic puzzles

Ali Baba and the Forty Thieves

Postby tarek » Mon May 25, 2020 6:30 pm

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?

Image
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves

Postby champagne » Tue May 26, 2020 12:58 pm

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: 7156
Joined: 02 August 2007
Location: France Brittany

Re: Ali Baba and the Forty Thieves

Postby 1to9only » Tue May 26, 2020 1:02 pm

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: 1985
Joined: 04 April 2018

Re: Ali Baba and the Forty Thieves

Postby tarek » Tue May 26, 2020 3:04 pm

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

Re: Ali Baba and the Forty Thieves

Postby Hajime » Tue May 26, 2020 7:08 pm

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.
User avatar
Hajime
 
Posts: 193
Joined: 20 April 2018
Location: Netherlands

Re: Ali Baba and the Forty Thieves

Postby tarek » Tue May 26, 2020 7:40 pm

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

Re: Ali Baba and the Forty Thieves

Postby rjamil » Wed May 27, 2020 2:41 am

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-99000000040008000000
031000000-99-99000-99-99000-99-99
-99-99000000000000-99-99000000000
000000-99000-99-58018000000-10-99
081000-99044-99000-99000-99000-01
000000-99000-99000000000-17+12-99
-99+10000000000000-99-99000000000
000000-37-99-99000-99+23000-99-99
-99-99000+10-99070000000000-79004
000000000000000000000062000000052

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:
1) after adding above value:
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: 594
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Ali Baba and the Forty Thieves

Postby 1to9only » Wed May 27, 2020 8:20 am

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)r6c11
route:  (4)r10c11
route:  (8)r2c9
route: (17)r7c9
route: (18)r5c7
route: (24)r1c5
route: (30)r1c1
route: (31)r3c1
route: (37)r9c3
route: (40)r2c8
route: (44)r6c4
route: (52)r11c11
route: (58)r5c6
route: (62)r11c8
route: (70)r10c6
route: (79)r10c10
exit:  (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: 1985
Joined: 04 April 2018

Re: Ali Baba and the Forty Thieves

Postby rjamil » Wed May 27, 2020 12:13 pm

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: 594
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Ali Baba and the Forty Thieves

Postby tarek » Wed May 27, 2020 12:35 pm

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

Re: Ali Baba and the Forty Thieves

Postby 1to9only » Wed May 27, 2020 1:03 pm

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.

I've made a little progress!
There is only one route for: (4)r10c11 - (8)r2c9
After this, there is only one route for: (1)r6c11 - (4)r10c11
.
1to9only
 
Posts: 1985
Joined: 04 April 2018

Re: Ali Baba and the Forty Thieves

Postby rjamil » Wed May 27, 2020 5:10 pm

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: 594
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Ali Baba and the Forty Thieves

Postby tarek » Wed May 27, 2020 7:34 pm

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

Re: Ali Baba and the Forty Thieves

Postby champagne » Thu May 28, 2020 3:13 am

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: 7156
Joined: 02 August 2007
Location: France Brittany

Re: Ali Baba and the Forty Thieves

Postby rjamil » Thu May 28, 2020 1:08 pm

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: 594
Joined: 15 October 2014
Location: Karachi, Pakistan

Next

Return to Other logic puzzles