<filename>project1/minesweeper/minesweeper.py
import itertools
import random


class Minesweeper():
    """
    Minesweeper game representation
    """

    def __init__(self, height=8, width=8, mines=8):

        # Set initial width, height, and number of mines
        self.height = height
        self.width = width
        self.mines = set()

        # Initialize an empty field with no mines
        self.board = []
        for i in range(self.height):
            row = []
            for j in range(self.width):
                row.append(False)
            self.board.append(row)

        # Add mines randomly
        while len(self.mines) != mines:
            i = random.randrange(height)
            j = random.randrange(width)
            if not self.board[i][j]:
                self.mines.add((i, j))
                self.board[i][j] = True

        # At first, player has found no mines
        self.mines_found = set()

    def print(self):
        """
        Prints a text-based representation
        of where mines are located.
        """
        for i in range(self.height):
            print("--" * self.width + "-")
            for j in range(self.width):
                if self.board[i][j]:
                    print("|X", end="")
                else:
                    print("| ", end="")
            print("|")
        print("--" * self.width + "-")

    def is_mine(self, cell):
        i, j = cell
        return self.board[i][j]

    def nearby_mines(self, cell):
        """
        Returns the number of mines that are
        within one row and column of a given cell,
        not including the cell itself.
        """

        # Keep count of nearby mines
        count = 0

        # Loop over all cells within one row and column
        for i in range(cell[0] - 1, cell[0] + 2):
            for j in range(cell[1] - 1, cell[1] + 2):

                # Ignore the cell itself
                if (i, j) == cell:
                    continue

                # Update count if cell in bounds and is mine
                if 0 <= i < self.height and 0 <= j < self.width:
                    if self.board[i][j]:
                        count += 1

        return count

    def won(self):
        """
        Checks if all mines have been flagged.
        """
        return self.mines_found == self.mines


class Sentence():
    """
    Logical statement about a Minesweeper game
    A sentence consists of a set of board cells,
    and a count of the number of those cells which are mines.
    """

    def __init__(self, cells, count):
        self.cells = set(cells)
        self.count = count

    def __eq__(self, other):
        return self.cells == other.cells and self.count == other.count

    def __str__(self):
        return f"{self.cells} = {self.count}"

    def known_mines(self):
        """
        Returns the set of all cells in self.cells known to be mines.
        """
        if self.count == len(self.cells):
            return self.cells
        else:
            return None

    def known_safes(self):
        """
        Returns the set of all cells in self.cells known to be safe.
        """
        if self.count == 0:
            return self.cells
        else:
            return None

    def mark_mine(self, cell):
        """
        Updates internal knowledge representation given the fact that
        a cell is known to be a mine.
        """
        if cell in self.cells:
            self.cells.remove(cell)
            self.count = self.count - 1

    def mark_safe(self, cell):
        """
        Updates internal knowledge representation given the fact that
        a cell is known to be safe.
        """
        if cell in self.cells:
            self.cells.remove(cell)



