Неархитектурная задачка

[vlad]

Итак, играем в судоку. Никаких архитектурных изысков. Чистой воды алгоритмика и разминка для мозга (зашоренного этими самыми изысками и прочей фигней типа скрещивания ежа с ужом). В интернет не подглядваем. Делимся впечатлениями, меряемся и т.д.

Дано поле 9 x 9 клеток. В клетках цифры 1 - 9. Некоторые клетки открыты (даны цифры), остальные нужно открыть (определить цифру). Цифры в каждой колонке и ряде не повторяются. Кроме того, поле поделено на квадраты 3 x 3 и цифры в квадрате тоже не повторяются. Wikipedia: http://en.wikipedia.org/wiki/Sudoku.

Пример. Ввод:

Код: [Выделить]

*******18
**9*3****
*7*******
8**1*****
*****73**
2********
*3****96*
1**48****
***2*****

Вывод:

Код: [Выделить]

342976518
689531427
571842639
853194276
914627385
267358194
438715962
126489753
795263841

Мой вариант решения аттачнут.

[Илья Ермаков]

Моё решение:

Код: [Выделить]

StdCoder.Decode ..,1 ..3,....VuAVtBTtET9N9v9bOR7vPLPRRtP5fN0pN015Gm.sEP9Nbf
 9TvMB1sEG4.1OGRtP51xL,...
 jBaN..ta....BuETuPJ.V,Vh.c.Yj2U.UERakwaHhiYxhfhC6.Ey5EGGW5ws0oUMYVKYVHAYWY
 YPQUwyj4IN56czf,LL48FA0GAyl,ivzOEcZVKY,D775MJBMA5Mizf,NKyXN,SokqqmumYuqoGb
 z50,EmWkngz4YjdNzB6SJn2Wn5WF14FyPP,Sokq4BOOlnz1lPzzzHK2SaAoRbc2b63LunmzNDk
 X4qqKaExhnRidJgghAvj,tPMZvEqT1Wrk8Ldgz42WXxhgtzVcYzzz790gTdcQTvRakd5k9SGJa
 mFimF0mISG9qFy9s0SokqqmQeZZCvj,V.6Q3EmWkn.MzWFv4KqAVBv1jc8Hd8FtAZ77t6z9i,D
 OMPXGhgnhgo,.Ts.GK2S4G,YVev2ZUSIYSIYhwYw5w5YemhiiRgExhnRi.gTt16S..uSzzTmWk
 nE8Ux94E40jHIWH.kxXkWWLuKKrGKcyqtC5m5Ew.sPkLvzzHK2UI.216.0k,6.hs5H6xhs5HE7
 E.0UY3t1SUt5t1SUtL06.GK9CJRipGqsyrSV4.FfzzDN5.,6..fc,E.GK.6.7,fc0YVyzzY3.0
 EY2.fc1E.GK,6.0.kGGF.A.2U.E0kGe,B.5.0.kGu,1.0.7.9776.GK.2U.Yl0k8e0VdzzDNSo
 kqqm0EoyKtoiZJC1fQ9PMbHnaKwKKmoiVZBBPOl13vP1fQ7HsyqtAB6.2...vP.E.Yv5g.Pk5A
 .TE.6.....r9,6.op,E.2UY,E6qzzHK4qzzHK.E.EynzzH42en24.E..k2U.6N3U.2cyzzYB,2
 uwzzYJ.2U.6Nzzzzzz6N,...6.lj.2swzzYBU,EEuzzHK.0U...........GKyzzzzjz12.0E2
 E8nzzHa.EYnzzHK.6..........UY,yDH.d7zzDN3U.A,Q.YvvzzYJ..EajzzH42U.6Nz5,U.Y
 BYrvzzYB.YmxzzYV..........EwnzzHKyzzztzQsJRlgTk25z9ic6oMSwWmD0kor3SwWWD0ko
 X2isWmz,Xz28L,qsnjseWz,fz28L,qcBaU.TU0TlJ3V4bc0b.LQF.QF.gF.DCF3C06.zTFlzUv
 9yFcTZxz98z5QTtD0xPbDSFt5,Mub,L2l5QFFsl7gUNg.oz1k3L2..Vh.0.wz3Zz1iDws5jcwX
 .AxzU510kof0,sW6y5cQ3MXDbsn,8L,qcB8E5ck.di..2TIUy3uzjcwPT8Eziv3Lyi8Q2ge9ax
 9ic62kss17w.MXVD3LQFFcl4k3Lyi8AsUWDVcj5U.Anrrz7IutBU6Bl3Zz9icIor1..6yLQFds
 UlT0k33V9iiEQkyDVmJ.gj6Ql2KkAWXYkr4q0k3LJyDMxD.MRlzUxz.Zf.glIIe1ou9ii6QY2q
 mIL.gwRJsEMJLYx3X,wVAK,Qkx3X7wVCS.gF625AyH.iseGl,fz2UBaU.1CMy8Q2wV20gWzjiI
 wzp3WcBfzzzYxzp3Vzj0,EmiseWl5COczE,D.c3LQFVsU.LY10gF.LIAaMu8Q2isWWE.F81w3L
 J6CMxb.QlpZW1qz7.PA3Zy.h4FAFhC,zTRlszf93zL6oz,6NzL2WyYl3LCdkeic90gk1E.63.k
 3L3.PA,.52gEUJQl33W10QF.gF.,AT3C,yE0,O,.QF.gF.zDR3C0zTR62SmzzTmyDKAgcE.sW.
 MX.SQWE.2U9iQ0VJl,HAoLMa.6zcj..2TP84lhzzzzzzo,yWf82.isuWkEGM91P,kaW,.Gl,,.
 mM,..6z.6y.qM883M6Yu0UZH8....YT..Us11.bCkLQJV.k33V7YkK4KMH.E8..YF..YT.2T.P
 2k26pkmVEGqTLAHEaXLSHEsbLMDEiPLmDEubLsHE2f5lRStD.7xSNQ.DA,FR.NQSlR.NBSlg.t
 zSVj.dxR,w.NzSVw.twRFx.7xR,EEbLA9EGbr.WuwOP,muw8s00vwCv,GMx6UpH..tF,...
 jBaN..kG....BuETuPJ.,b.2c,EAFW4.lj.IWERakwaHhiYxhfhi1hhYRCVuAVtB.,6Ib7A.4o
 YQeoZgAxhb7J99SdfJHPNjvQCoruKu4qouqm8rtoedhAQeoxhmhgndFH9P9vQqorGqmmqt2ejJ
 ioRCBuPR9RbnVy4ZvPN9P9fQbHc8rr0rm8LuaqmCbIhAqorG4YeZldKKuGrm8rtYeZFdKLqKKt
 CbdJalQitRi7pBdONlna4Ks0rm8rt2.0..tT.777qT6EmwgVhhZN0hR.VM19s1Nc3Ns2HM2VM4
 jM9Jc2ns55Mwxf,fQ.5Mpxf,ZR.Vc0tjg16HTPM7nyPEuaaxrUkJBvj,NfR19PyETCFAmTe5kd
 yKqOrmgz,winxhgFmwVwgUCYVKYVH2ZVQUMpUkgU7QUlyj4oO960tDl3sIFvPjnyPEu.2.0...
 .Q.ouobWMB.0EWU.2UYpuob0d47e,E.G4IKYc9U.2UY3U.6............6HTPM7ndWqrSbHx
 hgpC,6.2..ky4.2.ty,9k4w,1E6E....Z.,6.Yc,Ewl5V.6N7aY3.2kyzzYZjyzzY3.2.2hyzz
 Y,VuAV,kVU.AzCVY3.njH..2U...5SJLAvjeJ5AldDOnzzzDNF17vzf.79uMNDSFVL.0UdTBws
 3ZS2Udr8gl3ZxE3Rgg.i56.TMV5.PAwdsUv9vyE4f.Csymy2yE5D.M35QTNb2C1wzpZxzjikzz
 pZycJ,GKoy.7vzEmyzWGz,rLuXEzGuzLIsDsy0T2ur5XKx6Ny57n8UBigsrfThf1je9aR6zPQF
 jDIF9bYgcBIGKoVBigsr9.6yF5SA2.HTFsl6.0koj0isWGz,Xz28L,qsnjse0z,fz28L,qcBaU
 .TU0Tl2gMYgNKeE3RggzjcoTkxVD5xRnmyjkTEMhFz81kmqsm.,EknLI5EmnLi5EqnLG9Ewnbc
 qjUCUsqjMCU6rjEC.,citfg1ckt9p1cmtP.dDT0k89E20Tyc.DOMMdpgxTjT5sd16S9Q.FP3dv
 j1.7sIT9PcebQc3z,HS.kYuKugoTCsxzURK.GEauaKDxH5s3Ar0E.0E...7.qvETzBPkR6,T8Q
 9fPOxoFBs.7vPRPNmwpzyzbrUF.0.hz....
 jBaN..MF....BuETuPJ.V0VM.2F2a0U.2.76Ib7AjtIf9NTvOfPEHGcCHM.2UAxhbtG9fQRPNN
 ndKKtOroCqmC52.Yz,YYY6,7S.bs2ncnCk5Cl7GFKzrKyiwTl,QeZBgmRgcpcjJirt,dt2bM4F
 q,yk7cgzP9HLyLN,Cpm4KtcE1vMLn14hA2a1Ah7YZ1oVwDr0oeVZBvj,FcNZvPPnybE40rrCrt
 AWJwUBIV9vD1qHCG80G38l94n,yE3Sl,yk0qwyGlj9E4KFyzO0CprmKvKaxrUkRgZZhgNzB6P5
 vPNnz1ll5UY3VbNzB6OZvPjnz5E6CrrmKvYAvj,7fR19P0U.E,k44.,vzzDNNs.A.,6.1.JRGF
 8TnN.Yc8U.2UYV...sNCrrm4QejZB0E.2U..vP.2.,EiTk0g,Tk.w,,U....76.2.wZ0.,EU7.
 6N.2qyzzYZpyzzY3.2.2nyzzY,VuAV,kU6.AzCVY3.0..QsJRlgTl13yyC,Anrrz7IutBU6Bl1
 3x9Sck1.8k,Ox2DJqbSJkzDIsjsV0D.M....3.Qkv3yFxVBS2Ql1Zx14z7Ii0glbTlH3x1Kz7I
 i0gFPA,,y.3yWb805AT3C0KrIjsmrpVLp3nC..1...c.Ud1iIsjsV..4...E,.5Y.wVCSY.2U.
 ..L2.P2E.nLVHUpBJ.1QHNE0Mu5.zTFFsW980Tsc981b9xLQFFsW9TL3C0Kp3nydSJfCMW1z3r
 xXLIs3U.6uXhzzzzHDg2UzjiczzpZxc7.GqzLL2yz8Em0p3LIqDMwb.QlJ3x1Kz7.P2ge6Ql2J
 s62cE3x2yzzzz7icYTl3ZR.L2.P2k,nLVt17A3sz.tO.GqzL5U1ijYLVDglY.GyzLLoV0D.7vz
 .wz33ycDVyzzz90ka0ToPMzzzzDsy0jDYl8U1ijkDeDYlwwzzzz1iDXG81w3LJ6WM,qsmGTjyp
 hqJVnUEG6rLg5E8rLq5ECrLy5EIrbMqj.D.eTyaP,Guy6cvX0wcVhhZdZBRunS,36v56OLy.NP
 t36QdhT2U.2.fe1...
 --- end of encoding ---

