Skip to content

Solution for placing 12 amaze chess pieces in 12x12 chessboard using backtracking in python.

License

Notifications You must be signed in to change notification settings

HareeshwarKarthikeyan/Amaze-Problem-n-Amazes-in-nxn-chessboard-

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

17 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

The Amaze Chess Piece Problem

The Amaze Chess Piece Problem requires the player to place n number of amaze chess pieces in a nxn chessboard so that no two amazes attack each other.

Just in case if you ain't familiar with the terms of chess, let's just have a quick run through the terms that we wil be using in this scenario.

Chessboard

A chessboard is simply a square board consisting of nxn smaller evenly sized squares each of which can accomodate a chess piece. Consider a sample 8x8 chessboard as shown below.

The Queen

The queen chess piece has the power to move any number of steps either forward or backward in the vertical, horizontal and diagonal directions. The queen can the power to attack any rival chess piece that lies in its path.

Image Credits : @shivanibaskar

The Knight

The knight chess piece has the power to move in a 'L' shape with two steps in either of the four directions and then take one step to the left or right. The knight cannot make any diagonal steps. The knight can also, attack any rival chess piece that lies in its path.

Image Credits : @shivanibaskar

The Amaze

An 'Amaze' is a chess piece that has the combined powers of both a queen and a knight in the game of chess.

Image Credits : @shivanibaskar

Placing Amazes in a 12x12 Chessboard

Let us consider n to be 12 and hence the case of placing amazes in a 12x12 chessboard.

  • Since there are only 12 rows in a 12x12 chessboard and only one amaze can be placed in a row, a total of only 12 amazes can be placed in the 12x12 board without one attacking the other.
  • For the 12 amazes, the i'th amaze will be placed in the i'th row. We just have to find out the column number (stored as its position) for placing the corresponding amaze.
  • Backtracking approach is used in the algorithm to solve this problem.
    • We start by placing one amaze and then call the algorithm again recursively to place the next amaze piece.
    • Backtracking : In case an amaze cannot be placed anywhere amongst the 12 columns, we return back to the previous function call and change the position (column) of the previous amaze piece.

Algorithms

nAmazes

  • The 'nAmazes' function is used for the backtracking solution logic.

place

  • The 'place' function is used for finding if the amaze piece can be placed at a certain square in the chessboard.

Tracing the Recursions

Image Credits : @shivanibaskar https://github.com/shivanibaskar

Can you guess how many such possible solutions are there?

A whopping 156 different solutions!

Output

  • The corresponding python code can be found in the amaze.py file.
  • The entire output printed onto the terminal console can be found in the Outputfile.txt file.
  • The solution position combinations alone can be found in the Solutions.txt_ file.

Complexity Analysis

  • Space Complexity : O(n)

  • Time Complexity : O(n!)

    By backward substitution method...

That's all folks!

Gracias!

Releases

No releases published

Packages

No packages published

Languages