class MinesweeperAI():
    """
    Minesweeper game player
    """

    def __init__(self, height=8, width=8):

        # Set initial height and width
        self.height = height
        self.width = width

        # Keep track of which cells have been clicked on
        self.moves_made = set()

        # Keep track of cells known to be safe or mines
        self.mines = set()
        self.safes = set()

        # List of sentences about the game known to be true
        self.knowledge = []

    def mark_mine(self, cell):
        """
        Marks a cell as a mine, and updates all knowledge
        to mark that cell as a mine as well.
        """
        self.mines.add(cell)
        for sentence in self.knowledge:
            sentence.mark_mine(cell)

    def mark_safe(self, cell):
        """
        Marks a cell as safe, and updates all knowledge
        to mark that cell as safe as well.
        """
        self.safes.add(cell)
        for sentence in self.knowledge:
            sentence.mark_safe(cell)

    def add_knowledge(self, cell, count):
        """
        Called when the Minesweeper board tells us, for a given
        safe cell, how many neighboring cells have mines in them.

        This function should:
            1) mark the cell as a move that has been made
            2) mark the cell as safe
            3) add a new sentence to the AI's knowledge base
               based on the value of `cell` and `count`
            4) mark any additional cells as safe or as mines
               if it can be concluded based on the AI's knowledge base
            5) add any new sentences to the AI's knowledge base
               if they can be inferred from existing knowledge
        """
        self.moves_made.add(cell)
        self.mark_safe(cell)
        self.knowledge.append(Sentence(self.check_neighbours(cell), count))
        while True:
            new_safes = self.safes
            new_mines = self.mines
            for sentence in self.knowledge:
                if sentence.known_safes() is not None:
                    for sentence_cell in sentence.cells:
                        new_safes.add(sentence_cell)
                if sentence.known_mines() is not None:
                    for sentence_cell in sentence.cells:
                        new_mines.add(sentence_cell)
            for new_safe in new_safes:
                self.mark_safe(new_safe)
            for new_mine in new_mines:
                self.mark_mine(new_mine)
            self.knowledge = [x for x in self.knowledge if len(x.cells) != 0]
            new_knowledge = []
            for sentence in self.knowledge:
                for another_sentence in self.knowledge:
                    if sentence != another_sentence:
                        if another_sentence.cells.issubset(sentence.cells):
                            new_sentence = Sentence(
                                sentence.cells - another_sentence.cells,
                                sentence.count - another_sentence.count
                                )
                            new_knowledge.append(new_sentence)
            new_knowledge = [ x for x in new_knowledge if x not in self.knowledge]
            if not new_knowledge:
                break
            else:
                self.knowledge = self.knowledge + new_knowledge

    def make_safe_move(self):
        """
        Returns a safe cell to choose on the Minesweeper board.
        The move must be known to be safe, and not already a move
        that has been made.

        This function may use the knowledge in self.mines, self.safes
        and self.moves_made, but should not modify any of those values.
        """
        for move in self.safes:
            if move not in self.moves_made and move not in self.mines:
                return move

    def make_random_move(self):
        """
        Returns a move to make on the Minesweeper board.
        Should choose randomly among cells that:
            1) have not already been chosen, and
            2) are not known to be mines
        """
        for i in range(100):
            random_move = (random.randrange(0,self.height),random.randrange(0, self.width))
            if random_move not in self.moves_made and random_move not in self.mines:
                return random_move
        return None

    def check_neighbours(self, cell):
        return set([
                    (cell[0] + x, cell[1] + y) 
                    for x in (-1, 0, 1) for y in (-1, 0, 1) 
                    if (cell[0] + x >= 0 and cell[0] + x < self.height) and 
                        (cell[1] + y >= 0 and cell[1] + y < self.width) and 
                        (cell[0] + x, cell[1] + y) != cell
                ]
            )

<filename>project1/minesweeper/minesweeper.py
import itertools
import random


class Minesweeper():
    """
    Minesweeper game representation
    """

    def __init__(self, height=8, width=8, mines=8):

        # Set initial width, height, and number of mines
        self.height = height
        self.width = width
        self.mines = set()

        # Initialize an empty field with no mines
        self.board = []
        for i in range(self.height):
            row = []
            for j in range(self.width):
                row.append(False)
            self.board.append(row)

        # Add mines randomly
        while len(self.mines) != mines:
            i = random.randrange(height)
            j = random.randrange(width)
            if not self.board[i][j]:
                self.mines.add((i, j))
                self.board[i][j] = True

        # At first, player has found no mines
        self.mines_found = set()

    def print(self):
        """
        Prints a text-based representation
        of where mines are located.
        """
        for i in range(self.height):
            print("--" * self.width + "-")
            for j in range(self.width):
                if self.board[i][j]:
                    print("|X", end="")
                else:
                    print("| ", end="")
            print("|")
        print("--" * self.width + "-")

    def is_mine(self, cell):
        i, j = cell
        return self.board[i][j]

    def nearby_mines(self, cell):
        """
        Returns the number of mines that are
        within one row and column of a given cell,
        not including the cell itself.
        """

        # Keep count of nearby mines
        count = 0

        # Loop over all cells within one row and column
        for i in range(cell[0] - 1, cell[0] + 2):
            for j in range(cell[1] - 1, cell[1] + 2):

                # Ignore the cell itself
                if (i, j) == cell:
                    continue

                # Update count if cell in bounds and is mine
                if 0 <= i < self.height and 0 <= j < self.width:
                    if self.board[i][j]:
                        count += 1

        return count

    def won(self):
        """
        Checks if all mines have been flagged.
        """
        return self.mines_found == self.mines


