Ali Baba and the Forty Thieves

For fans of all other kinds of logic puzzles

Re: Ali Baba and the Forty Thieves

Postby Hajime » Thu Jun 04, 2020 11:22 am

Sorry Tarek, I could not resist to write an algorithm
Very slow but short recursive program (in Excel).

1.5 hours of programming and a night running produced the solution of V3
Hidden Text: Show
ab3.png
ab3.png (53.39 KiB) Viewed 189 times

Only 50 lines of recursive code:
Hidden Text: Show
Code: Select all
Private Sub CommandButton1_Click() 'GO
    n = 1
    For i = 1 To 11
     For j = 1 To 11
      If Cells(i, j) = -1 Then ii = i: jj = j
      If Cells(i, j) < 0 Then Cells(n, 16) = Cells(i, j): Cells(n, 15) = Cells(i, j): n = n + 1
     Next
    Next
    Columns("O:P").Sort key1:=Range("P1"), order1:=xlDescending, Header:=xlNo 'sort the givens
    Call jumpto(1, 1, ii, jj)
End Sub

Sub jumpto(step, seq, i, j) 'step on cell i, j
  Cells(1, 13) = step:  Cells(2, 13) = seq:  DoEvents
  If Cells(i, j) = "" Then 'empty cell to is good
    If step < -Cells(seq, 15) Then 'still time for a next hurdle
        Cells(i, j) = step
        Call jumpfrom(step + 1, seq, i, j)
        Cells(i, j) = ""
    End If
  ElseIf Cells(i, j) = -step Then ' is an intermediate check of step
    If step = 81 Then
      MsgBox ("Done")
      End
    Else
      If -step = Cells(seq, 15) Then Call jumpfrom(step + 1, seq + 1, i, j)
    End If
  Else 'must be a jar or already been here, no good
  End If
End Sub

Sub jumpfrom(step, seq, i, j)
 For x = -1 To 1
  For y = -1 To 1
   If x = 0 And y = 0 Then
     'nothing
   Else
     xx = clip(i + 2 * x)
     yy = clip(j + 2 * y)
     Call jumpto(step, seq, xx, yy)
   End If
  Next
 Next
End Sub

Function clip(z)
  If z < 1 Then z = z + 11
  If z > 11 Then z = z - 11
  clip = z
End Function

For Ali Baba V1 and V2 it could not produce a solution within a night time span
User avatar
Hajime
 
Posts: 193
Joined: 20 April 2018
Location: Netherlands

Re: Ali Baba and the Forty Thieves V4

Postby tarek » Sat Jun 06, 2020 9:56 am

Great work …

I solved V3 manually …

My last Ali Baba and forty thieves in this thread will be this:

Ali Baba and the Forty Thieves V4

Image

In this enchantment, Ali Baba has to finish at the starting tile to break the enchantment and exit. In other words: Tile number 81 is one jump away from Tile 1 where Ali Baba currently stands

I will Put a link to all of these puzzles later & post some more variations in the http://forum.enjoysudoku.com/fairy-chess-piece-tour-puzzles-including-numbrix-hidato-t30443.html thread.

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

Re: Ali Baba and the Forty Thieves V4

Postby m_b_metcalf » Sat Jun 06, 2020 10:14 am

tarek wrote: In other words: Tile number 81 is one jump away from Tile 1 where Ali Baba currently stands

So, tile 1 is also tile 82, if I understand correctly.

As always, a text file is much appreciated.

Thanks,

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

Re: Ali Baba and the Forty Thieves V4

Postby tarek » Sat Jun 06, 2020 10:49 am

m_b_metcalf wrote:
tarek wrote: In other words: Tile number 81 is one jump away from Tile 1 where Ali Baba currently stands

So, tile 1 is also tile 82, if I understand correctly.

As always, a text file is much appreciated.

yes, You can look at it that way

Code: Select all
X   X   .   X   X   .   X   X   .   X   X
X   .   .   .   55  X   56  .   .   .   X
X   .   47  26  .   .   .   28  66  .   X
19  X   54  4   .   .   .   78  8   X   7
.   X   .   .   X   X   X   .   .   X   .
.   .   .   .   17  1   9   .   .   .   .
.   X   .   .   X   X   X   .   .   X   .
14  X   15  2   .   .   .   22  70  X   73
X   .   50  39  .   .   .   41  62  .   X
X   .   .   .   12  X   69  .   .   .   X
X   X   .   X   X   .   X   X   .   X   X


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

Re: Ali Baba and the Forty Thieves

Postby m_b_metcalf » Sat Jun 06, 2020 11:47 am

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


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

Re: Ali Baba and the Forty Thieves

Postby StrmCkr » Sun Jun 07, 2020 5:30 am

So, tile 1 is also tile 82, if I understand correctly.

As always, a text file is much appreciated.


yes, You can look at it that way
that's pretty much how i saw it as well.

slightly modified my code for the closed loop tour {updated code for the slight change as well} : basically expanded the 80 cell path to 81 to end on the start then ran "limiter" on the expanded array.

Hidden Text: Show
alibaba4.PNG
alibaba4.PNG (11.76 KiB) Viewed 130 times

Code: Select all
X   X   .   X   X   .   X   X   .   X   X X   .   .   .   55  X   56  .   .   .   X X   .   47  26  .   .   .   28  66  .   X 19  X   54  4   .   .   .   78  8   X   7 .   X   .   .   X   X   X   .   .   X   . .   .   .   .   17  1   9   .   .   .   . .   X   .   .   X   X   X   .   .   X   . 14  X   15  2   .   .   .   22  70  X   73 X   .   50  39  .   .   .   41  62  .   X X   .   .   .   12  X   69  .   .   .   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 tarek » Tue Jun 09, 2020 7:54 pm

