Contest 6 - Sudoku solver - Discussion

Quote:

---

Originally Posted by eyeRmonkey

I threw together a program to split these into .msk files.

---

It seems that I have a LOONG way to go...

Code:

---

dukuso's_hardest_000.msk    SOLVED in 1,814.934859 milliseconds !
dukuso's_hardest_001.msk    SOLVED in 20,988.223364 milliseconds !
dukuso's_hardest_002.msk    SOLVED in 1,084.403185 milliseconds !
dukuso's_hardest_003.msk    SOLVED in 7,949.478775 milliseconds !
dukuso's_hardest_004.msk    SOLVED in 517.331672 milliseconds !
dukuso's_hardest_005.msk    SOLVED in 688.069573 milliseconds !
dukuso's_hardest_006.msk    SOLVED in 28.336004 milliseconds !
dukuso's_hardest_007.msk    SOLVED in 34.762239 milliseconds !
dukuso's_hardest_008.msk    SOLVED in 116.598339 milliseconds !
dukuso's_hardest_009.msk    SOLVED in 180.910982 milliseconds !
dukuso's_hardest_010.msk    SOLVED in 1,317.542872 milliseconds !
dukuso's_hardest_011.msk    SOLVED in 816.710504 milliseconds !
dukuso's_hardest_012.msk    SOLVED in 63.958408 milliseconds !
dukuso's_hardest_013.msk    SOLVED in 66.043031 milliseconds !
dukuso's_hardest_014.msk    SOLVED in 29.587839 milliseconds !
dukuso's_hardest_015.msk    SOLVED in 349.861784 milliseconds !
dukuso's_hardest_016.msk    SOLVED in 822.774403 milliseconds !
dukuso's_hardest_017.msk    SOLVED in 1,103.592216 milliseconds !
dukuso's_hardest_018.msk    SOLVED in 7,181.811375 milliseconds !
dukuso's_hardest_019.msk    SOLVED in 1,841.077288 milliseconds !
dukuso's_hardest_020.msk    SOLVED in 478.773420 milliseconds !
dukuso's_hardest_021.msk    SOLVED in 127.953134 milliseconds !
dukuso's_hardest_022.msk    SOLVED in 1,874.943324 milliseconds !
dukuso's_hardest_023.msk    SOLVED in 1,569.060034 milliseconds !
dukuso's_hardest_024.msk    SOLVED in 3,256.705810 milliseconds !
dukuso's_hardest_025.msk    SOLVED in 1,184.486576 milliseconds !
dukuso's_hardest_026.msk    SOLVED in 1,127.795851 milliseconds !
dukuso's_hardest_027.msk    SOLVED in 525.698378 milliseconds !
dukuso's_hardest_028.msk    SOLVED in 641.548018 milliseconds !
dukuso's_hardest_029.msk    SOLVED in 4,680.740709 milliseconds !
dukuso's_hardest_030.msk    SOLVED in 2.567365 milliseconds !
dukuso's_hardest_031.msk    SOLVED in 2,191.370691 milliseconds !
dukuso's_hardest_032.msk    SOLVED in 1,568.653279 milliseconds !
dukuso's_hardest_033.msk    SOLVED in 926.920042 milliseconds !
dukuso's_hardest_034.msk    SOLVED in 72.577939 milliseconds !
dukuso's_hardest_035.msk    SOLVED in 1,122.788511 milliseconds !
dukuso's_hardest_036.msk    SOLVED in 17,217.268955 milliseconds !
dukuso's_hardest_037.msk    SOLVED in 3.290642 milliseconds !
dukuso's_hardest_038.msk    SOLVED in 158.018407 milliseconds !
dukuso's_hardest_039.msk    SOLVED in 2,711.075849 milliseconds !
dukuso's_hardest_040.msk    SOLVED in 4,585.880887 milliseconds !
dukuso's_hardest_041.msk    SOLVED in 235.107255 milliseconds !
dukuso's_hardest_042.msk    SOLVED in 7,684.072696 milliseconds !
dukuso's_hardest_043.msk    SOLVED in 2,694.652533 milliseconds !
dukuso's_hardest_044.msk    SOLVED in 94.306679 milliseconds !
dukuso's_hardest_045.msk    SOLVED in 3.803835 milliseconds !
dukuso's_hardest_046.msk    SOLVED in 1,171.015031 milliseconds !
dukuso's_hardest_047.msk    SOLVED in 492.836939 milliseconds !
dukuso's_hardest_048.msk    SOLVED in 1,336.245249 milliseconds !
dukuso's_hardest_049.msk    SOLVED in 1,851.328311 milliseconds !
dukuso's_hardest_050.msk    SOLVED in 1,563.441443 milliseconds !
dukuso's_hardest_051.msk    SOLVED in 229.470226 milliseconds !
dukuso's_hardest_052.msk    SOLVED in 1,751.772362 milliseconds !
dukuso's_hardest_053.msk    SOLVED in 5,373.513952 milliseconds !
dukuso's_hardest_054.msk    SOLVED in 3.258794 milliseconds !
dukuso's_hardest_055.msk    SOLVED in 2,124.089794 milliseconds !
dukuso's_hardest_056.msk    SOLVED in 362.830751 milliseconds !
dukuso's_hardest_057.msk    SOLVED in 697.073511 milliseconds !
dukuso's_hardest_058.msk    SOLVED in 3,070.439399 milliseconds !
dukuso's_hardest_059.msk    SOLVED in 31.392537 milliseconds !
dukuso's_hardest_060.msk    SOLVED in 592.567491 milliseconds !
dukuso's_hardest_061.msk    SOLVED in 131.283725 milliseconds !
dukuso's_hardest_062.msk    SOLVED in 5.294528 milliseconds !
dukuso's_hardest_063.msk    SOLVED in 186.337370 milliseconds !
dukuso's_hardest_064.msk    SOLVED in 499.935327 milliseconds !
dukuso's_hardest_065.msk    SOLVED in 2,933.956690 milliseconds !
dukuso's_hardest_066.msk    SOLVED in 3,703.020635 milliseconds !
dukuso's_hardest_067.msk    SOLVED in 81.654791 milliseconds !
dukuso's_hardest_068.msk    SOLVED in 1,566.145418 milliseconds !
dukuso's_hardest_069.msk    SOLVED in 16.566351 milliseconds !
dukuso's_hardest_070.msk    SOLVED in 6,697.108990 milliseconds !
dukuso's_hardest_071.msk    SOLVED in 138.773783 milliseconds !
dukuso's_hardest_072.msk    SOLVED in 3,035.243027 milliseconds !
dukuso's_hardest_073.msk    SOLVED in 2,812.802465 milliseconds !
dukuso's_hardest_074.msk    SOLVED in 1,645.052933 milliseconds !
dukuso's_hardest_075.msk    SOLVED in 71.782028 milliseconds !
dukuso's_hardest_076.msk    SOLVED in 1,567.040783 milliseconds !
dukuso's_hardest_077.msk    SOLVED in 4.113372 milliseconds !
dukuso's_hardest_078.msk    SOLVED in 160.286852 milliseconds !
dukuso's_hardest_079.msk    SOLVED in 209.047519 milliseconds !
dukuso's_hardest_080.msk    SOLVED in 1,637.917668 milliseconds !
dukuso's_hardest_081.msk    SOLVED in 158.578255 milliseconds !
dukuso's_hardest_082.msk    SOLVED in 106.245906 milliseconds !
dukuso's_hardest_083.msk    SOLVED in 422.900117 milliseconds !
dukuso's_hardest_084.msk    SOLVED in 586.114716 milliseconds !
dukuso's_hardest_085.msk    SOLVED in 343.262901 milliseconds !
dukuso's_hardest_086.msk    SOLVED in 276.229521 milliseconds !
dukuso's_hardest_087.msk    SOLVED in 100.897181 milliseconds !
dukuso's_hardest_088.msk    SOLVED in 585.171858 milliseconds !
dukuso's_hardest_089.msk    SOLVED in 75.375781 milliseconds !
dukuso's_hardest_090.msk    SOLVED in 5,191.501993 milliseconds !
dukuso's_hardest_091.msk    SOLVED in 1,175.437940 milliseconds !
dukuso's_hardest_092.msk    SOLVED in 2.269283 milliseconds !
dukuso's_hardest_093.msk    SOLVED in 2,440.270202 milliseconds !
dukuso's_hardest_094.msk    SOLVED in 7,537.211852 milliseconds !
dukuso's_hardest_095.msk    SOLVED in 327.713718 milliseconds !
dukuso's_hardest_096.msk    SOLVED in 111.759176 milliseconds !
dukuso's_hardest_097.msk    SOLVED in 1,912.464852 milliseconds !
dukuso's_hardest_098.msk    SOLVED in 38.651560 milliseconds !
dukuso's_hardest_099.msk    SOLVED in 19.043202 milliseconds !
Files Processed: 100, Total Solved: 100, Total time: 172,901.809588, Average Time: 1,729.018096