class Sentence():
    """
    Logical statement about a Minesweeper game
    A sentence consists of a set of board cells,
    and a count of the number of those cells which are mines.
    """

    def __init__(self, cells, count):
        self.cells = set(cells)
        self.count = count

    def __eq__(self, other):
        return self.cells == other.cells and self.count == other.count

    def __str__(self):
        return f"{self.cells} = {self.count}"

    def known_mines(self):
        """
        Returns the set of all cells in self.cells known to be mines.
        """
        if self.count == len(self.cells):
            return self.cells
        else:
            return None

    def known_safes(self):
        """
        Returns the set of all cells in self.cells known to be safe.
        """
        if self.count == 0:
            return self.cells
        else:
            return None

    def mark_mine(self, cell):
        """
        Updates internal knowledge representation given the fact that
        a cell is known to be a mine.
        """
        if cell in self.cells:
            self.cells.remove(cell)
            self.count = self.count - 1

    def mark_safe(self, cell):
        """
        Updates internal knowledge representation given the fact that
        a cell is known to be safe.
        """
        if cell in self.cells:
            self.cells.remove(cell)



class MinesweeperAI():
    """
    Minesweeper game player
    """

    def __init__(self, height=8, width=8):

        # Set initial height and width
        self.height = height
        self.width = width

        # Keep track of which cells have been clicked on
        self.moves_made = set()

        # Keep track of cells known to be safe or mines
        self.mines = set()
        self.safes = set()

        # List of sentences about the game known to be true
        self.knowledge = []

    def mark_mine(self, cell):
        """
        Marks a cell as a mine, and updates all knowledge
        to mark that cell as a mine as well.
        """
        self.mines.add(cell)
        for sentence in self.knowledge:
            sentence.mark_mine(cell)

    def mark_safe(self, cell):
        """
        Marks a cell as safe, and updates all knowledge
        to mark that cell as safe as well.
        """
        self.safes.add(cell)
        for sentence in self.knowledge:
            sentence.mark_safe(cell)

    def add_knowledge(self, cell, count):
        """
        Called when the Minesweeper board tells us, for a given
        safe cell, how many neighboring cells have mines in them.

        This function should:
            1) mark the cell as a move that has been made
            2) mark the cell as safe
            3) add a new sentence to the AI's knowledge base
               based on the value of `cell` and `count`
            4) mark any additional cells as safe or as mines
               if it can be concluded based on the AI's knowledge base
            5) add any new sentences to the AI's knowledge base
               if they can be inferred from existing knowledge
        """
        self.moves_made.add(cell)
        self.mark_safe(cell)
        self.knowledge.append(Sentence(self.check_neighbours(cell), count))
        while True:
            new_safes = self.safes
            new_mines = self.mines
            for sentence in self.knowledge:
                if sentence.known_safes() is not None:
                    for sentence_cell in sentence.cells:
                        new_safes.add(sentence_cell)
                if sentence.known_mines() is not None:
                    for sentence_cell in sentence.cells:
                        new_mines.add(sentence_cell)
            for new_safe in new_safes:
                self.mark_safe(new_safe)
            for new_mine in new_mines:
                self.mark_mine(new_mine)
            self.knowledge = [x for x in self.knowledge if len(x.cells) != 0]
            new_knowledge = []
            for sentence in self.knowledge:
                for another_sentence in self.knowledge:
                    if sentence != another_sentence:
                        if another_sentence.cells.issubset(sentence.cells):
                            new_sentence = Sentence(
                                sentence.cells - another_sentence.cells,
                                sentence.count - another_sentence.count
                                )
                            new_knowledge.append(new_sentence)
            new_knowledge = [ x for x in new_knowledge if x not in self.knowledge]
            if not new_knowledge:
                break
            else:
                self.knowledge = self.knowledge + new_knowledge

    def make_safe_move(self):
        """
        Returns a safe cell to choose on the Minesweeper board.
        The move must be known to be safe, and not already a move
        that has been made.

        This function may use the knowledge in self.mines, self.safes
        and self.moves_made, but should not modify any of those values.
        """
        for move in self.safes:
            if move not in self.moves_made and move not in self.mines:
                return move

    def make_random_move(self):
        """
        Returns a move to make on the Minesweeper board.
        Should choose randomly among cells that:
            1) have not already been chosen, and
            2) are not known to be mines
        """
        for i in range(100):
            random_move = (random.randrange(0,self.height),random.randrange(0, self.width))
            if random_move not in self.moves_made and random_move not in self.mines:
                return random_move
        return None

    def check_neighbours(self, cell):
        return set([
                    (cell[0] + x, cell[1] + y) 
                    for x in (-1, 0, 1) for y in (-1, 0, 1) 
                    if (cell[0] + x >= 0 and cell[0] + x < self.height) and 
                        (cell[1] + y >= 0 and cell[1] + y < self.width) and 
                        (cell[0] + x, cell[1] + y) != cell
                ]
            )