Распаковать кодовые файлы в ББ 1.6 и выполнить команды:
!P307SudokuCmds.Load
0 0 0 0 0 0 0 1 8
0 0 9 0 3 0 0 0 0
0 7 0 0 0 0 0 0 0
8 0 0 1 0 0 0 0 0
0 0 0 0 0 7 3 0 0
2 0 0 0 0 0 0 0 0
0 3 0 0 0 0 9 6 0
1 0 0 4 8 0 0 0 0
0 0 0 2 0 0 0 0 0

!P307SudokuCmds.Solve
!P307SudokuCmds.Show

Даёт то же решение, что и у Влада.
Время исполнения: 2227 msec

P.S. Программу Влада не запустил, так как под Wine выдаёт fixme:heap:HeapSetInformation (nil) 1 (nil) 0 и зависает. Виртуалку стартовать нехоцца...

[Илья Ермаков]

Ы, должен стоять i21sysIn.
http://oberoncore.ru/bbcc/subs/i21sys/start

[valexey]

Но вообще, задача NP-полна, так что решение у всех будет не полиномиальное. Следовательно меряться можно только константными множителями да коэффициентами при экспоненте :-)

[Илья Ермаков]

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

[valexey]

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

Я тоже :-) Помню только что она NP-полна (поскольку NP-задачами  интересовался).

