Abit of Python-to-C help.

Hey guys,

Im writing a sudoku game following this article:
http://norvig.com/sudoku.html

Im getting close, but Im having a problem with the "search" function.
Its:

Code:

---

def search(values):
    "Using depth-first search and propagation, try all possible values."
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in squares):
        return values ## Solved!
    ## Chose the unfilled square s with the fewest possibilities
    _,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
    return some(search(assign(values.copy(), s, d))
                for d in values[s])

---

Im trying to implement this in C but I dont get it :/ I see there is a recursive thing and the 2 ifs in the beginning check if the board is already sorted. But the last 3 lines. What do they do?

(I know its not the best place to ask this :/ )

Quote:

---

Originally Posted by +Azazel+

Hey guys,

Im writing a sudoku game following this article:
http://norvig.com/sudoku.html

Im getting close, but Im having a problem with the "search" function.
Its:

Code:

---

def search(values):
    "Using depth-first search and propagation, try all possible values."
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in squares):
        return values ## Solved!
    ## Chose the unfilled square s with the fewest possibilities
    _,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
    return some(search(assign(values.copy(), s, d))
                for d in values[s])

---

Im trying to implement this in C but I dont get it :/ I see there is a recursive thing and the 2 ifs in the beginning check if the board is already sorted. But the last 3 lines. What do they do?

(I know its not the best place to ask this :/ )

---

The last few lines try to choose the next cell to take a guess at it's value. The cell with the lowest number of candidate values, is chosen, and one of the candidate values (usually in the order of lowest to highest digit), is chosen for the next guess.

My solver, also in C, uses a small array of structs which the cells remaining unsolved are put into, along with their row and col, and the number of candidate values it has remaining after the logic portion is done with it.

Then there's an index array that is used to sort the small array of structs, so they don't move from their original position.

Now I go through the remaining cells, just by accessing the small array of structs, through it's index. The code looks quite like stew, but some of that is because I did the DFS iteratively, rather than recursively.

If you'll post up your C code search function, I'll be able to help you more.

For more Sudoku programming help, you may want to also check out the Sudoku Programmers Forum.