Minesweeper game representation # Set initial width, height, and number of mines # Initialize an empty field with no mines # Add mines randomly # At first, player has found no mines Prints a text-based representation
         of where mines are located. Returns the number of mines that are
         within one row and column of a given cell,
         not including the cell itself. # Keep count of nearby mines # Loop over all cells within one row and column # Ignore the cell itself # Update count if cell in bounds and is mine Checks if all mines have been flagged. Logical statement about a Minesweeper game
     A sentence consists of a set of board cells,
     and a count of the number of those cells which are mines. Returns the set of all cells in self.cells known to be mines. Returns the set of all cells in self.cells known to be safe. Updates internal knowledge representation given the fact that
         a cell is known to be a mine. Updates internal knowledge representation given the fact that
         a cell is known to be safe. Minesweeper game player # Set initial height and width # Keep track of which cells have been clicked on # Keep track of cells known to be safe or mines # List of sentences about the game known to be true Marks a cell as a mine, and updates all knowledge
         to mark that cell as a mine as well. Marks a cell as safe, and updates all knowledge
         to mark that cell as safe as well. Called when the Minesweeper board tells us, for a given
         safe cell, how many neighboring cells have mines in them.
 
         This function should:
             1) mark the cell as a move that has been made
             2) mark the cell as safe
             3) add a new sentence to the AI's knowledge base
                based on the value of `cell` and `count`
             4) mark any additional cells as safe or as mines
                if it can be concluded based on the AI's knowledge base
             5) add any new sentences to the AI's knowledge base
                if they can be inferred from existing knowledge Returns a safe cell to choose on the Minesweeper board.
         The move must be known to be safe, and not already a move
         that has been made.
 
         This function may use the knowledge in self.mines, self.safes
         and self.moves_made, but should not modify any of those values. Returns a move to make on the Minesweeper board.
         Should choose randomly among cells that:
             1) have not already been chosen, and
             2) are not known to be mines