I'm working on a sudoku solver that solves sudoku like a novice human sudoku solver would.

I start off by making a candidate list for each of the 81 boxes, a 2d array of arralylists (ArrayList[][] candidates).

Then I strip away candidates from the lists, and insert the element if there's just one candidate. I think the code is correct for this(?)

Then I check for hidden singles, which is a lot harder. I think the code for rows and columns should be okay, but I don't really know how to handle it for boxes.

Any help would be greatly appreciated, also, please let me know if this method is completely retarded.

Thanks

David Phluphy wrote:Any help would be greatly appreciated, also, please let me know if this method is completely retarded.

Well you've plainly put some thought into it, so it's unlikely to be retarded, even if it doesn't completely work.

This page might help.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." --- Martin Fowler

Please correct my English.

Thanks to Wouter and Winston for contributing.

My theory is that if all the candidates of a group (row, column or block) for a particular digit are also candidates for one other group (I use the word "intersect"), you can eliminate that digit as a candidate for all other cells in the two intersecting groups. For an intersecting block and row/column, this usually leaves a triplet of candidates.

In the example, you can eliminate 2, 4 and 6 as candidates from the cells marked by *. Each of these digits is a candidate of a cell where the column intersects with one other group, so you can eliminate them in the remainder of the two groups, which is trivial for the column, but gives you new information about the block.

You can extend this theory to all sorts of soduku types. It works really well on X-sudokus and the sudokus which have the 4 grey blocks. You just need to determine in which cells two groups intersect, if at all.

Granted, I tested my strategy using a functional language, which may be much easier than in Java. Heed Wouter's suggestion of using a boolean array to check for patterns.

I'm not familiar with patterns, and I don't want to sound stubborn, but I -really- want to solve it the way I started. This solver is not supposed to be able to solve every single sudoku-puzzle, just the ones with naked singles and hidden singles. I've updated the code, but my mind is a bit tired. If anyone knows a puzzle with just naked singles and hidden singles, please show it to me so I can test it.

{ {1,0,0, 2,0,0, 3,0,0},

{0,2,0, 0,1,0, 0,4,0},

{0,0,3, 0,0,5, 0,0,6},

{7,0,0, 6,0,0, 5,0,0},

{0,5,0, 0,8,0, 0,7,0},

{0,0,8, 0,0,4, 0,0,1},

{8,0,0, 7,0,0, 4,0,0},

{0,3,0, 0,6,0, 0,2,0},

{0,0,9, 0,0,2, 0,0,7}};

I used the following strategy, a candidate 'x' that has only one cell to go and other candidates have legal possibility to occupy that cell, then candidate is said to be the hidden single.

I used this strategy to solve.

1) First pencil up the candidates.

2) Check for naked singles.

3)Update the candidates.

4)Check for hidden singles.

To check for hidden singles, just try if a candidate can occupy more than one cell that row and column, then it is not hidden, else its hidden candidate.

SCJP

Visit my download page