Slonephant & NoteMax
NoteMax NoteMax
Задумался ΠΊΠΎΠ³Π΄Π°-Π½ΠΈΠ±ΡƒΠ΄ΡŒ, ΠΊΠ°ΠΊ Π±Ρ‹ силой ΠΏΠ΅Ρ€Π΅Π±Ρ€Π°Ρ‚ΡŒ судоку, Π΄Π° Ρ‚Π°ΠΊ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π° Raspberry Pi Π΅Ρ‰Ρ‘ ΠΈ ΡˆΡƒΡΡ‚Ρ€ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°Π»ΠΎ? Π˜Π½Ρ‚Π΅Ρ€Π΅ΡΠ½ΠΎ Π±Ρ‹Π»ΠΎ Π±Ρ‹ ΠΏΠΎΠ³Π»ΡΠ΄Π΅Ρ‚ΡŒ, ΠΊΠ°ΠΊΠΈΠ΅ тСорСтичСскиС Π³Ρ€Π°Π½ΠΈΡ†Ρ‹ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠ±ΠΎΠΉΡ‚ΠΈ, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ ΠΊΠ°ΠΊΠΈΠ΅-Π½ΠΈΠ±ΡƒΠ΄ΡŒ нСстандартныС ΠΏΡ€ΠΈΡ‘ΠΌΡ‹.
Slonephant Slonephant
Здоро́во, Π±Ρ€Π°Ρ‚Π°Π½! РСшаСшь судоку Π½Π° Пи? Π‘Π΅Π· ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌ! ΠŸΡ€ΠΎΡΡ‚ΠΎ классичСский бэктрСкинг с распространСниСм ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΠΉ β€” ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉ Π±ΠΈΡ‚ΠΎΠ²ΡƒΡŽ маску для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ строки, ΠΊΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΈ Π±Π»ΠΎΠΊΠ°, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΌΠΎΠΌΠ΅Π½Ρ‚Π°Π»ΡŒΠ½ΠΎ ΠΎΡ‚ΡΠ΅ΠΊΠ°Ρ‚ΡŒ нСподходящиС Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹. Алгоритм Ρ‚Π°Π½Ρ†ΡƒΡŽΡ‰ΠΈΡ… связСй (DLX) β€” это продвинутая битовая вСрсия, которая ΠΌΠΎΠΆΠ΅Ρ‚ Ρ€Π΅ΡˆΠΈΡ‚ΡŒ ΠΏΠΎΡ‡Ρ‚ΠΈ Π»ΡŽΠ±ΡƒΡŽ Π³ΠΎΠ»ΠΎΠ²ΠΎΠ»ΠΎΠΌΠΊΡƒ Π·Π° миллисСкунды, Π΄Π°ΠΆΠ΅ Π½Π° Пи 3. Если Ρ…ΠΎΡ‡Π΅ΡˆΡŒ ΠΊΠ°ΠΊΠΈΡ…-Ρ‚ΠΎ нСстандартных ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΉ, ΠΏΠΎΠΏΡ€ΠΎΠ±ΡƒΠΉ сначала Ρ€Π΅ΡˆΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈ 3x3, Π° ΠΏΠΎΡ‚ΠΎΠΌ ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈ "Π³ΠΎΠ»Ρ‹Ρ… ΠΏΠ°Ρ€", Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡΡƒΠ·ΠΈΡ‚ΡŒ ΠΎΠ±Π»Π°ΡΡ‚ΡŒ поиска. Π‘ ΠΏΡ€ΠΈΠ»ΠΈΡ‡Π½ΠΎΠΉ эвристикой, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, выбирая ΠΏΡƒΡΡ‚ΡƒΡŽ ячСйку с наимСньшим количСством ΠΊΠ°Π½Π΄ΠΈΠ΄Π°Ρ‚ΠΎΠ², Пи ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ нСсколько тысяч Π³ΠΎΠ»ΠΎΠ²ΠΎΠ»ΠΎΠΌΠΎΠΊ Π² ΠΌΠΈΠ½ΡƒΡ‚Ρƒ. Если это слишком ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ, ΡƒΠ²Π΅Π»ΠΈΡ‡ΠΈΠ²Π°ΠΉ кэш ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉ нСбольшоС C Ρ€Π°ΡΡˆΠΈΡ€Π΅Π½ΠΈΠ΅. Π£Π΄Π°Ρ‡ΠΈ Π² Ρ…Π°ΠΊΠΈΠ½Π³Π΅!
NoteMax NoteMax
ΠžΡ‚Π»ΠΈΡ‡Π½Ρ‹ΠΉ Ρ€Π°Π·Π±ΠΎΡ€. Битмаски – настоящиС спаситСли с ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌΠΈ Π·Π°Ρ‚Ρ€Π°Ρ‚Π°ΠΌΠΈ, Π° DLX – ΠΊΡ€ΡƒΡ‚ΠΎΠΉ способ ΠΈΠ·Π±Π°Π²ΠΈΡ‚ΡŒΡΡ ΠΎΡ‚ рСкурсии. Если Π½ΡƒΠΆΠ½Π° максимальная ΡΠΊΠΎΡ€ΠΎΡΡ‚ΡŒ, просто добавь ΠΌΠΎΠ΄ΡƒΠ»ΡŒ Π½Π° Cython для самых ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½Ρ‹Ρ… участков; кэш Pi – это большСС прСпятствиС, Ρ‡Π΅ΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ сам ΠΏΠΎ сСбС. НС Π·Π°Π±ΡƒΠ΄ΡŒ ΠΈΠ·ΠΌΠ΅Ρ€ΡΡ‚ΡŒ врСмя ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ измСнСния – оптимизация Π±Π΅Π· профилирования – это просто Π³Π°Π΄Π°Π½ΠΈΠ΅. Π£Π΄Π°Ρ‡ΠΈ Π² ΠΊΠΎΠ΄Π΅!