Excellent and well done all … I'm glad that you found them entertaining and challenged you to find solutions in you own way :idea:

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

Re: Ali Baba and the Forty Thieves

Postby StrmCkr » Wed Jun 10, 2020 6:04 am

A new piece for you to play with

Sin bad the sailor moves in an arc path

Up down left or right

Code: Select all
x
.x
x


All xs must be clear to make the move.
Sinbads path starts and end at home as all his advetures cover the 7 seas but he retuns home. For all of them
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 10, 2020 11:08 am

StrmCkr wrote:A new piece for you to play with

Sin bad the sailor moves in an arc path

Up down left or right

Code: Select all
x
.x
x


All xs must be clear to make the move.
Sinbads path starts and end at home as all his advetures cover the 7 seas but he retuns home. For all of them

Hold that thought … I'm playing with a new concept (sort of) which should suit Sinbad nicely!
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves

Postby m_b_metcalf » Wed Jun 10, 2020 11:32 am

m_b_metcalf wrote: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.

And, of course, where there's a solver we have the basis of a generator. I wasn't concerned about symmetry, for the moment, and found that making minimal puzzles (for this configuration?) produces what I think are very hard puzzles. Here's my first attempt in text form:
Code: Select all
  J  .  J  .  J  .  J  J  J  .  J
  J  J  J  .  .  .  . 24  .  .  .
  J  .  J  .  J  .  . 54  .  .  .
  J  .  .  .  .  . 73 21  .  .  .
  J  .  J  .  .  .  .  .  .  . 46
 65  J  . 81  J  1 70  .  J  J  .
  J  . 29 51  J  9  .  7 45  J 34
  .  J  J 57  J  .  J  .  J  .  J
  .  .  .  .  .  .  J  .  J 26  J
  J  .  J  .  J  .  J  3  J  .  J
  J 13  J 16  .  .  .  .  . 25  .   minimal

I'd be grateful if someone could check it.

I'm leaving soon for a couple of weeks, so won't be looking into any variants.

Regards,

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

Re: Ali Baba and the Forty Thieves

Postby StrmCkr » Wed Jun 10, 2020 2:31 pm

The other concept i am tinkering with is blocking cells that can move at the same time we can move in preset patern
to go with sinbad
basically an island fish Jasconius (Aspidochelone)

Of variable. Size that can trap our poor sailor if he cant avoid it in 1 move.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 1163
Joined: 05 September 2006

Redundancies

Postby m_b_metcalf » Wed Jun 10, 2020 4:11 pm

I used my program to check tarek's first four puzzles for redundant clue combinations. It found:

    V1: 40 and 79;

    V2: 41 (at least);

    V3: 22, 67, 70 (at least);

    V4: 2, 4, 7, 12, 14, 18, 39, 41, 78 (at least).

FWIW

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

Re: Ali Baba and the Forty Thieves

Postby tarek » Thu Jun 11, 2020 11:36 am

m_b_metcalf wrote:
Code: Select all
  J  .  J  .  J  .  J  J  J  .  J
  J  J  J  .  .  .  . 24  .  .  .
  J  .  J  .  J  .  . 54  .  .  .
  J  .  .  .  .  . 73 21  .  .  .
  J  .  J  .  .  .  .  .  .  . 46
 65  J  . 81  J  1 70  .  J  J  .
  J  . 29 51  J  9  .  7 45  J 34
  .  J  J 57  J  .  J  .  J  .  J
  .  .  .  .  .  .  J  .  J 26  J
  J  .  J  .  J  .  J  3  J  .  J
  J 13  J 16  .  .  .  .  . 25  .   minimal

I'd be grateful if someone could check it.


Single solution!
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Re: Ali Baba and the Forty Thieves

Postby m_b_metcalf » Thu Jun 11, 2020 11:49 am

Thanks. And, for a parting shot, here's a version of your second puzzle that has only 15 numbered tiles. Note the leap of 15 tiles between 42 and 57. What's the maximum possible size of a leap? What's the minimum possible number of tiles?

Code: Select all
  30   .   .   .  24   .   .   .   .   .   .
  JJ  JJ   .  JJ  JJ   .   .   .   8   .   .
   .   .  32  JJ  JJ   .  JJ  JJ   .  JJ  JJ
  JJ  JJ   .   .   .   .  JJ  JJ   .   .   .
   .   .  JJ   .  JJ   .  18  59   .  JJ  JJ
  81   .  JJ   .  JJ  42  JJ   .  JJ   .   1
   .   .  JJ   .  JJ  57  19   .   .  JJ  JJ
  JJ  JJ   .   .   .   .  JJ  JJ   .   .   .
   .   .  37  JJ  JJ   .  JJ  JJ   .  JJ  JJ
  JJ  JJ   .  JJ  JJ  70   .   .   3   .   .
   .   .   .   .   .   .   .  62   .   .   .  only 15 numbered tiles, based on V2


Regards,

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

Re: Ali Baba and the Forty Thieves

Postby tarek » Thu Jun 11, 2020 1:19 pm

The Jar configuration will have an effect on that but even with a symmetric configuration of 40 jars I was able to get 17 clue double orthogonal symmetry. My estimate is that there will be puzzles with less than 15 clues

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

PreviousNext

Return to Other logic puzzles