In this blog, I will add a new post all 3-5 days. Each post contains a complete (optimization) problem, many of them are puzzles. Each problem consists of a comprehensive description of the problem, a description of the modeling (translation from spoken language to mathematical language), a mathematical formulation, an implementation in the LPL modeling language, and a link to solve the problem directly through the Internet. A full document is also downloadable as a PDF.
I start with easy puzzle problems, but later on, more complicated problems will be presented. Enjoy!
An initial position of 8 Queens on a chessboard is given. Now move exactly three of the Queens to other cells so that there will be 11 cells on the board which are not under attack. To move the Queens, it is not necessary to use proper ’Queen moves’. You may take them up and place them anywhere. Is there only one solution? The initial positions are as follows (1 means “a Queen is placed there”, 0 “no Queen is placed) :
Implement a linear algorithm for finding a solution of the n-queens problem.
Place a maximal number of Queens on a chessboard in such a way that they are not attacking each other (see [2] and [1]).
How many queens are needed, and in what position, so that every unoccupied square of the chessboard could be attacked directly by a queen? (see [2] and [1]).
What is the largest number of Bishops that can be placed on the chessboard without any Bishop attacking another? (see [2] and [1]).
Place as few Bishops as possible on an ordinary chessboard so that every square of the board will be occupied or attacked (see [2] and [1]).
Place as few Knights as possible on a chessboard in such a way that each square is controlled by at least one Knight, including the squares on which there is a Knight (see [2] and [1]).
Use each digit from 1 to 7 exactly once, and place them into the circles of Figure 1 in such a way that the sum along each of the five lines is the same.
This model draws a clock. It is the template for the following simple puzzle: “Divide the clock with a straight cut into two parts such that the sum of the numbers in both parts are equal ?”. Can you see the solution at once?
“One day a customer arrived at a 7-Eleven shop and selected four items. He then approached the counter to pay for these items. The salesman took out his calculator, pressed a few buttons, and said: “The total price is $7.11.” “Why?” said the customer, who was amazed by this coincidence. “Do I have to pay $7.11 because the name of the shop is 7-Eleven?” “Of course not!” replied the salesman. “I have multiplied the prices of these four items and I have given you the result!” “Why did you multiply these numbers?” asked the surprised customer. “You should have added them to get the total price!” “Oh, yes, I’m sorry,” the salesman said. “I have a terrible headache and pressed the wrong button!” Then the salesman repeated all the calculations (i.e., he added the prices of these four items), but to both of their great surprise, the total was still $7.11. What are the prices of these four items? Believe it or not, there is a unique solution to this problem…” (This puzzle is from [3], Puzzle 12-6.)