[vlad]

Даёт то же решение, что и у Влада.
Время исполнения: 2227 msec

P.S. Программу Влада не запустил, так как под Wine выдаёт fixme:heap:HeapSetInformation (nil) 1 (nil) 0 и зависает. Виртуалку стартовать нехоцца...

У меня < секунды. Моя программа ждет stdin в процитированном формате - обязано работать, там ничего странного/нестандартного нет.

Твой вариант чуть позже посмотрю. И опубликую свой, если никто больше не присоединится.

[vlad]

Но вообще, задача NP-полна, так что решение у всех будет не полиномиальное. Следовательно меряться можно только константными множителями да коэффициентами при экспоненте :-)

Ну вообще совсем тупой перебор там не работает. Так что за коэффициенты можно еще побороться. Вариант Ильи еще не смотрел, но какой-то простор для творчества там есть, как мне кажется.

[valexey]

Но вообще, задача NP-полна, так что решение у всех будет не полиномиальное. Следовательно меряться можно только константными множителями да коэффициентами при экспоненте :-)

Ну вообще совсем тупой перебор там не работает. Так что за коэффициенты можно еще побороться. Вариант Ильи еще не смотрел, но какой-то простор для творчества там есть, как мне кажется.

Ну будет не тупой перебор, а тупой перебор с эвристиками (которые будут пытаться отрубить максимум вариантов как можно раньше) :-)

[valexey]

Вообще задачка (точнее метод решения) классическая. Настолько, что аж в журнале "практика функционального программирования" подробно разбиралась. Не судоку конечно, а на примере какой то другой задачи. На таких задачах функциональщики обычно любят показывать превосходство ФЯ над ИЯ :-)

В общем когда доеду до города (я сейчас в поезде), попробую что то накатать на каком-нибудь Go :-)

А от geniepro ждем решение на хаскелле :-)

[Илья Ермаков]

Как раз размышлял над тем, как это будет выглядеть на ФП.
Там вместо модификации данных придётся использовать на каждый чих копирование, или я чего-то не понимаю в ФП

[valexey]

я чего-то не понимаю в ФП

Угу :-)

[vlad]

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

Я тоже никогда... Но таки попала в мое поле зрения заветная газетка Причем там сразу был какой-то большой уровень сложности, так что чисто аналитически оно не решалось - нужно было разные варианты подбирать. Плюнул, и не сползая с дивана написал програмку (на нетбуке, в ФАРе и без отладичка)

[vlad]

Распаковать кодовые файлы в ББ 1.6 и выполнить команды:
!P307SudokuCmds.Load
0 0 0 0 0 0 0 1 8
0 0 9 0 3 0 0 0 0
0 7 0 0 0 0 0 0 0
8 0 0 1 0 0 0 0 0
0 0 0 0 0 7 3 0 0
2 0 0 0 0 0 0 0 0
0 3 0 0 0 0 9 6 0
1 0 0 4 8 0 0 0 0
0 0 0 2 0 0 0 0 0

Получаю "string expected" в логе. Что я делаю не так?

[vlad]

А от geniepro ждем решение на хаскелле :-)

И еще O-7 не забудте Динамические массивы не нужны