# Combination forumla

1. Jun 20, 2012

### badluckbrian

I'm writing a C++ program to brute-force solve a puzzle, but in order to determine the number of iterations the loop of the program should have (in order to exhaust all possible solutions) I need to know how many possible combinations there are. This isn't homework, I was just intrigued on how to do it.

The puzzle has nine distinct squares which are to be arranged in a 3x3 grid, like one face of a Rubik's cube; any piece can go in any place. However, each piece, being a square, can be rotated in its place to produce a different solution (each edge of the square has a unique "piece" on it that must pair with other edges).

9^9^4 yielded a number that seemed way too big, and 9*9*4 seemed too small. I tried researching the formula, but since I have found every way possible through both high school and college to avoid math, it was lost on me.

tl;dr: how many possible combinations are there for a puzzle like this

http://www.google.com/imgres?imgurl...=pF7iT5ahLc_16gGmtbUI&ved=0CH8Q9QEwBg&dur=630

Thanks to anyone who can give me some help.

2. Jun 20, 2012

### haruspex

Break it into two parts: first, how many ways are there of assigning the tiles to positions in the 3x3 grid? (For simplicity, don't worry about symmetries.)
Having assigned the tiles to positions, how many ways are there of orienting each tile?
The 10 numbers obtained above are independent of each other, so multiply them together.
You should get a number a bit under 10^11.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook