Рекурсивное решение для генератора судоку
Я пытаюсь написать алгоритм, который создает легальную доску судоку на Java или Javascript. Ни одна из них не работает, и я не совсем уверен, почему.
По сути, проблема в обеих программах заключается в том, что x или y увеличиваются больше, чем должны (пропуская квадрат). Я не могу на всю жизнь понять, как это происходит. Я могу предоставить HTML, который дополняет решение JS, если это будет необходимо.
Я думаю, это связано с тем, как я создал стек с использованием рекурсии, но, насколько я могу судить, он должен работать. В моем старом коде был неправильный цикл for, я знаю об этом. Я вставил старую версию, сейчас она исправлена.
Джава:
import java.util.*;
public class SudokuGenerator
{
//credit:cachao
//http://stackru.com/questions/9959172/recursive-solution-to-sudoku-generator
public static final int BOARD_WIDTH = 9;
public static final int BOARD_HEIGHT = 9;
public SudokuGenerator() {
board = new int[BOARD_WIDTH][BOARD_HEIGHT];
}
//Recursive method that attempts to place every number in a square
public int[][] nextBoard()
{
nextBoard(0,0);
return board;
}
public void nextBoard(int x, int y)
{
int nextX = x;
int nextY = y;
//int[] toCheck = Collections.shuffle(Arrays.asList({1,2,3,4,5,6,7,8,9}));
int[] toCheck = {1,2,3,4,5,6,7,8,9};
Collections.shuffle(Arrays.asList(toCheck));
for(int i=0;i<toCheck.length;i++)
{
if(legalMove(x, y, toCheck[i]))
{
board[x][y] = toCheck[i];
if(x == 8)
{
if(y == 8)
break;//We're done! Yay!
else
{
nextX = 0;
nextY++;
}
}
else
{
nextX++;
}
nextBoard(nextX, nextY);
}
}
board[x][y] = 0;
}
public boolean legalMove(int x, int y, int current) {
for(int i=0;i<9;i++) {
if(current == board[x][i])
return false;
}
for(int i=0;i<9;i++) {
if(current == board[i][y])
return false;
}
int cornerX = 0;
int cornerY = 0;
if(x > 2)
if(x > 5)
cornerX = 6;
else
cornerX = 3;
if(y > 2)
if(y > 5)
cornerY = 6;
else
cornerY = 3;
for(int i=cornerX;i<10 && i<cornerX+3;i++)
for(int j=cornerY;j<10 && j<cornerY+3;j++)
if(current == board[i][j])
return false;
return true;
}
public void print()
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
System.out.print(board[i][j] + " ");
System.out.println();
}
}
public static void main(String[] args)
{
SudokuGenerator sg = new SudokuGenerator();
sg.nextBoard();
sg.print();
}
int[][] board;
}
Javascript:
//Recursive method that attempts to place every number in a square
function driver()
{
board = new Array(10);
for(var i=0;i<9;i++)
board[i] = new Array(10);
nextBoard(0,0);
print();
}
function nextBoard(x, y)
{
var nextX = x;
var nextY = y;
for(var i=1;i<10;i++) {
console.log(y + " " + x + " " + i);
document.getElementById(y + " " + x).innerHTML = i;
if(legalMove(x, y, i)) {
board[x][y] = i;
if(x === 8) {
if(y === 8)
return board;//We're done! Yay!
else {
nextX = 0;
nextY++;
}
}
else
nextX++;
nextBoard(nextX, nextY);
}
}
//This is needed for legalMove to work, otherwise [x][y] == 9
board[x][y] = undefined;
}
function legalMove(x, y, current) {
for(var i=0;i<9;i++) {
if(current === board[x][i])
return false;
}
for(var i=0;i<9;i++) {
if(current === board[i][y])
return false;
}
var cornerX = 0;
var cornerY = 0;
if(x > 2)
if(x > 5)
cornerX = 6;
else
cornerX = 3;
if(y > 2)
if(y > 5)
cornerY = 6;
else
cornerY = 3;
for(var i=cornerX;i<10 && i<cornerX+3;i++)
for(var j=cornerY;j<10 && j<cornerY+3;j++)
if(current === board[i][j])
return false;
return true;
}
function print() {
for(var i=0;i<9;i++)
for(var j=0;j<9;j++)
{
document.getElementById(i + " " + j).innerHTML = board[i][j];
console.log(board[i][j]);
}
}
var board;
6 ответов
Джава:
Вы должны инициализировать ваш
boardпеременная, вы можете инициализировать ее в конструкторе:public class SudokuGenerator { public static final int BOARD_WIDTH = 9; public static final int BOARD_HEIGHT = 9; public SudokuGenerator() { board = new int[BOARD_WIDTH][BOARD_HEIGHT]; } }Я считаю, что ваш цикл итератор в функции nextBoard это неправильно:
for(int i=1;i<10;i++){ ... }Я думаю, что вы хотите повторить от 0 до 9.
В функции nextBoard вам также необходимо проверить переменную:
int[] toCheck = {1,2,3,4,5,6,7,8,9};Вы получаете
java.lang.ArrayIndexOutOfBoundsException, вы должны инициализировать его от 0 до 8, в противном случае вы попытаетесь получить доступ к строке номер платы 9 и получите ошибку времени выполнения.Еще одна проблема, которую вам нужно решить, это то, что x устанавливается на девять в
nextBoard()функция. Вызвать функциюnextBoard(int x, int y)"вручную" с этими параметрами:nextBoard(7,3)и вы поймете, почему х устанавливается на девять. Проверьте конкретно значения переменнойnextX,
Я считаю, что это действительно поможет вам, если вы используете отладчик для проверки ошибок такого рода, здесь у вас есть хороший учебник с объяснением видео (на случай, если вы используете Eclipse IDE).
Надеюсь, поможет.
В коде Java: я переведу его в psuedocode:
for all z values:
If for current (x,y), the number 'z' is legal then:
insert z to current (x,y)
if finished
hooray!
else
go to next square
else try next number
Но что, если вы не можете поместить туда какое-либо число, так как оно оказывается незаконным (то есть доска, на которой вы не можете вставить любое число в конкретный квадрат)?
Вы не обращаетесь к этому. Что вам нужно сделать, это реализовать его с помощью обратного отслеживания:
for all z values:
If for current (x,y) the number 'z' is legal then:
insert z to current (x,y)
go to next(x,y)
try to complete the board // recursive call
if you completed the board // == the result of the recursion is legal
return the completed board
If all z values have been attempted
return "cannot complete board"
increment z, try again with current (x,y)
Интересный вопрос, я только что заметил одну ошибку в коде Java: не является ли вызов Collection.shuffle() бесполезным, поскольку массив toCheck останется неизмененным (unshuffled) после этого вызова? Вот мое быстрое решение (и я уверен, что есть более умные способы сделать это):
List<Integer> lst = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
Collections.shuffle(lst);
for (int i=0; i<lst.size(); i++)
toCheck[i] = lst.get(i);
Джава:
Ваш итератор цикла в nextBoard находится в диапазоне от 1 до 9. Не думаю, что вы это имели в виду. То же самое в функции legalMove.... инициализировать cornerX и cornerY в 0.
В массивах Java индексы начинаются с нуля. В nextBoard ты зациклишься 1..9 за i и использовать его в качестве индекса в toCheck который пропустит первый элемент в индексе 0 и пройти мимо конца массива. Это бросит ArrayIndexOutOfBoundsException если строка, содержащая toCheck[i] достигается с i равно 9,
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;
public class SudokuNrupen {
public static int[][] p;
public static int tmp[] ;
public static int tmp2D[][] ;
public static void main(String[] args){
tmp = new int[9];
tmp2D = new int[3][3];
p = new int[9][9];
System.out.print("Enter the name of he file below ");
Scanner scan = new Scanner (System.in);
String name = scan.nextLine();
File file = new File( name );
if ( file.exists()){
try {
Scanner inFile = new Scanner( file );
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
if(inFile.hasNextInt()){
p[i][j] = inFile.nextInt();
}
}
}
inFile.close();
} catch (FileNotFoundException ex) {
Logger.getLogger(SudokuNrupen.class.getName()).log(Level.SEVERE, null, ex);
}
}
display(p);
solve(p);
System.out.println("Solved Sudoku is:");
display(p);
}
public static void display(int [][] p)
{
for(int i=0; i<p.length;i++)
{
for(int j=0; j<p[i].length;j++)
{
System.out.print(" ");
if(p[i][j]<10) System.out.print(p[i][j] + " ");
else System.out.print(p[i][j]);
System.out.print(" ");
}
System.out.println();
}
}
public static boolean solve(int [][] p)
{
if(!isValidSudoku(p))
{
return false;
}
if(isComplete(p)==true)
{
return true;
}
for(int i=0; i<9; i++)
{
for(int j=0 ; j<9 ; j++)
{
if(p[i][j]==0)
{
int k=1;
while(k<=9)
{
p[i][j]=k;
if(solve(p))
{
return true;
}
else k++;
}
p[i][j]=0;
return false;
}
}
}
return true;
}
public static boolean isComplete(int [][]p)
{
for(int i=0; i<9; i++)
{
for(int j=0 ; j<9 ; j++)
{
if(p[i][j]==0){
return false;
}
}
}
return true;
}
public static boolean isRepeated(int [] a)
{
for(int i=0; i<8; i++)
{
if((a[i]!=0 || a[i+1]!=0))
{
if(a[i]==a[i+1]){
return true;
}
}
}
return false;
}
public static boolean isDuplicateEx0(int [][]p)
{
for(int i=0; i<p[0].length; i++)
{
for(int j=0 ; j<9 ; j++)
{
tmp[j]=p[i][j];
}
Arrays.sort(tmp);
System.out.println(Arrays.toString(tmp));
if(isRepeated(tmp)==true)
{
System.out.println("Duplicates are found in row");
return true;
}
}
display(p);
for(int j=0; j<p[0].length; j++)
{
for(int i=0 ; i<9 ; i++)
{
tmp[i]=p[i][j];
}
Arrays.sort(tmp);
if(isRepeated(tmp)==true)
{
System.out.println("Duplicates are found in columns");
return true;
}
}
display(p);
for(int z=0;z<9;z++){
tmp[z]=0;
}
int x=0,y=0;
for(int i=0; i<3;i++)
{
y=0;
for(int j=0;j<3;j++)
{
tmp2D[x][y]=p[i][j];
y++;
}
x++;
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
}
}
Arrays.sort(tmp);
if(isRepeated(tmp)==true)
{
return true;
}
for(int z=0;z<9;z++){
tmp[z]=0;
}
x=0;
y=0;
for(int i=0; i<3;i++)
{
y=0;
for(int j=3;j<6;j++)
{
tmp2D[x][y]=p[i][j];
y++;
}
x++;
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
}
}
Arrays.sort(tmp);
if(isRepeated(tmp)==true)
{
return true;
}
for(int z=0;z<9;z++){
tmp[z]=0;
}
x=0;
y=0;
for(int i=0; i<3;i++)
{
y=0;
for(int j=6;j<9;j++)
{
tmp2D[x][y]=p[i][j];
y++;
}
x++;
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
}
}
Arrays.sort(tmp);
if(isRepeated(tmp)==true)
{
return true;
}
for(int z=0;z<9;z++){
tmp[z]=0;
}
x=0;
y=0;
for(int i=3; i<6;i++)
{
y=0;
for(int j=0;j<3;j++)
{
tmp2D[x][y]=p[i][j];
y++;
}
x++;
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
}
}
Arrays.sort(tmp);
if(isRepeated(tmp)==true)
{
return true;
}
for(int z=0;z<9;z++){
tmp[z]=0;
}
x=0;
y=0;
for(int i=3; i<6;i++)
{
y=0;
for(int j=3;j<6;j++)
{
tmp2D[x][y]=p[i][j];
y++;
}
x++;
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
}
}
Arrays.sort(tmp);
if(isRepeated(tmp)==true)
{
return true;
}
for(int z=0;z<9;z++){
tmp[z]=0;
}
x=0;
y=0;
for(int i=3; i<6;i++)
{
y=0;
for(int j=6;j<9;j++)
{
tmp2D[x][y]=p[i][j];
y++;
}
x++;
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
}
}
Arrays.sort(tmp);
if(isRepeated(tmp)==true)
{
return true;
}
for(int z=0;z<9;z++){
tmp[z]=0;
}
x=0;
y=0;
for(int i=6; i<9;i++)
{
y=0;
for(int j=0;j<3;j++)
{
tmp2D[x][y]=p[i][j];
y++;
}
x++;
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
}
}
Arrays.sort(tmp);
if(isRepeated(tmp)==true)
{
return true;
}
for(int z=0;z<9;z++){
tmp[z]=0;
}
x=0;
y=0;
for(int i=6; i<9;i++)
{
y=0;
for(int j=3;j<6;j++)
{
tmp2D[x][y]=p[i][j];
y++;
}
x++;
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
}
}
Arrays.sort(tmp);
if(isRepeated(tmp)==true)
{
return true;
}
for(int z=0;z<9;z++){
tmp[z]=0;
}
x=0;
y=0;
for(int i=6; i<9;i++)
{
y=0;
for(int j=6;j<9;j++)
{
tmp2D[x][y]=p[i][j];
y++;
}
x++;
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
tmp[(i*tmp2D.length) + j] = tmp2D[i][j];
}
}
Arrays.sort(tmp);
if(isRepeated(tmp)==true)
{
return true;
}
return false;
}
public static boolean isValidSudoku(int [][] p)
{
return (!isDuplicateEx0(p));
}
}