This is a Nim-style game. There is a lot of information available on the web for winning strategies for this class of games.
In general, the idea is to start with the basic winning configurations. These are situations where you can win on that turn. For this game, this is any case where there are only matches in one box. You can always take all the remaining matches from that one box and win the game. So your objective is to get your opponent to eventually leave you in that position. This means forcing him to take the last match from the next to last box. You have to assume that your opponent plays optimally as well, so he won't take the last match from the next to last box if he doesn't have to. So you have to force a situation where there are two boxes with one match in each. The brute force method to find winning moves is to build up a list of winning positions, starting with end-game positions and working backwards to earlier positions. Your move is a winning move if it leaves your opponent in a losing position. Your move is a losing move if it leaves your opponent in a winning position. If there is any winning move from a position, that is a winning position. Otherwise, it is a losing position. With this particular game, the number of possible positions is so large that you can't use the brute force method except for very small games. But looking at small games you can figure out the mathematical characteristics of a winning position. Once you know that, you can solve a big problem easily. Don On Monday, October 28, 2013 3:22:54 AM UTC-4, robin wrote: > > We have a game of matchboxes with the following rules: > * It is a 2-player game. > * There are n matchboxes with varying number of matchsticks in them. The n > matchboxes are numbered from 1 through n. > * The two players take alternating turns. > * Both players can count how many matchsticks are remaining in each box at > any time. > * In each turn, the player playing the turn removes matchsticks from > exactly one box. The rule for choosing the box is described below. > * In any turn the matchbox that is chosen must have the highest number of > matchsticks before the turn. If there are multiple such boxes, the matchbox > that is numbered higher is chosen. > * The player can choose to remove any number of matchsticks ranging from 1 > to the total number of matchsticks in the matchbox chosen as per the rules. > * The game ends when all matchboxes are empty. > * The player who played the last turn wins. > A move is called a “winning move” if after the move, the player who made > the move can eventually win irrespective of what the opponent does. You are > required to write a program which analyzes a given state of the game and > finds a winning move. If there are multiple winning moves, you have to pick > the move where the number of matchsticks removed is maximum among all > possible winning moves. > > *Input Format* > First Line will contain number of test cases: T(1 <= T <= 100). > For each test case: First line contains number of matchboxes: n(1 <= n <= > 10000). > Next line contains n non-negative integers(<= 10000) as number of > matchsticks in matchboxes from left to right. > > *Output Format* > For each testcase print a single line: > If there is no winning move print “No winning move” without quotes. > else print “Remove number_of_matchsticks matchstick from matchbox > matchbox_id” > > > *Sample Input* > 3 > 3 > 0 0 10 > 3 > 1 1 1 > 2 > 1 1 > > > *Sample Output* > Move 10 matchstick from matchbox 3 > Move 1 matchstick from matchbox 3 > No winning move > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
