Number Grid Search 1.0

Anyone who is interested in puzzle solving using Matlab might appreciate this simple code. It stems from a need to solve a grid puzzle posed by a fellow geocacher here in Australia. (Look to GC2YWE1 Minimax on the geocaching website for further details, or if you don't know what geocaching is :-) The puzzle asks you to find the maximum and minimum values of the sum of elements picked from a 10 x 10 grid of numbers. The rule is that every element must be chosen from a unique row and column. After some head scratching I decided this is a computationally irreducible problem. I am not sure I am correct in this assumption but proceeded on that basis anyway. To solve it you need to calculate all 10! (3,638,800) possible sums and find the limits.The idea struck me that what was required was calculations of the grid trace. Something that Matlab is adept at with the 'trace' function. The sum of the diagonal of the square matrix automatically picks elements with unique rows and columns, and so complies with the geocaching rule. All that was needed was to generate all possible 10! matrices made from the original grid by switching the columns (or the rows), and compute their tracesI found you can generate these matrices using recursion. Working this out how to do this might be a nice exercise for a computer science student :-) I thought I would publish the solution I devised here.Start by calculating the trace of the original matrix setting this as the first value of the maximum (or minimum). The matrix is then circularly rotated column-wise by one, bringing the next column is in the left-most position (column 1). Again Matlab is great to use since there is a versatile circular shift function 'circshift'. The trace is re-calculated and compared to the current maximum (or minimum). A sub-matrix is identified by ignoring the first row and column then the algorithm recursively called until you reach the smallest, bottom right-most 2X2 matrix.This algorithm is undoubtedly not as fast as a nested loop, but quite concise and arguably more fun!

Requirements:	No special requirements
Platforms:	Matlab
Keyword:	Calculating,  Columnwise,  Devised,  Publish,  Rotated,  Solution,  Start,  Student,  Thought
Users rating:	0/10