• MacTech Network:
  • Tech Support
  • |
  • MacForge.net
  • |
  • Apple News
  • |
  • Register Domains
  • |
  • SSL Certificates
  • |
  • iPod Deals
  • |
  • Mac Deals
  • |
  • Mac Book Shelf

MAC TECH

  • Home
  • Magazine
    • About MacTech in Print
    • Issue Table of Contents
    • Subscribe
    • Risk Free Sample
    • Back Issues
    • MacTech DVD
  • Archives
    • MacTech Print Archives
    • MacMod
    • MacTutor
    • FrameWorks
    • develop
  • Forums
  • News
    • MacTech News
    • MacTech Blog
    • MacTech Reviews and KoolTools
    • Whitepapers, Screencasts, Videos and Books
    • News Scanner
    • Rumors Scanner
    • Documentation Scanner
    • Submit News or PR
    • MacTech News List
  • Store
  • Apple Expo
    • by Category
    • by Company
    • by Product
  • Job Board
  • Editorial
    • Submit News or PR
    • Writer's Kit
    • Editorial Staff
    • Editorial Calendar
  • Advertising
    • Benefits of MacTech
    • Mechanicals and Submission
    • Dates and Deadlines
    • Submit Apple Expo Entry
  • User
    • Register for Ongoing Raffles
    • Register new user
    • Edit User Settings
    • Logout
  • Contact
    • Customer Service
    • Webmaster Feedback
    • Submit News or PR
    • Suggest an article
  • Connect Tools
    • MacTech Live Podcast
    • RSS Feeds
    • Twitter

December 1997 Programmer's Challenge

Clueless Crosswords

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm EDT, Monday, 1 December 1997

Clueless Crosswords

 A couple of months ago, Bob Noll sent me a Challenge suggestion involving a crossword puzzle variant published by one of his local newspapers. The difficulty in using that suggestion was deciding how to provide the clues to the puzzle in a usable form. I thought about providing some sort of thesaurus, but giving simple synonyms as clues didn't seem to capture the crossword spirit. Then it occurred to me that clues serve only to make the crossword easy to solve, an advantage that certainly wouldn't be needed by our skilled Challenge readers or by the code they write. So the Challenge this month is to write code that will solve a crossword puzzle without clues.

The prototype for the code you should write is:

#define kMaxSize 32
typedef char Puzzle[kMaxSize][kMaxSize];

void Crossword(

Puzzle thePuzzle,   /* return solved puzzle here */
char *dictionary, /* array of words to choose from */
long puzzleSize,    /* number of rows/cols in puzzle */
long dictSize       /* number of words in dictionary */

);

Your Crossword routine will be provided with thePuzzle, where cell thePuzzle[row][col] will be initialized to a zero if you are to fill in that cell, or initialized to 0xFF if the cell is blacked out. The first puzzleSize rows and columns constitute the puzzle; the remaining cells in thePuzzle array are padding and should be ignored. You are to fill in the empty cells of thePuzzle with words from the dictionary provided, such that each uninterrupted sequence of blank cells, both horizontal and vertical, forms a word from the dictionary. The dictionary will contain all of the words needed to solve thePuzzle, but, to make things more interesting, it will also contain extra words not needed to solve thePuzzle. The dictionary may contain only a few extra words, or it may contain as many as 10 extra words for each word used in thePuzzle. Words in the dictionary are not guaranteed to be in any order, and any word might be used more than once in thePuzzle.

Each puzzle is guaranteed to have at least one solution using the dictionary provided. You will be guaranteed 20MB of memory for your code, static data, and any dynamically allocated memory. You may use more memory if it is available, but your code should detect and respond to memory allocation failures if you ask for more than the guaranteed amount of memory. As always, you must deallocate any dynamically allocated memory before returning.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal. The Challenge winner will be the entry that provides a correct solution to a set of crossword puzzles in the minimum time. Thanks to Bob Noll for suggesting a crossword puzzle problem, he wins two Challenge points for the suggestion.

 
MacTech Only Search:
Community Search:

 
 
 

 
 
 
 
 
  • SPREAD THE WORD:
  • Slashdot
  • Digg
  • Del.icio.us
  • Reddit
  • Newsvine
  • Generate a short URL for this page:



MacTech Magazine. www.mactech.com
Toll Free 877-MACTECH, Outside US/Canada: 805-494-9797
MacTech is a registered trademark of Xplain Corporation. Xplain, "The journal of Apple technology", Apple Expo, Explain It, MacDev, MacDev-1, THINK Reference, NetProfessional, Apple Expo, MacTech Central, MacTech Domains, MacNews, MacForge, and the MacTutorMan are trademarks or service marks of Xplain Corporation. Sprocket is a registered trademark of eSprocket Corporation. Other trademarks and copyrights appearing in this printing or software remain the property of their respective holders.
All contents are Copyright 1984-2010 by Xplain Corporation. All rights reserved. Theme designed by Icreon.
 
Nov. 20: Take Control of Syncing Data in Sow Leopard' released
Nov. 19: Cocktail 4.5 (Leopard Edition) released
Nov. 19: macProVideo offers new Cubase tutorials
Nov. 18: S Stardom anounces Safe Capsule, a companion piece for Apple's
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live