Toughest backtracking problems in algorithmic competitions

backtrack

TL;DR

In algorithmic competitions there are frequently problems that can be attacked with recursive backtracking algorithms – a well-known approach to traverse a search tree. Usually, it is good smell, if there’s a goal to analyze all existing combinations of a problem. And, of course, there needs to be the right strategy to meet time limits (e.g. prune it). Here, I’ve decided to talk about a few very interesting backtracking problems I came across. I touch on a backtracking approach to develop in competitors, but bear in mind that, not trying to solve a problem by yourself, seeing the answer up front is a waste of time. Furthermore, this is an advanced level, if you haven’t practiced a recursive backtracking or DFS, please spend some time on basic backtracking problems and come back.

1. Chess Puzzler

chess

This is quite an interesting problem I’ve ever come across, solving it you realize some very important uses cases to consider like memory limits, recursion, combinatorics and optimization techniques. I’ve seen a chess problem in Skiena’s  algorithmic book some time ago, but as turned out, this one is very different.

Problem Statement:

The problem is to find all distinct layouts of a set of normal chess pieces on a chess board with dimensions MxN where none of the pieces is in a position to take any of the others. Assume the color of the piece does not matter, and that there are no pawns among the pieces.

Write a program which takes as input:

•The dimensions of the board: M, N.

•The number of pieces of each type (King, Queen, Bishop, Rook and Knight) to try and place on the board.

As output, the program should yield the number of distinct layouts for which all of the pieces can be placed on the board without threatening each other.

Solution:

We represent each piece as: “K” – King “N” – Knight “Q” – Queen “R” – Rook “B” – Bishop M – Horizontal size of the board N – Vertical size of the board S – is a set of remaining pieces. For example: Input: 3×3 board containing 2 Kings and 1 Rook, that is S = [K,K,R]. Answer: 4 layouts.

layouts

Since we need to find all possible layouts of a chessboard, it can be solved with a recursive backtracking as follows. We take the next piece from S and calculate for it all possible freeSquares on the chess board. Next, by iterating in a loop over freeSquares for current piece, we try to put it in all possible freeSquares. Each loop-step is a potential solution (layout) calls itself recursively by trying to put the next piece for current chess board and so forth until there are no pieces left or freeSquares is empty. Once a piece is placed on the board, we update the set of the free squares by subtracting a set of squares threatened by this piece. In case the set of free squares is empty and there are still any remaining pieces not on the board, there’s no solution to this combination and the recursive function backtracks to the upper level in the recursive tree trying the next loop-step. Thereby, we loop over all steps and stop traversing by pruning impossible configuration in advance – as simple as this. There could be some arithmetic optimization with a number of threatened squares for each piece type by taking into account all remaining pieces to be put on the board and number of free squares, calculated in one go. Since the time limit in this problem was 20 mins to solve, I ditched an optimization. Undoubtedly, my solution can be drastically improved by cutting the search tree even more, and hence I leave this to the reader. Moreover you might want to parallelize this recursive task.

Finishing touch, namely what to do about duplicated pieces like 3 queens or 2 knights etc. Honestly, I spent a great deal of time on this while solving. The thing is that, duplicates are interchangeable in terms of different combinations on the chessboard. For instance, for a board of 1×2 length with free squares [x:1,y:1][x:1,y:2], 2 queens can be placed as [Q1][Q2] or [Q2][Q1] yielding 2 different combinations. A simple solution is to put at once all pieces of one type inside a loop-step. From combinatorics, we can enumerate all C(n, k) unique combinations (aka n choose k) in a single loop. Because we recurse, I created a utility function wrapped around with a standard java iterator which doesn’t have to calculate all combinations up front, rather it traverses them lazily by calculating the next one on the fly. The reason for this was a memory taken on each level of the recursion stack to keep an array of all combinations. E.g. C(n, k) = C(1000,5) results into 8,250,291,250,200 elements. There were also some minor issues with Groovy not being able to correctly calculate a difference between 2 lists of coordinate-pairs. Thanks to guys on stackoverflow who quickly replied with a workaround. The full working code  is now available on GitHub. If somebody of you have an idea to optimize it somehow, please comment one at the end of this post!

