Что нового

Алгоритм построения сетки Sudoku

CreatoR

Must AutoIt!
Команда форума
Администратор
Сообщения
8 610
Репутация
2 438
Надеюсь не нужно объяснять что такое игра Sudoku?

Пытался сам создать алгоритм построения сетки 9x9, так чтобы в горизонтальной линий, в вертикальной линий, и в каждом блоке 3x3, цифры от 1 до 9 не повторялись.
Но самому не удалось это осилить (у меня код переваливал за 100 строк, и это меня навело на мысль, что я в корне задачу решаю неправильно), и я всё таки открыл гугель и получил ответ в wikipedia. Там приведён пример на java, перевёл я это дело на AutoIt:

Код:
#include <Array.au3>

$n = 3
Dim $field[$n * $n][$n * $n]

For $i = 0 To ($n * $n) - 1
	For $j = 0 To ($n * $n) - 1
		$field[$i][$j] = Int(Mod(($i * $n + $i / $n + $j), ($n * $n)) + 1)
	Next
Next

_ArrayDisplay($field)


Всё отлично работает, но оно постоянно генерирует одну и туже таблицу, т.ч нужно сделать случайную генерацию, иначе нет смысла в одинаковых таблицах.

У кого какие будут мысли по теме?


Добавлено:
Сообщение автоматически объединено:

Вот как то ещё так я пытался:

Код:
#include <Array.au3>

Global $n = 3
Global $field[$n * $n][$n * $n]

For $x = 0 To 8
	For $y = 0 To 8
		_SetCell($x, $y)
	Next
Next

_ArrayDisplay($field)

Func _SetCell($x, $y)
	$field[$x][$y] = Random(1, 9, 1)
	
	While 1
		For $i = 0 To ($n * $n) - 1
			If $i <> $x And $field[$i][$y] = $field[$x][$y] Then
				$field[$x][$y] = Random(1, 9, 1)
				ContinueLoop 2
			EndIf
		Next
		
		ExitLoop
	WEnd
	
	While 1
		For $i = 0 To ($n * $n) - 1
			If $i <> $y And $field[$x][$i] = $field[$x][$y] Then
				$field[$x][$y] = Random(1, 9, 1)
				ContinueLoop 2
			EndIf
		Next
		
		ExitLoop
	WEnd
	
	If Mod($x, 3) = 0 Then
		;Check the 3x3 block
	EndIf
EndFunc


:wacko:


Добавлено:
Сообщение автоматически объединено:

Оказывается генерировать случайные цифры и не нужно, достаточно можно случайным образом отсеивать “ненужные” ячейки:

Код:
#include <Array.au3>

$aSudoku_Fields = _Sudoku_GetFields(3, 6)
_ArrayDisplay($aSudoku_Fields)

Func _Sudoku_GetFields($nCels = 3, $iLevel = 6)
	Local $aFields[$nCels * $nCels][$nCels * $nCels]
	
	For $i = 0 To ($nCels * $nCels) - 1
		For $j = 0 To ($nCels * $nCels) - 1
			$aFields[$i][$j] = Int(Mod(($i * $nCels + $i / $nCels + $j), ($nCels * $nCels)) + 1)
		Next
	Next
	
	For $i = 0 To $iLevel * Random(6, ($nCels * $nCels) - 1, 1)
		$aFields[Random(0, ($nCels * $nCels) - 1, 1)][Random(0, ($nCels * $nCels) - 1, 1)] = ""
	Next
	
	Return $aFields
EndFunc


но случайная генерация всё же нужна, чтобы сохранить разновидность таблиц, и чтобы таблица не имела способность “запоминаться”.
 

Redline

AutoIT Гуру
Сообщения
506
Репутация
369
Я бы делал так:
1. Создаем массив 1-9
2. Заполняем ячейки в одной строке, выбирая элементы из него рандомно, убирая очередную цифру из массива (ReDim). Понятно что выбранную цифру нужно проверять по строке, столбцу и квадрату.
Ну а так нашел решение (см. способ 3)

Свой способ попробую реализовать позже :smile:


Добавлено:
Сообщение автоматически объединено:

Мой способ ведет в тупик :wacko:
При том что мне не удалось организовать поиск внутри малого квадрата
Наработки:
Код:
#include <Array.au3>

