蛮力数独算法 [英] Brute force Sudoku algorithm

问题描述

  

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

有关几天我试图写一个蛮力算法求解数独，我的问题是，我从来没有真的得到了算法的工作100％，可有人请直接与我，给一些帮助？

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

 公共抽象类广场{

接下来的私人广场;

私人箱箱;
私人排排;
私人Columne columne;

私人int值;

广场（int值，箱盒，鳞次栉比，Columne columne）{
    THIS.VALUE =价值;
    this.box =盒;
    this.row =行;
    this.columne = columne;
}

无效setNumberMeAndTheRest（董事会板）{
    如果（GETNEXT（）== NULL）{
        的System.out.println（下一个==空）;
        的for（int i = 1; I＆LT; = board.getDimension（）;我++）{
            如果（legalValue（i））的{
                的setValue（ⅰ）;
            }
        }
        board.saveSolution（）;
        返回;
    } 其他 {
        如果（这的instanceof DefinedSquare）{
            GETNEXT（）setNumberMeAndTheRest（板）。

        } 其他 {
            的for（int i = 1; I＆LT; = board.getDimension（）;我++）{
                如果（legalValue（i））的{
                    的setValue（ⅰ）;
                    GETNEXT（）setNumberMeAndTheRest（板）。
                }
            }
            返回;
        }
    }
}

INT的getValue（）{
    返回值;
}

无效的setValue（int值）{
    THIS.VALUE =价值;
}

无效setNext（广场旁边）{
    this.next =下一个;
}

公共广场GETNEXT（）{
    返回下一个;
}

/ **
 *如果值是合法的​​箱子，行和列的检查。
 *参数值来检查。
 * @返回true，如果值是合法的​​，否则为假。
 * /
布尔legalValue（int值）{
    如果（box.legalValue（值）及和放大器; row.legalValue（值）及和放大器; columne.legalValue（值））{
        返回true;
    }
    返回false;
}
 

解决方案

我认为你的问题可能会躺在这里

 的for（int i = 1; I＆LT; = board.getDimension（）;我++）{
        如果（legalValue（i））的{
            的setValue（ⅰ）;
            GETNEXT（）setNumberMeAndTheRest（板）。
        }
    }
 

如果legalValue（我）将返回true的独立的i的当前状态，那么你就回追踪，如果没有，你不回溯

然而，大多数回溯看起来就像是osmething像htis

 的for（int i = 1; I＆LT; = board.getDimension（）;我++）{
        如果（legalValue（i））的{
            的setValue（ⅰ）;
                //布尔值，指示液是否被发现
            如果（GETNEXT（）。setNumberMeAndTheRest（板））
               返回true;
            其他
               unsetValue㈠
        }
    }
 

我们需要更多的code知道，如果legalValue时方我已经设置返回false

试试这个，看看我是在正确的轨道或交的所有的你的code

 的System.out.println（启动迭代）
    的for（int i = 1; I＆LT; = board.getDimension（）;我++）{

        如果（legalValue（i））的{
            的System.out.println（GOING+ I）
            的setValue（ⅰ）;
            GETNEXT（）setNumberMeAndTheRest（板）。
        }
    }
    的System.out.println（结束迭代）
 

如果它填补了网格，然后停止，不回溯，你的问题是，你调用的setValue（我），然后调用legalValue第（i + 1），它是返回false ，因为该值alraedy集，不因为它是不合法。如果是这样的话，你需要一个相当的未设置的reucrsion后

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

解决方案

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

这篇关于蛮力数独算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！