-2
2
Given an a-by-b sized grid, and a chess knight, determine:
- A starting point and path the knight can take to visit every square in the grid
- or "NOT POSSIBLE", if not possible.
Input: Two integers, a
, b
.
Output: Numbers output in an a-by-b grid:
1 4 7 10
8 11 2 5
3 6 9 12
Where 1
is where the knight starts, a*b
is where the knight ends, and the numbers signify the path the knight must take, in ascending order. The knight cannot land on the same square twice.
The rows of the grid must be separated with a newline, and the items in each row must be separated with a space.
Test Cases:
| is a newline.
3 4 -> 1 4 7 10 | 8 11 2 5 | 3 6 9 12
2 3 -> NOT POSSIBLE
If there is a solution there will be more than one: any valid solution is acceptable.
Shortest code wins. Please do not use any programming languages that are known to produce short programs: e.x. GolfScript, APL, J, K, etc.
Are coordinates able to be visited more than once? If so, should they counted/reported in the output? – Gaffi – 2012-06-25T13:52:15.427
@Gaffi: Nope, they can't. – beary605 – 2012-06-25T14:13:53.230
@Gaffi I don't think that's valid, as
1
and2
are on the same row. From1
to2
there should be a regular knight move. (see beary605's first test case result for an example) – Cristian Lupascu – 2012-06-25T14:42:20.553OH, nevermind. The numbers in the expected output are the step numbers. I was going with the order/position of the spaces to move to. i.e. in my own example, you start at POS 1, then move to POS 7, which is the same as the original example, just formatted differently. I'll adjust my code on that. Sorry! – Gaffi – 2012-06-25T14:47:57.523
15The recently added language restriction seems to be against the spirit of code golf, and is additionally rather vague on languages like Perl. – Peter Taylor – 2012-06-25T16:23:42.227
11-1. Although I have no desire to ever write solutions in GolfScript, APL, J, or K, I find this restriction irksome enough to warrant a down-vote (which I will rescind if you change the requirement). – Steven Rumbalski – 2012-06-25T17:04:38.673
@StevenRumbalski: I did this because I don't want people to take an easy answer, just because they coded in a character-compressed programming language. You may downvote if you like, but I want people to work to make their answers short. – beary605 – 2012-06-26T01:50:13.387
8@beary605: I'll happily upvote any answer to this question in GolfScript, APL, J, K, or any similarly extremely terse programming language. It's takes plenty of work to write short programs in those languages because it takes plenty of work to learn them. I've coded all my answers in Python (except for one in Perl). The game I play is that I try to be shortest among Ruby, Perl, Python, JavaScript, etc. Doing so usually produces a satisfactory number of upvotes even if I don't "win". Not winning is my fault for not taking time to learn the right tool for the job. – Steven Rumbalski – 2012-06-26T02:05:59.737
4Writing GolfScript isn't easy. The debugging support is negligible, and you have to keep track of exactly what's on the stack at any time with no static checking to ensure you were right. – Peter Taylor – 2012-06-26T06:35:19.763
I just want languages of the same type. You can have either all terse, or all verbose. I don't want them mixing in this particular problem. – beary605 – 2012-06-26T06:45:30.927
3
If you want to eliminate GolfScript, J, APL etc. from the answers to your questions, you should make the questions difficult, impractical or impossible to answer in those languages. (eg. require floats and GolfScript is out, the requirement for operator precedence in this question made it difficult enough for me to give up trying in J).
– Gareth – 2012-06-26T09:56:23.203Ok. I will keep that in mind, if I ever come up with a question like that. – beary605 – 2012-06-26T14:52:10.517
2The language thing is ridiculous. APL and K are not designed specifically to make short answers (like Golfscript for example) - they are programming languages people use in actual jobs (well paying ones too). I know people that only know how to program in APL - they aren't even allowed to answer? – Jerry Jeremiah – 2014-06-09T03:43:04.687