Перейти к содержимому

Фото
- - - - -

Алгоритм генерации рандомной Судоку

Судоку алогритм java

  • Вы не можете создать новую тему
  • Please log in to reply
11 ответов в этой теме

#1 Genezis

Genezis
  • Пользователь
  • 81 сообщений

Отправлено 03 Март 2013 - 18:55

Требуется помощь в написании алгоритма генерации судоку на java.
В общем, есть 3 метода: checkLine, checkColumn и checkBlock, которые по отдельности работают, т.е заполняют таблицу цифрами от 1 до 9 без повторений либо в строку, в столбец, либо в блок 3х3. Но при объединении каких-либо 2-ух из них программа зацикливается. Как решить это - фиг знает.
Собственно сам код:
package sudoku;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class Numbers
{
static final int N = 9;
static Random rnd = new Random();

static List<Integer>[] numbers = new ArrayList[N];

public Numbers()
{
	 for(int i = 0; i < N; i++)
	 {
		 numbers[i] = new ArrayList<>();
		 for(int j = 1; j <= N; j++)
		 {
			 if(i == 0)
			 {
				 numbers[i].add(j);
			 }
			 else
			 {
				 numbers[i].add(0);
			 }
			
		 }
	 }
	 Collections.shuffle(numbers[0]);
}

private boolean checkLine(int line, int value)
{
	 for(int i = 0; i < N; i++)
	 {
		 if(numbers[line].get(i) == value)
		 {
			 return false;
		 }
	 }
	 return true;
}

private boolean checkColumn(int column, int value)
{
	 for(int i = 0; i < N; i++)
	 {
		 if(numbers[i].get(column) == value)
		 {
			 return false;
		 }
	 }
	 return true;
}

private boolean checkMove(int l, int c, int r)
{
	 if(!checkLine(l, r))
	 {
		 return false;
	 }
	 if(!checkColumn(c, r))
	 {
		 return false;
	 }
	 if(!checkBlock(l, c, r))
	 {
		 return false;
	 }
	
	 return true;
}

private boolean checkBlock(int line, int column, int value)
{
	 for(int i = 0; i < 3; i++)
	 {
		 for(int j = 0; j < 3; j++)
		 {
			 if(numbers[line - (line % 3) + i].get(column - (column % 3) + j) == value)
			 {
				 return false;
			 }
		 }
	 }
	 return true;
}

public void generateSudoku()
{
	 boolean move = false;
	 int r = 0;
	
	 for(int line = 1; line < N; line++)
	 {
		 for(int column = 0; column < N; column++)
		 {
			 while(!move)
			 {
				 r = rnd.nextInt(9) + 1;
				 move = checkMove(line, column, r);
				
				
				 for(int i = 0; i < N; i++)
				 {
					 System.out.println(numbers[i].toString());
				 }
				 System.out.println(" ------------------- ");
			 }
			
			 if(move)
			 {
				 numbers[line].set(column, r);
				 move = false;
			 }
		 }
	 }
}

public void printNumbers()
{
	 for(int i = 0; i < N; i++)
	 {
		 System.out.println(numbers[i].toString());
	 }
}
}

Зацикливается примерно в таких местах:
Прикрепленный файл  sud.jpg   88,29К   94 Количество загрузок
В данном случае остаётся в строку вставить только 3, но она уже есть в текущем блоке 3х3. Хочется добить, но самому не по зубам (
  • 0

#2 skill-A

skill-A

    Huge Cojones

  • Постоялец
  • 6 711 сообщений

Отправлено 03 Март 2013 - 19:30

если судоку не более чем 5 на 5 полей и интервал от 1 до 9 то лучше сделать это рандомно
и каждый раз проверять, если все окей то возвращаем массив данных.

но это при условии что вычисления на стороне клиента Размещенное изображение

Сообщение изменено: skill-A (03 Март 2013 - 19:31 )

  • 0

улыбнись


#3 Corak

Corak
  • Новобранец
  • 12 сообщений

Отправлено 15 Март 2013 - 00:37

алгоритм поменяй , последовательность должна быть такая
1) генерируешь первую строчку
2) генерируешь вторую строчку
3) генерируешь третью строчку
третья строчка с некоторой вероятностью не сможет сгенерироваться, потомучто недостающая девятая цифра в последнем 3на3 блоке будет уже присутствовать в этом блоке.
лечится легко , когда достаешь из массива последнюю цифру в 3на3 блоке и она зацикливается, стираешь всю текущую строчку (третью) и генерируешь третью строчку заново,
если опять третья строчка не сможет сгенерироваться, опять ее стираешь и генерируешь заново ,поставь счетчик , который считает неудачные попытки генерации строчки, если с десятой попытки не получается сгенерировать третью строчку , стираешь тогда третью и вторую строчку и генерируешь обе строчки заново.


такуюже систему применяшь ко всем остальным строчкам, в итоге судоку может сгенерироваться с первой попытки , а может сгенерироваться и с 1000-ой попытки.
  • 2

#4 EastHastings

EastHastings

    Титулярный советникъ

  • Постоялец
  • 2 852 сообщений

