contest_2011-10-04

This shows you the differences between two versions of the page.

Both sides previous revision Previous revision | |||

contest_2011-10-04 [2011/10/03 18:47] jtkorb |
contest_2011-10-04 [2011/10/04 11:04] (current) jtkorb |
||
---|---|---|---|

Line 21: | Line 21: | ||

**Hints:** | **Hints:** | ||

- | * A: [[Backtracker.java|Here]] is an abstract class that defines the backtracking interface and solution from the textbook. Candidates are the numbers 1..N (or 0..N-1); but prune out the ones that have already appeared in a. | + | * A: Use this abstract class that defines the [[Backtracker.java|backtracking]] interface and solution from the textbook. Candidates are the numbers ''1..N'' (or ''0..N-1''); but prune out the ones that have already appeared in ''a''. |

- | * B: The solution array is a vector of booleans: ai true means element i is in the subset; false means not in the subset. What are the candidate values? (Obviously, true and false.) | + | * B: The solution array is a vector of booleans: ''a[i]'' true means element ''i'' is in the subset; false means not in the subset. What are the candidate values? |

- | * 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 value ''a[i]'' indicates the row in which the queen in column ''i'' appears. Choose candidates by pruning all the rows that conflict with (i.e., are "attacked by") queens already placed in the earlier 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 (they only conflict diagonally, not via rows and columns). The solution vector contains ''n*n'' booleans indicating if a bishop is located in that space. Need functions that convert a square number (''0..n*n-1'') to row and column numbers (integer division and mod are your friends). See Queens solution to determine if two bishops are in attack positions (i.e., 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 from left edge, or closer than R locations from right edge). More efficient representations and pruning criteria possible. | + | * E: Generate people placements from left to right. Need functions to compute the number of people who can see to the left and the number who can see to the right. Prune when impossible situations arise (e.g., if the tallest person is less than ''p'' locations from the left edge, or if closer than ''r'' locations from the right edge). More efficient representations and pruning criteria are possible (and necessary to be accepted at the UVA or PC sites). |

* F: More exotic application of backtracking. | * F: More exotic application of backtracking. |

contest_2011-10-04.txt · Last modified: 2011/10/04 11:04 by jtkorb