Here are a few problems that involve hill climbing or some form of local search. Feel free to suggest others and to discuss solutions.
 

# You are given a list of A of n points with integer coordinates in the 2d plane. Find another point P(x, y) such that the *sum of square distances* from the points in A to P is minimum.
# You are given a list of A of n points with integer coordinates in the 3d plane. Find another point P(x, y) such that the *maximum of the Manhattan distances* from the points in A to P is minimum. (the manhattan distance between (x1, y1, z1) and (x2, y2, z2) is |x1 - x2| + |y1 - y2| + |z1 - z2|)
# You are given a list of A of n points with integer coordinates in the 2d plane. Find another point P(x, y) such that the *sum of euclidean distances* from the points in A to P is minimum.
# You are given a convex polygon P with n vertices, find out the radius of the *largest inscribed circle* in that polygon..
# You are given a list A of n points in the plane, find out the *minimum enclosing circle*.
# Given a number n, find out a placement of *n queens* on an nxn chessboard such that they don’t attack each other.

Given n and S integers, find out a permutation p such that <tex>1 x p[1] + 2 x p[2] + .. + n x p[n] = S</tex>.

# Given n (n <= 1000) and S integers, find out a permutation p such that <tex>1 * p[1] + 2 * p[2] + .. + n * p[n] = S</tex>.

# 2n knights have to sit around a roundtable. Each knight is friends with n + 1 other knights. Find a seating arrangement such that each knight is placed between two friends.
# Given two line segments in 3d space find the minimum distance between them.
# A party of n people is too large and has to be split to two tables. Given that each of the people has at most three enemies in the group, find a seating arrangement such that each person sits at a table with at most one of his enemies.

public

protected