algern0n the most obvious speedup to the code would be to call candidate() once per call to solve_cell() instead of 9.
algern0n that is turning it in a candidate*s* ;)
algern0n just fill in a candidates[9] array and loop over it
algern0n int candidates(sudoku_t *stuff, int cur_row, int cur_col)
algern0n crap.
algern0n int candidates(sudoku_t *stuff, char *candidates[9], int cur_row, int cur_col)
algern0n return value: the array size
superdump mmm
superdump sounds food
superdump good*
algern0n lol
superdump :)
algern0n you probably won't get the same speedup as finding the least candidates cell, but still...
superdump i'd like to do it anyway
superdump as an exercise
superdump and the other logical methods too
algern0n I don't think most logical stuff brings any speedup on a 3x3 grid
superdump i'd still like to do it :)
algern0n oh. and since you're at it, note that the "least candidates find_unsolved()" already computes the candidates for each cell ;)
superdump yes
superdump you have to do that at the beginning
algern0n so you can actually make a cell_t with an array of candidates and a size
superdump and update it as you go along
algern0n and a grid_t as cell_t[9][9] plus other stuff
algern0n that's where C++'s classes come handy :)
superdump i dare say but it's not too difficult with structs from what i see
algern0n not if you want to support grids of any size :)
superdump maybe :)
algern0n and thus allocating dinamically everything
superdump thankfully i'm only interested in 3x3 for the moment
algern0n you also don't have to pass pointers all around, since a class contains methods for dealing with its data
algern0n doing a cell[i][j].candidates() sure is nice :)
algern0n I'd say that sudoku solving is a kind of problem where C++ shows what's it's good for
superdump i dare say
algern0n you dare! :p
superdump but i don't know c++ yet, and i thought it would be a nice challenge to do it in C
algern0n even in C, it's better to implement a function that populates fields (candidates[], cand_num) of a cell_t structure
algern0n once, when analysing a "node"
algern0n and then just find the minimum of all cand_num, and run brute-force for that cell
algern0n so you'd get two loops (9x9) that can compute candidates, store them and find the min, all at once
algern0n for (i = 0; i < 9; i++)
algern0n for (j = 0; j < 9; j++) {
algern0n int c = candidates(cell[i][j]);
algern0n if (c < min_cand) {
algern0n // save c, i, j
algern0n }
algern0n }
algern0n something along these lines
superdump ok
superdump but you think that for problems of this size i'm not going to see much of a speed improvement over basic brute force?
algern0n I guess this is the most efficient brute-force thing you can do
algern0n brute force as you do it now is not very efficient
algern0n but with those improvements, you'll get very fast on 99.9% of grids
superdump i thought so
algern0n keep in mind that for 9x9 your data easily fit in L1
algern0n *3x3
superdump L1?
superdump oh
superdump level 1 cache
algern0n yup
algern0n fast as merry hell(tm)
superdump i'll do that tonight then
algern0n and even on that 0.1% unlucky grids, you'll be well under 1 second in almost all cases
superdump i might have a go at donald knuth's dancing links in C too
algern0n btw, if a cell has been *solved* (1 candidate), you need not to compute anything more on it. though I have to think about the cosequences of it, since you're doing everything "on place" and thus this may break backtracking.
algern0n thinking more about it, I'd say it certainly breaks backtracking, unless you do something about it. It would have worked for the "copy, try and copy back" approach of the original version.