Skip to content

Instantly share code, notes, and snippets.

@daxfohl
Last active December 10, 2015 03:38
Show Gist options
  • Save daxfohl/4375461 to your computer and use it in GitHub Desktop.
Save daxfohl/4375461 to your computer and use it in GitHub Desktop.
9-row LR and SI all regions in one-shot (51K logic elements, 2hr compile)
module trigger(clk, rxReady, rxData, txBusy, txStart, txData);
input clk;
input[7:0] rxData;
input rxReady;
input txBusy;
output reg txStart;
output reg[7:0] txData;
integer countIO;
reg[8:0] data[0:8][0:8];
localparam read=0, solving=1, write1=2, write2=3;
localparam ROW=0, COL=1, SQ=2;
integer state;
initial begin
txStart <= 0;
state <= read;
end
always @(posedge clk) begin
integer ioCell, ioByte, ioCol, ioRow;
ioByte = countIO%4;
ioCell = countIO/4;
ioCol = ioCell%9;
ioRow = ioCell/9;
case (state)
read:
if (rxReady) begin
data[ioRow][ioCol][ioByte*8+7 -:8] <= rxData;
if (countIO == 81*4-1) begin
countIO <= 0;
state <= state + 1;
end else begin
countIO <= countIO + 1;
end
end
solving: begin
integer r,c,i,j,v,rgn,rgnType;
reg finished;
reg[8:0] mask[0:8][0:8];
reg[8:0] rowMask[0:8];
reg[8:0] colMask[0:8];
reg[8:0] sqMask[0:8];
reg[8:0] dataNew[0:8][0:8];
reg solved[0:8][0:8];
for (r=0; r<9; r=r+1) begin
for (c=0; c<9; c=c+1) begin
dataNew[r][c] = data[r][c];
end
end
for (rgnType=0; rgnType<3; rgnType=rgnType+1) begin
for (rgn=0; rgn<9; rgn=rgn+1) begin
reg[8:0] cells[0:8];
reg[8:0] cover;
reg[8:0] coverRemoved[0:8];
reg covered[0:8];
integer coveredCount;
integer vCount;
reg[8:0] exactlyOneCellContainsV;
for (i=0; i<9; i=i+1) begin
cells[i] = rgnType == ROW ? dataNew[rgn][i]
: rgnType == COL ? dataNew[i][rgn]
: dataNew[rgn/3*3+i%3][rgn%3*3+i/3];
end
for (i=0; i<9; i=i+1) begin
cover = cells[i];
coveredCount = 0;
for (j=0; j<9; j=j+1) begin
coverRemoved[j] = cells[j] & (~cover);
covered[j] = coverRemoved[j] == 0;
coveredCount = coveredCount + (covered[j] ? 1 : 0);
end
vCount = 0;
for (v=0; v<9; v=v+1) begin
vCount = vCount + cover[v];
end
if (vCount == coveredCount) begin
for (j=0; j<9; j=j+1) begin
cells[j] = covered[j] ? cells[j] : coverRemoved[j];
end
end
end
for (v=0; v<9; v=v+1) begin
reg atLeastOneCellContainsV;
reg twoCellsContainV;
atLeastOneCellContainsV = 0;
twoCellsContainV = 0;
for (i=0; i<9; i=i+1) begin
twoCellsContainV = twoCellsContainV || atLeastOneCellContainsV && cells[i][v];
atLeastOneCellContainsV = atLeastOneCellContainsV || cells[i][v];
end
exactlyOneCellContainsV[v] = atLeastOneCellContainsV && !twoCellsContainV;
end
for (i=0; i<9; i=i+1) begin
reg[8:0] dataTest;
dataTest = exactlyOneCellContainsV & cells[i];
cells[i] = dataTest==0 ? cells[i] : dataTest;
end
for (i=0; i<9; i=i+1) begin
dataNew[rgnType == ROW ? rgn
: rgnType == COL ? i
: rgn/3*3+i%3]
[rgnType == ROW ? i
: rgnType == COL ? rgn
: rgn%3*3+i/3] = cells[i];
end
end
end
for (r=0; r<9; r=r+1) begin
for (c=0; c<9; c=c+1) begin
reg atLeastOne;
reg moreThanOne;
atLeastOne = 0;
moreThanOne = 0;
for (i=0; i<9; i=i+1) begin
moreThanOne = moreThanOne || atLeastOne && dataNew[r][c][i];
atLeastOne = atLeastOne || dataNew[r][c][i];
end
solved[r][c] = atLeastOne && !moreThanOne;
mask[r][c] = solved[r][c] ? ~dataNew[r][c] : ~0;
end
end
for (rgn=0; rgn<9; rgn=rgn+1) begin
rowMask[rgn] = ~0;
colMask[rgn] = ~0;
sqMask[rgn] = ~0;
for (j=0; j<9; j=j+1) begin
rowMask[rgn] = rowMask[rgn]&mask[rgn][j];
colMask[rgn] = colMask[rgn]&mask[j][rgn];
sqMask[rgn] = sqMask[rgn]&mask[rgn/3*3+j%3][rgn%3*3+j/3];
end
end
finished = 1;
for (r=0; r<9; r=r+1) begin
for (c=0; c<9; c=c+1) begin
reg[8:0] newVal;
newVal = dataNew[r][c] & (solved[r][c] ? ~0 : rowMask[r]&colMask[c]&sqMask[r/3*3+c/3]);
finished = finished && newVal == data[r][c];
data[r][c] = newVal;
end
end
if (finished) begin
state <= write1;
end end
write1:
if (!txBusy) begin
txData <= data[ioRow][ioCol][ioByte*8+7 -:8];
txStart <= 1;
state <= write2;
end
write2: begin
txStart <= 0;
if (countIO != 81*4-1) begin
countIO <= countIO + 1;
state <= write1;
end else begin
countIO <= 0;
state <= read;
end end
endcase
end
endmodule
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment