# File: verifyNQueens.py
# Purpose: A program to check if a given configuration of pieces satisfies
#          N-Rooks or N-Queens.
# Author: TODO
#
# Collaboration statement: TODO

import random

##############################################################
## Checking for N-Rooks and N-Queens                        ##
##############################################################

def doesSatisfyNRooks(boardState):
    """
    Checks whether the given state of the board satisfies N-Rooks.
    If no two pieces are in the same row or column, returns True.
    Otherwise, returns False.

    boardState: a nested lists containing 0s (no piece) and 1s (a piece)
    
    returns: True or False
    """
    # TODO: Part 2
    return False # replace with your code

def doesSatisfyNQueens(boardState):
    """
    Checks whether the given state of the board satisfies N-Queens.
    If no two pieces are in the same row, column, or diagonal,
    returns True.  Otherwise, returns False.

    boardState: a nested lists containing 0s (no piece) and 1s (a piece)
    
    returns: True or False
    """
    # TODO: Part 3
    return False # replace with your code

##############################################################
## Helper functions for testing                             ##
##############################################################

def buildEmptyBoard(n):
    """
    Builds and returns a board state representing an empty
    nxn game board.

    returns: an empty board as a list of lists (all zeros)
    """
    boardState = []
    for i in range(n):
        row = []
        for j in range(n):
            row.append(0)
        boardState.append(row)
    return boardState

def addPieceToBoard(boardState, row, column):
    """
    Modifies the board state to place a piece in a given
    row and column.

    boardState: a nested lists containing 0s (no piece) or 1s (a piece)
    row: integer from 0 to n-1
    column: integer from 0 to n-1
    (n is the length of boardState, which is assumed to be square)
    """
    boardState[row][column] = 1

def createBoardWithPieces(n, rows, columns):
    """
    Creates a board state with pieces placed on the positions
    given by corresponding-indexed pairs in rows and columns.

    n: integer indicating side of the square board
    rows: list of integers from 0 to n-1
    columns: list of integers from 0 to n-1 (same len as rows)

    returns: board state (a nested lists containing 0s (no piece) or 1s (a piece))
    """
    boardState = buildEmptyBoard(n)
    for i in range(len(rows)):
        addPieceToBoard(boardState, rows[i], columns[i])
    return boardState

##############################################################
## Testing code                                             ##
##############################################################

def testNRooksPositive(numTests, n):
    """
    Builds numTests random lists that satisfy N-Rooks and verifies
    that doesSatisfyNRooks() returns True.
    """
    numPassed = 0
    for i in range(numTests):
        # Build a board state that satisfies N-Rooks
        cols = list(range(n))
        random.shuffle(cols)

        boardState = createBoardWithPieces(n, list(range(n)), cols)

        # Test the function
        if doesSatisfyNRooks(boardState):
            numPassed += 1

    print("Passed {0} out of {1} tests (n={2}).".format(numPassed, numTests, n))

def testNRooksNegative(numTests, n):
    """
    Builds numTests completely random lists that likely do not satisfy
    # N-Rooks and verifies that doesSatisfyNRooks() returns False, usually.
    """
    numPassed = 0
    for i in range(numTests):
        # Build a completely random board
        indices = list(range(n))

        rows = []
        cols = []
        for j in range(n):
            rows.append(random.choice(indices))
            cols.append(random.choice(indices))

        boardState = createBoardWithPieces(n, rows, cols)

        # Test the function
        if not doesSatisfyNRooks(boardState):
            numPassed += 1

    print("Passed {0} out of {1} tests (n={2}).".format(numPassed, numTests, n))

def testNQueensPositive(n):
    """
    Uses known solutions to N-Queens to test N-Queens.
    """
    solutions = {0:  [],
                 1:  [[1]],
                 2:  [[1,0], [0,1]],
                 3:  [[0, 0, 1], [1, 0, 0], [0, 1, 0]],
                 4:  [[0, 0, 1, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0]],
                 5:  [[0, 0, 1, 0, 0], [0, 0, 0, 0, 1], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [1, 0, 0, 0, 0]],
                 6:  [[1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0]],
                 7:  [[0, 0, 0, 1, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0, 0]],
                 8:  [[0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0]],
                 9:  [[0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0]],
                 10: [[0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]]}

    # If the value of n doesn't have a known-valid board state, don't do this test
    if n not in solutions:
        print("Skipping test for n={0}, no solution stored.".format(n))
        return

    # Choose a known-valid board state
    boardState = solutions[n]

    if doesSatisfyNQueens(boardState):
        print("Passed 1 out of 1 test (n={0}).".format(n))
    else:
        print("Passed 0 out of 1 test (n={0}).".format(n))
    
def testNQueensNegative(numTests, n):
    """
    Builds numTests random lists that satisfy N-Rooks but likely
    do not satisfy N-Queens and verifies that doesSatisfyNQueens()
    returns False, usually.
    """
    numPassed = 0
    for i in range(numTests):
        # Build a random-ish board that satisfies N-Rooks but probably
        # not N-Queens
        rows = list(range(n))
        random.shuffle(rows)

        cols = list(range(n))
        random.shuffle(cols)

        boardState = createBoardWithPieces(n, rows, cols)

        # Test the function
        if not doesSatisfyNQueens(boardState):
            numPassed += 1

    print("Passed {0} out of {1} tests (n={2}).".format(numPassed, numTests, n))

def testNQueensSuperNegative(numTests, n):
    """
    Builds numTests random lists that likely do not satisfy N-Queens
    and verifies that doesSatisfyNQueens() returns False, usually.
    """
    numPassed = 0
    for i in range(numTests):
        # Build a completely random board
        indices = list(range(n))

        rows = []
        cols = []
        for j in range(n):
            rows.append(random.choice(indices))
            cols.append(random.choice(indices))

        boardState = createBoardWithPieces(n, rows, cols)

        # Test the function
        if not doesSatisfyNQueens(boardState):
            numPassed += 1

    print("Passed {0} out of {1} tests (n={2}).".format(numPassed, numTests, n))

if __name__ == "__main__":
    maxN = 10
    numTests = 100
    
    print("Performing positive N-Rooks tests.")
    for i in range(maxN+1):
        testNRooksPositive(numTests, i)

    print("\nPerforming negative N-Rooks tests.")
    print("(Note that not all will pass, but the number should go up as n increases.)")
    for i in range(maxN+1):
        testNRooksNegative(numTests, i)

    print("\nPerforming positive N-Queens tests.")
    for i in range(maxN+1):
        testNQueensPositive(i)

    print("\nPerforming negative N-Queens tests (assuming N-Rooks passes).")
    print("(Note that not all will pass, but the number should go up as n increases.)")
    for i in range(maxN+1):
        testNQueensNegative(numTests, i)

    print("\nPerforming negative N-Queens tests (likely fails N-Rooks).")
    print("(Note that not all will pass, but the number should go up as n increases.)")
    for i in range(maxN+1):
        testNQueensSuperNegative(numTests, i)