$n = 3
Dim $aField[$n * $n][$n * $n]
Dim $aBase[9] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Dim $aTemp = $aBase

For $i = 0 To UBound($aTemp) - 1 ; перемешиваем массив
	$iRandNumber = Random(0, UBound($aTemp) - 1, 1)
	$iRand = $aTemp[$iRandNumber]
	$aTemp[$iRandNumber] = $aTemp[$i]
	$aTemp[$i] = $iRand
Next

For $i = 0 To ($n * $n) - 1 ; заполняем первую строку
	$aField[0][$i] = $aTemp[$i]
Next


For $i = 1 To ($n * $n) - 1
	$aTemp = $aBase
	For $j = 0 To ($n * $n) - 1
;~ 		$iTrip = 0
;~ 		$hTrue = False
		$hTrue = False
;~ 		Do
			$iTempNumber = $aTemp[Random(0, UBound($aTemp))]
			$sHorizont = ''
			For $z = 0 To $j
				$sHorizont &= $aField[$i][$z]
			Next
			If Not StringInStr($sHorizont, $iTempNumber) Then ; поиск в строке
				$sVertical = ''
				For $y = 0 To $i
					$sVertical &= $aField[$y][$j]
				Next
				If Not StringInStr($sVertical, $iTempNumber) Then ; поиск в столбце
;~ 					$sSquare = '' ; здесь должен быть поиск в квадрате
					$aField[$i][$j] = $iTempNumber
					For $o = 0 To UBound($aTemp) - 1
						If $aTemp[$o] = $iTempNumber Then
							For $g = $o To UBound($aTemp) - 2
								$aTemp[$g] = $aTemp[$g + 1]
							Next
							If UBound($aTemp) <> 1 Then ReDim $aTemp[UBound($aTemp) - 1]
							ConsoleWrite(_ArrayToString($aTemp) & @CRLF)
							ExitLoop
;~ 							$iTrip = 3
;~ 							$hTrue = True
						EndIf
					Next
;~ 				Else
;~ 					$iTrip += 1
				EndIf
;~ 			Else
;~ 				$iTrip += 1
			EndIf
;~ 		Until $iTrip > 2
;~ 		Until $hTrue
	Next
Next

_ArrayDisplay($aField)
 

madmasles

Модератор
Глобальный модератор
Сообщения
7 790
Репутация
2 320
CreatoR,
Попробовал сделать по принципу ссылки, которую дал Redline (способ 3), с рандомной первой строкой, сыровато, но вроде работает. не работает. :( Код удалил.
 

Yashied

Модератор
Команда форума
Глобальный модератор
Сообщения
5 379
Репутация
2 714
CreatoR сказал(а):
Надеюсь не нужно объяснять что такое игра Sudoku?
Может я конечно отстал от жизни, но я в первый раз слышу о Sudoku...

:whistle:
 
Автор
CreatoR

CreatoR

Must AutoIt!
Команда форума
Администратор
Сообщения
8 610
Репутация
2 438
Yashied [?]
я в первый раз слышу о Sudoku...
:shok: :laugh:
Это моя вторая любимая игра (из серий головоломок) после шахмат.

Описание игры

Судоку — логическая головоломка, квадрат 9x9, который нужно заполнить цифрами по следующим правилам: в свободных клетках надо расставить цифры от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3x3 каждая цифра встречалась бы только один раз.
В некоторых клетках уже в начале игры стоят числа (от 1 до 9). Чем больше цифр стоит изначально, тем проще решить головоломку.

Судоку (яп. 数独 су:доку — «одинокое число») — популярная головоломка-пазл с числами. В переводе с японского «су» — «цифра», «доку» — «стоящая отдельно». Иногда судоку называют «магическим квадратом», что в общем-то не верно, так как судоку является латинским квадратом 9-го порядка. Судоку активно публикуют газеты и журналы разных стран мира, сборники судоку издаются большими тиражами. Решение судоку — популярный вид досуга.

Игровое поле представляет собой квадрат размером 9x9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), так как незаполненное игровое поле не имеет смысла. В зависимости от того, сколько клеток уже заполнены, конкретную судоку можно отнести к лёгким или сложным.

Правило игры

В судоку есть всего одно правило. Необходимо заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3x3 каждая цифра встречалась бы только один раз.

