Find the moves that bring a chess squad to a given destination.

You control a chess squad consisting of a king and several other pieces, on a larger chess board. Your army is placed so that no piece is further than K=8 squares away (horizontally and vertically) from your king. You will receive a destination square for the king and you must generate a list of moves for all your pieces so that your king reaches that square and your pieces' final positions will be at the same distances from your final king as the distances between your pieces' initial positions and the initial king. The constraint that no piece can wander further than K=8 squares from the king (in any direction) must be respected at all times.

# Inputs and Outputs

The board is a matrix of size 41x51, with each cell containing a digit with the following meaning:

• 0: empty square
• 1: obstacle square
• 8: your final king position
• 9: unused

Your task is to write a function that, being given a matrix, generates a list of moves, in order, so that the king reaches the final king position and the other pieces reach their final positions, relative to the king. The format of the list should be an array of moves, where the move is an array of the form [x1, y1, x2, y2]. See the example solver for details.

# Extended Rules

• Pawns move one square orthogonally, in any direction
• All special moves from chess are invalid in this setting: two-square pawn advance, en passant, pawn promotion, castling
• "no-further-than-8" rule: no move that makes a piece become further than 8 squares away from the king (horizontally or vertically) is allowed

# Scoring

The controller (challenge.html) comes with a battery of 16 test sets. If your solver doesn't output a move list consisting only of valid moves and having the final position of the pieces at their destination fields, you score 10000 for that test. Otherwise, you score the number of moves in your solution. The lowest total score wins.

# Controller

https://github.com/altvali/chess_march_challenge

https://raw.githack.com/altvali/chess_march_challenge/main/challenge.html

You can open the controller (challenge.html) in your browser and interact with it using your browser's console. No local server required. Use the dropdown to visualize any of the test set positions.

You can look at a sample solver implementation in the Javascript of the page. It outputs a hardcoded best solution to the test set 0, but keep in mind that only a general solver is accepted for the contest. Your own solver will have to take as input the data_map matrix and output the list of valid moves in the same format (explained above).

To evaluate your solver, you can type in the browser console the following:

evaluate(window.t.test_sets, solver)


It will reply with a breakdown of your score, per category, and the total score.

To visualize one of your solutions your can use the Move Player. Example using the first test set and the default solver:

var move_list = solver(window.t.test_sets[0])


This will load the map and the moves up to the last valid move. You'll be able to use the Move Player's buttons to interact with your solution.

# Submissions

Submit your solver function and total score achieved. Remember, the solver must generalize well and your score should be as low as possible. Good luck!

• Nice challenge. You can update the github readme, it still says (todo: link to it once it's posted).
– user100752
Jul 26, 2021 at 9:08
• @EliteDaMyth Thank you, I've updated. Jul 26, 2021 at 10:38
• By “horizontally and vertically”, do you mean that each distance should be at most 8, or that their sum should be at most 8? Jul 27, 2021 at 23:24
• @xigoi I mean each distance; see test set 10 for an example where all other pieces are at maximum distance from the king Jul 29, 2021 at 12:28
• Will all the test cases require less than 10000 moves - otherwise, a program could just not respond for anything with more than 10000 moves. Aug 5, 2021 at 17:27