AI examples. Not very fast/clever, no heuristic.

eight_queens_solver.py

#!/usr/bin/env python


class EightQueens:

    def __init__(self):
        self.array = 64 * [-1]

    def get(self, x, y):
        return self.array[x + y * 8]

    def __str__(self):
        s = ""
        for y in range(8):
            for x in range(8):
                s += " "
                val = self.get(x, y)
                if val == -1:
                    s += "."
                else:
                    s += str(val)
            s += "\n"
        return s

    def valid(self):
        queenPositions = [(i%8, i/8) for i in range(64) if self.array[i] == 1]
        for x1, y1 in queenPositions:
            for x2, y2 in queenPositions:
                if x1 == x2 and y1 == y2:
                    continue
                if x1 == x2 or y1 == y2:
                    return False
                if (x1 - y1) == (x2 - y2):
                    return False
                if (x1 - y1) == - (x2 - y2):
                    return False
        return True

    def complete(self):
        return sum([i > 0 for i in self.array]) >= 8

    def solve(self):
        position = 0
        while True:
            if position == 64:
                if self.complete():
                    print self
                position -= 1
            if self.array[position] >= 1:
                self.array[position] = -1
                position -= 1
                continue
            self.array[position] += 1
            if self.valid():
                position += 1


eq = EightQueens()
print eq
eq.solve()

sudoku_solver.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
Řešení Sudoku pomocí postupů AI - prohledávání stavového prostoru do hloubky.
"""


class Sudoku:
    """
    Třída pro objekt reprezentující hrací pole Sudoku a také
    reprezentující stav během řešení.
    """

    def __init__(self):
        self.array  = 9 * 9 * [0]


    def get(self, x, y):
        return self.array[x + y * 9]


    def set(self, x, y, val):
        self.array[x + y * 9] = val


    def __str__(self):
        s = ""
        for y in range(9):
            for x in range(9):
                s += " " + str(self.get(x, y) or ".")
            s += "\n"
        return s


    def valid(self):
        return self._valid_rows() \
            and self._valid_columns() \
            and self._valid_blocks()


    def _valid_rows(self):
        for y in range(9):
            numbers = set()
            for x in range(9):
                number = self.get(x, y)
                if number in numbers and number is not 0:
                    return False
                numbers.add(number)
        return True


    def _valid_columns(self):
        for x in range(9):
            numbers = set()
            for y in range(9):
                number = self.get(x, y)
                if number in numbers and number is not 0:
                    return False
                numbers.add(number)
        return True


    def _valid_blocks(self):
        for bx in range(3):
            for by in range(3):
                numbers = set()
                for x in range(3):
                    for y in range(3):
                        number = self.get(bx*3 + x, by*3 + y)
                        if number in numbers and number is not 0:
                            return False
                        numbers.add(number)
        return True


    def _go_right(self):
        self.pos += 1
        while self.pos in self.staticPositions:
            self.pos += 1


    def _go_left(self):
        self.pos -= 1
        while self.pos in self.staticPositions:
            self.pos -= 1


    def solve(self):
        self.solve_begin()
        return self.solve_next()


    def solve_begin(self):
        if not self.valid():
            raise Exception("Sudoku neni validni.")
        self.staticPositions = set([n for n in range(81) if self.array[n]])
        self.pos = -1
        self._go_right()


    def solve_next(self):
        if self.pos == 81:
            self._go_left()

        while self.pos < 81:

            if self.array[self.pos] == 9:
                self.array[self.pos] = 0
                self._go_left()
                if self.pos < 0:
                    return False
                continue

            self.array[self.pos] += 1

            if self.valid():
                self._go_right()
                continue

        return True


def main():
    sudoku = Sudoku()

    """
    for i in range(9):
        sudoku.set(i, i, i + 1)
    sudoku.set(1, 4, 9)
    sudoku.set(1, 5, 8)
    """
    sudoku.set(5, 0, 8)
    sudoku.set(0, 1, 2)
    sudoku.set(4, 1, 1)
    sudoku.set(5, 1, 4)
    sudoku.set(8, 1, 7)
    sudoku.set(1, 2, 4)
    sudoku.set(2, 2, 6)
    sudoku.set(3, 3, 7)
    sudoku.set(2, 4, 9)
    sudoku.set(4, 4, 3)
    sudoku.set(6, 4, 1)
    sudoku.set(7, 4, 2)
    sudoku.set(1, 5, 3)
    sudoku.set(5, 5, 6)
    sudoku.set(7, 5, 8)
    sudoku.set(0, 6, 8)
    sudoku.set(1, 6, 2)
    sudoku.set(2, 6, 1)
    sudoku.set(8, 6, 4)
    sudoku.set(3, 7, 4)
    sudoku.set(5, 7, 7)
    sudoku.set(6, 7, 9)
    sudoku.set(6, 8, 6)

    print sudoku
    sudoku.solve_begin()
    while sudoku.solve_next():
        print sudoku


if __name__ == "__main__":
    main()