Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | Last revisionBoth sides next revision |
| contest_2011-10-04 [2011/10/03 18:44] – jtkorb | contest_2011-10-04 [2011/10/03 18:47] – jtkorb |
|---|
| * C: The solution array values ai indicate the row in which the queen in column i appears. Choose candidates by pruning all the rows that conflict with (are "attacked by") queens already placed in the previous columns. | * C: The solution array values ai indicate the row in which the queen in column i appears. Choose candidates by pruning all the rows that conflict with (are "attacked by") queens already placed in the previous columns. |
| * D: Like Queens, except more Bishops are possible. Solution vector contains n*n booleans indicating if a bishop is located in that space. Need functions that convert square number (0..n*n-1) to row and column values (integer division and mod are your friends). See Queens solution to determine if two bishops are in attack positions (the slope of the line between them is 45 degrees). | * D: Like Queens, except more Bishops are possible. Solution vector contains n*n booleans indicating if a bishop is located in that space. Need functions that convert square number (0..n*n-1) to row and column values (integer division and mod are your friends). See Queens solution to determine if two bishops are in attack positions (the slope of the line between them is 45 degrees). |
| * E: Generate people placements from left to right. Need functions to compute number of people who can see left and number who can see right. Prune when impossible situations arise (e.g., tallest person is less than p locations of right). | * E: Generate people placements from left to right. Need functions to compute number of people who can see left and number who can see right. Prune when impossible situations arise (e.g., tallest person is less than P locations from left edge, or closer than R locations from right edge). More efficient representations and pruning criteria possible. |
| * F: More exotic application of backtracking. | * F: More exotic application of backtracking. |