---

Quote:

---

Originally Posted by eyeRmonkey

Well, thanks for giving me about 20 tips as to how to modify my program to me more like yours. ;)

---

Could you highlight those 20 tips somehow ? Cuz I didn’t get any tips from anyone, maybe I’m just too blind to see them.

Quote:

---

Originally Posted by CVMichael

Could you highlight those 20 tips somehow ? Cuz I didn’t get any tips from anyone, maybe I’m just too blind to see them.

---

:lol: Well maybe its just because my program is so messed up to start with, but he uses a bunch of things that seem much faster that what I am using. I'm not gonna tell you if you don't know. You probably don't see them because you are already doing things similar to what he posted.

I get the feeling you are doing something wrong because nothing takes me more than 20 ms in the IDE and nothing takes more than 6 ms in .EXE.

I wish this contest wasn't a contest because I am so curious to see how everyone is doing what they are doing. I guess I will just have to wait and see.

I've been giving so many tips here that it is making me sick! You can conclude all kinds of stuff from what I've said. A programmer needs his social skills too!

eyeRmonkey: I could do mass output while doing benchmarking for example. Because of the interface, it is easy to use the solver as I like. Currently the visual view isn't linked to my benchmarker in any way.


More sudokus! These include the hardest I've found so far. Beware the minimal sudokus!

You can clearly see when my backtracker kicks in...

Code:

---

