Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
AI examples. Not very fast/clever, no heuristic.
#!/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()
#!/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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment