Problem 54780. Trap a knight

Created by ChrisR

Solve Later

Consider a knight on an infinite chessboard labeled with numbers spiraling outward. A knight starting on the square labeled 1 can reach 8 squares, marked in green below (i.e., squares 10, 12, 14, 16, 18, 20, 22, and 24). Take the smallest of these numbers, or 10. Repeating the step while avoiding squares already visited puts the knight at squares 3, 6, 9, 4, 7, 2, 5, etc. This tour continues until step 2016, when the knight reaches square 2084. At that point the knight is trapped: it has visited all eight possible squares. 
Write a function that takes the starting square and returns the sequence of squares visited by the knight on the tour. 

Solve

Solution Stats

23 Solutions
4 Solvers

Last Solution submitted on Apr 30, 2024

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Asif Newaz on 13 Aug 2022

my solution (using brute force) is giving the right answer (on the test cases I checked) but it's failing in Cody due to time constraints. I hate it when it does that.
in test case - 5, tic-toc is giving me 5s. I might be able to optimize the code a little more but I am not sure that would be enough. I think it's failing on the loop test cases due to runtime.
is it necessary to use loop cases as they tend to take a long time? why not just random settings?

GeeTwo on 30 Apr 2024

First off, why doesn't the MATLAB GUI find spiral when you search for it? I spent a lot of time building this myself before going on the internet for it.
Second, sorting a list and keeping the indices (second output argument from sort())is much faster than repeated finds when you're in the tens of thousands of finds and tens of thousands of array elements.

Solution Comments

Show comments

Problem Recent Solvers4

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 54780. Trap a knight

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author281

Problem Tags

Community Treasure Hunt

Problem 54780. Trap a knight

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author281

Problem Tags

Community Treasure Hunt

Players