2. To backtrack or not, that’s the question: Meet “Mine Sweeper Master” from Google code jam 2014

minesweeper

A tricky and simple at the same time problem was posed last year on Google Code Jam in qualification round – a famous Mine Sweeper master. Yes, the one that comes with Windows operating system – I bet, most of you are aware of! It’s well-known solving minesweeper is NP-complete. But conditions of the problem don’t require you to do that (Please read a problem statement before proceeding).

Solving it with a backtracking is the wrong way, as you are not required to analyze all configurations. The catch is that any correct result is a solution (read carefully a problem  statement)! And thus, you don’t have to attack it with backtracking as this pattern is quite costly, aimed at getting all possible solutions. It is possible, but you won’t pass the large set most likely. Hence, the simplest idea is to start at (0,0) – upper-left corner and fill an area of N cells  with non-mine space from left to right and top to bottom – line-by-line. Further, fill the rest with mines. Clicking the (0,0) cell should reveal if this is a good solution. If (0,0) is not a mine – we have won. If the square contains a 0, repeat this recursively for all the surrounding squares.

There are also a number of important corner cases to consider for this approach:

Single non-mine

If N=1, any configuration is a correct solution.

Single row or single column

If R=1, simply fill in the N non-mines from left-to-right. If C=1, fill N rows with a (single) non-mine.

Too few non-mines

If N is even, it must be >= 4.
If N is odd, it must be >= 9. Also, R and C must be >= 3.
Otherwise there's no solution.

Can’t fill first two rows

If N is even and you can't fill at least two rows with non-mines, then fill the first two rows with N / 2 non-mines.
If N is odd and you can't fill at least two rows with non-mines and a third row with 3 non-mines, then fill the first two rows with (N - 3) / 2 non-mines and the third row with 3 non-mines.

Single non-mine in the last row

If N % C = 1, move the final non-mine from the last full row to the next row.

I was lazy to depict each one. As can be seen, there is bunch of special cases to consider to make this solution pass.

3. Another Chess Board Puzzler: “King” from Google Code Jam 2008

This is one of the toughest problems from Google Code Jam. It differs in that no one solved it in global Code Jam rounds during the round in which it was posed. Algorithmic competitions is like sports, if you feel you can solve easier problems faster – go for it. Otherwise you’re at risk of loosing the competition. Some day next time I will try to attack it too, and for now I say goodbye to  all of you.

Advertisements

Google code Jam 2013 – Qualification round finished

As many of you know, it’s been 10 hours since qualification round finished at Google code jam contest: http://code.google.com/codejam/

Appx. 21000 participants took part around the world with 25h time available for the round.

codejam_pic

Here are my solutions to 3 problems given out of 4:

https://github.com/vibneiro/googleJam2013

So, here’s the analysis:

1. Problem A: Tic-Tac-Toe-Tomek

Works on small and large sets. Just a simple algorithm to implement. The point is to comply with all the conditions. The goal is to find a winner. If there’s no winner, it should be draw, otherwise if we have empty cells the game is not completed.

import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

/**
  @Author: Ivan Voroshilin
  @Date: April 13 2013
  Problem A
  Small and large inputs
 */
public class TicTacToeTomek {

    private final static char XPLAYER = 'X';
    private final static char OPLAYER = 'O';
    private final static char T = 'T';
    private final static char EMPTY = '.';

    private final static String X_WON = "X won";
    private final static String O_WON = "O won";
    private final static String DRAW = "Draw";
    private final static String NOT_COMPLETED = "Game has not completed";

