Checkers: Difference between revisions

From charlesreid1

No edit summary
No edit summary
Line 2: Line 2:


* Problem Motivation and Description
* Problem Motivation and Description
* Problem analysis and computational thinking
* Problem analysis: data structures and algorithms
* Solution approach/algorithm
* Solution approach/algorithm
* Implementation
* 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.


In the Checkers problem, you are given a checkerboard with several black and white pieces arranged on the board. It is your task to answer the question of whether any one of the black pieces on the board can jump all of the white pieces on the board with a single sequence of legal moves.


To solve the checkers problem, it is important to focus on the data structure. It is possible (and interesting, and useful) to tie in the checkerboard with graph theory (spec. the Bridge of Koningsberg problem), it is also overly-complicated to construct a Graph object and decide how to populate it using logic that checks different squares, etc.


Keep it simple. Use a 2D char array.




Revision as of 23:59, 18 June 2017

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.

Retrieved from "https://charlesreid1.com/w/index.php?title=Checkers&oldid=18442"