Game 15

In early 1880, a certain Charles Pevi, a dentist from Worcester, drew public attention by offering $ 1000 (then it was good money), for solving the following problem: fifteen checkers were placed in a square box in the correct order, and only checkers 14 and 15 were rearranged , as it shown on the picture. The task was to gradually move the checkers, bring them to the normal position, and, moreover, the order of the checkers 14 and 15 should be corrected.

In our company, every employee can be self-educated 5 hours a week (read / write on Habr, learn F # or read SICP). Over time, this practice has evolved into the creation of mini-projects. For example, Maxim, an experienced JavaScript developer, decided to try creating apps for iOS, and for about a month and a half released tags that, without any advertising, were included in the TOP 10 Russian App Store in the game category for a week.

Further, the verification code on Objective-C and the principle of the passage of the Fifths from Yakov Isidorovich Perelman's book “Live Mathematics”.
')
For many of us, it was a surprise that exactly half of all possible (1,307,674,368,000) combinations have no solutions. To test for decisiveness, we took a formula from Wikipedia: let the square with the number i be located before (if you count from left to right and from top to bottom) k squares with numbers less than i . We assume that n _i = k , that is, if after a knuckle with the i -th number there are no numbers less than i , then k = 0. We also enter the number e - the row number of the empty cell (counting from 1). If the amount



is odd, then a puzzle solution does not exist.

Objective-C verification code

#import "GamePositionValidator.h" @interface GamePositionValidator(){ NSInteger emptyCellRowNumber; } @property (nonatomic, retain) NSArray* validPosition; @property (nonatomic, retain) NSArray* currentPosition; @end @implementation GamePositionValidator @synthesize validPosition; @synthesize currentPosition; -(id) initWithValidPosition:(NSArray *) _validPosition emptyCellRowNumber:(NSInteger ) _emptyCellRowNumber{ if(self = [super init]){ self.validPosition = _validPosition; emptyCellRowNumber = _emptyCellRowNumber; } return self; } -(NSInteger) positionOfChipInValidPosition:(NSInteger) chipNumber{ for(NSInteger i=0; i<self.validPosition.count; i++){ NSNumber* number = [self.validPosition objectAtIndex:i]; if(number.intValue == chipNumber){ return i; } } return -1; } -(NSInteger) countOfDisordersInPosition:(NSInteger) position{ NSInteger chipNumber = ((NSNumber*)[self.currentPosition objectAtIndex:position]).intValue; NSInteger chipPosition = [self positionOfChipInValidPosition:chipNumber]; NSInteger countOfDisorders = 0; for( NSInteger i= position+1; i<15; i++){ chipNumber = ((NSNumber*)[self.currentPosition objectAtIndex:i]).intValue; NSInteger nextChipPosition = [self positionOfChipInValidPosition:chipNumber]; if( nextChipPosition < chipPosition){ countOfDisorders ++; } } return countOfDisorders; } -(BOOL) isPositionCanBeTransformedToValidPosition:(NSArray*) position{ self.currentPosition = position; NSInteger totalDisorders = 0; for(NSInteger i=0; i<self.currentPosition.count; i++){ totalDisorders+=[self countOfDisordersInPosition:i]; } self.currentPosition = nil; return (totalDisorders + _emptyCellRowNumber) % 2 == 0; } @end 

This is Max’s first Objective-C app so you can safely criticize it.

Lastly, the principle of the passage of the “Fifths” in the book “Living Mathematics” by Y.I. Perelman:
“Imagine a location in which 15 checkers are placed in a motley mess. Near moves you can always bring a checker 1 into place. Similarly, it is possible, without touching checker 1, to bring checker 2 to the right to the next place. Then, without touching the checkers 1 and 2, you can put the checkers 3 and 4 in their normal places: if they do not happen to be in the last two vertical rows, then it is easy to bring them into this area and then with a series of movements achieve the desired result.
Now the top line 1, 2, 3, 4 is put in order, and with further manipulations with the checkers, we will not touch this row.

In the same way we try to put in order and the second line: 5, 6, 7, 8; it is easy to make sure that this is always achievable. Further, in the space of the last two rows, checkers 9 and 13 must be brought to the normal position; this is also always possible. Of all the put in order checkers 1, 2, 3, 4, 5, 6, 7, 8, 9 and 13 in the future, not one move;



there remains a small area of ​​six fields, in which one is free and the other five are occupied with checkers 10, 11, 12, 14, 15 in random order. Within this six-place section, you can always bring checkers 10, 11, 12 to their normal places. When this is achieved, checkers 14 and 15 will be placed in the last row either in the normal order or in the reverse. ” Good luck!