    private void solve(Scanner sc, PrintWriter pw) {

        char[][] array = { sc.next().toCharArray(), sc.next().toCharArray(), sc.next().toCharArray(), sc.next().toCharArray() };

        int xXCount = 0;
        int yXCount = 0;
        int xOCount = 0;
        int yOCount = 0;

        int dForwardXCount = 0;
        int dBackwardXCount = 0;
        int dForwardOCount = 0;
        int dBackwardOCount = 0;
        boolean hasEmptyCells = false;
        boolean hasWinner = false;

        for(int x = 0; x < array.length; x++) { // 4

            for(int y = 0; y < array.length; y++) { // 4

                //x-X
                if(array[x][y] == XPLAYER || array[x][y] == T) {
                    xXCount++;
                }

                //y-X
                if(array[y][x] == XPLAYER || array[x][y] == T) {
                    yXCount++;
                }

                //x-O
                if(array[x][y] == OPLAYER || array[x][y] == T) {
                    xOCount++;
                }

                //y-O
                if(array[y][x] == OPLAYER || array[x][y] == T) {
                    yOCount++;
                }

                if(array[x][y] == EMPTY) {
                    hasEmptyCells = true;
                }
            }

            if(!hasWinner && (xXCount == array.length || yXCount == array.length)) {
                System.out.println(X_WON);
                pw.println(X_WON);
                hasWinner = true;
            }

            if(!hasWinner && (xOCount == array.length || yOCount == array.length)) {
                System.out.println(O_WON);
                pw.println(O_WON);
                hasWinner = true;
            }

            xXCount = yXCount = xOCount = yOCount = 0;

            if(array[x][x] == XPLAYER || array[x][x] == T) {
                dForwardXCount++;
            }

            if(array[(array.length - 1 - x)][x] == XPLAYER || array[(array.length - 1 - x)][x] == T) {
                dBackwardXCount++;
            }

            if(array[x][x] == OPLAYER || array[x][x] == T) {
                dForwardOCount++;
            }

            if(array[(array.length - 1 - x)][x] == OPLAYER || array[(array.length - 1 - x)][x] == T) {
                dBackwardOCount++;
            }

        }

        if(!hasWinner && (dForwardXCount == array.length || dBackwardXCount == array.length)) {
            System.out.println(X_WON);
            pw.println(X_WON);
            hasWinner = true;
        } else
        if(!hasWinner && (dForwardOCount == array.length || dBackwardOCount == array.length)) {
            System.out.println(O_WON);
            pw.println(O_WON);
            hasWinner = true;
        }

        if(!hasWinner) {
            if(hasEmptyCells) {
                System.out.println(NOT_COMPLETED);
                pw.println(NOT_COMPLETED);
            } else {
                System.out.println(DRAW);
                pw.println(DRAW);
            }
        }

    }

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(new FileReader("A-large.in.txt"));
        PrintWriter pw = new PrintWriter(new FileWriter("output.txt"));

        int caseCnt = sc.nextInt();
        sc.nextLine();
        for (int caseNum = 0; caseNum < caseCnt; caseNum++) {
            System.out.println("Processing test case " + (caseNum + 1));
            pw.print("Case #" + (caseNum + 1) + ": ");
            new TicTacToeTomek().solve(sc, pw);

        }

        pw.flush();
        pw.close();
        sc.close();
    }

}

3. Problem C: Fair and Square

Small Data Sets

On small data sets it is a piece of cake – a classical algorithmic task which took me about 10 mins to write the code:

import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 @Author: Ivan Voroshilin
 @Date: April 13 2013
 Problem C
 Small inputs
 */
public class FairNSquare {

    private boolean isPalindrome(long num) {
        long reversed = 0;
        long n = num;

        while (n > 0) {
            reversed = reversed * 10 + n % 10;
            n /= 10;
        }

        return num == reversed;
    }

