Brute force Sudoku algorithm [duplicate]

问题:

Possible Duplicate:
Sudoku algorithm, brute force

For several days I have tried to write a brute force algorithm for solving sudoku, my problem is that I never realy get the algorithm to work 100 %, can someone please direct me and give some help ?

The Algorithm is located in Square class, recursive function.

public abstract class Square {

private Square next;

private Box box;
private Row row;
private Columne columne;

private int value;

Square(int value, Box box, Row row, Columne columne) {
    this.value = value;
    this.box = box;
    this.row = row;
    this.columne = columne;
}

void setNumberMeAndTheRest(Board board) {
    if(getNext() == null) {
        System.out.println("next == null");
        for(int i = 1; i <= board.getDimension(); i++) {
            if(legalValue(i)) {
                setValue(i);
            }
        }
        board.saveSolution();
        return;
    } else {
        if(this instanceof DefinedSquare) {
            getNext().setNumberMeAndTheRest(board);

        } else {
            for(int i = 1; i <= board.getDimension(); i++) {
                if(legalValue(i)) {
                    setValue(i);
                    getNext().setNumberMeAndTheRest(board);
                }
            }
            return;
        }
    }
}

int getValue() {
    return value;
}

void setValue(int value) {
    this.value = value;
}

void setNext(Square next) {
    this.next = next;
}

public Square getNext() {
    return next;
}

/**
 * Checks if value is legal in box, row and column.
 * @param value to check.
 * @return true if value is legal, else false.
 */
boolean legalValue(int value) {
    if(box.legalValue(value) && row.legalValue(value) && columne.legalValue(value)) {
        return true;
    }
    return false;
}

回答1:

I think your problem may lie here

    for(int i = 1; i <= board.getDimension(); i++) {
        if(legalValue(i)) {
            setValue(i);
            getNext().setNumberMeAndTheRest(board);
        }
    }

If legalValue(i) returns true independent of the current state of i, then you're back tracking, if not, you're not backtracking

What most backtracking looks like is osmething like htis

    for(int i = 1; i <= board.getDimension(); i++) {
        if(legalValue(i)) {
            setValue(i);
                // boolean indicating whether solution was found
            if(getNext().setNumberMeAndTheRest(board))
               return true;
            else
               unsetValue(i)
        }
    }

We need more code to know if legalValue returns false when square i is already set

Try this to see if I'm on the right track or post all of your code

    System.out.println("STARTING ITERATION")
    for(int i = 1; i <= board.getDimension(); i++) {

        if(legalValue(i)) {
            System.out.println("GOING " + i)
            setValue(i);
            getNext().setNumberMeAndTheRest(board);
        }
    }
    System.out.println("ENDING ITERATION")

If it fills out the grid and then stops without backtracking, your problem is that you calling setValue(i) and then calling legalValue(i+1) and it is return false because the value is alraedy set, not because it's not legal. If this is so, you need an equivalent 'unset' after the reucrsion

回答2:

From a quick look at your algorithm, it looks as though it only ever tries a single possible value in each square. When it reaches a square where it can't find a legal value, it just gives up. It needs some mechanism of backtracking and trying alternative legal values in squares that it has previously filled.

As an example, here's a mini 4x4 puzzle:

  1 |    
    | 2  
---------
    |   4
3   |

Your algorithm, from what I can tell, will get this far then quit:

2 1 | 3 X 
    | 2  
---------
    |   4
3   |

Instead of quitting, it ought to go back and change either of the 2 values it has inserted.