What's New -  September, 2008

[Home]

 

A Numbrix Puzzle

Solved!

September 29, 2008:  Numbrix™ is a puzzle currently (September, 2008) being published in the "Ask Marilyn" column of the weekly Parade Magazine and daily in the "Fun and Games" section of the Parade Magazine website.

The puzzle board is a square array of cells, 7x7, 8x8, or 9x9 in puzzles seen  so far.  For a puzzle with N cells per side, the objective is to fill  the cells with integers from 1 to NxN contiguously with each number after the first adjoining the next lower number vertically or horizontally.   Some of the numbers are pre-filled and the user's additions must interface with those to keep the entire number chain in proper order.   Our Numbrix programming exercise posted today, saves paper and your  eraser as you solve the puzzle, and provides hints or solves the entire puzzle for you.
 

 

September 25, 2008:  I spent a few days this week thinking about applying the "tabu" search used in the Kirkman's Schoolgirl problem to the "Cutting Stock" problem (determine the best way to cut parts of required lengths from  stock with given lengths and cost).   As a preliminary to help study the process, program "Manual Cutting Stock" was posted today.  It allows the user to select from all possible cutting patterns and specify how many of each pattern to cut.  The objective of course is to get all the required parts at the lowest cost.    So far I have not been able to beat the original  "Cutting Stock"  program available from the same web page.   Both programs read and save test cases in the same format, so checking the quality of a result is easy.  My main conclusion to date is that the manual version would  make a challenging puzzle game!    

September 9, 2008:  For what it's worth, I spent the last 6 days working on the algorithm which checks two solutions to Kirkman's Schoolgirl problem to see if one is really a disguised version of the other.   There are only 7 distinct cases and all of the other millions  of solutions map to one of the these.  I didn't improve it much, but I did add a page to Kirkman_Tabu V3 which helps understand how it works.   It probably won't solve global warming, but it was a fun and challenging way to spend some spare hours.   

September 3, 2008:  Kirkman's Schoolgirl Problem asks how to line up15 girls in 5 rows of 3 for each day for a week in such a way that no girl walks in a group with the same girl more than once during the week.  

I coded a solution to the problem several years ago but it had two defects.  It was slow, and and it did not identify the 7 essentially unique solutions to the problem.  Two solutions are considered to be the same if one could be converted to the other by rearranging the girls within one or more days or the sequence of daily arrangements could be changed.

 A recent paper introduced me to the Tabu search technique and led to today's  Kirkman Tabu program which finds solutions a the rate of a couple per second.  I also incorporated some old but previously un-posted code that searches for isomorphic cases and now finds the 7 distinct solutions in a few minutes.