Checkers

Checkers

• Problem Motivation and Description
• Problem analysis: data structures and algorithms
• Solution approach/algorithm
• Implementation

Problem Motivation and Description

The Checkers Problem: You are presented with a checkerboard that consists of black and white squares. The boards follow the normal rules of checkers, i.e., pieces appear only on the black or white squares. There are several white and black pieces arranged on the board. It is your task to answer the following question: can any one single black piece be used to jump and capture all of the white pieces in a single move? This assumes that each of the black pieces are black "kings" and can jump in either direction.

Data Structures and Algorithms

To solve the checkers problem, it is important to focus on a simple data structure. While graph theory can be utilized to analyze the problem and find solutions, it is best not to stray too far from a simple 2D array. Char array is simplest.

It's also important not to worry too much:

• Don't worry about the computational cost of loops, or loops within loops, or nested nested nested nested loops. These boards are all relatively small.
• Don't worry about checking if the checkerboard positions are valid. While it might be useful to know before going in, the problem isn't asking you to validate it, so don't sweat that detail. If we need to implement any checks on black pieces only, do it when we tally up all the black pieces. If we need to implement any checks on 2white pieces only, do it when we tally up the white pieces.

The algorithm:

• Load the checkerboard into a char array
• Loop over each piece
• If we find a black piece,
  • Check if this board/piece is a viable solution (does the board meet criteria)
  • If this is a viable solution, take a tour of possible solution squares, jumping white pieces each time
  • If all white pieces jumped, then found black piece that yields solution, add to list of solution pieces

Code Structure

Here it is best not to over-complicate things. We want to keep the data structure simple, we want to keep the algorithm simple, so let's keep the overall program simple.

W = white, not west.

Four part code structure:

1. Load chessboard

2. For each square, check if square is viable and if square is solution

3. Definition of check if square solution function

4. Definition of check if square viable function

load chessboard into char[] array
for each square on chessboard:
    if square has black piece:
        checkSquare(square)


def checkSquare(square):
    if(viable(square)):
        Wsjumped
        for each neighbor:
            next square
            next next square
            if next square is W and next next square is _ empty and we haven't visited this W,
                visited this W
                Wsjumped += 1 + checkSquare(next next neighbor)
        return( Wsjumped==Wcount )


def viable(square):
    remove piece
        for each row, for each column:
            if row/col is off by 2 with the black piece
                for each of the 4 neighbors:
                    next square
                    next next square
                    if next square is W
                        if next next square not empty:
                            fail fast
                        increment neighbors (W neighbors)
                        if black piece original,
                            isodd = true

    if more than 2 odd neighbors, fail fast
    if 2 odd neighbors and isodd not true, fail fast