Checkers - Revision history

Admin: /* Data Structures and Algorithms */

2017-06-19T00:24:13Z

Data Structures and Algorithms

← Older revision		Revision as of 00:24, 19 June 2017
Line 14:		Line 14:
	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.		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 about ~~for~~ loops ~~that involve multiple~~ nested ~~for~~ loops ~~- the~~ boards are all relatively small so the ~~nested loops are not a big deal~~.		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:		The algorithm:
	* ~~Look for black pieces~~		* Load the checkerboard into a char array
	* ~~For~~ each black piece ~~that is found~~,		* Loop over each piece
	** Check if this piece is a viable solution (~~based on counts of open squares~~)		* If we find a black piece,
	** If this is a viable solution, take a tour of possible squares, ~~trying to jump~~ white pieces each time		** Check if this board/piece is a viable solution (does the board meet criteria)
	** If all white ~~piece~~ pieces ~~are~~ jumped, then we found a black piece that ~~can yield us a~~ solution		** 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===		===Code Structure===

Admin: /* Code Structure */

2017-06-19T00:18:13Z

Code Structure

← Older revision		Revision as of 00:18, 19 June 2017
Line 30:		Line 30:

	Four part code structure:		Four part code structure:

	1. Load chessboard		1. Load chessboard

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

	3. Definition of check if square solution function		3. Definition of check if square solution function

	4. Definition of check if square viable function		4. Definition of check if square viable function

Admin: /* Code Structure */

2017-06-19T00:16:53Z

Code Structure

← Older revision		Revision as of 00:16, 19 June 2017
Line 28:		Line 28:

	W = white, not west.		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

	<pre>		<pre>

Admin: /* Data Structures and Algorithms */

2017-06-19T00:14:12Z

Data Structures and Algorithms

← Older revision		Revision as of 00:14, 19 June 2017
Line 14:		Line 14:
	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.		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 about for loops that involve multiple nested for loops - the boards are all relatively small so the nested loops are not a big deal.

			The algorithm:
			* Look for black pieces
			* For each black piece that is found,
			** Check if this piece is a viable solution (based on counts of open squares)
			** If this is a viable solution, take a tour of possible squares, trying to jump white pieces each time
			** If all white piece pieces are jumped, then we found a black piece that can yield us a solution

			===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.

			<pre>
			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
			</pre>

Admin at 23:59, 18 June 2017

2017-06-18T23:59:39Z

← Older revision		Revision as of 23:59, 18 June 2017
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.~~

Admin at 22:22, 18 June 2017

2017-06-18T22:22:53Z

← Older revision		Revision as of 22:22, 18 June 2017
Line 1:		Line 1:
	==Checkers==		==Checkers==

			* Problem Motivation and Description
			* Problem analysis and computational thinking
			* Solution approach/algorithm
			* Implementation



	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.		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.

Admin: Created page with "==Checkers== 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 whethe..."

2017-06-18T08:25:43Z

Created page with "==Checkers== 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 whethe..."

New page

==Checkers==

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.

[[Category:Arrays]]
[[Category:Java]]
[[Category:Competitive Programming]]
[[Category:Final Project]]