1 files changed, 103 insertions, 0 deletions
diff --git a/challenge-062/paulo-custodio/python/ch-2.py b/challenge-062/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..ca8a0f3c6a
--- /dev/null
+++ b/challenge-062/paulo-custodio/python/ch-2.py
@@ -0,0 +1,103 @@
+#!/usr/bin/env python3
+
+# Challenge 062
+#
+# TASK #2 > N Queens
+# Submitted by: Ryan Thompson
+#
+# A standard 8x8 chessboard has 64 squares. The Queen is a chesspiece that can
+# attack in 8 directions, as shown by the green shaded squares below:
+#
+#
+#
+# It is possible to place 8 queens on to a single chessboard such that none of
+# the queens can attack each other (i.e., their shaded squares would not
+# overlap). In fact, there are multiple ways to do so, and this is a favourite
+# undergraduate assignment in computer science.
+#
+# But here at PWC, we're going to take it into the next dimension!
+#
+# Your job is to write a script to work with a three dimensional chess cube,
+# MxMxM in size, and find a solution that maximizes the number of queens that
+# can be placed in that cube without attacking each other. Output one possible
+# solution.
+#
+# Example
+# A trivial 2x2x2 solution might look like this (1 = queen, 0 = empty):
+#
+# [
+#     [[1,0],     # Layer 1
+#      [0,0]],
+#
+#     [[0,0],     # Layer 2
+#      [0,0]],
+# ]
+
+from copy import deepcopy
+import re
+
+M = 2
+
+board = [[[0 for _ in range(M)] for _ in range(M)] for _ in range(M)]
+max_board = deepcopy(board)
+max_queens = 0
+
+def set_position(board, l, r, c):
+    if 0 <= l < M and 0 <= r < M and 0 <= c < M:
+        board[l][r][c] = 1
+
+def place_queens(queens, board):
+    global max_queens, max_board
+
+    # check for empty spaces
+    full = True
+    for l in range(M):
+        for r in range(M):
+            for c in range(M):
+                if board[l][r][c] == 0:
+                    full = False
+                    # empty, place queen
+                    copy_board = deepcopy(board)
+                    # fill attack positions
+                    for i in range(M):
+                        set_position(copy_board, i, r, c)
+                        set_position(copy_board, l, i, c)
+                        set_position(copy_board, l, r, i)
+
+                        set_position(copy_board, l, r-i, c-i)
+                        set_position(copy_board, l, r-i, c+i)
+                        set_position(copy_board, l, r+i, c-i)
+                        set_position(copy_board, l, r+i, c+i)
+
+                        set_position(copy_board, l-i, r, c-i)
+                        set_position(copy_board, l-i, r, c+i)
+                        set_position(copy_board, l+i, r, c-i)
+                        set_position(copy_board, l+i, r, c+i)
+
+                        set_position(copy_board, l-i, r-i, c)
+                        set_position(copy_board, l-i, r+i, c)
+                        set_position(copy_board, l+i, r-i, c)
+                        set_position(copy_board, l+i, r+i, c)
+
+                        set_position(copy_board, l-i, r-i, c-i)
+                        set_position(copy_board, l-i, r-i, c+i)
+                        set_position(copy_board, l-i, r+i, c-i)
+                        set_position(copy_board, l-i, r+i, c+i)
+
+                        set_position(copy_board, l+i, r-i, c-i)
+                        set_position(copy_board, l+i, r-i, c+i)
+                        set_position(copy_board, l+i, r+i, c-i)
+                        set_position(copy_board, l+i, r+i, c+i)
+                    # fill queen position
+                    copy_board[l][r][c] = 'Q'
+                    # recurse
+                    place_queens(queens + 1, copy_board)
+    if full:
+        if queens > max_queens:
+            max_queens = queens
+            max_board = deepcopy(board)
+
+place_queens(0, board)
+out = str(max_board)
+out, _ = re.subn("'", '"', out)
+print(out)