000.txt - 2.5243 ms
001.txt - 1.6399 ms
002.txt - 3.6608 ms
003.txt - 3.8343 ms
004.txt - 1.3488 ms
005.txt - 4.3369 ms
006.txt - 1.9092 ms
007.txt - 2.1768 ms
008.txt - 2.3430 ms
009.txt - 1.8094 ms
010.txt - 1.4924 ms
011.txt - 2.3746 ms
012.txt - 1.9064 ms
013.txt - 2.5506 ms
014.txt - 1.8986 ms
015.txt - 1.5441 ms
016.txt - 1.4773 ms
017.txt - 1.4980 ms
018.txt - 1.6913 ms
019.txt - 1.5793 ms
020.txt - 1.2935 ms
021.txt - 1.2429 ms
022.txt - 1.0985 ms
023.txt - 1.1085 ms
024.txt - 2,165.0185 ms
025.txt - 1.2644 ms
026.txt - 1.5725 ms
027.txt - 2.4539 ms
028.txt - 3.1381 ms
029.txt - 1.6276 ms
030.txt - 2.3740 ms
031.txt - 2.1142 ms
032.txt - 2.0883 ms
033.txt - 2.2978 ms
034.txt - 2.6434 ms
035.txt - 1.0959 ms
036.txt - 1.2834 ms
037.txt - 1.5156 ms
038.txt - 2.1260 ms
039.txt - 1.0806 ms
040.txt - 13.0533 ms
041.txt - 1.6441 ms
042.txt - 2.5411 ms
043.txt - 14.7834 ms
044.txt - 1.7553 ms
045.txt - 1.5991 ms
046.txt - 1.5955 ms
047.txt - 1.3334 ms
048.txt - 1.5172 ms
049.txt - 1.2474 ms
050.txt - 1.4616 ms
051.txt - 1.7994 ms
052.txt - 1.3764 ms
053.txt - 1.3692 ms
054.txt - 1.9201 ms
055.txt - 1.4960 ms
056.txt - 6.2961 ms
057.txt - 3.2194 ms
058.txt - 1.8399 ms
059.txt - 1.3069 ms
060.txt - 1.1180 ms
061.txt - 1.3627 ms
062.txt - 1.1957 ms
063.txt - 1.0683 ms
064.txt - 1.8108 ms
065.txt - 1.1515 ms
066.txt - 1.4250 ms
067.txt - 4.3992 ms
068.txt - 1.9536 ms
069.txt - 1.2256 ms
070.txt - 1.1806 ms
071.txt - 1.5387 ms
072.txt - 1.6038 ms
073.txt - 2.5154 ms
074.txt - 1.5642 ms
075.txt - 4.5545 ms
076.txt - 2.0142 ms
077.txt - 13.1447 ms
078.txt - 2.1045 ms
079.txt - 1.8279 ms
080.txt - 1.3678 ms
081.txt - 1.2217 ms
082.txt - 1.5798 ms
083.txt - 1.3865 ms
084.txt - 1.3111 ms
085.txt - 1.7122 ms
086.txt - 2.7124 ms
087.txt - 1.4714 ms
088.txt - 2.0648 ms
089.txt - 1.4982 ms
090.txt - 59.5964 ms
091.txt - 23.1236 ms
092.txt - 1.3370 ms
093.txt - 14.7910 ms
094.txt - 1.5555 ms
095.txt - 46.4939 ms
096.txt - 2.4076 ms
097.txt - 1.5220 ms
098.txt - 8.4944 ms
099.txt - 23.8248 ms
100.txt - 1.4287 ms
101.txt - 1.4720 ms
102.txt - 1.5854 ms
103.txt - 1.3457 ms
104.txt - 1.4080 ms
105.txt - 1.5963 ms
106.txt - 2.0964 ms
107.txt - 1.5874 ms
108.txt - 1.4552 ms
109.txt - 1.6097 ms
110.txt - 1.8703 ms
111.txt - 3.0954 ms
112.txt - 16.4867 ms
113.txt - 67.2197 ms
114.txt - 1.7905 ms
115.txt - 1.5921 ms
116.txt - 1.8402 ms
117.txt - 35.7082 ms
118.txt - 389.6585 ms
119.txt - 1.6999 ms
120.txt - 2.8425 ms
121.txt - 586.9436 ms
122.txt - 527.5914 ms
123.txt - 123.2903 ms
124.txt - 1.8921 ms
125.txt - 3.0135 ms
126.txt - 1.5739 ms
127.txt - 1.2356 ms
128.txt - 10.4108 ms
129.txt - 4.1494 ms
130.txt - 2.7478 ms
131.txt - 1,927.2868 ms
132.txt - 1,105.3690 ms
133.txt - 1.2678 ms
134.txt - 1.2742 ms
135.txt - 1.3024 ms
136.txt - 1.5410 ms
137.txt - 1.2650 ms
138.txt - 1.1406 ms
139.txt - 1.4091 ms
140.txt - 1.7388 ms
141.txt - 1.5860 ms
142.txt - 7.2414 ms
143.txt - 4.7660 ms
144.txt - 18.2314 ms
145.txt - 1.2354 ms
146.txt - 1.6661 ms
147.txt - 2.3070 ms
148.txt - 2.0656 ms
149.txt - 4.6436 ms
150.txt - 6.8964 ms
151.txt - 3.2093 ms
152.txt - 1.4150 ms
153.txt - 1.1180 ms
154.txt - 27.4661 ms
155.txt - 1.4561 ms
156.txt - 1.5779 ms
157.txt - 1.2940 ms
158.txt - 1.3762 ms
159.txt - 1.0985 ms
160.txt - 3.2728 ms
161.txt - 1.3046 ms
162.txt - 1.1054 ms
163.txt - 1.0675 ms
164.txt - 1.2166 ms
165.txt - 1.0627 ms
166.txt - 1.4940 ms
167.txt - 1.2060 ms
168.txt - 2.3274 ms
169.txt - 1.1971 ms
170.txt - 1.3309 ms
171.txt - 1.9651 ms
172.txt - 1.9438 ms
173.txt - 237.1480 ms
174.txt - 1.3985 ms
175.txt - 1.1680 ms
176.txt - 33.5540 ms
177.txt - 3.2552 ms
178.txt - 1.4963 ms
179.txt - 1.0946 ms
180.txt - 1.2113 ms
181.txt - 5.6348 ms
182.txt - 6.2782 ms
183.txt - 26.4176 ms
184.txt - 26.5500 ms
185.txt - 68.9856 ms
186.txt - 4.4967 ms
187.txt - 1.6952 ms
188.txt - 670.1908 ms
189.txt - 198.3515 ms
190.txt - 401.3748 ms
191.txt - 479.8657 ms
192.txt - 1.7092 ms
193.txt - 3.3415 ms
194.txt - 2.2631 ms
195.txt - 2.6632 ms
196.txt - 4.6738 ms
197.txt - 1.7681 ms
198.txt - 7.4711 ms
199.txt - 2.3598 ms
200.txt - 1.1496 ms
201.txt - 1.2275 ms
202.txt - 17.7031 ms
203.txt - 1.1018 ms
204.txt - 1.2094 ms
205.txt - 1.2460 ms
206.txt - 3.7854 ms
207.txt - 1.3362 ms
208.txt - 1.2080 ms
209.txt - 1.2155 ms
210.txt - 2.7040 ms
211.txt - 4.0019 ms
212.txt - 1.2261 ms
213.txt - 1.2817 ms
214.txt - 1.5742 ms
215.txt - 1.3999 ms
216.txt - 1.4611 ms
217.txt - 1.9525 ms
218.txt - 1.4502 ms
219.txt - 1.3136 ms
220.txt - 9.6685 ms
221.txt - 1.3965 ms
222.txt - 1.5614 ms
223.txt - 1.0677 ms
224.txt - 1.1895 ms
225.txt - 1.3044 ms
226.txt - 1.1222 ms
227.txt - 1.6315 ms
228.txt - 1.1457 ms
229.txt - 1.4474 ms
230.txt - 1.3091 ms
231.txt - 2.2145 ms
232.txt - 2.2321 ms
233.txt - 214.5468 ms
234.txt - 0.9127 ms
235.txt - 0.9163 ms
236.txt - 1.1158 ms
237.txt - 1.5547 ms
238.txt - 1.4602 ms
239.txt - 1.9835 ms
240.txt - 1.1862 ms
241.txt - 1.7664 ms
242.txt - 1.3854 ms
243.txt - 3.3957 ms
244.txt - 1.9391 ms
245.txt - 2.2852 ms
246.txt - 1.6265 ms
247.txt - 3.0825 ms
248.txt - 2.3813 ms
249.txt - 1.6485 ms
250.txt - 1.2588 ms
251.txt - 1.5019 ms
252.txt - 1.4295 ms
253.txt - 1.9860 ms
254.txt - 1.3041 ms
255.txt - 1.2560 ms
256.txt - 0.9501 ms
257.txt - 2.3631 ms
258.txt - 1.4809 ms
259.txt - 4.0541 ms
260.txt - 4.0631 ms
261.txt - 2.0218 ms
262.txt - 2.0195 ms
263.txt - 2.2469 ms
264.txt - 1.9678 ms
265.txt - 2.0215 ms
266.txt - 2.8962 ms
267.txt - 109.0035 ms
268.txt - 1.7986 ms
269.txt - 3.2462 ms
270.txt - 1.9257 ms
271.txt - 1.6617 ms
272.txt - 1.4591 ms
273.txt - 37.5411 ms
274.txt - 86.3216 ms
275.txt - 1.5591 ms
276.txt - 23.0764 ms
277.txt - 24.5313 ms
278.txt - 242.9060 ms
279.txt - 53.6814 ms
280.txt - 1.6443 ms
281.txt - 2.1732 ms
282.txt - 187.9719 ms
283.txt - 227.5588 ms
284.txt - 0.9300 ms
285.txt - 1.0236 ms
286.txt - 0.9417 ms
287.txt - 0.9303 ms
288.txt - 1.2446 ms
289.txt - 1.2625 ms
290.txt - 1.8128 ms
291.txt - 1.1476 ms
292.txt - 1.3999 ms
293.txt - 4.5310 ms
294.txt - 2.4685 ms
295.txt - 1.1985 ms
296.txt - 1.6913 ms
297.txt - 1.8972 ms
298.txt - 1.1985 ms
299.txt - 1.2133 ms
300.txt - 3.6063 ms
301.txt - 1.6997 ms
302.txt - 1.7290 ms
303.txt - 2.3475 ms
304.txt - 3.5611 ms
305.txt - 1.2546 ms
306.txt - 1.7466 ms
307.txt - 1.2566 ms
308.txt - 1.4812 ms
309.txt - 1.2963 ms
310.txt - 5.8952 ms
311.txt - 1.4616 ms
312.txt - 1.2756 ms
313.txt - 1.7656 ms
314.txt - 1.3309 ms
315.txt - 1.9461 ms
316.txt - 1.5927 ms
317.txt - 1.7273 ms
318.txt - 6.4869 ms
319.txt - 6.9157 ms
320.txt - 2.3590 ms
321.txt - 1.4340 ms
322.txt - 1.1091 ms
323.txt - 5.1484 ms
324.txt - 11.4285 ms
325.txt - 21,115.4932 ms
326.txt - 1.9827 ms
327.txt - 1.1555 ms
328.txt - 1.9019 ms
329.txt - 1.7242 ms
330.txt - 1.1974 ms
331.txt - 1.2722 ms
332.txt - 2.0813 ms
333.txt - 1.2010 ms
334.txt - 2.2743 ms
335.txt - 4.8221 ms
336.txt - 2.0695 ms
337.txt - 2.2869 ms
338.txt - 2.7138 ms
339.txt - 5.9994 ms
340.txt - 1.7100 ms
341.txt - 2.1274 ms
342.txt - 1.3647 ms
343.txt - 1.7723 ms
344.txt - 21.6606 ms
345.txt - 1.5130 ms
346.txt - 1.4669 ms
347.txt - 1.4276 ms
348.txt - 2.6095 ms
349.txt - 2.7621 ms
350.txt - 2.2874 ms
351.txt - 3.0127 ms
352.txt - 2.6696 ms
353.txt - 1.3521 ms
354.txt - 1.5318 ms
355.txt - 1.8106 ms
356.txt - 1.4516 ms
357.txt - 1.4767 ms
358.txt - 1.2449 ms
359.txt - 1.9022 ms
360.txt - 361.5337 ms
361.txt - 236.3859 ms
362.txt - 1.9494 ms
363.txt - 2.6196 ms
364.txt - 1.4915 ms
365.txt - 2.5825 ms
366.txt - 1.7539 ms
367.txt - 1.4435 ms
368.txt - 1.7161 ms
369.txt - 1.7969 ms
370.txt - 4.7042 ms
371.txt - 3.0537 ms
372.txt - 1.8821 ms
373.txt - 1.7731 ms
374.txt - 1.9718 ms
375.txt - 1.4703 ms
376.txt - 0.9954 ms
377.txt - 4.3137 ms
378.txt - 1.2261 ms
379.txt - 1.3312 ms
380.txt - 1.0878 ms
381.txt - 1.3024 ms
382.txt - 2.3120 ms
383.txt - 2.0609 ms
384.txt - 1.1166 ms
385.txt - 2.3299 ms
386.txt - 2.4400 ms
387.txt - 1.1203 ms
388.txt - 2.0933 ms
389.txt - 1.2493 ms
390.txt - 1.1144 ms
391.txt - 1.2513 ms
392.txt - 4.1773 ms
393.txt - 3.7508 ms
394.txt - 3.3091 ms
395.txt - 1.0767 ms
396.txt - 2.2911 ms
397.txt - 2.5045 ms
398.txt - 1.7458 ms
399.txt - 9.1302 ms
400.txt - 1.5270 ms
401.txt - 1.2694 ms
402.txt - 1.5899 ms
403.txt - 6.9984 ms
404.txt - 1.4055 ms
405.txt - 3.1686 ms
406.txt - 2.2707 ms
407.txt - 1.2387 ms
408.txt - 2.4092 ms
409.txt - 1.5748 ms
410.txt - 1.8944 ms
411.txt - 1.7974 ms
412.txt - 1.4086 ms
413.txt - 1.2680 ms
414.txt - 1.5644 ms
415.txt - 1.6050 ms
416.txt - 1.6125 ms
417.txt - 1.3060 ms
418.txt - 2.2151 ms
419.txt - 1.3884 ms
420.txt - 3.7485 ms
421.txt - 2.0447 ms
422.txt - 1.2345 ms
423.txt - 1.7072 ms
424.txt - 1.8807 ms
425.txt - 4.9638 ms
426.txt - 2.1145 ms
427.txt - 2.5554 ms
428.txt - 1.9374 ms
429.txt - 2.1673 ms
430.txt - 1.4885 ms
431.txt - 17.9185 ms
432.txt - 5.6007 ms
433.txt - 2.5783 ms
434.txt - 1.8189 ms
435.txt - 1.8069 ms
436.txt - 1.0962 ms
437.txt - 1.9885 ms
438.txt - 1.3789 ms
439.txt - 1.1270 ms
440.txt - 1.5904 ms
441.txt - 1.7938 ms
442.txt - 1.3627 ms
443.txt - 1.2074 ms
444.txt - 1.4555 ms
445.txt - 2.3179 ms
446.txt - 2.1503 ms
447.txt - 1.0613 ms
448.txt - 1.8025 ms
449.txt - 1.2951 ms
450.txt - 1.7851 ms
Files Processed: 451, Total Solved: 451, Total time: 33,173.741076, Average Time: 73.555967

