C++

Forum

 
DFS Backtracking algorithm

adam2016 (1529)
hi guys,

I've been trying to implement a backtracking algorithm that solves Sudoku I may plan on using for a project.

The code somewhat works, it does seem to solve the later sub grids it doesn't for whatever reason work in the first half.

I used Python to implement it

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
 
def valid(grid,x,y,number):


    for i in range(0,9):
        if grid[y][i] == number:
            return False

    for i in range(0,9):
        if grid[i][x] == number:
            return False

    xOffset = (x // 3) * 3
    yOffset = (y // 3) * 3

    for i in range(0,3):
        for j in range(0,3):
            if grid[yOffset+i][xOffset+j] == number:
                return False

    return True



def solve(game):
    
    grid = game.board # grid is a 2d list of the grid
    for y in range(0,9):
        for x in range(0,9):
            if grid[y][x] == None:
               for num in range(1,10):

                if valid(grud,x,y,num,9):
                       grid[y][x] = num
                       func = solve(game)
                       if not func:
                           grid[y][x] = None
            
                if num == 9 and not valid(grid,x,y,num,9):
                       return False
deleted account xyzzy (5768)
A topic about coding in a forum that is not about coding. *SMH*
jonnin (11437)
lounge is OK for other language stuff, I guess. There isnt really a great place for that.
I got nothing, my python is too weak to spot anything off
salem c (3700)
Maybe post the real code?

> if valid(grud,x,y,num,9):
You know, the one without typo's and an incorrect number of parameters.

> func = solve(game)
If you're calling yourself recursively, at least make sure you always return a meaningful answer.
Topic archived. No new replies allowed.