## More Recursive Backtracking (UVa 574)

Last week I wrote about solving UVa 11085 using the recursive backtracking search technique. This week, I’m going to outline a more general approach to recursive backtracking problems. Then I’ll show how it can be adapted to solve UVa 574.

UVa 574 asks us to solve this problem:

Given a multiset $S$ of integers and a target sum $t$, find all subsets of $S$ that sum to $t$.

« Continue »

## Solving UVa 11085 with Recursive Backtracking

The uHunt Chapter 1 starred problems contain three examples of chess problems. In Chapter 3, we get back to chess with a variation on the classic eight queens puzzle. UVa 11085 is used to illustrate the algorithmic technique known as recursive backtracking.

« Continue »

## When Not to Simulate a Game (UVa 11553)

Some programming puzzles can be solved by simulating a game or process. For example:

• UVa 978 is based on simulating a conflict between warring lemmings.
• For UVa 732, you have to simulate something more abstract: a stack that pushes and pops characters.

UVa 11553 may seem like a classic simulation problem: a board game between two players. But it soon becomes clear that this problem can’t be solved by simulating the players’ moves.

« Continue »

## Command-Line Tools for Competitive Programming

When they select their tools, programmers have a choice between command-line and GUI options. Most people use both. For example, I prefer to use GUI tools for diffing a set of files I’m preparing to commit to a source repository. I also like my editor to be graphical, though I use a lot of keyboard shortcuts. But command-line tools are preferable when I’ll be repeating the same action multiple times. It’s a lot more efficient to retrieve a typed command from the shell history than to do the same steps repeatedly using mouse clicks or even keyboard shortcuts. Today I’ll be explaining some commands that are useful for programming puzzles.

« Continue »