alglus/sudoku-solver

A solver for sudokus of different sizes, written in haskell.

sudoku-solver's Issues

Rows list too long

When converting a sudoku of size L into a cover problem, a matrix is generated with the size:

• columns:
• rows:

So for a 25x25 sudoku the rows list is already 15625 elements long. Every access to an element becomes very expensive.

So an idea is to somehow split the list into k sub-lists and access the one corresponding to the desired index. This would reduce the time complexity from O(n) to O(k + n/k)

Column size: wrong incrementation and decrementation

Currently the minimal column is calculated with the function updateCols. It has a time complexity of O(n*m), which is not ideal.

This was a quick fix for a bug when decrementing or incrementing each column size after covering a cell.
The problem was, that after some rounds of backtracking, some column had a size of n>0, but no uncovered cells left. So the function head run into an error.

Correct this bug and change the size of each column directly when cov/uncovering a cell. Then just go through the columns list and search for the minimum, which would be O(n).