CMU 15-112: Fundamentals of Programming and Computer Science
Week 5-6 Practice (Due never)
- These problems will help you prepare for hw5/hw6 and for quiz5/quiz6.
- No starter files this week.
- Do not use recursion this week.
- Do not hardcode the test cases in your solutions.
- Some Worked Examples Using Lists:
-
Word Search
-
Word Search Redux
-
Connect4
-
Othello
- makeMagicSquare(n)
Write the function makeMagicSquare(n) that takes a positive odd integer n and returns an nxn magic square by following De La Loubere's Method as described
here.
If n is not a positive odd integer, return None.
- isLatinSquare(a)
Write the function isLatinSquare(a) that takes a 2d list and returns
True if it is a
Latin square
and False otherwise.
- isKnightsTour(a)
Background: A "knight's
tour in chess is a sequence of legal knight moves such that the knight
visits every square exactly once. We can represent a (supposed)
knight's tour as an NxN list of the integers from 1 to N2 listing
the positions in order that the knight occupied on the tour. If it is
a legal knight's tour, then all the numbers from 1 to N2 will be
included and each move from k to (k+1) will be a legal knight's move.
With this in mind, write the function isKnightsTour(board) that takes such a
2d list of integers and returns True if it represents a legal knight's tour
and False otherwise.
- nQueensChecker(a)
Background: The "N Queens" problem asks if we can place N queens on an NxN chessboard such that no two queens are attacking each other. For most values of N, there are many ways to solve this problem. Here, you will write the function nQueensChecker(board) that takes a 2d list of booleans where True indicates a queen is present and False indicates a blank cell, and returns True if this NxN board contains N queens all of which do not attack any others, and False otherwise.
- makeOthelloMove(board, row, col, player)
Background: read about the game of
Othello
(also known as Reversi). Maybe even play it briefly (say,
here). We can represent an Othello board as an NxN list of values
-- 'w' for white, 'b' for black, and the empty string for empty (of course).
If we number the rows from the top and columns from the left, write the
function makeOthelloMove(board, row, col, player) that takes such a board, a
row, a col, and a player ('w' or 'b'), and, if it is legal for the given
player to place a piece at the given position, the function destructively
modifies the board to reflect this move (flipping pieces as needed), and it
returns the number of pieces flipped. If the move is not legal,
the function does not modify the board and returns 0.
- Games, games, games!
Console-based 2d board games (human-human mainly, but maybe a simple human-computer game) such as:
- Checkers
- Chess
-
Isola
-
Fox and Hounds
- Backgammon
- Stratego
- Or many, many others...