Description

Submit An Entry

Standings

The Elevator Pitch

Solve 25 versions of a sliding tile puzzle similar to the well-known 15 puzzle.

The Puzzles

Each of the 25 puzzles is played on a regular hexagonal grid. The puzzles differ from each other only in the sizes of their grids, which vary from order 3 to order 27. For this contest we'll generally refer to a grid of order n as being of size n.

Each grid has k - 1 moveable tiles, numbered from 1 to k - 1, where k is the number of cells in the grid.

Initially, each puzzle's tiles are distributed randomly among its grid's cells, leaving one cell empty.

The starting grids for the 25 puzzles are here.

Your goal for each puzzle is to find a sequence of moves which relocates each tile to (or close to) its home cell, and does so with as few moves as possible.

The following diagram shows a grid with each tile in its home cell – the center cell is empty and the tiles are otherwise arranged in row major order.

A move consists of choosing one of the vertices of the empty cell as a "center of rotation", and then rotating the tiles in the 3 adjacent cells by 120 degrees. Your first move can rotate either clockwise or anticlockwise. Thereafter, the direction of rotation must change with each move.

If the center of rotation is on the perimeter of the grid, the rotation will necessarily include one or two cells from other sides of the grid. These diagrams indicate which cells are considered adjacent to the vertices on the grid's perimeter.

How to Enter

Represent a solution (that is, a sequence of moves) as a string, each character of which represents a move. This character indicates both the center and direction of the rotation, as shown here. Numeric characters are used for clockwise rotation, and alphabetic characters for anticlockwise.

For example, the string "1D5" indicates three moves to be executed in sequence:
      • clockwise around vertex 1 of the empty cell,
      • anticlockwise around vertex D of the empty cell, and
      • clockwise around vertex 5 of the empty cell.

To submit this sequence of 3 moves as a solution, preface the string with the size of the grid to which it applies, and insert a colon to separate the size from the moves. Then paste this concatenation into the large box on the Submit page and click Submit Entry. For this solution you would paste:

      3:1D5

To submit more than one solution at a time, separate them with semicolons. Do not place a semicolon after the last solution.

Include spaces and other white space (tabs, line breaks, etc.) anywhere you like – but not, of course, within the grid-size prefix.

Over the course of the contest, you can submit more than one solution for the same grid size, but only the best of them will count.

The Scoring System

• Frist, two values are calculated from each solution:

  • sum-of-distances
  • number-of-moves
  
  
  Sum-of-distances is the sum, over all tiles, of the taxicab distance between the tile's ending cell and its home cell. The taxicab distance between two cells is best explained with a few examples:
  
  
  
  Distance = 2

  
  Distance = 4

  
  Distance = 4

  
  Distance = 3

  Here is an example of computing sum-of-distances for a grid of size 2:

  
  
  Final positions of tiles

  
  
  Home positions of tiles

  Tile	Distance
  1	0
  2	1
  3	1
  4	2
  5	2
  6	0
  Sum-of-distances	6

  
  Distances

  Number-of-moves for a solution is, unsurprisingly, the number of moves in the solution.

• Then, a raw-score for each submission is calculated as follows:

  Raw-score   =   sum-of-distances   +   ( number-of-moves / 1000000)   +   1

• Finally, we use the raw-scores from your submissions to compute your contest-score. The contestant with the highest contest-score wins. Here's how we calculate your contest-score:

  • For each of the 25 grid sizes, your grid-size-score is the best (that is, lowest) grid-score for your submissions of that size.
  
  • For each of the 25 grid sizes, we compute your subscore. We do this by dividing your grid-size-score into the lowest grid-size-score for that grid size across all contestants. Each of your subscores therefore has a value from 0 to 1.
  
  • Your contest-score is the sum of your 25 subscores.

• If two contestants have the same contest-score, we break the tie by giving preference to the contestant whose last improvement was submitted least recently.

Let's walk through an example. Suppose we modify the contest by asking you to submit solutions for only 3 grid sizes: 3, 4 and 5. Further suppose that we have only 3 contestants (Harry, Ron and Hermione) and that each has submitted exactly one solution for each grid size.

We begin by noting the sum-of-distances and number-of-moves for each submitted grid:

	Grid size = 3		Grid size = 4		Grid size = 5
	Sum of Distances	Number of Moves	Sum of Distances	Number of Moves	Sum of Distances	Number of Moves
