Skip to content
Snippets Groups Projects
Select Git revision
  • main default protected
1 result
Blame Permalink
  • Michael Mutote's avatar
    8caf06a5
    22202956 · 8caf06a5
    Michael Mutote authored 
    optimised successors function for sudoku to use the most complete row, column or sub-square
Added helper functions for selecting next position to solve for sudoku
Heuristics for Sudoku updated and tested for A*, works but slow, 30 seconds
    8caf06a5
    History
    22202956
    Michael Mutote authored 
    optimised successors function for sudoku to use the most complete row, column or sub-square
Added helper functions for selecting next position to solve for sudoku
Heuristics for Sudoku updated and tested for A*, works but slow, 30 seconds
Search_Algorithms.py 1.66 KiB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 






import queue
from collections import deque


def BreadthFirstSearch(state, successor, isgoal):
    """accepts start state, Please do not change this function"""
    toDo = queue.Queue()
    toDo.put([state])
    explored = {state}
    while not toDo.empty():
        path = toDo.get()
        current = path[-1]
        if isgoal(current):
            return path
        for next_state in successor(current):
            if next_state not in explored:
                explored.add(next_state)
                path2 = path + [next_state]
                toDo.put(path2)
    return "Error Path not found"


def DepthFirstSearch(state, successor, isgoal):
    """accepts start state, Please do not change this function"""
    toDo = deque()
    toDo.append([state])
    explored = {state}
    while toDo:
        path = toDo.pop()
        current = path[-1]
        if isgoal(current):
            return path
        for next_state in successor(current):
            if next_state not in explored:
                explored.add(next_state)
                path2 = path + [next_state]
                toDo.append(path2)
    return "Error Path not found"


def A_StarSearch(state, successor, isgoal, h):
    """accepts start state, Please do not change this function"""
    toDo = [[state]]
    explored = {state}
    while toDo:
        toDo.sort(key=h)
        path = toDo.pop(0)
        current = path[-1]
        if isgoal(current):
            return path
        for next_state in successor(current):
            if next_state not in explored:
                explored.add(next_state)
                path2 = path + [next_state]
                toDo.append(path2)
    return "Error Path not found"