---

I'm at the point of giving up on this thing, I've spent a TON of time on this, and I didn't make much improvement in speed.

I give you a BIG tip: make your backtracker use the same code you use for logic. My history: I first made my fast logic thingy, then I made a different backtracker, then I combined the both, then I saw I just couldn't make it good with the backtracker I had, I dumbed it out and made a new backtracker based on the existing logic.

Quote:

---

Originally Posted by CVMichael

You can clearly see when my backtracker kicks in...
....
I'm at the point of giving up on this thing, I've spent a TON of time on this, and I didn't make much improvement in speed.

---

How did you get your times down to so low all of the sudden? The last set of times you posted were in the 50-1000 range. Now you have 1-2 ms and 1000-2000ms. Were the last speeds you posted from the IDE?

For all the lurkers out there: :wave:

NotLKH1, 69 files, ~15ms
NotLKH2, 532 files, ~187ms
NotLKH3, 123 files, ~55ms
Merri's Hardest, 337 files, ~513ms
Dukuso's Hardest, 100 files, ~275ms

No time for minimum sudokus as they don't have the format of the rest *.msk files. Attaching an image of my user interface - nothing fancy here. I output solutions of all directory *.msk files on the clipboard like:

Code:

---

Filename: E:\Projects\dotNetProjects\_Personal_\Soduku\bin\FILES\0003_0003_022.msk
Solved in 0,46628574 ms
.........
..4..3...
.2.91.4.6
.........
...32..1.
95.....32
.1...5..7
..7....53
..6.4....


