No 3 X's In a Row

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



Search WWW


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.


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

Search 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 

Suggestions for Further Explorations



Original:  mmmm dd, yyyy

Modified:  February 18, 2016

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