От того, сколько клеток уже заполнено, зависит сложность игры. Некоторые головоломки можно решить за несколько минут, на другие можно потратить часы.

Правильно составленная головоломка имеет только одно решение. Тем не менее, на некоторых сайтах в интернете под видом усложненных головоломок пользователю предлагаются варианты судоку с несколькими вариантами решения, а также с ветвлениями самого хода решения.
http://ru.wikipedia.org/wiki/Судоку
 

madmasles

Модератор
Глобальный модератор
Сообщения
7 790
Репутация
2 320
CreatoR
Так проще, но тоже вроде работает:
Код:
#include <Array.au3>

$sString = ''
$sTemp = ''
$sResult = ''
$iCount = 0
Dim $aSudoku[9][9]

While $iCount < 9
	$iRandom = Random(1, 9, 1)
	If Not StringInStr($sString, $iRandom) Then
		$sString &= $iRandom
		$iCount += 1
	EndIf
WEnd

For $i = 0 To 8
	If $i > 0 And Mod($i, 3) Then
		$sTemp = StringLeft($sString, 3)
		$sString = StringTrimLeft($sString, 3) & $sTemp
	ElseIf $i > 0 And Not Mod($i, 3) Then
		$sTemp = StringLeft($sString, 4)
		$sString = StringTrimLeft($sString, 4) & $sTemp
	EndIf
	$sResult &= $sString & @LF
Next
$aTempRow = StringSplit(StringTrimRight($sResult, 1), @LF, 2)
For $i = 0 To 8
	$aTempColumn = StringSplit($aTempRow[$i], '', 2)
	For $j = 0 To 8
		$aSudoku[$i][$j] = $aTempColumn[$j]
	Next
Next
_ArrayDisplay($aSudoku)
 

Yashied

Модератор
Команда форума
Глобальный модератор
Сообщения
5 379
Репутация
2 714
CreatoR

По мне, так крестики-нолики прикольнее...

:smile:
 
Автор
CreatoR

CreatoR

Must AutoIt!
Команда форума
Администратор
Сообщения
8 610
Репутация
2 438
madmasles
Мне просто интересно, вы это по формуле делали, или как? :scratch:
Спасибо, то что нужно!

Yashied [?]
крестики-нолики прикольнее
Очень быстро становится скучно.
 

madmasles

Модератор
Глобальный модератор
Сообщения
7 790
Репутация
2 320
CreatoR,
Если честно, то алгоритм я подсмотрел в Вашей формуле _Sudoku_GetFields(). Первая строка рандомная, а со второй строки идет смещение на 3 знака, а 4 и 7 строки - на 4.
 
Автор
CreatoR

CreatoR

Must AutoIt!
Команда форума
Администратор
Сообщения
8 610
Репутация
2 438
madmasles [?]
Если честно, то алгоритм я подсмотрел в Вашей формуле _Sudoku_GetFields(). Первая строка рандомная, а со второй строки идет смещение на 3 знака, а 4 и 7 строки - на 4.
Тогда у вас очень хорошо развито чувство к повторяющимся шаблонам.

OffTopic:
А тем временем, мне уже удалось построить оболочку GUI вокруг этого алгоритма :whisper:, позже выложу.
 

madmasles

Модератор
Глобальный модератор
Сообщения
7 790
Репутация
2 320
CreatoR [?]
хорошо развито чувство к повторяющимся шаблонам
Вряд ли, я совершенно случайно заметил закономерность. :smile:
 

Redline

AutoIT Гуру
Сообщения
506
Репутация
369
madmasles [?]
Попробовал сделать по принципу ссылки, которую дал Redline (способ 3), с рандомной первой строкой, сыровато, но вроде работает. не работает. Код удалил.
Получилось простым перебором/подстановкой, но ваш способ интереснее
И реализовал функцию перемешивания судоку :zorro:
Код:
#include <Array.au3>

Global $sSudoku = '', $iCount = 0, $aSudoku[9][9]

While $iCount < 9
    $iRandom = Random(1, 9, 1)
    If Not StringInStr($sSudoku, $iRandom) Then
        $sSudoku &= $iRandom
        $iCount += 1
    EndIf
WEnd