189476325
764253198
325918476
273591864
648327519
951864732
812635947
497182653
536749281


Filename: E:\Projects\dotNetProjects\_Personal_\Soduku\bin\FILES\0004_0001_022.msk
Solved in 0,34931381 ms
9..2.....
....5...8
..4.1...6
59...8...
63...7...
......95.
...9.3...
.6....84.
..1...6..


983276514
126354798
754819326
597148263
632597481
418632957
845963172
369721845
271485639

---

My tip: when you're done applying logic rules and you have to start guessing, don't just start with the first empty cell. Finding the right cell makes a huge difference in speed. :bigyello:

Oh, oops. I didn't notice the format difference, my solver can load several file formats :D Actually, any file... It is fun to try to load Windows system files and see if there happen to be any valid sudokus!



Humm... wonder if I'll...


...I shall persist!


...no...


...what is this weird feeling...


...I can't hold it! NO!


NotLKH1: 2.9 ms (0.042 ms per file)
NotLKH2: 39 ms (0.073 ms per file)
NotLKH3: 13 ms (0.106 ms per file)
NotLKH4: 37 ms (0.071 ms per file)
Hardest: 85 ms (0.252 ms per file)
dukuso's TOP 100: 38 ms (0.38 ms per file)
Minimum: 73 ms (0.162 ms per file)