Отправлено 15 Март 2013 - 23:49

Corak, вроде правильно, но очень уж неоптимально
  • 0

юноша бледный со взором горящим


#5 Corak

Corak
  • Новобранец
  • 12 сообщений

Отправлено 16 Март 2013 - 00:42

это же java :) , если судоку сгенерируеться с 1000-ой попытки , это все дело займет 0,001 секунду , так что нормально :)
  • 0

#6 Vitalts

Vitalts
  • Постоялец
  • 1 842 сообщений

Отправлено 16 Март 2013 - 13:33

Какова практическая польза от рандомной генерации полного поля? Где вы собираетесь применять данный метод? Если это некая исследовательская работа, то норм. Если же пишете игру, то полное поле вам ничего не даст, ибо нет гарантий, что по оставленным числам можно будет получить исходное поле. Для практического использования, ИМХО, стоит генерировать саму задачу и пытаться ее решить, дабы не выдавать не решаемые варианты.
  • 1

#7 Akhenaton

Akhenaton
  • Постоялец
  • 8 042 сообщений

Отправлено 16 Март 2013 - 18:19

Вот чисто наобум - проще генерировать блок за блоком. Забить рандомно цифрами самый первый блок, и потом копировать в следующий блок с перестановкой(ами). Тот же рандомизированный алгоритм, только в уменьшенном формате, только не надо париться на проверку блока, потому что этот блок по умолчанию забит правильно, без повторов, и содержит все цифры.
ХЗ. Интересная задача. Надо подумать.
  • 0

#8 EastHastings

EastHastings

    Титулярный советникъ

  • Постоялец
  • 2 852 сообщений

Отправлено 22 Март 2013 - 20:14

Genezis, если ещё актуально, то почитай http://habrahabr.ru/post/173795/
  • 1

юноша бледный со взором горящим


#9 Genezis

Genezis
  • Пользователь
  • 81 сообщений

Отправлено 15 Апрель 2013 - 15:05

стираешь всю текущую строчку (третью) и генерируешь третью строчку заново

Объявил хешсет, куда добавляются числа после неудачной попытки. Если размер достигает 9, сбрасываю счётчик столбца и чищу строку. В общем, генерируется. Спасибо.

Какова практическая польза от рандомной генерации полного поля? Где вы собираетесь применять данный метод?

От нечего делать)

Если же пишете игру, то полное поле вам ничего не даст, ибо нет гарантий, что по оставленным числам можно будет получить исходное поле

Скажем, если делать маску так, чтобы в каждом блоке 3x3 были видны 4 цифры - тоже нет гарантий, что будет 1 правильное решение? Имеет смысл, наверное, писать сольвер.

если ещё актуально

Актуально, т.к. я на какое-то время забросил это дело. Спасибо.

Сообщение изменено: Genezis (15 Апрель 2013 - 15:12 )

  • 0

#10 Vitalts

Vitalts
  • Постоялец
  • 1 842 сообщений

Отправлено 15 Апрель 2013 - 20:10

Скажем, если делать маску так, чтобы в каждом блоке 3x3 были видны 4 цифры - тоже нет гарантий, что будет 1 правильное решение?


Гарантию единственности решения может дать разве что:
• игровое поле с менее чем 4 не заполненных значений
• попытка найти все решения, дабы убедится в его единственности
Ни то ни другое, думается, ни устроит ни одну из сторон.
Если же имелось в виду хотя бы одно решение, то да, в данном случае гарантия есть, только она такая же, как и если открыть на поле по одной цифре в квадратах 3х3, и равна 100%, ведь игровое поле получено из решения. Однако, где гарантия, что его сможет решить человек с IQ < 200? При условии по 4 цифры из каждого квадрата, думается, с задачкой любой справится, только вот игра будет, ИМХО, ущербной, слишком жесткие рамки для выдаваемых игровых полей.
  • 0

#11 Genezis

Genezis
  • Пользователь
  • 81 сообщений

Отправлено 15 Апрель 2013 - 21:49

При условии по 4 цифры из каждого квадрата, думается, с задачкой любой справится

Ну если оценивать по сложности - будет норм. Часто встречающийся вариант. Из любопытства проверил в онлайн-сольверах несколько вариантов масок с 4 открытыми цифрами в блоке 3x3 на уникальность решения, всё сходилось. Так же видел варианты с 1 решением, где в блоках открыты были 1-4 цифры.
Интересно, с чего можно оттолкнуться для генерации маски?)
Или, iyho, без сольвера не обойтись?

Сообщение изменено: Genezis (15 Апрель 2013 - 22:19 )

  • 0

#12 Genezis

Genezis
  • Пользователь
  • 81 сообщений

Отправлено 22 Апрель 2013 - 01:00

Таки добил, написав сольвер. Генерирует доску с 1 решением. На высокой сложности, правда, генерация может занять несколько секунд. Если кому надо - обращайтесь. Может, пригодится)

Сообщение изменено: Genezis (22 Апрель 2013 - 01:01 )

  • 0





Читать еще на тему: Судоку алогритм, java