A195668 Length of longest Sokoban game with n spaces and 1 bag.

1, 2, 3, 5, 9, 11, 15, 18, 21, 25, 28, 32, 35, 41, 42, 48, 50, 57

Offset

3,2

Comments

This sequence grows as O(n^2), and the constant is known to be between 3/49 and 1. -Zachary DeStefano, Jun 05 2021

Links

Table of n, a(n) for n=3..20.

Zachary DeStefano and Michael Gottlieb, Sokoban Max Moves Archive

Erich Friedman, Problem of the month March 2000

Wikipedia, Sokoban

Example

From Zachary DeStefano, Jun 05 2021: (Start)
In standard Sokoban notation, for n = 12 the a(12) = 25 board is:
#####
#@  ###
# # $ #
#    .#
#######
(End)

Crossrefs

Cf. A195667, A195669.

Sequence in context: A328642 A102940 A157049 * A324698 A059042 A157604

Adjacent sequences: A195665 A195666 A195667 * A195669 A195670 A195671

Keyword

nonn,more,hard

Author

Kausthub Gudipati, Sep 22 2011

Extensions

a(14)-a(29) from Zachary DeStefano, Jun 05 2021

Status

approved