There we go.

Quote:

---

Originally Posted by Merri

...I can't hold it! NO!

...
There we go.

---

lol!

Btw... should I some time actually solve a sudoku by myself? Still have never solved one.

I suggest, at the very least,
Run your progie on some samples, but without backtracking.

Then output your Cells, the values of the solved ones, and the could_be's of the unsolved cells, in a human friendly fashion,

and THEN try to solve that by hand.

You should see some more strategies to throw into your progie that way.

:wave:
-Lou

http://www.vbforums.com/showthread.php?t=351477

Added the updates suggested. Just FYI :)

Well, I've pretty much read up about all the strategies :) I'm thinking about it as a programming task, not as a solver. There is only one potential logic left that might be fast enough to implement into my solver... about all the other ones would be more of performance killers than of help. So I can't take that as an excuse to solve one :D

Looks good.
"Option to output the solved sudoku in a folder in the app path folder with your username"

You might want to restrict the output filename a little bit more.

Someone might name them with no relation to the input file whatsoever.

I Doubt it, but its possible.

:wave:

[edit]
"Time and keep track of the time for each sudoku solved and output in a list at the end (with the total time if possible)"

You might also want to be strict about how the entries in this list are formatted.
What is the pertinant data?

Filename and seconds
Anything else?

What is the order of the data?
What deliminates each line of data?
What deliminates between the data of each line?
Some people use commas, some decimal points for the time. Is this an issue?

How should the total time entry be formatted and where should it go?


IF someones solver fails to solve a soduko, they still need to enter the time it took.

Should each line report the status of the processed sudoku? ie... "Solved" or "Failed"?

Hmmm, I think these are about all the potential issues.

:)
-Lou

Lou, the input ones are *.msk and the output ones *.sol?

I'll edit it, thanks for the suggestion :)

Edited! Any more suggestions?

Thanks again :)

Quote:

---

FileName001.msk: (SOLVED or FAILED) in 0,000000 seconds!
FileName002.msk: (SOLVED or FAILED) in 0,000000 seconds!
FileName003.msk: (SOLVED or FAILED) in 0,000000 seconds!
.
.
.
Total Time: 0,000000 seconds

---

I'm not sure why we are using a comma in the seconds. Is that suppose to be the decimal point in seconds (not milliseconds)? I'm assuming so.

Yep. That's how I know it, "," decimal point and "." to show thousands, millions, etc...

Quote:

---

Originally Posted by manavo11

Yep. That's how I know it, "," decimal point and "." to show thousands, millions, etc...

---

Ok, maybe I am an idiot, but you just confused me more. First off, since when does a "." mark thousands, millions, etc. and do you want any "."s in the time or just a "," where the decimal point normally is?

That's how we learn it in Greece :ehh: The "." isn't needed. Or use the dot if you want in the Format function... Doesn't make much difference...

Quote:

---

Originally Posted by Merri

More sudokus! These include the hardest I've found so far. Beware the minimal sudokus!

---

Ok, I used the program I made to fix dukuso's puzzles and modified it a little to fix merri's "minimum sudokus." I attached them here.

Note: the first (original) file (000.txt) was in a different format then the rest (and caused my program to not output the right type of file) so there might be others in the group, if so please let me know.

Quote:

---

Originally Posted by manavo11

That's how we learn it in Greece :ehh: The "." isn't needed. Or use the dot if you want in the Format function... Doesn't make much difference...

---

Now I have choices to make? Thats no good. I need to be told exactly what to do. I have no decision making capacity. I guess I will just use the format function then replace "." with ","

I just needed to clear up that the , represented the decimal point in seconds and that we weren't talking about miliseconds or 1000 seconds or something like that.

I specified in the rules that the "," is the decimal point character :)

Quote:

---

Originally Posted by Merri

...what is this weird feeling...
...I can't hold it! NO!

---

lol merri :lol:

Quote:

---

Originally Posted by manavo11

I specified in the rules that the "," is the decimal point character :)

---

Thanks. ;)

I'll stop being dumb now. :D

Hey Merri, can you define what a "minimum sudoku" is? How is it different than a normal one?

maybe we should stop measuring time in ms...

Let 1 Merri (mr) be the number of CPU-cycles needed by Merri's solver
to solve one of the easy sudokus. (about 72000)
My solver takes about 4mr for a msk_001-sudoku and 20mr for a top100-sudoku.
My exact-cover matrix has 729*324 (=placements*constraints) cells,
that's 3.3mr, but the matrix is sparse, so I only store the
addresses of the nonzero entries which is 2*0.04mr .
Would I process this list just only for each of the about 55 placements
of a sudoku-clue with one examination per CPU-cycle, then I would already
need 4.4mr, so there must be a better method.

