I am super stuck on how to go about starting this problem, any help would be appreciated!

Finding the Number of Possible, Unique Boards At first glance, it may seem easy to calculate the number of possible boards: after the first spot is taken by x, there are 8 locations for o to take; so there are 9 * 8 (72) different board configurations with 1 x and 1 o. After a second move, there are 9 * 8 * 7 different board configurations, after the third, 9*8* 7 * 6. After the 9th move, there are 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 9! . Therefore, the total number of game boards (including the empty board) are: 1 + 9 + 9 * 8 + 9 * 8 * 7+ ... 9! = 986,410 However, there are a lot of duplicate boards. Consider the following moves, shown below, which result in the same board: X x] L ---+---+--- |0| ---+---+--- X | 0 | X ---+---+--- ---+---+--- ---+---+--- ---+---+--- 1 X ---+---+--- 10 X ---+---+--- X | 0 | X ---+---+--- ---+---+--- ---+---+--- ---+---+--- When all the duplicates are removed, there are 6,046 different boards left. However, not all of these boards are possible. Since the game ends once a player wins, there are game boards that can not possibly exist. For instance, the board below can never exist, as the game would have stopped before both x and o could have won: xl ---+---+--- x | x | x ---+---+--- 0|00 Your Program You will write a program that generates every unique and valid tic-tac-toe board. There are fewer than 6,000 of these once you remove duplicates and unreachable boards! Additionally, you will keep track of the number of (unique & valid) boards where: X wins o wins No one wins (a tie). These should be output in this exact format: total boards: nnn, wins for 'o': nnn, wins for 'X': nnn, ties: nnn After that first line, the output from your program should be one line per board, where each line is a string representing the board using the following indexing scheme below: 0|1 | 2 ---+---+--- 3 | 4 | 5 ---+---+--- 6 | 7 | 8 For example, the string X o ox X represents the following board: x 10 ---+---+--- 10 x ---+---+--- | x | Additionally, your program's output should be in sorted order. ....so if you're storing the strings representing the boards in a vector, you'll need to sort it before printing. Keep in mind the following rules: . x goes first The empty board is a valid board The game stops when someone wins-no more moves are made. Your program does not have to be fast, but it should run in less than a minute. With the right algorithm, it is possible to have it run in seconds. The following is the first several boards (when printed in sorted order)