No 3 X's In a Row

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

Background & Techniques

Another puzzle from our 2013  "Brain Game" page-a-day calendar.  I worked on this one for about 10 minutes before deciding that a 10 minute program would be more fun and  more likely to guarantee a solution.  To write it took more like 30 minutes, but it does find the two solutions in less than a second.

We'll number the cells of a tic-tac-toe board 1 to 9 from left to right and top to bottom.   We can then use the numbers to represent positions in a 9 digit binary number and interpret 1's as X's.

1 2 3
4 5 6
7 8 9

The program searches for solutions by generating the 9 binary digit representation of all numbers all integers from 1('000000001') to 511 ('111111111') and testing all of those which have six 1's.

The "forbidden" rows, columns and diagonals are predefined as the eight triples (1,2,3), (4,5,6), (7,8,9), (1,4,7), (2,5,8), (3,6,9), (1,5,9), and (3,5,7). Any number with six 1's which does not have 1's in all 3 of any of those triplets is a solution!
 

Programmer's Notes:

The key to this 50 line program is our IntToBinaryString function contained in the DFFUtils unit.  Calling the function passing integers up to 511 and specifying a minimum length of 9 makes it an easy matter to check all arrangements of six X's on the board.  For example, 207 has binary representation 011001111 which has six "1" bits, but is not a solution since the bits in the positions 7, 8, and 9 represent three X's in the last row.

Everything else is simple and well commented in the source code.     

Running/Exploring the Program 

bulletDownload  executable
bulletDownload source  (Note: Our library zip file of commonly used units.  Library file DFFVLIB13 or later contains the DFFUtils unit which is required to recompile this program )
bulletDownload current library file (DFFLibV15) required to recompile..

 

Suggestions for Further Explorations

???
 
   
   

 

Original:  mmmm dd, yyyy

Modified:  May 15, 2018

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.