I guess, if your solver takes 10mr for an average sudoku,
that's already pretty good...

Quote:

---

Originally Posted by eyeRmonkey

Hey Merri, can you define what a "minimum sudoku" is? How is it different than a normal one?

---

It has only 17 starting values, yet the puzzle has only one solution. There is no known single solution puzzle with only 16 given values. If we put it straight, I think some of this kind of puzzles cause the most work for a backtracker.

the number of clues has not been a useful measure for hardness.
In fact most of the 17-clue-puzzles from Gordon Royle's webpage
were rather easy to solve.

Yes, most of course. But some of them are the hardest my solver has got its hands into, thus there is some point behind my words.

you're right. I never noticed this. Distribution of clues in my 100 hardest:
10,0,1,1,65,0,2,9,5,4,1,1 counts for 17,18,..,28 clues.
Even my 3 top-hardest are 17-clue-puzzles.
I'll ask Gordon for his other 17-clue sudokus, he has about 5000 of them !

The interesting part being: I thought some of them must be the hardest when I first read about them :)

that's what the creator thought too. But it soon turned out that they were not, see:
http://www.sudoku.com/forums/viewtop...r=asc&start=15
having this in mind, I didn't very much check which of these finally made their
way into my top100 list.
In the hardest 17-puzzle, you can fill in some numbers and it's still hard:

.18...73.
...3.72..
.73......
....713..
6...3..4.
3........
4..5....3
.2..83...
.3.....6.

lol.

The only way that is a seventeen is if you think .18...73. is a 2 entry! But it really is a 4 entry.

.18...73.
...3.72..
.73......
....713..
6...3..4.
3........
4..5....3
.2..83...
.3.....6.

That is a 24 entry.

BTW, I've been marking my sol & msk files since the getgo with the #Entries as the first number in the filename.


:wave:
-Lou

The discussion you pointed to... he clearly haven't thought in that point that there are always easy ones and hard ones. Majority of the puzzles are always easy, otherwise it wouldn't be hard to find the hard ones. So majority with 17 clues are easy, but the select few among them are very hard.

Btw, that one isn't hard. Atleast for my solver.


Something Else: re-read his post :)

"In the hardest 17-puzzle, you can fill in some numbers and it's still hard:"
and then its followed with a puzzle with 24 entries.

Its NOT sayingthat its a 17 entry WITH some cells solved, its implying that if you look at this 17 entry, you'll find some numbers to fill in.

If they were filled in, how would you know what numbers were easily filled in?

Or is this not what you're talking about?

:wave:
-Lou

I'm saying that, atleast to me, he is clearly stating he is giving a 17 puzzle with additional numbers included (which is different thing than solved) and claiming it still is hard with those numbers included.

In the other hand... it is quite hard to follow what dukuso is saying or meaning with what he says every now and then :D

I'm taking the first puzzle from http://magictour.free.fr/top100
which is by far the hardest for my solver which I ever found,
even when considering 1000 random equivalence transformations
of that sudoku :

.18...7.....3..2...7...........71...6......4.3........4..5....3.2..8...........6.


.18...7..
...3..2..
.7.......
....71...
6......4.
3........
4..5....3
.2..8....
.......6.

I can't understand why it's so easy to solve for Merri.
I swapped the 1s and 3s in that sudoku, since one of my programs solves for
the one-digit. You can fill in all 9 threes in above sudoku by relatively simple logic.
These then are painted as ones and vice versa. Plus one seven could also be filled in.
That was the 24-clue-sudoku which I posted.
The point is, that this 24-clue sudoku was no easier for my solver
than the original 17-clue-puzzle.
Clear now ?

Especially if you notice that if you count the number of run on number groups per line, you DO have 17 such groups:

.18...73.
...3.72..
.73......
....713..
6...3..4.
3........
4..5....3
.2..83...
.3.....6.

Line 1: 18, 73 : 2 run on groups of numbers
Line 2: 3, 72 : 2 RunOn's
Line 3: 73 : 1 RunOn
Line 4: 713 : 1
Line 5: 6,3,4 : 3
Line 6: 3 : 1
Line 7: 4,5,3 : 3
Line 8: 2, 83 : 2
Line 9: 3, 6 : 2

So, # RunOn's = 2 + 2 + 1 + 1 + 3 + 1 + 3 + 2 + 2 = 17
Which is coincidentally the number of the order that he claims it to be.

So, if he did start with a true 17, ie.. 17 single hints given,
And then added his fillins, resulting in 24 revealed cells, somehow it ended up with 17 runon groups of numbers, which led me to think that he was counting the groups instead of the individual numbers themselves.

I wonder what it looked like before he added his fillins, if this is the case.

:wave:
-Lou

Quote:

---

Originally Posted by dukuso

I'm taking the first puzzle from http://magictour.free.fr/top100I can't understand why it's so easy to solve for Merri....The point is, that this 24-clue sudoku was no easier for my solver
than the original 17-clue-puzzle.
Clear now ?

---

Thanks!
-Lou

Quote:

---

Originally Posted by dukuso

The point is, that this 24-clue sudoku was no easier for my solver than the original 17-clue-puzzle.

---

Maybe because the result is different. The numbers 1 and 3 switch their place on several occasions. The 24 clue one is a bit harder for my solver as well. But since the numbers switch their place in the solution, it is a completely different sudoku.

Ok, not to change the subject, buuuuut...

I was wondering about when the timer should start. Here me out:

Everyone has to store the possiblities that each cell could be in some manner. Lets assume they use a string to do this (although I hope no one is). The string would originally be "123456789" for each cell.
Now lets assume that the actual value of each cell is stored in a different (byte?) array.
When the original board is loaded into the solver the program sets the byte array to the given numbers.
Now the time starts
Now the solver takes any cell that was originally solved for and removes the rest of the possiblites from the string for that cell.
(Now the solver does everything else.)
Time stops.

My questions is if the step in bold should be included in timing or not. Because if someone did is similarly, but instead automatically eliminated all the possibilities in the string AND set the byte array before the time started that wouldn't necessarily be against the rules.

Did that make sense?

I know not everyone will do theirs in a manner similar to this, but I think some people will.

As told before, I have a function called PrepareSudoku. What it actually does is, besides initializing my optimization arrays (only in first call), convert the given array into the internal format I use to process in. However, it does not do any real calculation. It only fills the array and counts how many solved cells there are. It does not work out any possibles. Thus all the real work is done by the solver, which I time. PrepareSudoku is not included in timing.

Removing possibles should be counted in the timing, because that is what the whole thing is about. But I think setting the sudoku can be counted as initialization, which is not required to be timed (though in the other hand it wouldn't make a big difference).

That is how I have it now Merri (the way you just mentioned).

I was just thinking that if someone took a class approach then maybe sudoku.setval(cellnumber, value) might automatically remove all other possibles. What I mean is that when they are loading the original puzzle, their class will do work (untimed) that out methods time. They would have a leg up on us, just by design.

True, but doing it that way is slow, so there isn't much to complain :) Though, that would be solving the puzzle, because it is using a solving method.

Yeah, plus its a waste... nevermind. I think I won't finish that because I would be giving away more hints (not that I have that many to give).

I wrote that my top1-example is still hard for my solver when
I rotate and permute the sudoku without destroying its structure and the
number of solutions.
And I wrote that I don't understand why it's so easy for Merri's solver.

Now I permuted the order of the constraints and placements,
and that did indeed make my solver solve it much faster.
(but without being faster on the list as a whole)

So, what was happening ? Presumably I went into a
large region of the search tree with no solution
and lots of useless branches, while Merri avoided this region
either by mere luck or by lookahead-prediction.

But such things happen rarely and it might be better to
tolerate it rather than to waste time on predicting how to
avoid it ?!?
I know, there are also sudokus which my program solves much
faster than Merri's - it would help, if we were able to
detect which problems are best solved by which method.

It makes me also believe that further optimizations
in the algorithm are possible....

can't we forget about the contest and work together on the
best program in teamwork instead ?
I mean, it's better to exchange ideas right now,
since after the contest people will be no longer interested to
improve the programs.

Gordon Royle kindly uploaded all his 17-clue-puzzles !

4.6sec*GHz for these 7600:
http://www.csse.uwa.edu.au/~gordon/sudoku17

I don't think so. Entered code will be available after the contest ends. It will be a learning experience for everyone, and things can continue after it ends. The thread was started before the contest was even brought up.

wouldn't that be a cool contest, if people would collaborate to find
the best program and everyone is _somehow_ scored by the
"value" of her contribution ?

Well, only 11 days before the contest is over. I make my own code public right away after the deadline, atleast elsewhere if not here. I'm actually expanding my program in other ways, I have made a multifile converter for an example (still a bit buggy though). Should next make the required feature for the contest, I still don't save the data in the required way...

My problem is starting to be that there isn't much to improve. The list of includeable logics is pretty short... probably the only one I can do to speed things up is Nishio. Probably I'll continue to do some work even after the contest, if my interest just keeps going on.

The contribution contest would be pretty hard to rate. It sounds nice as an idea, but it doesn't work well in practise. Atleast I think it is unlikely to be so.

Her contribution sounds a bit weird btw :D

Here are the 7611 17 clues in the contest format :) Though... the ZIP file contains a 7-zip file. I had to do this because for some reason the ZIP file became over 1 MB in size, even though the files it stored took only about 300 kB compressed! So, I decided to use the best format I know: ending result is 129 kB. So... curse the ZIP.

How to uncompress:
- extract clues.7z.txt from the ZIP file
- rename the file to clues.7z
- extract in a program that can open 7z files (IZarc is a good one)


Oh... and solved them all in ~1710 ms.

But they're in msk format already in my post?

Ignore me. I have edited that reply 5 times then re-read yours and notice I am still worng. Let me edit it again.

EDIT: Ok, I deleted that reply. Now, what I was trying to say is can you upload them in separate .zip's?

In the other hand... you could always get my converter program to change sudoku files from a format to another. You can get that list for example, save it as a text file and then convert that "batch" file to separate sudokus. The converter can save five different file formats and read several others.



I hate silly TYPOS!

Nice one. Yours is much more flexible than mine. I had to modify mine every time I was dealing with a different format.

EDIT: MERRI!!! I think I am going to wet myself. That is beautiful! So clean... SO FAST!! Gimme gimme code! GIMME! ... Ok, I'm done. Deep breaths. I'm better now. :wave:

EDIT: Can I steal your icon? I think I'll resource hack it, unless you don't want me to.

You shouldn't steal my icon! It is a copyrighted work afterall! ;) I'll sue you!

Code will come in... what, 11 days?

Hey lurkers, ;) about 3secs for those 7611 puzzles. I won't do much more work on this, so I'll be posting in a few days because my girlfriend is pressuring me to take vacations on something called the real world - we'll probably go to the place on attached pics (try not to cry too much everyone :D ).

Well, as your wordings in each of your posts say... bit happens. Try to survive!