Int board_m1 = board_size - 1 /* board size - 1 */ĪQueenBitCol = aQueenBitPosDiag = aQueenBitNegDiag = 0 Int odd = board_size & 1 /* 1 if board_size odd */ Unsigned int bitfield /* set bits denote possible queen positions */ Unsigned int lsb /* least significant bit */ Int numrows = 0 /* numrows redundant - could use stack */ Int aStack /* a stack instead of recursion */ Int aQueenBitNegDiag /* marks used "negative diagonals" */ Int aQueenBitPosDiag /* marks used "positive diagonals" */ Int aQueenBitCol /* marks used columns */ Submitted by several from Romania, this solution uses bitmasks instead of a list to speed searching: #include Next]:=next prev]:=prev Īssign(Input,'checker.in') Reset(Input) Īssign(Output,'checker.out') Rewrite(Output) įillChar(diagPLUS,SizeOf(diagPLUS),False) įillChar(diagMINUS,SizeOf(diagMINUS),False) His program runs almost 4x faster then N=13. The Ukraine's Michael Rybak removed the 'this row is used' search (which obviously at the end of the recursion is a lot of wasted iterating) and replaced it with a list of valid rows to use (which presumably has but a single element at the end of the recursion). * on each row of the board starting at row i and going to row n. * Calculate number of ways to place checkers Since we number rows from 0 to N-1 rather than 1 to N, we need to add 1 to each digit as we print (in "printsol"). The N>6 lines get the program out of trouble when N=6, because at that point, the first 3 solutions include one of the symmetric answers. An exception happens when N is odd the odd row needs to be counted once. Symmetry enables us to count the first half of the solutions double and avoid calculating the second half. Since we generate solutions in increasing order, we record the first 3 in the "sol" array. We keep track of which columns and diagonals already have checkers on them in the "col", "updiag", and "downdiag" arrays. The search proceeds by trying to put one checker in each row. We use a recursive complete search to simply test all boards. Here are the test data inputs: - test 1. YOUR PROGRAM ('checker') WORKED FIRST TIME! That's fantastic TIME LIMIT: 1 CPU second PROGRAM NAME: checker INPUT FORMATA single line that contains a single integer N (6 If you insist on cheating, your login to the USACO training pages will be removed and you will be disqualified from all USACO competitions. Work on your program until it can solve the problem properly. Do not precalculate the value and print it (or even find a formula for it) that's cheating. Special note: the larger values of N require your program to be especially efficient. Print the the first three solutions in numerical order, as if the checker positions form the digits of a large number, and then a line with the total number of solutions. Print the solutions using the column notation described above. Write a program that finds all unique solution sequences to the Checker Challenge (with ever growing values of N). This is one solution to the checker challenge. The solution shown above is described by the sequence 2 4 6 1 3 5, which gives the column positions of the checkers for each row from 1 to 6: ROW (Diagonals run from southeast to northwest and southwest to northeast and include all diagonals, not just the major two.) Examine the 6圆 checkerboard below and note that the six checkers are arranged on the board so that one and only one is placed in each row and each column, and there is never more than one in any diagonal.
0 Comments
Leave a Reply. |