$sLeft = StringLeft($sSudoku, 3)
$sCenter = StringMid($sSudoku, 4, 3)
$sRight = StringRight($sSudoku, 3)
$sSudoku &= @CRLF & $sRight & $sLeft & $sCenter & @CRLF & $sCenter & $sRight & $sLeft & @CRLF

$sLeft = StringRight($sLeft, 2) & StringLeft($sLeft, 1)
$sCenter = StringRight($sCenter, 2) & StringLeft($sCenter, 1)
$sRight = StringRight($sRight, 2) & StringLeft($sRight, 1)
$sSudoku &= $sLeft & $sCenter & $sRight & @CRLF & $sRight & $sLeft & $sCenter & @CRLF & $sCenter & $sRight & $sLeft & @CRLF

$sLeft = StringRight($sLeft, 2) & StringLeft($sLeft, 1)
$sCenter = StringRight($sCenter, 2) & StringLeft($sCenter, 1)
$sRight = StringRight($sRight, 2) & StringLeft($sRight, 1)
$sSudoku &= $sLeft & $sCenter & $sRight & @CRLF & $sRight & $sLeft & $sCenter & @CRLF & $sCenter & $sRight & $sLeft & @CRLF
ConsoleWrite($sSudoku & @CRLF)
$sSudoku = StringStripWS($sSudoku, 8)
For $i = 0 To 8
    For $j = 0 To 8
        $aSudoku[$i][$j] = StringMid($sSudoku, $iCount - 8, 1)
        $iCount += 1
    Next
Next
_ArrayDisplay($aSudoku)
$aMixed_sudoku = _Mix_Sudoku($aSudoku, 16)
_ArrayDisplay($aMixed_sudoku)

Func _Mix_Sudoku($aInput, $iPass = 1)
	Local $iTarget, $iDirection, $iIndex1, $iIndex2, $iTemp, $iIndex_Square
	For $i = 1 To $iPass
		$iTarget = Random(0, 1, 1) ; выбор способа перемешивания
		$iDirection = Random(0, 1, 1) ; выбор направления перемешивания
		$iIndex1 = Random(0, 2, 1) ; выбор столбцов/строк для перемешивания
		$iIndex2 = Random(0, 2, 1)
		If $iIndex1 <> $iIndex2 Then
			If $iTarget Then ; перемешиваем столбцы/строки по три разом
				If $iDirection Then ; перемешиваем строки
					For $j = 0 To 8
						For $n = 0 To 2
							$iTemp = $aInput[$iIndex1 * 3 + $n][$j]
							$aInput[$iIndex1 * 3 + $n][$j] = $aInput[$iIndex2 * 3 + $n][$j]
							$aInput[$iIndex2 * 3 + $n][$j] = $iTemp
						Next
					Next
				Else ; перемешиваем столбцы
					For $j = 0 To 8
						For $n = 0 To 2
							$iTemp = $aInput[$j][$iIndex1 * 3 + $n]
							$aInput[$j][$iIndex1 * 3 + $n] = $aInput[$j][$iIndex2 * 3 + $n]
							$aInput[$j][$iIndex2 * 3 + $n] = $iTemp
						Next
					Next
				EndIf
			Else ; перемешиваем столбцы/строки по одному
				$iIndex_Square = Random(0, 2, 1) ; выбор квадрата внутри которого будет вестись перемешивание
				If $iDirection Then ; перемешиваем строки
					For $j = 0 To 8
						$iTemp = $aInput[$iIndex_Square * 3 + $iIndex1][$j]
						$aInput[$iIndex_Square * 3 + $iIndex1][$j] = $aInput[$iIndex_Square * 3 + $iIndex2][$j]
						$aInput[$iIndex_Square * 3 + $iIndex2][$j] = $iTemp
					Next
				Else ; перемешиваем столбцы
					For $j = 0 To 8
						$iTemp = $aInput[$j][$iIndex_Square * 3 + $iIndex1]
						$aInput[$j][$iIndex_Square * 3 + $iIndex1] = $aInput[$j][$iIndex_Square * 3 + $iIndex2]
						$aInput[$j][$iIndex_Square * 3 + $iIndex2] = $iTemp
					Next
				EndIf
			EndIf
		EndIf
	Next
	Return $aInput
EndFunc
 

Yashied

Модератор
Команда форума
Глобальный модератор
Сообщения
5 379
Репутация
2 714
Так тема решена или нет?

:whistle:
 
Верх