    private void solve(Scanner sc, PrintWriter pw) {

        sc.nextLong();

        long a = sc.nextLong();
        long b = sc.nextLong();

        System.out.println(a);
        System.out.println(b);

        long number = a;
        long count = 0;

        while(number <= b) {
            if(isPalindrome(number)) {
                double d = Math.sqrt(number);
                if((d % 1) == 0 && isPalindrome((long)d)) {
                    count++;
                }
            }
            number++;
        }

        pw.println(count);
    }

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(new FileReader("C-small-attempt0.in.txt"));
        PrintWriter pw = new PrintWriter(new FileWriter("output.txt"));

        int caseCnt = sc.nextInt();
        sc.nextLine();
        for (int caseNum = 0; caseNum < caseCnt; caseNum++) {
            System.out.println("Processing test case " + (caseNum + 1));
            pw.print("Case #" + (caseNum + 1) + ": ");
            new FairNSquare().solve(sc, pw);
        }

        pw.flush();
        pw.close();
        sc.close();
    }

}

Large Data Sets

I tried to come up with a solution on large data sets, wrote the code which works using standard Bisection method based on a binary search but struggled to optimize time complexity of square root on BigInteger and palindrome checking on large ranges, I vaguely remember from Euler’s project there were some mathematical proofs regarding number 11 and palindromic numbers. There might be some very important facts which would allow to optimize for better performance however I decided not to waste time on it and moved to another problem.

Ok, here’s my solution which as been said didn’t pass time requirement.

import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Scanner;

/**
 @Author: Ivan Voroshilin
 @Date: April 13 2013
 Problem C
 Large inputs
 Comment: Poor time complexity
 */
public class FairNSquareLarge {

    private static boolean isPalindrome(BigInteger num) {
        BigInteger reversed = BigInteger.ZERO;
        BigInteger n = num;

        while (n.compareTo(BigInteger.ZERO) > 0) {
            reversed = reversed.multiply(BigInteger.valueOf(10)).add(n.mod(BigInteger.valueOf(10)));
            n = n.divide(BigInteger.valueOf(10));
        }

        return num.compareTo(reversed) == 0;
    }

    private static BigInteger sqrt(BigInteger n) {
        BigInteger a = BigInteger.ONE;
        BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
        while(b.compareTo(a) >= 0) {
            BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
            if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(BigInteger.ONE);
            else a = mid.add(BigInteger.ONE);
        }
        return a.subtract(BigInteger.ONE);
    }

    private void solve(Scanner sc, PrintWriter pw) {

        BigInteger a = sc.nextBigInteger();
        BigInteger b = sc.nextBigInteger();

        BigInteger number = a;
        long count = 0;

        while(number.compareTo(b) <= 0) {
            if(isPalindrome(number)) {

                BigInteger d = sqrt(number);

                if(d.multiply(d).compareTo(number) == 0 && isPalindrome(d)) {
                    count++;
                }
            }
            number = number.add(BigInteger.ONE);
            System.out.println(number.toString());
        }

        pw.println(count);
    }

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(new FileReader("C-large-1.in.txt"));
        PrintWriter pw = new PrintWriter(new FileWriter("output.txt"));

        int caseCnt = sc.nextInt();
        sc.nextLine();
        for (int caseNum = 0; caseNum < caseCnt; caseNum++) {
            System.out.println("Processing test case " + (caseNum + 1));
            pw.print("Case #" + (caseNum + 1) + ": ");
            new FairNSquareLarge().solve(sc, pw);
        }

        pw.flush();
        pw.close();
        sc.close();
    }

}

4. Problem D: Treasure

Small Data Sets

I first did a straightforward BFS with checking for deadlocks and then realized from conditions that there might be several paths to open all chests and the goal is to select minimal path from all sorted lexicographically. Sure, we could make a simple systematic backtracking using all permutations of paths which has a terrible complexity O(n!) and doesn’t meet time requirements even on small sets, e.g. N=20 chests where we have 20! distinct permutations (ouch!).

I had time pressure (1h until the end of round) and nixed that idea to proceed but this problem is really challenging. Sorry!