Time for a redesign

So for N=7, it takes our algorithm more than 8 hours to solve on a Pentium 4. We have analyzed how our solver is solving the puzzle; the problem it is guessing too much. While our logical methods are fast, we are spending at least 99.9% of the time using them on a puzzle that is going to be shown to be invalid.

So we need to implement more logical "human" methods. However, we have exhausted the analytic methods that operate on the data structures we store (we store the possibilities for the rows, columns, and boxes--but not the possibilities for each cell.) The more complex methods will require that we store the possibilities for every cell on the grid. So we will basically have to start over on our algorithm.

In other news, the hardware I designed for accelerating FindUniqueRow doesn't fit on the FPGA. Oops. So I'm starting over resigned to reading in only a limited number of the constraint arrays at a time and doing some processing--and also only store an even more limited amount of interim work.

As long as we are redesigning the algorithm, I think Vlad is going to aim for having the software operate on bit vectors rather than character arrays. This means we are basically throwing out our software and starting over.

Sudoku is hard.