Our Runtimes

we have started a scoreboard on the whiteboard in class...mainly, it's Infinite Execution vs BNSS vs us, and we welcome (i guess?) all the other teams too (your names are all up on there at least for the next 2 hours!).

Here are our runtimes:

Puzzle Runtime
3_1 11.31854 milliseconds
3_2 12.76578 milliseconds
4_1 0.90984202 seconds
4_2 8.55818944 seconds
5_1 2.198 seconds
5_2 FAIL (SLOW)
6_1 FAIL (SLOW)
6_2 2.25446164 seconds
7_1 9.26728258 seconds
7_2 FAIL (SLOW)
8_1 FAIL (puzzle is MESSED UP)
8_2 1.57 seconds
9_1 FAIL (SLOW)
9_2 12.3104381 seconds
10_1 ~4 minutes
10_2 26.23 second

For most updated times, click here

Long march to Friday's Demo

Over the weekend I finished most of the hardware accelerator logic, (Erick is doing the rest), and Vlad modified the software to use bit vectors rather than an array. Now it is time to figure out the details of interfacing with memory. We can use the CRC checksum accelerator as an example.. but it has more features than we need. For instance, it would be okay for the CPU to stall while waiting for the accelerator, rather than doing other work while waiting for an interrupt. Supporting these additional features will make the design more complicated; on the otherhand, trying to make something from scratch will almost certainly take longer to figure out.

Aliaa is working on the serial interface and trying to run the current software on the NIOS w/ SRAM. Vlad is improving his bit vector code to remove division where possible.

I'm not sure that we will really make the Friday deadline for full integration; but Sunday would be doable.

hard puzzles:
5_2
6_1
7_2
9_1
10_1

dunno what's wrong with 8_1. NOTE: there was a missing comma in 6_1, but I fixed that. hopefully the t.a remembers...line 31, the comma between 0 & 11 for puzzle 6_1 (this wasn't fixed even in the latest version of puzzles).

all other puzzles were solved pretty quickly on linux :) now to figure out that RS232 cable...

haven't figured out interfacing SRAM with checksum accelerator...pipelining reads is a little tricky, i guess. :p

We're making progress! YAY! :)

but some of those puzzles are hard (or incorrect)....boo.

Time Constraints based on Complexity of Puzzle

Tmax = 3 * 10^-4 * N^6 seconds

   N         Maximum Time Allowed

   3                  0.21 secs

   4                  1.23 secs

   5                  4.69 secs

   6                13.99 secs

   7                35.29 secs

   8                78.64 secs =    1.31 mins  (1 min and 18.64 secs)

   9              159.43 secs =  2.657 mins (2 mins and 39.43 secs)

  10                 300 secs =      5 mins

  11             531.46 secs =  8.857 mins (8 mins and 51.46 secs)

Time for a redesign

So for N=7, it takes our algorithm more than 8 hours to solve on a Pentium 4. We have analyzed how our solver is solving the puzzle; the problem it is guessing too much. While our logical methods are fast, we are spending at least 99.9% of the time using them on a puzzle that is going to be shown to be invalid.

So we need to implement more logical "human" methods. However, we have exhausted the analytic methods that operate on the data structures we store (we store the possibilities for the rows, columns, and boxes--but not the possibilities for each cell.) The more complex methods will require that we store the possibilities for every cell on the grid. So we will basically have to start over on our algorithm.

In other news, the hardware I designed for accelerating FindUniqueRow doesn't fit on the FPGA. Oops. So I'm starting over resigned to reading in only a limited number of the constraint arrays at a time and doing some processing--and also only store an even more limited amount of interim work.

As long as we are redesigning the algorithm, I think Vlad is going to aim for having the software operate on bit vectors rather than character arrays. This means we are basically throwing out our software and starting over.

Sudoku is hard.

Bump on the Road: Hardware vs. Software

With higher complexity puzzles (N>5), our software-based algorithm does not seem to solve the puzzles efficiently. We may need to implement some of our algorithm at the hardware-level with customized logic modules and see what happens when we try to solve the higher complexity puzzles; or we may need to reevaluate our software algorithm and develop further our methods to solve the sudoku puzzles. As a team, we will need to investigate and hopefully upgrade/adapt our current algorithm to solve puzzles with higher complexities faster (especially for N>5).