Skip to content

Latest commit

 

History

History
91 lines (67 loc) · 3.09 KB

README.md

File metadata and controls

91 lines (67 loc) · 3.09 KB
Raw

Chess Project

The problem is to find all unique configurations of a set of normal chess pieces on a chess board with dimensions M×N where none of the pieces is in a position to take any of the others. Providing the number of results is useful, but not enough to complete the assignment. Assume the colour of the piece does not matter, and that there are no pawns among the pieces.

To build and run

You can start > sbt run or > sbt -mem 4096 run

You can test > sbt -mem 4096 test

Sample for usage

Please enter the board size M:
7
Please enter the board size N:
7
Please enter the pieces of type:
KKQQBBN

The play is starting with 7*7 and KKQQBBN

 Solution 1
 - - B - - - N
 Q - - - - - -
 - - - - - - -
 - K - - - - B
 - - - - - - -
 - - - - - Q -
 - - K - - - -

 Solution 2
 Q - - - - - -
 - - K - - - -
 - - - - - - -
 - - N - - - -
 - - - - - - Q
 - - - - - - -
 - B B - - K -

        .
        .
        .


Solution 3063828
 K - - - - - -
 - - - - - Q -
 - - - - - - -
 - - - - - - -
 N - - - K - -
 B - - - - - B
 - - - Q - - -

Total elapsed time: 99124 ms
Total solution: 3063828

About Solution Algorithm

First, the pieces are sorted by their priorities. Because I want to calculate which piece occupy more place. For example, when I put a Queen to (0, 0) location on a 3x3 board. 6 board item can't be reached by other pieces. ((1, 0, (2, 0), (1, 1), (2, 2), (0, 1), (0, 2)) If I put Knight to (0, 0) location on the 3*3 board. Only one board item can't be reached by other pieces. (1, 2)

So priority order is: Queen, Rook, Bishop, Knight, King

After sorting, I start to calculate all possible boards for the first piece.

The calculation starts with calculate method. calculate method takes 2 parameters and returns the solutions (Set of Board)

def calculate(board: Board, pieces: List[ChessPiece]): Set[Board] = {`...

This method includes a variable which is name is markedBoard and it's type is MarkedBoard. Marked board is a kind of board in which you can mark a board item is occupied by a chess piece.

Step 1 - calculate method is called with m*n empty board and something like List(Rook, King, King)

Step 2 - calculate method calls placeBoards method. It's parameters are Set of MarkedBoard and the piece Rook - placeBoards method is called for each piece

Step 3 - placeBoards method calls placeBoard method with a marked board and piece - placeBoard method is called for each marked board

Step 4 - placeBoard method gets the not marked and empty coordinates, and for each possible coordinate calls maybePlace method - maybePlace method is called for the marked board's each not marked and empty coordinates

Step 5 - maybePlace method puts the piece on the coordinate and using the piece's moving strategies calls validatePiecePlacement method - validatePiecePlacement method is called by the maybePlace method for each move strategy of the piece

Step 6 - validatePiecePlacement method takes a start coordinate, and a move strategy of the piece and marked board. Then it checks if there is a conflict or not. If the piece can make more than one movement, the method is called recursively