Harry	49	5	119	120	269	75
Ron	39	60	138	10	259	130
Hermione	29	115	129	65	281	20

Then, we calculate the raw-score for each submission:

	Grid size = 3	Grid size = 4	Grid size = 5
Harry	50.000005	120.000120	270.000075
Ron	40.000060	139.000010	260.000130
Hermione	30.000115	130.000065	282.000020

Next, we note the lowest raw-score for each grid size:

	Grid size = 3	Grid size = 4	Grid size = 5
Lowest Raw-Score	30.000115	120.000120	260.000130

Finally, we calculate the subscores and contest-score for each contestant:

	Grid size = 3	Grid size = 4	Grid size = 5	Contest Score
Harry	30.000115 / 50.000005 = .600	120.000120 / 120.000120 = 1.000	260.000130 / 270.000075 = .962	2.562
Ron	30.000115 / 40.000060 = .750	120.000120 / 139.000010 = .863	260.000130 / 260.000130 = 1.000	2.613
Hermione	30.000115 / 30.000115 = 1.000	120.000120 / 130.000065 = .923	260.000130 / 282.000020 = .922	2.885

Hermione has the highest contest-score and therefore is the winner.

Getting Your Questions Answered

First, check the FAQ section below. If you can't find the information you need there, send your question to the discussion group. If your question is of a personal nature, and not of general interest, send an email directly to Al Zimmermann.

The Discussion Group

If you think you might enter the contest, you should join the contest discussion group. You can join either by sending a blank email here or by visiting the group on groups.io . The discussion group serves two purposes. First, it allows contestants to ask for clarifications to the rules. Be aware that sometimes these requests result in changes to the rules, and the first place those changes are announced is in the discussion group. Second, the discussion group allows contestants to interact with each other regarding programming techniques, results and anything else relevant to the contest.

Frequently Asked Questions

• Can teams enter the contest?

  Yes. But a team can only be formed by those who have not already entered the contest as individuals. Once you enter as an individual, team membership is no longer open to you. Likewise, once you've joined a team you can't resign from it and start submitting grids on your own behalf.

  If you would like to form a team, please follow these instructions:

  • If they do not already exist, create individual accounts for each team member. Do not create a second account for any team member who already has one.
    
    
  • Let me know each team member's name and registered email address. It is important that no team member submit any entries to this contest until I notify you that the team has been created.
    
    
  • After I've created the team, team members can submit entries to the contest from their individual accounts. The contest engine automatically intercepts these entries and diverts them to the team account. The team is listed on the standings page.
    
    
  • Unless you are satisfied with the defaults, also let me know what team name and team location you would like to use on the standings page. Note that if all team members are from the same organization, the organization name can be included in the location, e.g., "Olaf Academy, Oslo, Norway".
    – For name, the default is a combination of your last names. For example, "Newton / Leibniz".
    – For location, the default is the smallest geographic entity containing all team member locations. For example, "Western Europe".

  Note: Teams are contest-specific. Joining a team for this contest does not affect your participation in other contests.
  

• May I write a program that submits entries by bypassing my browser?

  Yes.

• May I programmatically download the standings page at regular intervals? How frequently would be reasonable?

  Yes, you may programmatically download the standings page at regular intervals. Please feel free to download it as often as once per second. If you want to download the standings page more frequently than that, please contact me first.

• I've written a little program that helps a person generate solutions manually. May I distribute the executable to other contestants?

  No. This is a programming contest and writing useful tools is something one should be able to do for oneself. That alone would be sufficient reason to disallow the distribution of such tools, but consider also that you would be disadvantaging those who either don't hear about your tool or can't run your executable in their environment.

  However, if you are part of a team, you may share such tools with your teammates.

• What topics are appropriate for the discussion group?

  With only one exception, if it's related to AZsPCs then it's fine to talk about it in the discussion group. The exception is spoilers. Spoilers include:

  • specific solutions
  
  • detailed algorithms (yes, detailedness is subjective)

  If you are not sure if something would be considered a spoiler, ask me.

• Who is Balto?

  Balto was an Alaskan husky and an American hero. He achieved fame leading a team of sled dogs on the final leg of the 1925 antitoxin run to Nome (Alaska) to combat an outbreak of diphtheria. A bronze statue of Balto is installed in New York City's Central Park.