1

可能重复：
数独算法，蛮力

几天来，我一直在尝试编写一个蛮力算法来解决数独问题，我的问题是我从来没有真正让算法 100% 工作，有人可以指导我并提供一些帮助吗？

该算法位于 Square 类，递归函数。

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;
}
4

2 回答 2

2

我认为您的问题可能出在此处

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

如果 legalValue(i)独立于 i 的当前状态返回 true，那么你正在回溯，如果不是，你没有回溯

大多数回溯看起来像 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)
        }
    }

我们需要更多的代码来知道当已经设置了 square i 时 legalValue 是否返回 false

试试这个看看我是否在正确的轨道上或发布你所有的代码

    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")

如果它填满了网格然后停止而不回溯，那么您的问题是您调用 setValue(i) 然后调用 legalValue(i+1) 并且它返回 false因为该值已设置，而不是因为它不合法。如果是这样，您需要在 reucrsion 之后进行等效的“未设置”

于 2012-04-17T15:01:01.493 回答
1

快速浏览一下您的算法，它看起来好像只在每个方格中尝试了一个可能的值。当它到达一个找不到合法值的方块时，它就放弃了。它需要一些回溯机制，并在其先前填充的方格中尝试替代法律值。

例如，这是一个迷你 4x4 拼图：

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

据我所知，你的算法会走到这一步然后退出：

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

而不是退出，它应该返回并更改它已插入的 2 个值中的任何一个。

于 2012-04-17T14:55:55.050 回答